c# - 使用整数索引进行数组表查找的最快方法是什么？

Question

我有一个可以移动大量数据的视频处理应用程序。

为了加快速度，我做了一个查找表，因为很多计算本质上只需要计算一次就可以重复使用。

但是现在所有查找都占用了 30% 的处理时间。我想知道它的 RAM 是否可能很慢。但是，我仍然想尝试进一步优化它。

目前我有以下内容:

public readonly int[] largeArray = new int[3000*2000];
public readonly int[] lookUp = new int[width*height];

然后，我使用指针 p(相当于 width * y + x)执行查找以获取结果。

int[] newResults = new int[width*height];
int p = 0;
for (int y = 0; y < height; y++) {
   for (int x = 0; x < width; x++, p++) {
      newResults[p] = largeArray[lookUp[p]];
   }
}

请注意，我无法复制整个数组来进行优化。此外，该应用程序是高度多线程的。

在缩短函数堆栈方面取得了一些进展，因此没有 getter，而是直接从只读数组中检索。

我也尝试过转换为 ushort，但它似乎更慢(据我所知，这是由于字长造成的)。

IntPtr 会更快吗？我该怎么做呢？

下面附上时间分布截图:

Answer 1

看起来你在这里所做的实际上是一次“聚集”。现代 CPU 对此有专用指令，特别是 VPGATHER** 。这是在 .NET Core 3 中公开的，应该可以像下面这样工作，这是单循环场景(您可能可以从这里开始获取双循环版本)；

结果第一:

AVX enabled: False; slow loop from 0
e7ad04457529f201558c8a53f639fed30d3a880f75e613afe203e80a7317d0cb
for 524288 loops: 1524ms

AVX enabled: True; slow loop from 1024
e7ad04457529f201558c8a53f639fed30d3a880f75e613afe203e80a7317d0cb
for 524288 loops: 667ms

代码:

using System;
using System.Diagnostics;
using System.Runtime.InteropServices;
using System.Runtime.Intrinsics;
using System.Runtime.Intrinsics.X86;

static class P
{
    static int Gather(int[] source, int[] index, int[] results, bool avx)
    {   // normally you wouldn't have avx as a parameter; that is just so
        // I can turn it off and on for the test; likewise the "int" return
        // here is so I can monitor (in the test) how much we did in the "old"
        // loop, vs AVX2; in real code this would be void return

        int y = 0;
        if (Avx2.IsSupported && avx)
        {
            var iv = MemoryMarshal.Cast<int, Vector256<int>>(index);
            var rv = MemoryMarshal.Cast<int, Vector256<int>>(results);

            unsafe
            {
                fixed (int* sPtr = source)
                {
                    // note: here I'm assuming we are trying to fill "results" in
                    // a single outer loop; for a double-loop, you'll probably need
                    // to slice the spans
                    for (int i = 0; i < rv.Length; i++)
                    {
                        rv[i] = Avx2.GatherVector256(sPtr, iv[i], 4);
                    }
                }
            }
            // move past everything we've processed via SIMD
            y += rv.Length * Vector256<int>.Count;
        }
        // now do anything left, which includes anything not aligned to 256 bits,
        // plus the "no AVX2" scenario
        int result = y;
        int end = results.Length; // hoist, since this is not the JIT recognized pattern
        for (; y < end; y++)
        {
            results[y] = source[index[y]];
        }
        return result;
    }

    static void Main()
    {
        // invent some random data
        var rand = new Random(12345);
        int size = 1024 * 512;
        int[] data = new int[size];
        for (int i = 0; i < data.Length; i++)
            data[i] = rand.Next(255);

        // build a fake index
        int[] index = new int[1024];
        for (int i = 0; i < index.Length; i++)
            index[i] = rand.Next(size);

        int[] results = new int[1024];

        void GatherLocal(bool avx)
        {
            // prove that we're getting the same data
            Array.Clear(results, 0, results.Length);
            int from = Gather(data, index, results, avx);
            Console.WriteLine($"AVX enabled: {avx}; slow loop from {from}");
            for (int i = 0; i < 32; i++)
            {
                Console.Write(results[i].ToString("x2"));
            }
            Console.WriteLine();

            const int TimeLoop = 1024 * 512;
            var watch = Stopwatch.StartNew();
            for (int i = 0; i < TimeLoop; i++)
                Gather(data, index, results, avx);
            watch.Stop();
            Console.WriteLine($"for {TimeLoop} loops: {watch.ElapsedMilliseconds}ms");
            Console.WriteLine();
        }
        GatherLocal(false);
        if (Avx2.IsSupported) GatherLocal(true);
    }
}