Direccionamiento de matriz más rápido

Question

Estoy ejecutando un código de análisis de imagen en una matriz que almacena información sobre la imagen. Desafortunadamente, el código es muy pesado y toma un promedio de 25 segundos para ejecutarse a través de un solo cuadro. El principal problema que veo es el direccionamiento de la matriz. El cual es el más rápido de ejecutar a través de una matriz 2D y están allí en todo cualquier diferencia en

horizontal y luego vertical,

for (int y = 0; y < array.Length; ++y) 
    for (int x = 0; x < array[].Length; ++x) 
     //Code using array[y][x] 

y vertical luego Horrizontal?

for (int x = 0; x < array[].Length; ++x) 
    for (int y = 0; y < array.Length; ++y) 
     //Code using array[y][x] 

Por otra parte, he tratado de evitar el direccionamiento y el uso de punteros directos en su lugar.

for (int y = 0; y < array.Length; ++y) 
    int* ptrArray = (int*)array[0]; 
    for (int x = 0; x < array[].Length; ++x, ++ptrArray) 
     //Code using ptrArray for array[y][x] 

o

for (int x = 0; x < array[].Length; ++x) 
    int* ptrArray = (int*)array[0]; 
    for (int y = 0; y < array.Length; ++y, ptrArray += array[].Length) 
     //Code using ptrArray for array[y][x] 

Cualquier ayuda es muy apreciada. Max

Answer 1

Una opción es utilizar un bucle inverso (iniciar su for() loop de array.Length a 0)

que va a acelerar las cosas un poco.

por ejemplo,

for (int x = array[].Length-1; x >= 0; --x) 
    int* ptrArray = (int*)array[0]; 
    for (int y = array.Length-1; y >= 0 ; --y, ptrArray += array[].Length) 
     //Code using ptrArray for array[y][x] 

Answer 2

no tengo ni idea, pero ya he llegado con los ejemplos. Por lo tanto, podría ejecutar sus muestras de código en un bucle y perfilarlo usted mismo.

var sw = new Stopwatch(); 
sw.Start(); 
ExecuteMyCode(); 
sw.Stop(); 
Console.WriteLine("Time: " + sw.Elapsed); 

Usted puede ser capaz de acelerar su procesamiento mediante el uso de un multi-threading construir like Parallel.ForEach. Esto funcionaría bien si el código en su bucle evita las dependencias entre iteraciones de bucle.

Answer 3

¿Puede usted inseguro? Puntero. El problema con la matriz es que TODAVÍA tiene las verificaciones de límites en cada acceso. Los punteros eliminan eso. Tenga en cuenta que esto es totalmente compatible con C#, pero debe colocarlo en un bloque inseguro. También significa que debe poder ejecutar código no seguro, que no siempre es un hecho.

http://msdn.microsoft.com/en-us/library/28k1s2k6.aspx

tiene un ejemplo de código.

Answer 4

Si es posible, intente reasignar su matriz de modo que la primera dimensión sea menor que la segunda. Aceleraría las cosas drásticamente. Otra solución es reasignar los datos en una matriz de dimensión única como se propuso anteriormente.

Answer 5

Siempre asegúrese de que su bucle más interno acceda a la memoria contigua.

Esta suele ser la fila de su imagen. Tenga en cuenta que en arreglos rectangulares, debe hacer que este sea el último índice: array[y,x].

this paper sugiere que las matrices rectangulares C# incorporadas (con los índices múltiples) son bastante lentas. Lo leí antes, pero esta es la única referencia que tengo. Comenzaría con una matriz lineal y calcularía una compensación una vez para cada fila. Unmanaged solo te ayudará en casos realmente triviales.

Si un solo fotograma tarda 25 segundos, entonces es huuuuge o realiza un procesamiento muy complejo. En ese caso, es interesante dedicar esfuerzos a la optimización del acceso a la memoria si accede a muchos píxeles de entrada para cada píxel de salida.

Answer 6

La regla más importante es que es toda la teoría hasta su perfil. No me detengo con los que insisten en que el perfilado es todo (sin una teoría, no eres mejor que un Cultista de carga poniéndose coco en los oídos y esperando que venga el avión), pero tu teoría siempre puede ser incorrecta o incompleta, por lo que perfilar es crucial.

En general, queremos que el escaneo interno sea horizontal (en términos de la matriz, en lugar de la imagen, aunque para la mayoría de los formatos es el mismo). La razón es que con una gran variedad como:

00 01 02 03 04 05 06 07 08 09 
10 11 12 13 14 15 16 17 18 19 
20 21 22 23 24 25 26 27 28 29 

Va a ser expuesto como:

00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 

Usted quiere ser exploración a lo largo bloques contiguos que se pueden cargar en cachés de la CPU y luego utilizados por completo, en lugar de escanear de bloque a bloque y la necesidad de cambiar regularmente el contenido de la caché de la CPU.

Esto es aún más importante si intentas paralelizar el algoritmo. Desea que cada subproceso trate sus propios bloques contiguos de memoria en lo que respecta tanto a la entrada como a la salida, en lugar de no solo sufrir el modo de código de subprocesamiento único con poca frecuencia de acierto de memoria caché, sino también causando que los búferes de cada uno se ensucien y necesita actualizar. Esta puede ser la diferencia entre el paralelismo que lleva a un aumento de la velocidad y la paralelización realmente ralentizando las cosas.

Otra cosa es la diferencia entre una matriz bidimensional byte[,] en lugar de una matriz de matrices byte[][], cuyo comentario en su pregunta "matriz [y] [x]" me hace preguntar si quizás esté utilizando. Con el primero para obtener arr [1,2] La lógica es:

1. revisar los límites
2. calcular la posición (simple aritmética rápido)
3. recuperar el valor.

Con este último, la lógica es:

1. revisar los límites
2. obtener matriz a través del puntero.
3. Verificar límites
4. Recuperar valor.

También hay menos memoria caché-hit-frecuencia. Este último tiene beneficios cuando se necesitan estructuras "dentadas", pero ese no es el caso aquí. 2D es casi siempre más rápido que una matriz de matrices.

Cosas que no me ven como probable que ayude, pero ciertamente ellos tratarían en su situación:

Usted puede encontrar un impulso de hacer su < => lógica 2d 1d. Tener una matriz de una dimensión donde idx = y * ancho + x. No debería hacer una diferencia apreciable, pero vale la pena intentarlo.

Las optimizaciones intentan tanto llamar al .Length como omitir la verificación innecesaria de los límites, por lo que puede encontrar el izado manual y el cambio a la aritmética del puntero no gana nada, pero en caso de que realmente necesite bajar el tiempo Sin duda vale la pena perfilar.

Finalmente. ¿Ha perfilado qué tan rápido es su código para escanear la matriz y no hacer nada? Podría ser que otra parte del código sea el verdadero cuello de botella, y estás arreglando lo incorrecto.