c# - ¿Cuál es la forma más rápida de hacer una búsqueda de tabla de matriz con un índice entero?

memory lookup

Question

Tengo una aplicación de procesamiento de video que mueve muchos datos.

Para acelerar las cosas, he hecho una tabla de búsqueda, ya que muchos cálculos en esencia solo necesitan calcularse una vez y pueden reutilizarse.

Sin embargo, estoy en el punto donde todas las búsquedas ahora toman el 30% del tiempo de procesamiento. Me pregunto si podría ser RAM lenta. Sin embargo, todavía me gustaría intentar optimizarlo un poco más.

Actualmente tengo lo siguiente:

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

Luego realizo una búsqueda con un puntero p (que es equivalente al width * y + x ) para obtener el resultado.

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

Tenga en cuenta que no puedo hacer una copia completa de la matriz para optimizar. Además, la aplicación es muy multiproceso.

Se avanzó un poco en el acortamiento de la pila de funciones, por lo que no se obtuvieron sino una recuperación directa de una matriz de solo lectura.

Intenté convertir a ushort también, pero parecía ser más lento (según tengo entendido, se debe al tamaño de la palabra).

¿Sería un IntPtr más rápido? ¿Cómo iba a hacer eso?

A continuación se adjunta una captura de pantalla de la distribución del tiempo:

Answer 1

Parece que lo que estás haciendo aquí es efectivamente una "reunión". Las CPU modernas tienen instrucciones dedicadas para esto, en particular VPGATHER** . Esto se expone en .NET Core 3, y debería funcionar de la siguiente manera, que es el escenario de bucle único (probablemente pueda trabajar desde aquí para obtener la versión de doble bucle);

resultados primero:

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

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

código:

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

Answer 2

RAM ya es una de las cosas más rápidas posibles. La única memoria más rápida es el caché de la CPU. Por lo tanto, será Memory Bound, pero eso sigue siendo bastante rápido.

Por supuesto, en los tamaños dados, esta matriz tiene un tamaño de 6 millones de entradas. Es probable que eso no encaje en ningún caché. Y tomará una eternidad para repasar. No importa cuál es la velocidad, esto es simplemente demasiados datos.

Como regla general, el procesamiento de video se realiza en la GPU hoy en día. Las GPU están literalmente diseñadas para operar en matrices gigantes. Porque esa es la imagen que estás viendo en este momento: una matriz gigante.

Si tiene que mantenerlo en el lado de la GPU, ¿tal vez el almacenamiento en caché o la iniciación lenta ayudaría? Lo más probable es que realmente no necesite todos los valores. Solo necesitas valores comunes . Tomemos un ejemplo de dicerolling: si lanzas 2 dados de 6 lados, todos los resultados de 2-12 son posibles. Pero el resultado 7 sucede 6 de 36 casess. Los 2 y 12 solo 1 de 36 casos cada uno. Por lo tanto, tener el 7 almacenado es mucho más beneficioso que el 2 y el 12.