Zenn
Closed13

Unity JobSystemを使った並列ソート調査📝

Unity
sort
algorithm
jobsystem
ShitakamiShitakami

目的

  • JobSystemで近傍探索を実装したい
    • 近傍探索の実装でソートが必要
  • JobSystemで並列で動作するソートの処理速度を比較し、どのアルゴリズムが最適であるかを調査

要件

  • 引数でJobHandleを受け取り、JobHandleを返す
    • 前後のJobと依存関係を作りたいため
  • データ数は5000~30000を想定
    • この範囲で有効なアルゴリズムを検証する
  • Genericで型を指定
  • 実行環境はAndroid, Windowsを想定
    • iOSの検証端末を持ってない🙈
      • いつか余裕があれば

求めるパフォーマンス（希望）

  • データ数5000では1ms程度
  • データ数30000では3ms以下にしたい
  • （このパフォーマンスを出せない場合、近傍探索でソートを使わないアルゴリズムを採用する予定）
ShitakamiShitakami

ひとまず NativeArray.SortJob 用のテストを書いてたので📝
これを元に他のソートテストも書く。

NativeArray.SortJob
    [Test]
    public void IsValidNativeSort_IntValue()
    {
        var array = new NativeArray<int>(10000, Allocator.Temp);
        for (var i = 0; i < array.Length; i++)
        {
            array[i] = Random.Range(0, 100);
        }

        var handle = array.SortJob().Schedule();
        handle.Complete();

        for (var i = 0; i < array.Length - 1; i++)
        {
            Assert.LessOrEqual(array[i], array[i + 1]);
        }

        array.Dispose();
    }
    
    [Test]
    public void IsValidNativeSort_EntityGridData()
    {
        var array = new NativeArray<EntityGridData>(10000, Allocator.Temp);
        for (var i = 0; i < array.Length; i++)
        {
            array[i] = CreateRandomEntityGridData();
        }

        var handle = array.SortJob().Schedule();
        handle.Complete();

        for (var i = 0; i < array.Length - 1; i++)
        {
            var compare = array[i].CompareTo(array[i + 1]);
            Assert.LessOrEqual(compare, 0);
        }

        array.Dispose();
    }

    [Performance]
    [TestCase(10000)]
    [TestCase(30000)]
    public void NativeArraySort_IntValue(int arrayLength)
    {
        var array = new NativeArray<int>(arrayLength, Allocator.Temp);
        for (var i = 0; i < array.Length; i++)
        {
            array[i] = Random.Range(0, 300000);
        }

        Measure.Method(() =>
            {
                var handle = array.SortJob().Schedule();
                handle.Complete();
            })
            .CleanUp(() =>
            {
                for (var i = 0; i < array.Length; i++)
                {
                    array[i] = Random.Range(0, 100000);
                }
            })
            .WarmupCount(10)
            .MeasurementCount(100)
            .Run();

        array.Dispose();
    }
    
    [Performance]
    [TestCase(10000)]
    [TestCase(30000)]
    public void NativeArraySort_EntityGridData(int arrayLength)
    {
        var array = new NativeArray<EntityGridData>(arrayLength, Allocator.TempJob);

        Measure.Method(() =>
            {
                var handle = array.SortJob().Schedule();
                handle.Complete();
            })
            .CleanUp(() =>
            {
                for (var i = 0; i < array.Length; i++)
                {
                    array[i] = CreateRandomEntityGridData();
                }
            })
            .WarmupCount(10)
            .MeasurementCount(100)
            .Run();

        array.Dispose();
    }
EntityGridData
    [BurstCompile]
    public struct EntityGridData : IComparable<EntityGridData>, IEquatable<EntityGridData>
    {
        public int3 GridIndex;
        public int EntityIndex;

        public int CompareTo(EntityGridData other)
        {
            if (GridIndex.x != other.GridIndex.x) return GridIndex.x - other.GridIndex.x;
            if (GridIndex.y != other.GridIndex.y) return GridIndex.y - other.GridIndex.y;
            return GridIndex.z - other.GridIndex.z;
        }

        public bool Equals(EntityGridData other)
        {
            return GridIndex.Equals(other.GridIndex);
        }
    }

    [BurstCompile]
    public struct EntityGridDataComparer : IComparer<EntityGridData>
    {
        public int Compare(EntityGridData left, EntityGridData right)
        {
            if (left.GridIndex.x != right.GridIndex.x) return left.GridIndex.x - right.GridIndex.x;
            if (left.GridIndex.y != right.GridIndex.y) return left.GridIndex.y - right.GridIndex.y;
            return left.GridIndex.z - right.GridIndex.z;
        }
    }

友人と駄弁りながらなので、進捗は遅め🚶‍♂️

ShitakamiShitakami

UnityC＃で並列ソートをした話し より🗒️

var pivot = Median( keyPtr + l,keyPtr + m,keyPtr + r);

というコードがあり、メソッド自体の定義は記載されていない。
ひとまず、Median は中央値という意味なので、3つの値から真ん中を見つけるメソッドと定義して動作確認してみる。

        public static T Median(ref T left, ref T middle, ref T right)
        {
            if (left.CompareTo(middle) > 0)
            {
                if (middle.CompareTo(right) > 0)
                {
                    return middle;
                }

                if (left.CompareTo(right) > 0)
                {
                    return right;
                }

                return left;
            }
            else
            {
                if (right.CompareTo(middle) > 0)
                {
                    return middle;
                }

                if (left.CompareTo(right) > 0)
                {
                    return left;
                }

                return right;
            }
        }
ShitakamiShitakami

テキトーにコード書いてたので凄いごちゃごちゃしてきた、整理しましょ。

ShitakamiShitakami

UnityC＃で並列ソートをした話しの調整が面倒くさくなってきたので、Sort with JOB systemにてTestを書いて実行。

以下のWarning Messageが出てきた。

Warning Message
Compilation was requested for method `Unity.Jobs.IJobParallelForBatchExtensions+JobParallelForBatchProducer`1[[ParallelMergeSort+MergeSortJob`1[[System.Int32, mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089]], ParallelSort, Version=0.0.0.0, Culture=neutral, PublicKeyToken=null]], Unity.Collections, Version=0.0.0.0, Culture=neutral, PublicKeyToken=null::Execute(ParallelMergeSort+MergeSortJob`1[[System.Int32, mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089]]&, ParallelSort, Version=0.0.0.0, Culture=neutral, PublicKeyToken=null|System.IntPtr, mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089|System.IntPtr, mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089|Unity.Jobs.LowLevel.Unsafe.JobRanges&, UnityEngine.CoreModule, Version=0.0.0.0, Culture=neutral, PublicKeyToken=null|System.Int32, mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089)` but it is not a known Burst entry point. This may be because the [BurstCompile] method is defined in a generic class, and the generic class is not instantiated with concrete types anywhere in your code.


最後の行でGeneric classとBurstCompileが何たらとなっていた。

but it is not a known Burst entry point. This may be because the [BurstCompile] method is defined in a generic class, and the generic class is not instantiated with concrete types anywhere in your code.

原因として、ソートのコードを調整したときに BurstCompile(CompileSynchronously = true) の引数を消していた。
CompileSynchronously については詳しくないが、コンパイル周りで型が確定せずBusrtCompileに影響が出たのではとの推測で特定した💭


CompileSynchronously = true を消していた理由として、ドキュメントよりfpsへの影響があること、特定の使用状況でのみ推奨される点があった。
https://docs.unity3d.com/ja/Packages/com.unity.burst@1.8/manual/compilation-synchronous.html

CompileSynchronously = true に設定すると、非同期コンパイルが行えなくなります。そのため、Burst のコンパイルにかかる時間が長くなる可能性があります。このようなコンパイルの中断は現在の実行フレームに影響を与え、がたつき (フレーム落ち) を発生させます。その結果、ユーザーは応答性が低下したと感じる可能性があります。

一般に、CompileSynchronously = true は以下の状況でのみ使用してください。

  • 1 回のみ長時間実行されるジョブがある場合。コンパイルしたコードのパフォーマンスが、同期的にコンパイルを行うデメリットを上回る可能性があります。
  • Burst ジョブをプロファイルしているときに、Burst コンパイラーからのコードをテストする場合。この際には、ウォームアップを実行して、ジョブの最初の呼び出し以降のタイミング測定値を破棄してください。これは、プロファイリングデータにコンパイル時間が含まれると、結果が不正確になるからです。
  • マネージコードと Burst コンパイルコードの違いをデバッグしやすくする場合。


今回はテストを書いている都合上、以下の使用状況に該当しているから指定する必要があったのかも🤔

Burst ジョブをプロファイルしているときに、Burst コンパイラーからのコードをテストする場合。

ShitakamiShitakami

ちょっとコード見るのが疲れて記事を漁ってたので、メモ 👀
https://coffeebraingames.wordpress.com/2020/05/24/nativearray-sortjob-is-fast-or-is-it/

この記事によると、Unity Editor上とビルドしたアプリ上での実行速度が異なるとの情報。

In the sample profile here, SortJob() executes a total of 5.069ms while Quicksort runs faster at 1.28ms compared to its running time in the editor (1.73).

ちゃんと実行速度を調べたい場合はビルドして実行するのがよさそう💭

ShitakamiShitakami

ふと思ったこと💭
IComparable<T>.CompareTo では構造体を参照渡しできないので、パフォーマンスが落ちてしまうのでは？
（パフォーマンスを詰めるには構造体専用のソートを実装する必要がある？🤔）

追記

https://coffeebraingames.wordpress.com/2020/05/24/nativearray-sortjob-is-fast-or-is-it/
上記サイトの QuickSortJob で構造体を参照渡し (ref) してみたが、そこまで大きな差はなかった。
よって、IComparable<T>.CompareTo を参照渡しにするよう頑張る必要はなさそう。

ShitakamiShitakami

自分が昔書いたBitonicSortをJobSystemに置き換え。
配列の大きさが2の累乗である場合のみソートできる。

BitonicSort
using System;
using Unity.Burst;
using Unity.Collections;
using Unity.Collections.LowLevel.Unsafe;
using Unity.Jobs;
using Unity.Mathematics;

namespace ParallelSort
{
    public static unsafe class BitonicSort
    {
        public static JobHandle Sort<T>(
            NativeArray<T> array, 
            JobHandle jobHandle, 
            int innerLoopCount = 1000) 
            where T : unmanaged, IComparable<T>
        {
            var arrayLength = array.Length;
            if (!math.ispow2(arrayLength))
            {
                UnityEngine.Debug.LogError($"Array length must be power of 2: arrayLength={arrayLength}");
            }

            var length = math.ceillog2(arrayLength);

            for (var step = 0; step < length; ++step)
            {
                for (var stage = 0; stage < step + 1; ++stage)
                {
                    var swapDistance = 1 << (step - stage);
                    
                    var sortJob = new BitonicSortJob<T>
                    {
                        ArrayPtr = (T*)array.GetUnsafePtr(),
                        Step = step,
                        SwapDistance = swapDistance,
                        ArrayLength = arrayLength
                    };
                    
                    jobHandle = sortJob.Schedule(arrayLength / 2, innerLoopCount, jobHandle);
                }
            }

            return jobHandle;
        }

        [BurstCompile(CompileSynchronously = true)]
        private struct BitonicSortJob<T> : IJobParallelFor where T : unmanaged, IComparable<T>
        {
            [NativeDisableUnsafePtrRestriction] [ReadOnly] public T* ArrayPtr;
            [ReadOnly] public int Step;
            [ReadOnly] public int SwapDistance;
            [ReadOnly] public int ArrayLength;

            public void Execute(int index)
            {
                var low = index & (SwapDistance - 1);
                var left = (index << 1) - low;
                if (left >= ArrayLength)
                {
                    return;
                }
                
                var right = left + SwapDistance;
                if (right >= ArrayLength)
                {
                    return;
                }

                var isUpperOrdered = (ArrayPtr + left)->CompareTo(*(ArrayPtr + right)) < 0;
                var isUpper = (left & (2 << Step)) == 0;
                
                if (isUpper != isUpperOrdered)
                {
                    (*(ArrayPtr + left), *(ArrayPtr + right)) = (*(ArrayPtr + right), *(ArrayPtr + left));
                }
            }
        }
    }
}
ShitakamiShitakami

Unity Editor上でのPerformance Testの実行結果を載せる。

  • 最速が NativeArray.Sort
  • ParallelMergeSortがBitonicSortより若干速い
  • IJobで実行するQuickSortが遅め
int型 10000 int型 30000 自作int3型 10000 自作int3型 30000
NativeSort 10000 30000 10000 30000
ParallelMergeSort 10000 30000 10000 30000
BitonicSort 10000 30000 10000 30000
QuickSort 10000 30000 10000 30000
ShitakamiShitakami

いったんは別の作業に移行するため、並列ソートに関する調査を切り上げる。
またやる気が出てきたら調査を再開するかも。

このスクラップは5ヶ月前にクローズされました