NativeList.Sort performance/complexity?

Trying to determine if I should be using NativeList.Sort() in an algorithm or not, but I'm not sure what this does under the hood or how expensive it is. Does anyone know?

EDIT: wow, sorry, found it within seconds of posting thread. I thought I couldn't find it. My bad

Spoiler: Sort

Code (CSharp):

1.         const int k_IntrosortSizeThreshold = 16;
2.         unsafe static void IntroSort<T, U>(void* array, int lo, int hi, int depth, U comp) where T : struct where U : IComparer<T>
3.         {
4.             while (hi > lo)
5.             {
6.                 int partitionSize = hi - lo + 1;
7.                 if (partitionSize <= k_IntrosortSizeThreshold)
8.                 {
9.                     if (partitionSize == 1)
10.                     {
11.                         return;
12.                     }
13.                     if (partitionSize == 2)
14.                     {
15.                         SwapIfGreaterWithItems<T, U>(array, lo, hi, comp);
16.                         return;
17.                     }
18.                     if (partitionSize == 3)
19.                     {
20.                         SwapIfGreaterWithItems<T, U>(array, lo, hi - 1, comp);
21.                         SwapIfGreaterWithItems<T, U>(array, lo, hi, comp);
22.                         SwapIfGreaterWithItems<T, U>(array, hi - 1, hi, comp);
23.                         return;
24.                     }
25.  
26.                     InsertionSort<T, U>(array, lo, hi, comp);
27.                     return;
28.                 }
29.  
30.                 if (depth == 0)
31.                 {
32.                     HeapSort<T, U>(array, lo, hi, comp);
33.                     return;
34.                 }
35.                 depth--;
36.  
37.                 int p = Partition<T, U>(array, lo, hi, comp);
38.                 IntroSort<T, U>(array, p + 1, hi, depth, comp);
39.                 hi = p - 1;
40.             }
41.         }
42.  
43.         unsafe static void InsertionSort<T, U>(void* array, int lo, int hi, U comp) where T : struct where U : IComparer<T>
44.         {
45.             int i, j;
46.             T t;
47.             for (i = lo; i < hi; i++)
48.             {
49.                 j = i;
50.                 t = UnsafeUtility.ReadArrayElement<T>(array, i + 1);
51.                 while (j >= lo && comp.Compare(t, UnsafeUtility.ReadArrayElement<T>(array, j)) < 0)
52.                 {
53.                     UnsafeUtility.WriteArrayElement<T>(array, j + 1, UnsafeUtility.ReadArrayElement<T>(array, j));
54.                     j--;
55.                 }
56.                 UnsafeUtility.WriteArrayElement<T>(array, j + 1, t);
57.             }
58.         }
59.  
60.         unsafe static int Partition<T, U>(void* array, int lo, int hi, U comp) where T : struct where U : IComparer<T>
61.         {
62.             int mid = lo + ((hi - lo) / 2);
63.             SwapIfGreaterWithItems<T, U>(array, lo, mid, comp);
64.             SwapIfGreaterWithItems<T, U>(array, lo, hi, comp);
65.             SwapIfGreaterWithItems<T, U>(array, mid, hi, comp);
66.  
67.             T pivot = UnsafeUtility.ReadArrayElement<T>(array, mid);
68.             Swap<T>(array, mid, hi - 1);
69.             int left = lo, right = hi - 1;
70.  
71.             while (left < right)
72.             {
73.                 while (comp.Compare(pivot, UnsafeUtility.ReadArrayElement<T>(array, ++left)) > 0) ;
74.                 while (comp.Compare(pivot, UnsafeUtility.ReadArrayElement<T>(array, --right)) < 0) ;
75.  
76.                 if (left >= right)
77.                     break;
78.  
79.                 Swap<T>(array, left, right);
80.             }
81.  
82.             Swap<T>(array, left, (hi - 1));
83.             return left;
84.         }

 

Try to convert the NativeList into a NativeArray using AsArray() before calling Sort(). I think NativeArray has better random access performance based on how Unity recommends converting DynamicBuffers to NativeArrays

 

Sort does this internally.

It's a pretty fast fast comparison sort. At low counts (up to around 300) it beats my radix sort.

 

I've made a custom implementation of QuickSort for a few hundred float2s (posing as Vector2s) to sort them by X or Y-value and it beats Sort() in terms of overhead.

 

If you are willing to share code, I'd love to benchmark it!

 

It's not all my code, and I am trying to find where I got the source code from, but it was probably the Unitywiki or somewhere related to this place.

Here you go:

Code (CSharp):

1.     private void QuickSort(Edge[] array, int low, int high)
2.     {
3.         if (low < high)
4.         {
5.             int pi = Partition(array, low, high);
6.  
7.             // Recursively sort elements before
8.             // partition and after partition
9.             QuickSort(array, low, pi - 1);
10.             QuickSort(array, pi + 1, high);
11.         }
12.     }
13.  
14.     private int Partition(Edge[] array, int low,
15.                            int high)
16.     {
17.         float2 pivot = array[high].Position1;
18.  
19.         int i = (low - 1);
20.  
21.         for (int j = low; j < high; j++)
22.         {
23.             // To sort by Y and X:
24.             if (
25.                 array[j].Position1.y < pivot.y
26.                 || (array[j].Position1.y == pivot.y && array[j].Position1.x < pivot.x)
27.             )
28.             {
29.                 i++;
30.  
31.                 _tempEdge = array[i];
32.                 array[i] = array[j];
33.                 array[j] = _tempEdge;
34.             }
35.         }
36.  
37.         _tempEdge = array[i + 1];
38.         array[i + 1] = array[high];
39.         array[high] = _tempEdge;
40.  
41.         return i + 1;
42.     }
43.  
44.     private Edge _tempEdge;

To use this I do it like this:

Code (CSharp):

1.         //System.Array.Sort(_edges, Float2Comparer); // This is heavy on the milliseconds...
2.         //QuickSort(_edges, 0, _edges.Length - 1); // This not so much.

(An "Edge" is a struct that holds a few float2s and some bools, used in a sweepline-algorithm for triangulation of non-monotone polygonals.)

 

You aren't using Burst?

 

I've not yet come that far. I made a thread earlier that I asked for how to use functions/methods with the job system. This is a part of that... I wish I had more time. ;_;

 

Is there a parallelized sort for NativeList or NativeArray? The normal sorts are running on the main thread

 

Yea that would be cool.

https://software.intel.com/en-us/node/506167

 

NativeSortExtension.SortJob. However, because this is a generic scheduler to generic jobs, Burst doesn't work.

 

This is generic jobs used for sorting under hood, and they Burst compiled, isn't it?

 

Is that in a player? Burst will work in the editor.

 

Ah, yep, I checked in editor. Completely forgot about generic jobs scheduling when build. My bad!

 

Wow! SortJob() is fast! Here I was using a burst compiled quick sort.

 

Necrobumping because calling .Sort() on a NativeList (consting of a struct of an int and a float) inside a Job while-loop leads to this:

 

That's not anything to worry about; I get tons of those. It's not using some optimizations because it can't figure out the logic. But those sorts can't easily be vectorized anyway.

If you absolutely need a vectorizable sort, you might be able to do some sort of Bitonic Sort/sorting network (see: GPU sorting), or a Radix sort (if your types can be ordered by bits). I'd only be concerned here if sorting actually is causing a performance problem.

 

So far it's ok, though. I did it because I wanted to test it myself. However, I have spent a lot of time trying to optimise due to the scale of the game, and the more I optimise the less it seems I can use of Unity's API, and the more it feels like I am making the game engine myself in "pure" C#...