NativeList.Sort performance/complexity?

Unity Engine
,
1

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
Sort

        const int k_IntrosortSizeThreshold = 16;
        unsafe static void IntroSort<T, U>(void* array, int lo, int hi, int depth, U comp) where T : struct where U : IComparer<T>
        {
            while (hi > lo)
            {
                int partitionSize = hi - lo + 1;
                if (partitionSize <= k_IntrosortSizeThreshold)
                {
                    if (partitionSize == 1)
                    {
                        return;
                    }
                    if (partitionSize == 2)
                    {
                        SwapIfGreaterWithItems<T, U>(array, lo, hi, comp);
                        return;
                    }
                    if (partitionSize == 3)
                    {
                        SwapIfGreaterWithItems<T, U>(array, lo, hi - 1, comp);
                        SwapIfGreaterWithItems<T, U>(array, lo, hi, comp);
                        SwapIfGreaterWithItems<T, U>(array, hi - 1, hi, comp);
                        return;
                    }

                    InsertionSort<T, U>(array, lo, hi, comp);
                    return;
                }

                if (depth == 0)
                {
                    HeapSort<T, U>(array, lo, hi, comp);
                    return;
                }
                depth--;

                int p = Partition<T, U>(array, lo, hi, comp);
                IntroSort<T, U>(array, p + 1, hi, depth, comp);
                hi = p - 1;
            }
        }

        unsafe static void InsertionSort<T, U>(void* array, int lo, int hi, U comp) where T : struct where U : IComparer<T>
        {
            int i, j;
            T t;
            for (i = lo; i < hi; i++)
            {
                j = i;
                t = UnsafeUtility.ReadArrayElement<T>(array, i + 1);
                while (j >= lo && comp.Compare(t, UnsafeUtility.ReadArrayElement<T>(array, j)) < 0)
                {
                    UnsafeUtility.WriteArrayElement<T>(array, j + 1, UnsafeUtility.ReadArrayElement<T>(array, j));
                    j--;
                }
                UnsafeUtility.WriteArrayElement<T>(array, j + 1, t);
            }
        }

        unsafe static int Partition<T, U>(void* array, int lo, int hi, U comp) where T : struct where U : IComparer<T>
        {
            int mid = lo + ((hi - lo) / 2);
            SwapIfGreaterWithItems<T, U>(array, lo, mid, comp);
            SwapIfGreaterWithItems<T, U>(array, lo, hi, comp);
            SwapIfGreaterWithItems<T, U>(array, mid, hi, comp);

            T pivot = UnsafeUtility.ReadArrayElement<T>(array, mid);
            Swap<T>(array, mid, hi - 1);
            int left = lo, right = hi - 1;

            while (left < right)
            {
                while (comp.Compare(pivot, UnsafeUtility.ReadArrayElement<T>(array, ++left)) > 0) ;
                while (comp.Compare(pivot, UnsafeUtility.ReadArrayElement<T>(array, --right)) < 0) ;

                if (left >= right)
                    break;

                Swap<T>(array, left, right);
            }

            Swap<T>(array, left, (hi - 1));
            return left;
        }
2

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

3

Sort does this internally.

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

2 Likes
4

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.

5

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

6

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:

    private void QuickSort(Edge[] array, int low, int high)
    {
        if (low < high)
        {
            int pi = Partition(array, low, high);

            // Recursively sort elements before
            // partition and after partition
            QuickSort(array, low, pi - 1);
            QuickSort(array, pi + 1, high);
        }
    }

    private int Partition(Edge[] array, int low,
                           int high)
    {
        float2 pivot = array[high].Position1;

        int i = (low - 1);

        for (int j = low; j < high; j++)
        {
            // To sort by Y and X:
            if (
                array[j].Position1.y < pivot.y
                || (array[j].Position1.y == pivot.y && array[j].Position1.x < pivot.x)
            )
            {
                i++;

                _tempEdge = array[i];
                array[i] = array[j];
                array[j] = _tempEdge;
            }
        }

        _tempEdge = array[i + 1];
        array[i + 1] = array[high];
        array[high] = _tempEdge;

        return i + 1;
    }

    private Edge _tempEdge;

To use this I do it like this:

        //System.Array.Sort(_edges, Float2Comparer); // This is heavy on the milliseconds...
        //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.)

7

You aren’t using Burst?

8

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. ;_;

9

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

10

Yea that would be cool.

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

11

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

12

This is generic jobs used for sorting under hood, and they Burst compiled, isn’t it?:slight_smile:
5700088--595807--upload_2020-4-12_0-32-33.png

5700088--595804--upload_2020-4-12_0-31-36.png

13

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

1 Like
14

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

15

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

1 Like
16

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:

6266697--691797--nateefsort.PNG
6266697--691797--nateefsort.PNG711×160 6.23 KB

17

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.

1 Like
18

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#…

1 Like