Burst slower than Unity C# method?

This is my second night with IJobs and the BurstCompiler, it's 7:40 AM right now, the Job does its job, no errors, finally.
So I wanted to know how cool the performance is compared to my old version of the same algorithm:

Burst Job: 13ms
Old Version: 4ms

What it does is basically finding isolated islands in my node graph. The graph is based on Elements and Lines.
Elements are connected by lines and know about their connections.
Lines connect two elements and know about them.

More Detail about the setup:

In the Old Version everything was set up with refrences, lines had refrences to elementA and elementB, elements had a List of the connections, attached to them.
So for one element to know about their neighbours, it has to check the lines, like:

Element neighbour = element.connectionLines[0].GetOther(element);

In the new Version, with burst, I had to find another setup without references.
2 NativeArrays, 1 NativeMultiHashMap.
NativeArray<Element_S> (Element Struct)
NativeArray<Line_S> (Line Struct)
NativeMultiHashMap<int, int> (first int is the index of the element, sub-ints are the indexes of the lines, this element is connected to)

The Line_S knows the indexes of elementA and elementB.
The Element_S knows nothing, but has an index, that can be passed into the NativeMultiHashMap to get the indexes of the Line_S'es.

Old Version Algorithm:

Code (CSharp):

1.         bool IslandCheck()
2.         {
3.             HashSet<Element> alreadyChecked = new HashSet<Element>();
4.             int iteration = 0;
5.             HashSet<Element> elementsToCheck = new HashSet<Element>(Elements);
6.             foreach (Element startElement in elementsToCheck)
7.             {
8.                 if (alreadyChecked.Contains(startElement)) continue;
9.  
10.                 iteration++;
11.  
12.                 HashSet<Element> open = new HashSet<Element>();
13.                 open.Add(startElement);
14.                 HashSet<Element> closed = new HashSet<Element>();
15.                 HashSet<Line> closedLines = new HashSet<Line>();
16.  
17.                 bool hasFoundation = false;
18.  
19.                 Vector3 centerOfMass = Vector3.zero;
20.                 float totalMass = 0;
21.                 int breaker = 0;
22.                 while (open.Count > 0)
23.                 {
24.                     breaker++;
25.                     if (breaker > 5000)
26.                     {
27.                         Debug.LogError("Breaker Activated");
28.                         break;
29.                     }
30.                     Element current = open.First();
31.                     open.Remove(current);
32.                     alreadyChecked.Add(current);
33.                     closed.Add(current);
34.  
35.                     centerOfMass += current.newPos;// * current.mass;
36.  
37.                     totalMass += current.mass;
38.  
39.                     if (current.isFixed)
40.                     {
41.                         hasFoundation = true;
42.                     }
43.  
44.                     Element GetConnected(Element element, Line l)
45.                     {
46.                         {
47.                             if (l.elementA == element) return l.elementB;
48.                             else return l.elementA;
49.                         }
50.                     }
51.  
52.                     foreach (Line l in current.connections)
53.                     {
54.                         if (l.isDestroyed) continue;
55.  
56.                         closedLines.Add(l);
57.  
58.                         Element con = GetConnected(current, l);
59.                         if (!alreadyChecked.Contains(con) && elementsToCheck.Contains(con))
60.                         {
61.                             open.Add(con);
62.                         }
63.                     }
64.                 }
65.  
66.                 if (totalMass > 0 && closed.Count > 0) // closed is one island
67.                 {
68.                     centerOfMass /= closed.Count;
69.                     //centerOfMass /= totalMass;
70.  
71.                     BuildingIsland newIsland = new BuildingIsland
72.                     {
73.                         elements = closed,
74.                         lines = closedLines,
75.                         centerOfMass = centerOfMass,
76.                         totalMass = totalMass,
77.                         hasFoundation = hasFoundation
78.                     };
79.  
80.                     islands.Add(newIsland);
81.                 }
82.             }
83.  
84.             return islands.Count > 1;
85.         }

New Version Algorithm:

Code (CSharp):

1.         [BurstCompile]
2.         struct FindIslands : IJob
3.         {
4.             [ReadOnly]
5.             public NativeArray<Line_S> lines;
6.             [ReadOnly]
7.             public NativeArray<Element_S> elements;
8.             [ReadOnly]
9.             public NativeMultiHashMap<int, int> hashMap;
10.  
11.             public NativeArray<RootHolder> rootsOutput;
12.  
13.             [WriteOnly]
14.             public NativeArray<bool> hasIslandsOutput;
15.  
16.             public struct RootHolder
17.             {
18.                 // refers to the index of the root Element
19.                 // root = the current holder of the island
20.                 public int toIndex;
21.                 // size of the island -1 , only valid on the root
22.                 public int size;
23.             }
24.  
25.             public FindIslands(NativeArray<Line_S> lines, NativeArray<Element_S> elements,
26.                 NativeMultiHashMap<int, int> hashMap, NativeArray<bool> hasIslandsOutput,
27.                 NativeArray<RootHolder> rootsOutput)
28.             {
29.                 this.lines = lines;
30.                 this.elements = elements;
31.                 this.hashMap = hashMap;
32.                 findRootBreaker = 0;
33.                 this.hasIslandsOutput = hasIslandsOutput;
34.                 this.rootsOutput = rootsOutput;
35.             }
36.  
37.             public void Execute()
38.             {
39.                 for (int elementIndex = 0; elementIndex < elements.Length; elementIndex++)
40.                 {
41.                     // group up with all neighbours
42.                     var lineIndexes = hashMap.GetValuesForKey(elementIndex);
43.                     while (lineIndexes.MoveNext())
44.                     {
45.                         // find the root of the current object
46.                         int currentRootsize = 0;
47.                         int currentRoot = FindRoot(elementIndex, out currentRootsize);
48.  
49.                         // temporary get the real neighbour index
50.                         int neighbour = lines[lineIndexes.Current].GetOther(elementIndex);
51.  
52.                         // get the neighbour root
53.                         int neighbourRootSize;
54.                         int neighbourRoot = FindRoot(neighbour, out neighbourRootSize);
55.  
56.                         if (neighbourRoot == currentRoot) continue;
57.  
58.                         if (neighbourRootSize >= currentRootsize)
59.                         {
60.                             // set current root to neighbour
61.                             SetNewRoot(currentRoot, neighbourRoot);
62.                         }
63.                         else
64.                         {
65.                             // set neighbour root to current
66.                             SetNewRoot(neighbourRoot, currentRoot);
67.                         }
68.                     }
69.                 }
70.  
71.                 // there are no islands if the rootsize is the same as the array-size
72.                 // keep foundIslands at false and exit here, we don't have to set
73.                 // the toIndexes of the other elements
74.                 int totalSize;
75.                 FindRoot(0, out totalSize);
76.                 if (totalSize == elements.Length - 1)
77.                 {
78.                     return;
79.                 }
80.                 else
81.                 {
82.                     hasIslandsOutput[0] = true;
83.                 }
84.  
85.                 // otherwise iterate and set the correct root for all RootHolders
86.                 // so we don't need the FindRoot() method outside of this job and
87.                 // increase the speed on the main thread
88.                 for (int elementIndex = 0; elementIndex < elements.Length; elementIndex++)
89.                 {
90.                     RootHolder RH = rootsOutput[elementIndex];
91.  
92.                     // size is not relevant outside of the job, we don't have to
93.                     // correct it in the RootHolder
94.                     int rootSize;
95.                     RH.toIndex = FindRoot(elementIndex, out rootSize);
96.  
97.                     rootsOutput[elementIndex] = RH;
98.                 }
99.             }
100.  
101.             void SetNewRoot(int from, int to)
102.             {
103.                 RootHolder from_RH = rootsOutput[from];
104.                 RootHolder to_RH = rootsOutput[to];
105.  
106.                 // increase the size of the new group
107.                 to_RH.size += from_RH.size + 1;
108.                 // set the new toIndex
109.                 from_RH.toIndex = to;
110.  
111.                 rootsOutput[from] = from_RH;
112.                 rootsOutput[to] = to_RH;
113.             }
114.  
115.             int FindRoot(int current, out int size, bool isFirst_DontSet = true)
116.             {
117.                 FindRootBreaker(isFirst_DontSet);
118.  
119.                 RootHolder currentRH = rootsOutput[current];
120.  
121.                 // if the toIndex is not set, or it is a pointer to the current index, then
122.                 // this element is a root element
123.                 if (currentRH.toIndex == 0 || currentRH.toIndex == current)
124.                 {
125.                     size = currentRH.size;
126.                     return current;
127.                 }
128.  
129.                 current = currentRH.toIndex;
130.  
131.                 return FindRoot(current, out size, false);
132.             }
133.             int findRootBreaker;
134.             void FindRootBreaker(bool isFirst)
135.             {
136.                 if (isFirst)
137.                 {
138.                     findRootBreaker = 0;
139.                 }
140.                 findRootBreaker++;
141.                 if (findRootBreaker > elements.Length)
142.                 {
143.                     throw new System.StackOverflowException("Find Root Breaker Activated");
144.                 }
145.             }
146.         }

Did I do something wrong? Why is the burst job more than three times slower?
Burst compile is enabled, I've checked the burst inspector and checked the BurstTimings in the console. Burst seems to be running and doing it's job. Turning off the burst savety checks gives me 4ms back, but it's still twice as slow as the Old Version ... also when the Job is done, I have to create the BuildingIsland on the main thread, the data from this job can't be used in my other systems.

I thought it would be much faster, it should be, right?
So what can I do, to make this run much faster? 1ms or less is the goal.

Edit: Maybe I should mention that the old version runs on a second thread too. (I deactivated it testwise to check if my custom threading could somehow block the JobSystem but it had no impact, still the same StopWatch Times (varying between 8ms and 18ms, while my custom one varies between 0ms and 4ms))
Also I do count the NativeArray Disposing into the time of the IJob:

Code (CSharp):

1.             Toolbox.StartStopwatch();
2.             {
3.                 // testSolve
4.                 NativeArray<bool> hasIslandsOutput = new NativeArray<bool>(1, Allocator.TempJob);
5.                 NativeArray<FindIslands.RootHolder> rootsOutput =
6.                     new NativeArray<FindIslands.RootHolder>(lines_N.Length, Allocator.TempJob);
7.  
8.                 FindIslands islandJob = new FindIslands(lines_N, elements_N, hashMap,
9.                     hasIslandsOutput, rootsOutput);
10.  
11.                 var islandHandle = islandJob.Schedule();
12.                 islandHandle.Complete();
13.                
14.                 Debug.Log("islandJob.hasIslands = " + hasIslandsOutput[0]);
15.                 hasIslandsOutput.Dispose();
16.                 rootsOutput.Dispose();
17.             }
18.             Toolbox.StopStopwatch("Island JobSystem");

 

Just making sure, did you prime the test with unmeasured runs before taking the final measurements? because the first run is 10x+ slower due to reflection and setup. Also it looks like you have a Debug.Log inside your timed area and allocation/dispose could maybe be set to permanent allocations and therefore not need to be part of your comparison.

 

No I didn't make prime tests, but I will, asap.

 

Yes, that was it, you where right, I corrected my benchmark test, results below with 1000 iterations each:
[results in milliseconds]

Jobs

Completely connected
0,013013013013013
0,016016016016016
0,029029029029029
0,033033033033033
0,029029029029029
0,0770770770770771

Disconnected in the middle
0,002002002002002
0,004004004004004
0,004004004004004
0,00600600600600601
0,001001001001001
long run (5000 iterations) :
0,0022004400880176


Normal

Completely connected
0,109
0,121
0,155
0,15
0,172
0,169

Disconnected in the middle
0,044
0,168
0,013


It's about 10 times faster and while thinking about the algorithm I had an idea how I could even improve this.