Graph Evaluation (Again)

I did not post for a while, it doesn't means I've been doing nothing, actually quite the opposite.

Lately I've been reworking a bit of my graph internals (basically read, decouple some bits), and I had lot of ideas and implemented quite a few, so I decided I wanted to share some theory again.

First thing I already spoke about the fact that multi core evaluation is tricky to get right (basically, you need your nodes to do enough work to make it worthwhile, otherwise you gonna have serious issues or just have something slower). 

A second thought was to eventually have a compiled form of the graph, while that's a bit of buzzword, I also believe that compiled ones will not always be faster.

Why? Wouldn't removing evaluation overhead make things faster?

Yes, but by still having access to your model, there's a serious lot of optimizations that you can perform, so answer is : not always.

So I'm gonna talk a bit about graph evaluation strategies. (I'll speak of data flows mostly)

Let's take the following simple patch, as you can see, nothing really fancy, but that will perfectly fit

1/A very basic graph

A/Lazy recursion

This is by far the simplest to implement (to be honest, you can do it in less than 100 lines of code probably).

Pseudo code:

Start with NodeFinal

function processnode(node)

if node is already processed 

  return

for each input pin  

    get upwards node (info is likely stored in a link structure)

    processnode (parent node connected to input pin)

end for

end function

process node (some form of update/evaluate call)

mark node as processed

Yes, that's about it really, simple to understand and very idiomatic.

Now first things that we can notice:

We will call processnode several times on some of them (for example, Time is used by 3 different nodes)

In our case (Since I did not introduce any form of "graph cutting techniques") we can also see that actually order of execution is immutable (our graph will always run and process nodes in the same order).

So let's optimize that

B/Reversed List

Getting the above graph (i add the screenshot again):

We can deduce our dependency order (if I consider I'll scan for pins in a left to right fashion)

NodeFinal -> Node12 -> Node1 -> Time -> Node2 -> Time -> Node 9 -> Node 2 -> Time -> Node 5 -> Time

As mentioned, we prevent to execute twice, which gives the following order:

NodeFinal -> Node12 -> Node1 -> Time -> Node2  -> Node 9 -> Node 5

Now we need to transform that into a running order, we could reverse the second list, but that will not work.

Why? Simply because for example Node5 needs Time to run before to be updated.

So let's use the first list, and reverse it:

Time -> Node5 -> Time -> Node2 -> Node9 -> Time -> Node 2 ->Time -> Node 1 -> Node 12 -> NodeFinal

This list is correct, but replicates some elements, filtered version is :

Time -> Node 5 -> Node 2 -> Node 9 -> Node 1 -> Node 12 -> Node final

To build the list, we perform a first lazy evaluation pass as seen upwards, but instead of calling Update, we simply add the node to a list.

Once we get that first list, building the reverse order is done as follows:

var reversedList = reverse(dependencylist)

var executionList = new EmptyList

foreach node in reversedList

   if not executionList.Contains(node) then executionList.Add(node)

Store that list somewhere, and then graph evaluation becomes:

foreach node in executionList

   update(node)

As you can see, that removes recursion, and actually this is really easily compilable (just generate llvm/il/source code) and compile

Issue is of course that each time the graph changes, you need to preparse it again, which is not always advisable at runtime (the compilation step might severely hurt).

Now let's add some features in our graph

2/Lazy pins (and virtual links)

Let's take the following graph.

Here we consider that LargeData and Generator1 nodes are really heavy, and feed some data into builder, but does not need frequent updates.

Builder has been built with first pin to be Lazy (eg: only build upwards if the second pin something like Apply is true (which is dealt somehow by the conditions upwards)

Graph is then decomposed int the following path:

Builder -> And -> Condition1 -> UserInput -> Condition2

If Second pin (eg result of and node) is true

LargeData -> Generator1 -> Time

As you can see, now our evaluation is split into 2 different parts (basically, everything non lazy, then eventually the lazy part is required)

This is suddenly harder to convert into list (and kinda difficult to auto compile).

So suddenly the idiomatic purely lazy version above is not so bad after all. You only need to add a condition on the node to tell if you want to go upwards or not.

Another version is to have some form of internal link eg:

Here the switch node will decide (depending on SwitchValue result) to run either from Part1 or Part2

This can be implemented in 2 ways:

Use lazy as above.

Rebuild the graph structure (basically if SwitchValue  0, the internal representation of the graph is like this):

As you can see the user "sees" the first version of the graph, but internally the link is removed, so the Part2 node (and above) are now orphans and never run.

This is also really efficient, but of course if you use an optimization technique above, every time the internal representation changes (which can be every frame), you need to rebuild your structure. 

So deciding to do so means that you need to decide if it's worth it (does the optimization technique + optimized evaluation is still faster that idiomatic version).

Please note those techniques are always defined on runtime (eg: at some point, some node is granted "power" to cut the graph).

As we have seen, they add some complexity to the evaluation part.

Now let's separate our usage into 2 parts : 

• Authoring : When user is effectively building the patch
• Runtime : When we are running

In case you want to deploy your application, you will of course have effective gains by optimizing runtime performance version. 

But in many cases we still need fast authoring, even if those are niche scenarios, I always have cases where I need to go modify something very early before a show (or actually , during the show). 

Some people will say it's bad, but in cases where it's not avoidable (position some element properly, add a quick animation or whatever some client urgently requires) this becomes critical not to disrupt the render output too much (basically, freeze or lag).

So the whole key is to balance both (of course you can also provide several graph evaluation strategies, so the user can decide depending on his use case).

3/Dual graph

One very easy technique to balance this part is to maintain two evaluators, one idiomatic version, and one optimized version.

When patch structure changes, we swap to idiomatic (since it has close to zero rebuild time), and build a new optimized version in background.

When optimized version is ready, switch back to it.

And key if you use c#, keep a reference to your old optimized evaluators somewhere, it's likely that you'll have a Gen 1/2 GC trigger, which is not desirable either,a small "memory increase instead" might be preferred.

4/Determinism

Now let's introduce something interesting, since all the above was fairly basic.

Basically, let's consider a node as "Take some input and produce some outputs"

We could consider 3 cases of "output production"

• Deterministic : This is identical to "pure functions" in functional paradigm. Same inputs will always produce same outputs.
• Non deterministic : This will produce varying results (for example, an animaton filter with keep previous frame result and depend on that)
• User input, non deterministic: This is the same as above, but is a special case (for example a node that has an editable value)

So let's consider the following patch:

Let's say that Constant (and Constant2) nodes are immutable (basically you set the value when you create the node and you are not allowed to modify it).

Other operators are basic (math operators are fully deterministic).

This patch only needs to run once, it will always produce the same results.

You will of course say : I need to animate my data to show on the screen, and I agree, But I can be remotely sure that in large patches, there are a lot of sections like that.

You could of course use a lazy pin as specified above (below finalvalue), but we could be able to just automate this.

Let's take a second example:

In that case, only the Constant node is constant, since Time node is non deterministic, there is not much we can do, but then having:

Here we can see that all the section in gray can be ran only once and cached, it never needs to run several times.

If now we add user input to the mix:

Here the group on the right only changes when user input is changed, so we can also really easily cache results (as user data will not change ever so often).

We do not need to check for user changes manually (generally editors tend to trigger an event).

Pseudo code for evaluation is a tad more complex.

First when graph is updated, we need to propagate some information downwards as per:

Walk though node recursively, check if it has a Fully non deterministic parent (or a user input based one), mark that in a flag (and in case of user input, store some reference to it).

void ProcessNode(node)

   if node has no deterministic parents, stop here (unless it's the first frame or graph has changed)

   if node has a fully non deterministic parent (anything that depends on Time node in our case), process it

   if node has one "user signal" version, check if user has changed value (some form of dirty flag), and only process it if required.

In our example patch, we can see that unless user is editing value, only FinalValue, +, Add, Divide and Time need to be processed, the rest can be completely ignored most of the time, and this can be automated!

Again, in our example, if we deploy our application, the UserValue node can automatically be changed to a constant node (since user will not have access to editor anymore). So we can also even completely remove the User input, non deterministic case, and stay with only Deterministic of not.

As a side note, in case of deploy, we can also even store the result values we need and just remove the nodes completely.

For example :

Can be transformed to:

Here we store all results that are needed (Sine and Multiplies), and don't need those processors anymore.

Of course, in case nodes operate on large lists, storing results can require some large files, so we can of course keep the option to keep nodes and run it only once (and replace them my constants in the graph right after).

Where is the catch then?

There is one, every node must be annotated, we need to provide metadata in order to indicate about a node Determinism, this can of course easily be achieved using some attributes (in c# example)

What's then important is that each node must be "curated", as a Non deterministic node marked as Non Deterministic will prevent downward optimization, opposite scenario is worse, as it will lead to incorrect results (data will not change whereas it should), but adding those is a small cost versus the reward.

5/Conclusion

Compiling graphs as flattened structures can feel tempting as first sight, but graph data structure can hold a large amount of "knowledge" which is then lost, so before to decide to do so it can be interesting to take a step back and see if it's worthwhile at all (that for sure, is another debate and there will be pros and cons in each case).

Since this post probably feels long to digest, I'll keep the next section for later, which will include shaders in the mix, so stay tuned.

Shader Linker

I already posted about shader linking graph previously, so I thought I would give a bit more details about it.

Now that DirectX11.2 is implemented in SharpDX, it was much easier to integrate, removed some small c++ library hack in the meantime.

Now as much as I still don't think shader patching fits every use case, I have to admit there's a few times where it proves really useful.

First scenario is actually not using the linker, but the function reflector. You build a library of functions, and so some form of signature matching, for example:

Code Snippet

1. float3 GravityStrength = float3(0.0f,-1.0f,0.0f);
2.  
3. export float3 Gravity(float3 p, float3 v)
4. {
5.     return GravityStrength;
6. }

Now the library reflector will scan all functions, and if signature matches (in this example, particle force field needs pos/vel tuple), it will automatically create a node. Attaching this node to a generic force field node will take the base code, include the function header and compile a new shader.

This is something I did a lot already (using function headers to inject code in an incomplete shader and include then compile), so you can build a function library while having a single main function, but function reflection brings it to the next level, since I can now have fast collection of nodes in few line of code.

I use it for a lot of cases (geometry displacers, materials, particles interaction...) and it's great.

For geometry displacers, for example (it's overly simplified compared to the real version), I have several displace techniques (tetrahedron, tube, face), each need a displacement value from a position.

So as soon as I have a new displacement technique, it can be integrated with all displacer functions, which gives a great amount of flexibility (and removes a lot of boilerplate code).

Now I have some cases where I need some more complex functions, and where using the linker really shine:

• Pixel shader for screen space textures. I use this a lot for masks
• Deffered Pixel materials : Use noise/sine functions for color/rough/reflectivity can be done in handlers, but I often need more complex functions.
• Distance field builders

Here is an example for pixel mask builder:

Great thing about all this, I have a nice collection of pre built functions (noise, sine displaces...) since I don't want to patch that, and I can easily combine them to create variations. If I need a new function, I can also create a custom one using code and it will reflect parameters and create me a node. Having mixed support for patch/code is such a great feature.

Now one thing I also would like to build quite easily is Distance Field.

I already have distance field builder, which is made using compute shader, and uses an include script to build function. This works really well, but having it as patch could also be interesting.

So first thing, you build your small function collection (primitive distance function, bend/twist operators, union/substract/intersect...). And you have all your nodes ready. 

Now this runs into an issue, the shader linker only builds either Vertex or Pixel shader.

I could use the "GenerateHLSL" function, and include that in my code, but then you lose the advantage of using linker over compiler = speed. Link speed is REALLY fast compared to compile speed.

So let's rewrite that routine, since writing to volume is also really easy to implement in standard pipeline too.

• Create a single RenderTarget for your Volume
• Send a draw call with N full screen Quad instances (or triangle, your choice), where N = volume Depth
• In vertex Shader, multiply instance ID by inverse Slice count, and pass object space position plus this depth to geometry shader (as well as instance id itself)
• In geometry shader, assign Instance id to SV_RenderTargetArrayIndex so each quad instance is drawn in single slice.
• Compute your distance function in Pixel Shader :)

Here is definition:

Code Snippet

1. struct vsInput
2. {
3.     float4 p : POSITION;
4.     float2 uv : TEXCOORD0;
5.     uint ii : SV_InstanceID;
6. };
7.  
8. struct gsInput
9. {
10.     float4 p : POSITION;
11.     float3 xyz : SDFPOS;
12.     uint ii : SLICEINDEX;
13. };
14.  
15. struct gsOutput
16. {
17.     float4 p : SV_Position;
18.     float3 xyz : SDFPOS;
19.     uint rt : SV_RenderTargetArrayIndex;
20. };
21.  
22. struct psInput
23. {
24.     float4 p : SV_Position;
25.     float3 xyz : SDFPOS;
26. };
27.  
28. int SliceCount = 128;

Vertex Shader:

Code Snippet

34. gsInput VS(vsInput input)
35. {
36.     gsInput output;
37.     output.p = input.p;
38.     output.xyz = float3(input.uv, input.ii / (float)SliceCount) - 0.5f;
39.     output.ii = input.ii;
40.     
41.     return output;
42. }

Geometry Shader:

Code Snippet

44. [maxvertexcount(3)]
45. void GS(triangle gsInput input[3], inout TriangleStream<gsOutput> gsout)
46. {
47.     gsOutput output;
48.     for (int i = 0; i < 3; i++)
49.     {
50.         output.p = input[i].p;
51.         output.xyz = input[i].xyz;
52.         output.rt = input[i].ii;
53.         gsout.Append(output);
54.     }
55.     gsout.RestartStrip();
56. }

And a dummy pixel shader (that builds a sphere):

Code Snippet

58. float PS(psInput input) : SV_Target
59. {
60.     return length(input.xyz)-0.25f;
61. }

Now we can just bypass this dummy pixel shader and use a patch version of it, as in those screenshots:

Here we go, distance field patcher :)

And a version with some nodes built from code editor, hybrid is the future ;)

Graph API in FlareTic

Before a (long) post explaining new feature set which is going into FlareTic (and that is hefty believe me), I thought I would speak about the internals of it a little bit.

So let's start with graph evaluation.

Most node based software follow a single paradigm:
-Data driven (vvvv)
-Event driven (max)
-Bit of mix in between (vuo)

That means all your composition has to fit that model, which for me was always feeling non natural and unefficient.

So in contrast, FlareTic provides different patch types, each of those can have whatever paradigm they want.
Also node set is dependent on patch type, so some nodes are only allowed in some patch and not in others.

That gives some advantages/drawbacks, let's start by drawbacks:

• It can be a little bit confusing since when you create a new patch type you have to learn about how it works.
• Since each node set is on a per patch basis, you have a potential of high node duplication.

Now it gives some advantages:

• Since each patch type is isolated with some node set, it's very easy to optimize each type.
• I can create some patch types that do different things (State machine for example)
• To minimize node duplication, there is a connector system which allows transfer between patches based on some rules.
• Having a limited node set per patch allows to keep those patch clean (no mix up between logic/rendering for example).
• I could create a patch type which does everything if I want to ;)

So here is what we have for the moment:

• Root patch: Mix of Event/Data driven (event for devices, data for textures)
• Automation patch : Data driven, since in that case it's the easiest model.
• SceneGraph : No real model, everything is dealt on connections, and nodes define their own rules. So links are purely interface based, and a node will decide if it wants it or not. This gives a lot of work to nodes, but allows to have extremely simple pipeline (for example, particle system node can accept any emitter/collider/behavior, organizes all that lot internally, so we don't need any fancy grouping on patching side). It also ensures code quality, if a new behavior is created it will fit in the system directly.
• State Machine patch : No model either, since it rebuilds state machine when you add states/create links... after the state machine is passed around but there's no more graph evaluation
• Shader patch : Same as above, patch actions notify the patch to rebuild shader, then shader is passed as single object.

One big advantage over it is I can create a new patch type (in progress, there's an OpenCV patch, which runs in background and auto sync), define it's rules and I get some new optimized version for it. Not allowing to mess every node together also ensures some code quality, but more on this in next post too, there's few other parts in progress ;) 

Now also since I decided to follow the rule "less nodes/more workload", it fits pretty well in the pipeline, since I hardly need to optimize evaluation, Node set ensures I have quality components. New nodes need to fit into the pipeline, so it doesn't get polluted by lot of random nodes.

On evaluation, there's also no real fanciness, no parallel graph evaluation, no real hardcore graph branch elimination (that's only dealt by pin who tells if they want data or not), and if a patch does not run it does not run, which is just the easiest thing ever, but so efficient in 99% cases ;)

So why no parallel evaluation? Well I don't adhere to the fact that parallel is faster (not always at least, and can also be much slower). I think it's just some marketing crap for people who have no clue about programming internals.

So let's explain a bit.

Let's take a simple example (the one presented in one of those random vuo demo).

You have this graph

So as we can see A provides data to B and C, which are have no linear dependency, then both of those provide data to D, which need to create a barrier (eg : make sure B and C have evaluated) before to execute.

So we could easily say "OH, if we run B and C in separate threads we'd have a speed gain, let's do that!!"

NO!!!!

Let's explain : Thread synchronization has a cost, and here we have 4 operations which so minimal (one Add, one

Multiply , one Divide, plus little bit of graph parsing) that you'd have processed all that data serially before to dispatch threads/barrier.

Now let's say C has a huge workload (I added a large set of random values to the second pin as per the picture):

Now in that case running B and C in parallel would give no or very little gain, since you'll have one node (B) doing more or less no work, and one node (C) which will be pretty busy.

In that case a real gain would be to have C to spawn multiple threads, since a multiply is easy to make parallel (4 threads processing 100000/4 elements each). Running B and C concurrently is totally useless.

Only good use case for such a scheme would be:

In that case we have B which also has a decent workload, so running both concurrently would give some performance improvement. But....

Now let's look a bit closer again:

B still has much less workload than C, so D will have to wait for C again.

If now we push 10 times more data to C, D will still wait for C.

So bottleneck stays C.

Since both operators are easy to parallelize, running data parallel on B and C would still give a much higher performance boost.

Now we can also say? Why not Using both techniques? (eg: run task parallel and data parallel)

Well you'll run into issues, it can be done, but it's pretty complex. Now you'll have B and C fighting for processing time, so it's not as easy as it looks.

Now just to add a little bit, let's add 2 more nodes E and F.

Now what path is your scheduler gonna choose?
3 threads for B,C,E, barrier on D, barrier on F
2 threads, B,C,D in serial, E on it's own, barrier on F?

Since each node can also have different workload (which can also vary over time), well combinatorial explosion on the way.

And here I got only 6 nodes (I don't count the iobox ;) think of a composition with 1000 nodes (which is a small composition in general if you have low level node set).

Also add the fact that composition needs to submit data to gpu for rendering (Since we don't want to do hello world all the time ;) , GPU having parallel command list on it's own, You also have (like in my last project) several threads for network sync,camera/video decoding, texture streaming. In that case adding more cores into your graph might also pollute those and make you whole application run slower.

I'm not even mentioning that if you need to render the data above, you can replace that patch with a compute shader and blow away performance anyway (by a pretty huge factor).

So basically, multicore graph processing is hard, don't advertise it unless you can show some proper rock features, not an hello world with 4 nodes which doesn't even benefit from it ;)

Best solution (but not "designer friendly", is to give use the choice, to let them decide where they know some parts of their compositions are intensive and select that manually).

So here we are, next time I'll go a bit deeper into the Scene Graph, shader system (before the big fat post)

Stay tuned ;)

New birth

Finally back from Cannes Lions festival, was doing visual application in collaboration with Arcade Studio and Microsoft for Soft Array (Structure hold an hefty 39 surface pros and 4 all in one Asus).

Software runs real time distributed 3d audio reactive visuals, all synchronized of course.

That project will deserve it's own blog post, I'll do a write up once I'm done

For this project it was the first time I use my new shiny in house tool, called FlareTic.
It's basically written from scratch (almost).

So most people like to explain why they do something, I'm normally not like that (I just tend to say : because it's cool / because I can ;)

For once I have a decent rationale about it, so I decided I would share it :)

So why starting to write your own tool and not using some pre-made framework (like vvvv/openframeworks/cinder) ?

• I need an executable : original idea is to use it as demo tool, I need to be able to export, that removes vvvv
• I need source code : I am a programmer, I can read/debug code, and when you have lot of devices any bug in your framework can turn things into hell (when you on crunch time for final installation day/night). So I need to be able to run a full debug ... period.
• I want to use DirectX : No offense to OpenGL, but their API is clunky. Of course you always end up having an abstraction layer, but starting with already a clean API makes your life easy. So that means for OpenFrameworks or Cinder I need to write a DX rendering layer. Ofx I way too verbose for my taste (so that discards it out of the box), Cinder I already wrote a Directx11 Renderer for it (I should publish it at some point).
• I want Metro Export : For my phone mostly, that gives point 1 and 3 ;)
• I want dynamic compilation for shader/script, and some graph editing : Don't want to recompile/copy 43 times an app each time I tweak something. I could use lua and cinder, but dynamic c# compilation is easy and I already got lot of routines in c#, so I might as well reuse them.
• Showing off your tool and tell you wrote it yourself is cool ;)

Also since I didn't do any gui programming for a while, that would be a good exercise ))

When you start a new tool you have plenty of ideas, organizing them is not as simple. I normally tend to write fast, refine later. I need fast iterations so I can quickly test a new idea, which can make it into the tool and means I adapt rest of the code because it's so awesome, or can just end up in the recycle bin.

First thing you need is some form of gui (code editor window, graph editor, main form).

So I already have a small graph editor, written using Direct2D, which is pretty nice and has all the features I need for it : good font rendering engine, basic shapes, bezier for links, and hit test functions. Please note that hit testers was a bonus, it's plain easy to do, but saves you time since it's already there. So I added undo/select/smart link/zoom/pan features, which where all pretty easy.

Also I had a minimal inspector with basic controls (sliders, toggles...)

Code editor was some simple window with a TextBox. It's was super minimal, but enough for early dynamic compiler tests. So I moved to ICSharpCode.Editor so at least I could have syntax coloring. Intellisense support will be for later (only for the c# version, I don't like it for hlsl, I ditch the file right away anytime I install a new vvvv version ;)

Now last (but not least). Patches were into a TabPanel and scripts were separate windows. That can turn your desktop into a big mess quite fast. So I moved to the awesome DockPanelSuite so I can arrange everything I want Visual Studio style ;)

Here is early version of the tool:

New version (graph didn't changed that much except few refinements, but more on user side) :

Still needs some polish, but already quite nicely useable.

I'll speak about evaluation model in next post (eg: likely today), and two things to finish (and make things clear):

• This is an in house tool, and I have NO plans to release it in the near future. So please don't ask for a beta answer will be a polite no ;)
• I am not leaving VVVV (I could see some users to be a bit worried about that). VVVV is still an integral part of my workflow.
• A decent part of the codebase is shared (vlc player/kinect/dx11 rendering...) so lot of improvements will be beneficial for both softwares at the same time.
• Some nice new features come from ideas I had with the tool, like the up and coming JSON scene exporter was done so I could design scenes in VVVV and import them in FlareTic. But importer is also in VVVV.