Indirizzamento di array più veloce

Question

Sto eseguendo un codice di analisi dell'immagine su un array che memorizza informazioni sull'immagine. Sfortunatamente il codice è molto pesante e richiede una media di 25 per essere eseguito su un singolo frame. Il problema principale che vedo è l'indirizzamento dell'array. Che è il più veloce a correre attraverso una matrice 2D e ci sono tutte le eventuali differenze

orizzontale poi verticale

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

e verticale poi horrizontal?

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

Inoltre, ho cercato di evitare l'indirizzamento diretto e utilizzare invece i puntatori.

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] 

Qualsiasi aiuto è molto apprezzato. Max

Answer 1

Una possibilità è quella di utilizzare inverso loop (avviare il for() loop da array.Length fino a 0)

che sarà accelerare le cose un po 'nervosa.

per esempio,

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

ho idea, ma hai già venuta in mente gli esempi. In questo modo è possibile eseguire gli esempi di codice in un ciclo e analizzarli autonomamente.

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

Potreste essere in grado di accelerare il processo utilizzando un multi-threading costruire like Parallel.ForEach. Ciò funzionerebbe bene se il codice nel tuo loop evita le dipendenze tra iterazioni di loop.

Answer 3

Puoi non essere sicuro? Pointer. Il problema con la matrice è che ANCORA hai i controlli di confine su ogni accesso. I puntatori rimuovono quello. Nota che questo è completamente supportato da C#, ma devi metterlo in un blocco non sicuro. Significa anche che devi essere in grado di eseguire codice non sicuro, che non è sempre un dato.

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

ha un esempio di codice.

Answer 4

Se è possibile, provare a riallocare l'array in modo che la prima dimensione sia inferiore alla seconda. Accelererebbe le cose drasticamente. Un'altra soluzione è riallocare i dati in una matrice a dimensione singola come proposto sopra.

Answer 5

Accertarsi sempre che il ciclo più interno acceda alla memoria contigua.

Questa è solitamente la riga dell'immagine. Nota che negli array rettangolari, devi fare in modo che questo sia l'ultimo indice: array[y,x].

this paper suggerisce che gli array C# rettangolari incorporati (con gli indici multipli) sono piuttosto lenti. Ho letto questo prima, ma questo è l'unico riferimento che ho avuto. Vorrei iniziare con un array lineare e calcolare un offset una volta per ogni riga. Unmanaged ti aiuterà solo in casi davvero banali.

Se un singolo fotogramma prende 25 secondi, allora è uno huuuuge, oppure fare l'elaborazione molto complesso. In questo caso è solo interessante spendere sforzi per ottimizzare l'accesso alla memoria se si accede a molti pixel di input per ciascun pixel di uscita.

Answer 6

La regola più importante è che è tutta la teoria fino a che il profilo. Io non tengo a quelli che insistono che l'analisi è tutto (senza qualche teoria non sei meglio di un Cultista merci mettendo noci di cocco sulle loro orecchie e in attesa del piano a venire), ma la sua teoria può essere sempre sbagliata o incompleta, così la profilazione è cruciale.

In genere, vogliamo che la scansione interna sia orizzontale (in termini di matrice, piuttosto che di immagine, sebbene per la maggior parte dei formati sia la stessa). Il motivo è che con una serie come:

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 

Si sta per essere presentata come:

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 

si vuole essere scansione lungo blocchi contigui che possono essere caricati in cache della CPU e poi utilizzati interamente, piuttosto che scansionare da blocco a blocco e dover cambiare regolarmente i contenuti della cache della CPU.

Questo è ancora più importante se si tenta di parallelizzare l'algoritmo. Si desidera che ogni filo trattare con i propri blocchi contigui di memoria per quanto sia all'ingresso che all'uscita va, piuttosto che non solo sofferenza modo singolo codice filettati fa con scarsa cache-hit-frequenza ma anche causando reciproche buffer da sporcate e ho bisogno di essere rinfrescante Questa può essere la differenza tra la parallelizzazione che porta ad un aumento di velocità e la parallelizzazione che effettivamente rallenta le cose.

Un'altra cosa è la differenza tra una matrice a 2 dimensioni byte[,] piuttosto che un array di array byte[][], che il tuo commento in tua domanda "array [y] [x]" mi domando se forse si sta utilizzando. Con l'ex di ottenere arr [1,2] la logica è:

1. Controlla Bounds
2. posizione Calcolare (semplice aritmetica veloce)
3. recuperare il valore.

Con quest'ultimo, la logica è:

1. Vedi limiti
2. ottenere matrice attraverso puntatore.
3. Controlla i limiti
4. recuperare il valore.

C'è anche meno memoria cache-hit-frequence. Quest'ultimo ha benefici quando sono necessarie strutture "frastagliate", ma non è questo il caso. Il 2D è quasi sempre più veloce dell'array di array.

cose che non mi vedono come probabile per aiutare, ma certamente li provare per l'utente:

Si può trovare una spinta da fare il vostro => logica 1d < 2d. Avere un array a dimensione singola dove idx = y * width + x. Non dovrebbe fare una differenza apprezzabile, ma vale la pena provare.

ottimizzazioni provano a entrambe le chiamate di sollevamento per .Length e omettere limiti inutili controllo, in modo da possano trovare sollevamento manuale e il passaggio a l'aritmetica dei puntatori non guadagnare nulla, ma in un caso in cui si ha realmente bisogno di portare il tempo giù vale certamente la profilatura

Infine. Hai profilato la velocità con cui il tuo codice è in fase di scansione della matrice e non fare nulla? Potrebbe essere che un'altra parte del codice sia il vero collo di bottiglia, e tu stai aggiustando la cosa sbagliata.