Dispatcher.Sort is slower than Array.Sort (for expec... | stride3d/stride

Release Type: GitHub

Version: master @ c1445f3a51

Platform(s): Windows

Issue
Dispatcher.Sort is slower than Array.Sort for "reasonable" array sizes. Up until 2048 elements Dispatcher.Sort just forwards to Array.Sort, so perf is basically equal and you won't notice in smaller scenes, but if you hit that threshold and the parallel sorting kicks in there's a large hit.


BenchmarkDotNet v0.13.8, Windows 10 (10.0.19045.3324/22H2/2022Update)
AMD Ryzen 5 3600, 1 CPU, 12 logical and 6 physical cores
.NET SDK 8.0.100-preview.7.23376.3
  [Host]     : .NET 6.0.14 (6.0.1423.7309), X64 RyuJIT AVX2
  DefaultJob : .NET 6.0.14 (6.0.1423.7309), X64 RyuJIT AVX2

Method	Size	Mean	Error	StdDev	Allocated
ArraySortRandom	2048	45.17 μs	0.899 μs	1.000 μs	64 B
DispatcherSortRandom	2048	43.72 μs	0.789 μs	1.053 μs	112 B
ArraySortAllEqual	2048	35.65 μs	0.687 μs	0.791 μs	64 B
DispatcherSortAllEqual	2048	35.92 μs	0.540 μs	0.451 μs	112 B
ArraySortRandom	8192	230.45 μs	4.600 μs	7.161 μs	64 B
DispatcherSortRandom	8192	1,518.76 μs	174.042 μs	510.436 μs	468 B
ArraySortAllEqual	8192	177.25 μs	3.504 μs	5.137 μs	64 B
DispatcherSortAllEqual	8192	1,204.38 μs	140.923 μs	411.078 μs	471 B
ArraySortRandom	32768	1,019.05 μs	18.854 μs	35.872 μs	65 B
DispatcherSortRandom	32768	9,055.07 μs	515.215 μs	1,519.124 μs	1515 B
ArraySortAllEqual	32768	842.24 μs	13.953 μs	14.329 μs	65 B
DispatcherSortAllEqual	32768	8,773.73 μs	749.638 μs	2,210.325 μs	1466 B
ArraySortRandom	131072	4,565.46 μs	50.877 μs	47.591 μs	69 B
DispatcherSortRandom	131072	10,804.07 μs	384.954 μs	1,129.002 μs	5031 B
ArraySortAllEqual	131072	3,964.75 μs	28.756 μs	26.898 μs	68 B
DispatcherSortAllEqual	131072	10,429.99 μs	391.150 μs	1,153.314 μs	4963 B

For larger arrays Dispatcher.Sort will eventually become faster, but still at the cost of more allocation and keeping multiple cores busy.

Benchmark Source

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Configs;
using BenchmarkDotNet.Running;
using Stride.Core.Threading;
using System.Runtime.CompilerServices;
using static BenchmarkDotNet.Attributes.MarkdownExporterAttribute;

namespace ProfilerBenchmarks
{
    public readonly struct BigStruct : IComparable<BigStruct>
    {
        private readonly long _long;
        private readonly int _int0;
        private readonly int _int1;
        private readonly short _short0;
        private readonly short _short1;
        private readonly short _short2;
        private readonly short _short3;
        private readonly double _double;

        public BigStruct(int value)
        {
            _long = value;
            _int0 = value;
            _int1 = value;
            _short0 = (short)value;
            _short1 = (short)value;
            _short2 = (short)value;
            _short3 = (short)value;
            _double = value;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public int CompareTo(BigStruct other) => _int1 - other._int1;
    }

    [GitHub]
    [MemoryDiagnoser]
    [GenericTypeArguments(typeof(int))]
    [GenericTypeArguments(typeof(BigStruct))]
    public class Sort<T> where T : IComparable<T>, new()
    {
        private T[] _values;
        private T[] _results;

        private T[] _ordered;
        private T[] _equal;

        [Params(2048, 8192, 32768, 131072)]
        public int Size { get; set; }

        [GlobalSetup]
        public void Setup()
        {
            _values = GenerateValues();
            _results = new T[Size];
            _ordered = GenerateOrderedValues().ToArray(); ;
            _equal = GenerateEqualValues().ToArray();
        }


        private T[] GenerateValues()
        {
            var rng = new Random(3455378);
            if (typeof(T) == typeof(BigStruct))
            {
                var values = new BigStruct[Size];
                for (int i = 0; i < Size; i++)
                {
                    values[i] = new BigStruct(rng.Next());
                }
                return (T[])(object)values;
            }
            else
            {
                var values = new int[Size];
                for (int i = 0; i < Size; i++)
                {
                    values[i] = rng.Next();
                }
                return (T[])(object)values;
            }
        }

        private IEnumerable<T> GenerateOrderedValues()
        {
            var i = 0;
            if (typeof(T) == typeof(int))
                while (i++ < Size) yield return (T)(object)i;
            else
                while (i++ < Size) yield return (T)(object)new BigStruct(i);
        }

        private IEnumerable<T> GenerateEqualValues()
        {
            var i = 0;
            var val = Random.Shared.Next(0, 256);
            if (typeof(T) == typeof(int))
                while (i++ < Size) yield return (T)(object)val;
            else
                while (i++ < Size) yield return (T)(object)new BigStruct(val);
        }

        [Benchmark]
        public void ArraySortRandom() => Array.Sort(_values, ComparableComparer.Default);

        [Benchmark]
        public void DispatcherSortRandom() => Dispatcher.Sort(_values, 0, _values.Length, ComparableComparer.Default);

        //[Benchmark]
        //public void ArraySortOrdered() => Array.Sort(_ordered, ComparableComparerStruct.Default);

        //[Benchmark]
        //public void DispatcherSortOrdered() => Dispatcher.Sort(_ordered, 0, _values.Length, ComparableComparerStruct.Default);

        [Benchmark]
        public void ArraySortAllEqual() => Array.Sort(_equal, ComparableComparer.Default);

        [Benchmark]
        public void DispatcherSortAllEqual() => Dispatcher.Sort(_equal, 0, _values.Length, ComparableComparer.Default);

        private class ComparableComparer : IComparer<T>
        {
            public static readonly ComparableComparer Default = new ComparableComparer();

            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            public int Compare(T x, T y) => x.CompareTo(y);
        }
    }
}

internal class Program
{
    private static void Main(string[] args)
    {
        var summary = BenchmarkSwitcher.FromAssembly(typeof(Program).Assembly).Run(args, config: ManualConfig
            .Create(DefaultConfig.Instance)
            .WithOptions(ConfigOptions.DontOverwriteResults));
    }
}

Testing in a scene with >2048 objects also shows the impact clearly.

Suggested fix
Replace all calls with Array.Sort, remove Dispatcher.Sort. (There are only 3 calls and they are all in RenderSystem.cs)

If Array.Sort still has high performance impact, switch to counting/radix sort, depending on the values to be sorted.
Longer term figure out how to reorganize the renderer, so that at least some of this sorting can be avoided entirely.

Dispatcher.Sort is slower than Array.Sort (for expected uses)

Description

Contributor guide

First steps

Research direction

Assessment