SortJob with IComparer.

I need to sort a large array in parallel, but have a comparison method that requires extra, not directly related data. I have an IComparer class that works for NativeArray.Sort, but SortJob can't take an IComparer.

Is there another way to do this? Even a bursted IJob is too slow.

 

Can you have the types implement IComparable?

 

I don't think so(I'll admit my in depth C# knowledge isn't as good as Python).

It's a parallel variable poisson disk sampler that relies on the input points being sorted by their cell id.

But for the cell id I need to know the bounds(AABB) of the grid and the number of cells per axis(int3). AFAIK, with IComparable I would need to copy those for each point, which isn't great for memory when working with a lot of points.

IComparable also appears to limit me to using my own struct which I need to convert to, when in theory I could pack the points and weights into a float4 to begin with.

I could use statics, but wouldn't that break when I have multiple datasets to give the sampler(s)?

 

SortJob isn't reliable because it doesn't work with Burst in builds. You could copy and modify the code you need to make it work with your points.

If it were me, I would make a struct that holds an int key and an int index for each point and populate that in a parallel job. Then I would sort these structs, likely using a radix sort. And then lastly, I would use the now sorted indices to copy the source points array into the sorted destination array.

 

Thanks. But, eh, I'll come back to it later and see what more gets added. I have more to build on before this needs to be super fast. And I really don't want to implement a sorting algorithm.

 

Check this out.

 

Which package will this update appear in? The Jobs package or the entities package? I ask because I'd like to be able to use this in a non ECS project.

 

It would be great to have some documentation on these as I was completely unaware that anything beyond collections, attributes and fixed strings existed in the collections package

 

I will save QA the time (because they would likely consider this as intended):

From the Burst docs:

Code (CSharp):

1. //This is a generic method
2. public unsafe static JobHandle SortJob<T>(T* array, int length, JobHandle inputDeps = new JobHandle()) where T : unmanaged, IComparable<T>
3.         {
4.             if (length == 0)
5.             {
6.                 return inputDeps;
7.             }
8.  
9.             var segmentCount = (length + 1023) / 1024;
10.  
11.             var workerCount = math.max(1, JobsUtility.MaxJobThreadCount);
12.             var workerSegmentCount = segmentCount / workerCount;
13. //This is a private generic job with a non-concrete generic argument
14.             var segmentSortJob = new SegmentSort<T> { Data = array, Length = length, SegmentWidth = 1024 };
15. //This is that job being scheduled
16.             var segmentSortJobHandle = segmentSortJob.Schedule(segmentCount, workerSegmentCount, inputDeps);
17. //And this is the mistake being done twice within the same method
18.             var segmentSortMergeJob = new SegmentSortMerge<T> { Data = array, Length = length, SegmentWidth = 1024 };
19.             var segmentSortMergeJobHandle = segmentSortMergeJob.Schedule(segmentSortJobHandle);
20.             return segmentSortMergeJobHandle;
21.         }

See this thread for community workarounds: https://forum.unity.com/threads/detect-jobs-skipped-by-burst.798288/
Note: My solution is also public now but it doesn't cover the SortJob use case. I haven't needed a parallel sort yet, especially since I already have a very fast radix sort.

 

And just in case you need proof, this is profiling SortJob in a build.
2020.2.0a21 and burst 1.4.0p4
Notice the lack of burst.

 

@s_schoener Any idea if the comparer job will be dropping soon?

 

I am more interested in the Group algorithm. where the order is not important but items with the same value need to be "grouped" in a continuous range. This algorithm would be much faster than sort.
Use case:
when the sort key is Entity, I can make sure all the work related to that entity is done together. Like GetBufferFromEntitiy and write to that buffer.
In this case, Increment/Decrement order is not important. We just need them to be processed together.
This could be a performance boost to ECS alike system.

 

NativeMultiHashMap using key and index into your data container isn't good enough for this purpose?

 

No.
You are talking about a different concept.
What if my array is a DynamicBuffer?
Do I need to create a new temp NativeHashMap to group them?
I'm just talking about faster sort when the need is not the order.

 

Typically when I sort things, I use ranked sorts, so I have a key and an index. With a ranked sort, I can defer moving the payloads around until the very last step, which is much lighter on memory bandwidth. For grouping, instead of sorting the key, index pairs, I hash them. Maybe you are thinking of a different grouping algorithm, but in that case, why not write it yourself?

 

I did. and have been using it. But Group algorithm is not very common. people simply use sort. I just want to know if there's a better one.

Spoiler

Code (CSharp):

1. /// <summary>
2.         /// Group first found equal value together(group order is not consistent) and return group count
3.         /// </summary>
4.         /// <typeparam name="T">value type</typeparam>
5.         /// <typeparam name="TComp">Comparer</typeparam>
6.         /// <param name="slice">array to group</param>
7.         /// <typeparam name="index">group start index</typeparam>
8.         /// <returns>group count</returns>
9.         public static int GroupFrom<T, TComp>(this NativeSlice<T> slice, TComp comp, int index = 0) where T : struct where TComp : IComparer<T>
10.         {
11.             var len = slice.Length;
12.             Assert.IsTrue(index<=len,"Group start out range array");
13.  
14.             if (index == len) return -1;
15.             else if (index == len - 1) return len;
16.             else if (len < 2) return len;
17.  
18.             int position = index + 1;
19.             int missMatchStart = 0;
20.             int missMatchCount = 0;
21.             int matchToFillGapCount = 0;
22.             int nextSearchPosition = 0;
23.             int state = 1;
24.             T matchTarget = slice[index];
25.             while (true)
26.             {
27.                 switch (state)
28.                 {
29.                     case 1:
30.                         if (comp.Compare(matchTarget, slice[position]) == 0)//initial match
31.                         {
32.                             position++;
33.                             if (position >= len) return len;//match until end of array
34.                         }
35.                         else//missmatch after initial match
36.                         {
37.                             missMatchStart = position;
38.                             position++;
39.                             if (position >= len) return len - 1;//last element missmatch
40.                             state = 2;
41.                         }
42.                         break;
43.                     case 2:
44.                         if (comp.Compare(matchTarget, slice[position]) != 0)//missmatch gap
45.                         {
46.                             position++;
47.                             if (position >= len) return missMatchStart;//missmatch until end of array
48.                         }
49.                         else//match following missmatch gap
50.                         {
51.                             matchToFillGapCount = 1;
52.                             missMatchCount = position - missMatchStart;
53.                             position++;
54.                             if (position >= len)//last element match
55.                             {
56.                                 position--;
57.                                 //swap---------------------------
58.                                 var temp = slice[position];
59.                                 slice[position] = slice[missMatchStart];
60.                                 slice[missMatchStart] = temp;
61.                                 //swap---------------------------
62.                                 return missMatchStart + 1;
63.                             }
64.                             state = 3;
65.                         }
66.                         break;
67.                     case 3:
68.                         if (comp.Compare(matchTarget, slice[position]) == 0)//jump match
69.                         {
70.                             position++;
71.                             matchToFillGapCount++;
72.                             if (matchToFillGapCount >= missMatchCount)//missmatch gap can be fully filled
73.                             {
74.                                 state = 4;
75.                                 nextSearchPosition = position >= len ? 0 : position;
76.                                 //match position is 1 index before
77.                                 position--;
78.                             }
79.                             else if (position >= len)//jump match until last element
80.                             {
81.                                 state = 4;
82.                                 nextSearchPosition = 0;
83.                                 //match position is 1 index before
84.                                 position--;
85.                             }
86.                         }
87.                         else//missmatch after jump match
88.                         {
89.                             state = 4;
90.                             position++;
91.                             nextSearchPosition = position >= len ? 0 : position;
92.                             //match position is 2 index before
93.                             position -= 2;
94.                         }
95.                         break;
96.                     case 4:
97.                         //Assert.IsTrue(matchToFillGapCount > 0 && missMatchCount > 0, "zero gap or match in state 4");
98.                         int matchOffset = position;
99.                         position = nextSearchPosition;
100.  
101.                         while (matchToFillGapCount > 0)
102.                         {
103.                             //swap----------------------
104.                             var temp = slice[matchOffset];
105.                             slice[matchOffset] = slice[missMatchStart];
106.                             slice[missMatchStart] = temp;
107.                             //swap----------------------
108.                             matchOffset--;
109.                             missMatchStart++;
110.                             matchToFillGapCount--;
111.                         }
112.  
113.                         if (nextSearchPosition == 0) return missMatchStart;
114.                         state = 2;
115.                         break;
116.                 }
117.             }
118.         }

 

So far, the new sortjob performs worse in my scenario than sorting in an IJob or single threaded.

For 1 million float4s in editor:

Sort in main thread : 6800ms
Sort in IJob: 130ms
SortJob with IComparer: 7ms(SegmentSort, good), 12000ms(SegmentSortMerge, horrible)

I do call .Complete() 2 jobs later but I don't think that would effect it that badly since SegmentSortMerge is an IJob and the sort handle gets fed into into the next.

 

Any updates on this? Have we SortJob solution which works with burst?