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

Question

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

为了加快速度，我制作了一个查找表，因为许多计算本质上只需要计算一次，并且可以被重复使用。

然而，现在所有的查找都占用了30%的处理时间。我想知道这是否可能是因为内存过慢...不过，我仍然希望尝试进一步优化它。

目前我有以下内容：

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会更快吗？我该怎么做？

下面附有时间分布的屏幕截图：

- RobotRock

---

只使用一个for循环遍历height*width会略微更快，但除此之外很难发现任何明显的优化机会。 lookUp中的索引分布是否有任何模式？ - 500 - Internal Server Error

索引从等距矩形映射到立方体映射（反之亦然）进行分布。查找似乎是最快的方法，因为另一种选择是执行大量的乘法、cos、sin计算。 - RobotRock

我已经转换为单个循环，但这不是问题所在。我添加了一张截图，其中包含来自分析器的时间信息，以更详细地查看代码。 - RobotRock

@Postlagerkarte 这是 VS2017 诊断工具。 - RobotRock

一个带有细化步骤的小型LUT可能会给你中间地带。cos和sine是平滑函数，因此对于您的LUT条目，一个简单的起点+斜率将给您线性近似。或者只需在LUT条目之间使用线性插值。另外，cos = sin的斜率=导数。 - Peter Cordes

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);
    }
}

- Marc Gravell

---

@RobotRock 太好了！只是请注意，你的双重循环是一种复杂情况；上面的内容侧重于单循环场景，但原则是相同的；你只需要正确地切分你的跨度。 - Marc Gravell

没关系，我需要一些时间阅读有关在C#中使用Avx2和gather指令的资料。但至少我知道该去哪里寻找了。谢谢。 - RobotRock

@RobotRock 太棒了；使用 AVX2 后，运行时间从 1534ms（未使用 AVX2）缩短到了 698ms；正在更新答案。 - Marc Gravell

多个线程在不同的核心上运行有帮助吗？还是说内存是瓶颈？ - ca9163d9

@ca9163d9 这将是一个很好的测量指标！对于 AVX2，我认为它可能会有一点帮助，但不会太多。对于 AVX512（目前未公开，而且支持它的机器很少）：我不认为它会有所帮助，因为 AVX512 本身就可以非常占优势。 - Marc Gravell

Answer 2

RAM已经是可能的最快速度之一了。唯一更快的存储器是CPU缓存。因此，它会成为内存瓶颈，但仍然非常快。

当然，在给定的尺寸下，这个数组的大小为600万个条目。这可能不适合任何缓存。而且迭代过程将持续很长时间。无论速度如何，这只是太多的数据。

作为一个普遍规则，视频处理现在是在GPU上完成的。GPU被设计成可以操作巨大的数组。因为你现在看到的图像就是一个巨大的数组。

如果你必须保留在GPU端，也许缓存或惰性初始化会有帮助？很有可能你并不真正需要每个值。你只需要一些常见的值。以掷骰子为例：如果你掷两个六面骰子，从2到12的结果都是可能的。但结果7发生在36次中的6次。而2和12每次只有1次。所以存储7比存储2和12要更有益。

- Christopher

---

虽然在这里使用GPU可能会很好，但现代CPU也有专门支持此场景的操作 - 这就是“gather”（请参见上面的答案） - Marc Gravell