@schlonzo fixed the patched version.
@gegenlicht added your patch.
The c# version now has an UpdateParallel method using Parallel.For loops to calculate the forces.
While minimum effort, this already gives a nice performance boost.
VL.ForceDirected -0.3.7z (276.8 KB)
Hey, gave Barnes-Hut a shot. Not sure I got it quite right, though.
There is a speed-up for greater spread counts (starting at about 1000 particles on my machine).
I guess up to that, rebuilding the octree every frame eats up all gains.
Visually the results of both versions look quite similar, which can be observed in the HowTo create a simple Force Directed Graph patch when setting lower spreadcounts. This patch also has an option to show the subdivision of space.
And again: Any feedback and ideas for improvement very much appreciated.
VL.ForceDirected-0.4.7z (99.2 KB)
This doesn’t look correct:
You certainly have a race condition here. You’d need to take the overload which gives you a thread local state, so you calculate for each thread and then at the end again the min and max for all the mins and maxes produced by the different threads.
Shouldn’t the node.Update happen after all forces have been calculated?
And not sure if the tree allocations are an issue - if yes, there’s probably room for improvement by using an object pool.
Ok I’ll try.
It was that way before. One loop to calculate the repulsion and then another to update the nodes. Out of curiosity I then changed it to the way it is now and couldn’t spot any siginificant differences so I left it. But I guess the performace gained from one loop less is negligible (if any)? Will go back to the initial way then.
I did spot gen2 garbage collections. But wasn’t sure if they come from re-generating the tree (alone). In the version I posted the spread for the positions is generated in the patch using a foreach iteraring over all nodes, for higher spreadcounts this could also be a problem I guess?
In the meantime I did this:
And get the positions in patch from the array. Is this a viable way? Also thought abount calculating transforms directly in code.
Concerning the Objectpool: Since the octree is splitting itself recursively into smaller octrees is it enough to just get the root-tree from the pool and return it, or do the children also to be from the pool?
Also is the object automatically “reset” when returned? Couldn’t glean that from the docu and the examples I found seemed to be either ASP or Unity specific.
In the original beta code I believe the Update happens after everything else in a separate loop - that seems logical to me. Otherwise you calculate the forces for a particle while half of the others have already been updated. But maybe different properties get modified in those methods so it’s not an issue.
Here is an example of the object pool for the regular list using the Microsoft.Extensions.ObjectPool package:
public sealed class ListPool<TValue> : DefaultObjectPool<List<TValue>>
{
class Policy : PooledObjectPolicy<List<TValue>>
{
public override List<TValue> Create() => new List<TValue>();
public override bool Return(List<TValue> obj)
{
obj.Clear();
return true;
}
}
public static readonly ListPool<TValue> Default = new ListPool<TValue>();
public ListPool() : base(new Policy())
{
}
public List<TValue> Rent() => Get();
}is there a git repo with the latest state? the forces shouldn’t be in a static class, I did that back in beta without predicting that it will be used in an OO visual programming language 10 years later.
but the fix is easy, let me know where to put it.
@tonfilm Added you as collaborator. Haven’t had the time to implement Elias latest suggestions though.
Maybe you could also look into that :)