¿Se puede optimizar este código?

Question

Tengo un código de procesamiento de imágenes que recorre 2 matrices de bytes multidimensionales (del mismo tamaño). Toma un valor de la matriz fuente, realiza un cálculo en ella y luego almacena el resultado en otra matriz.

int xSize = ResultImageData.GetLength(0); 
int ySize = ResultImageData.GetLength(1); 

for (int x = 0; x < xSize; x++) 
{     
    for (int y = 0; y < ySize; y++) 
    {             
     ResultImageData[x, y] = (byte)((CurrentImageData[x, y] * AlphaValue) + 
            (AlphaImageData[x, y] * OneMinusAlphaValue)); 
    } 
} 

El bucle actualmente toma ~ 11 ms, que supongo se debe principalmente a acceder a los valores de las matrices de bytes como el cálculo es bastante simple (2 multiplicaciones y 1 Además).

¿Hay algo que pueda hacer para acelerar esto? Es una parte crítica del tiempo de mi programa y este código se llama 80-100 veces por segundo, por lo que cualquier ganancia de velocidad, aunque pequeña, hará la diferencia. También en el momento xSize = 768 y ySize = 576, pero esto aumentará en el futuro.

Actualización: Gracias a Guffa (ver respuesta a continuación), el siguiente código me ahorra 4-5ms por ciclo. Aunque es inseguro código.

int size = ResultImageData.Length; 
int counter = 0; 
unsafe 
{ 
    fixed (byte* r = ResultImageData, c = CurrentImageData, a = AlphaImageData) 
    { 
     while (size > 0) 
     { 
      *(r + counter) = (byte)(*(c + counter) * AlphaValue + 
            *(a + counter) * OneMinusAlphaValue); 
      counter++; 
      size--; 
     } 
    } 
} 

Answer 1

Para llegar cualquier aceleración real para este código necesitaría usar punteros para acceder a las matrices, que elimina todos los cálculos de índice y la verificación de límites.

int size = ResultImageData.Length; 
unsafe 
{ 
    fixed(byte* rp = ResultImageData, cp = CurrentImageData, ap = AlphaImageData) 
    { 
     byte* r = rp; 
     byte* c = cp; 
     byte* a = ap; 
     while (size > 0) 
     { 
     *r = (byte)(*c * AlphaValue + *a * OneMinusAlphaValue); 
     r++; 
     c++; 
     a++; 
     size--; 
     } 
    } 
} 

Editar:
variables fijas no se pueden cambiar, por lo que añade código para copiar los punteros a los nuevos punteros que se pueden cambiar.

Answer 2

Si está utilizando LockBits para llegar a la memoria de imagen, que debe recorrer y en el bucle externo y x en el bucle interno ya que es la forma en que se almacena en la memoria (por fila, no la columna) . Yo diría que 11ms es bastante rápido ...

Answer 3

¿Los datos de la imagen deben almacenarse en una matriz multidimensional (rectangular)? Si utiliza matrices dentadas, es posible que el JIT tenga más optimizaciones disponibles (incluida la eliminación de la comprobación de límites).

Answer 4

Una opción sería usar código inseguro: arreglar la matriz en la memoria y usar las operaciones del puntero. Sin embargo, dudo que el aumento de velocidad sea tan dramático.

Una nota: ¿cómo estás cronometrando? Si está utilizando DateTime, tenga en cuenta que esta clase tiene una resolución deficiente. Debería agregar un bucle externo y repetir la operación, por ejemplo, diez veces. Apuesto a que el resultado es menos de 110 ms.

for (int outer = 0; outer < 10; ++outer) 
{ 
    for (int x = 0; x < xSize; x++) 
    {     
     for (int y = 0; y < ySize; y++) 
     {             
       ResultImageData[x, y] = (byte)((CurrentImageData[x, y] * AlphaValue) + 
              (AlphaImageData[x, y] * OneMinusAlphaValue)); 
     } 
    } 
} 

Answer 5

Puesto que aparece que cada celda de la matriz se calcula enteramente independiente de los otros. Es posible que desee considerar tener más de un hilo manejar esto. Para evitar el costo de crear subprocesos, puede tener un grupo de subprocesos.

Si la matriz es de tamaño suficiente, podría ser una ganancia de velocidad muy buena. Por otro lado, si es demasiado pequeño, puede que no ayude (incluso duele). Vale la pena probarlo.

Un ejemplo (pseudo código) podría ser así:

void process(int x, int y) { 
    ResultImageData[x, y] = (byte)((CurrentImageData[x, y] * AlphaValue) + 
     (AlphaImageData[x, y] * OneMinusAlphaValue)); 
} 

ThreadPool pool(3); // 3 threads big 

int xSize = ResultImageData.GetLength(0); 
int ySize = ResultImageData.GetLength(1); 

for (int x = 0; x < xSize; x++) { 
    for (int y = 0; y < ySize; y++) { 
     pool.schedule(x, y); // this will add all tasks to the pool's work queue 
    } 
} 

pool.waitTilFinished(); // wait until all scheduled tasks are complete 

EDIT:Michael Meadows mencionado en un comentario que PLINQ puede ser una alternativa adecuada: http://msdn.microsoft.com/en-us/magazine/cc163329.aspx

Answer 6

Estos son todos los cálculos independientes por lo si tienes una CPU multinúcleo, deberías poder obtener algún beneficio paralelizando el cálculo. Tenga en cuenta que debe mantener los hilos a su alrededor y simplemente entregarles el trabajo, ya que la sobrecarga de la creación del hilo probablemente haría esto más lento en lugar de más rápido si los hilos se vuelven a crear cada vez.

La otra cosa que puede funcionar es cultivar el trabajo en el procesador de gráficos.Consulte this question para obtener algunas ideas, por ejemplo, usando Accelerator.

Answer 7

Recomendaría ejecutar algunas pruebas vacías para descubrir cuáles son tus límites teóricos. Por ejemplo, saque el cálculo del interior del ciclo y vea cuánto tiempo se guarda. Intente reemplazar el bucle doble con un solo bucle que se ejecute la misma cantidad de veces y vea cuánto tiempo ahorra. Entonces puede estar seguro de que está yendo por el camino correcto para la optimización (las dos rutas que veo son aplanar el doble bucle en un solo bucle y trabajar con la multiplicación [tal vez usar una tabla de búsqueda sería más rápido]).

Answer 8

Sólo muy rápido, puede obtener una optimización de bucle en sentido inverso y comparando contra 0. La mayoría de las CPU tienen una op rápida para la comparación a 0.

P. ej

int xSize = ResultImageData.GetLength(0) -1; 
int ySize = ResultImageData.GetLength(1) -1; //minor optimization suggested by commenter 

for (int x = xSize; x >= 0; --x) 
{     
    for (int y = ySize; y >=0; --y) 
    {             
      ResultImageData[x, y] = (byte)((CurrentImageData[x, y] * AlphaValue) + 
             (AlphaImageData[x, y] * OneMinusAlphaValue)); 
    } 
} 

Ver http://dotnetperls.com/Content/Decrement-Optimization.aspx

Answer 9

Si CurrentImageData y/o AlphaImageData no cambian cada vez que se ejecuta el fragmento de código, podría almacenar el producto antes de ejecutar el fragmento de código que muestra y evitar que la multiplicación en su bucles.

Editar: Otra cosa en la que he pensado: a veces las operaciones int son más rápidas que las operaciones de byte. Compense esto con la utilización de la memoria caché del procesador (aumentará considerablemente el tamaño de los datos y correrá un mayor riesgo de que falte la memoria caché).

Answer 10

Probablemente sufras de Boundschecking. Como dice Jon Skeet, una matriz dentada en lugar de una multidimensional (que es data[][] en lugar de data[,]) será más rápida, aunque parezca extraña.

El compilador optimizará

for (int i = 0; i < data.Length; i++) 

al eliminar la prueba de alcance por elemento. Pero es un tipo de caso especial, no hará lo mismo para Getlength().

Por la misma razón, el almacenamiento en caché o izar la propiedad Length (poniéndolo en una variable como xsize) también solía ser una mala cosa sin embargo no he podido comprobar que con Framework 3.5

Answer 11

442,368 adiciones y 884,736 multiplicaciones para el cálculo, creo que 11ms es realmente extremadamente lento en una CPU moderna.

mientras que no sé mucho sobre los detalles de .net sé que el cálculo de alta velocidad no es su punto fuerte. En el pasado, he creado aplicaciones Java con problemas similares, siempre he usado bibliotecas C para hacer el procesamiento de imagen/audio.

Desde una perspectiva de hardware, usted quiere asegurarse de que los accesos a la memoria sean secuenciales, es decir, pasar por el búfer en el orden en que existe en la memoria. también es posible que deba reordenar esto para que el compilador aproveche las instrucciones disponibles, como SIMD. Cómo abordar esto terminará dependiendo de tu compilador y no puedo ayudarte en vs.net.

en un DSP incorporado i estallaría

(AlphaImageData [x, y] * OneMinusAlphaValue) y (CurrentImageData [x, y] * AlphaValue) y el uso de instrucciones SIMD para calcular tampones, posiblemente en paralelo antes de realizar la adicion. quizás haciendo trozos lo suficientemente pequeños para mantener los búferes en el caché de la CPU.

Creo que cualquier cosa que haga requerirá más acceso directo a la memoria/CPU de lo que permite .net.

Answer 12

Es posible que también desee echar un vistazo al tiempo de ejecución Mono y sus extensiones Simd. Tal vez algunos de sus cálculos pueden hacer uso de la aceleración SSE ya que deduzco que básicamente hace cálculos vectoriales (no sé hasta qué tamaño de vector hay aceleración para la multiplicación pero hay algunos tamaños)

(Blog después de anunciar Mono.Simd: http://tirania.org/blog/archive/2008/Nov-03.html)

Por supuesto, eso no funcionaría en Microsoft .NET pero tal vez le interese experimentar.

Answer 13

Curiosamente, los datos de imagen suelen ser muy similares, lo que significa que los cálculos son muy repetitivos. ¿Has explorado haciendo una tabla de búsqueda para los cálculos? Entonces, cualquier tiempo 0.8 fue multiplicado por 128 - valor [80,128] que has precalculado a 102.4, ¿simplemente lo buscaste? Básicamente estás intercambiando espacio de memoria para la velocidad de la CPU, pero podría funcionar para ti.

Por supuesto, si los datos de su imagen tienen una resolución demasiado alta (y van a un dígito demasiado significativo), esto puede no ser práctico.

Answer 14

Intente intercambiar los bucles xey por un patrón de acceso a memoria más lineal y (por lo tanto) menos errores de caché, como ese.

int xSize = ResultImageData.GetLength(0); 
int ySize = ResultImageData.GetLength(1); 

for (int y = 0; y < ySize; y++) 
{ 
    for (int x = 0; x < xSize; x++) 
    { 
     ResultImageData[x, y] = (byte)((CurrentImageData[x, y] * AlphaValue) + 
      (AlphaImageData[x, y] * OneMinusAlphaValue)); 
    } 
}