只需少量更改即可大幅提升性能

这个问题如果解决了 ,请参阅评论以获得答案

我最近开始测试一些对图像像素进行排序的方法。具体来说,我正在使用 System.Drawing.Common.Bitmap 。我有两种方法:

[Benchmark]
public unsafe void HorizontalOuter()
{
    for (int row = 0; row < _bmpData.Height - 1; row++)
    {
        int bytes = _bmpData.Stride;
        void* ptr = (void*)(_bmpData.Scan0 + _bmpData.Stride * row);
        var span = new Span<TPixel>(ptr, bytes);

        InsertionSort(
            keys: span,
            comparer: (IComparer<TPixel>)new Comparer24bit_soA_stR());
    }
}

在图像数据的每一行周围创建一个跨度,但使用更快的 InsertionSort 。

和

[Benchmark]
public unsafe void HorizontalInner()
{
    int bytes = _bmpData.Stride * _bmpData.Height;
    void* ptr = (void*)_bmpData.Scan0;
    var span = new Span<TPixel>(ptr, bytes);

    for (int row = 0; row < _bmpData.Height - 1; row++)
    {
        InsertionSort(
            keys: span,
            comparer: (IComparer<TPixel>)new Comparer24bit_soA_stR(),
            step: 1,
            from: _bmpData.Width * row,
            to: (row + 1) * _bmpData.Width);
    }
}

围绕整个图像数据创建跨度,但使用较慢的实现 插入排序 。

我对这两种方法的性能进行了基准测试,我很惊讶地看到 HorizontalInner 比快一个数量级 HorizontalOuter :

HorizontalOuter
Standard Deviation: 00:00:00.0550178
Average:            00:00:00.686941

HorizontalInner
Standard Deviation: 00:00:00.0531962
Average:            00:00:00.0619287

(JIT的预热时间已考虑在内。)

我现在的问题是:为什么 水平外部 慢得多 水平内部 ?

以下是的两个实现 插入排序 : ( 水平内部 )

private static void InsertionSort(Span<TPixel> keys, IComparer<TPixel> comparer, int step, int from, int to)
{
    for (int i = from; i < to - step; i += step)
    {
        TPixel t = keys[i + step];

        int j = i;
        while (j >= from && comparer.Compare(t, keys[j]) < 0)
        {
            keys[j + step] = keys[j];
            j -= step;
        }

        keys[j + step] = t;
    }
}

( 水平外部 )

private static void InsertionSort(Span<TPixel> keys, IComparer<TPixel> comparer)
{
    for (int i = 0; i < keys.Length - 1; i += 1)
    {
        TPixel t = keys[i + 1];

        int j = i;
        while (j >= 0 && comparer.Compare(t, keys[j]) < 0)
        {
            keys[j + 1] = keys[j];
            j -= 1;
        }

        keys[j + 1] = t;
    }
}

编辑:我用来进行基准测试的代码:

{
    var methods = typeof(T).GetMethods().Where(x => x.GetCustomAttribute<BenchmarkAttribute>() != null);
    var results = new Dictionary<MethodInfo, List<long>>();

    foreach (var method in methods)
    {

        Console.WriteLine("\n" + method.Name);

        Stopwatch metTime;
        List<long> allElapsedTicks = new();


        Console.WriteLine("Warming up...");
        metTime = Stopwatch.StartNew();
        while (metTime.ElapsedTicks <= WarmupTimePerMethod.Ticks)
        {
            T instance = Activator.CreateInstance<T>();
            Stopwatch sw = Stopwatch.StartNew();
            method.Invoke(instance, null);
            sw.Stop();
        }
        metTime.Stop();
        Console.WriteLine("Finished warm up.");


        Console.WriteLine("Starting benchmark...");
        metTime = Stopwatch.StartNew();
        while (metTime.ElapsedTicks <= BenchmarkTimePerMethod.Ticks)
        {
            T instance = Activator.CreateInstance<T>();

            Stopwatch sw = Stopwatch.StartNew();
            method.Invoke(instance, null);
            sw.Stop();

            allElapsedTicks.Add(sw.ElapsedTicks);
            Console.WriteLine($"{TimeSpan.FromTicks(sw.ElapsedTicks)}");
        }
        metTime.Stop();


        results.Add(method, allElapsedTicks);
    }


    foreach (var result in results)
    {
        Console.WriteLine("\n" + result.Key.Name);
        Console.WriteLine($"Standard Deviation: {TimeSpan.FromTicks(StdDev(result.Value))}");
        Console.WriteLine($"Average:            {TimeSpan.FromTicks(Average(result.Value))}");
    }
}

class SorterBenchmark : Sorter<Pixel_24bit> 
{ 
    public SorterBenchmark() : base(GetBmpData(new Bitmap(IMG))) { } 
}


static BitmapData GetBmpData(Bitmap bmp)
{
    Rectangle rect = new Rectangle(0, 0, bmp.Width, bmp.Height);
    return bmp.LockBits(rect, ImageLockMode.ReadWrite, bmp.PixelFormat);
}

static void Main()
{
    Benchmark.WarmupTimePerMethod = TimeSpan.FromSeconds(10);
    Benchmark.BenchmarkTimePerMethod = TimeSpan.FromSeconds(10);
    Benchmark.Run<SorterBenchmark>();
}