Parallelizzazione della funzione dell'istogramma

Question

Ho implementato un verion normale e parallelo di una funzione semplice che calcola un istogramma da una bitmap 32bppArgb. La versione normale richiede circa 0,03 secondi su un'immagine 1920x1080 mentre la versione parallela richiede 0,07 secondi.

Il threading in testa è davvero così pesante? C'è qualche altro costrutto oltre a Parallel. Per accelerare questo processo? Ho bisogno di accelerarlo visto che sto lavorando con video a 30fps.

Ecco il codice semplificato:

public sealed class Histogram 
{ 
    public int MaxA = 0; 
    public int MaxR = 0; 
    public int MaxG = 0; 
    public int MaxB = 0; 
    public int MaxT = 0; 

    public int [] A = null; 
    public int [] R = null; 
    public int [] G = null; 
    public int [] B = null; 

    public Histogram() 
    { 
     this.A = new int [256]; 
     this.R = new int [256]; 
     this.G = new int [256]; 
     this.B = new int [256]; 

     this.Initialize(); 
    } 

    public void Initialize() 
    { 
     this.MaxA = 0; 
     this.MaxR = 0; 
     this.MaxG = 0; 
     this.MaxB = 0; 
     this.MaxT = 0; 

     for (int i = 0; i < this.A.Length; i++) 
      this.A [i] = 0; 
     for (int i = 0; i < this.R.Length; i++) 
      this.R [i] = 0; 
     for (int i = 0; i < this.G.Length; i++) 
      this.G [i] = 0; 
     for (int i = 0; i < this.B.Length; i++) 
      this.B [i] = 0; 
    } 

    public void ComputeHistogram (System.Drawing.Bitmap bitmap, bool parallel = false) 
    { 
     System.Drawing.Imaging.BitmapData data = null; 

     data = bitmap.LockBits 
     (
      new System.Drawing.Rectangle(0, 0, bitmap.Width, bitmap.Height), 
      System.Drawing.Imaging.ImageLockMode.ReadOnly, 
      System.Drawing.Imaging.PixelFormat.Format32bppArgb 
     ); 

     try 
     { 
      ComputeHistogram(data, parallel); 
     } 
     catch 
     { 
      bitmap.UnlockBits(data); 

      throw; 
     } 

     bitmap.UnlockBits(data); 
    } 

    public void ComputeHistogram (System.Drawing.Imaging.BitmapData data, bool parallel = false) 
    { 
     int stride = System.Math.Abs(data.Stride); 

     this.Initialize(); 

     if (parallel) 
     { 
      unsafe 
      { 
       System.Threading.Tasks.Parallel.For 
       (
        0, 
        data.Height, 
        new System.Threading.Tasks.ParallelOptions() { MaxDegreeOfParallelism = System.Environment.ProcessorCount }, 
        y => 
        { 
         byte* pointer = ((byte*) data.Scan0) + (stride * y); 

         for (int x = 0; x < stride; x += 4) 
         { 
          this.B [pointer [x + 0]]++; 
          this.G [pointer [x + 1]]++; 
          this.R [pointer [x + 2]]++; 
          this.A [pointer [x + 3]]++; 
         } 
        } 
       ); 
      } 
     } 
     else 
     { 
      unsafe 
      { 
       for (int y = 0; y < data.Height; y++) 
       { 
        byte* pointer = ((byte*) data.Scan0) + (stride * y); 

        for (int x = 0; x < stride; x += 4) 
        { 
         this.B [pointer [x + 0]]++; 
         this.G [pointer [x + 1]]++; 
         this.R [pointer [x + 2]]++; 
         this.A [pointer [x + 3]]++; 
        } 
       } 
      } 
     } 

     for (int i = 0; i < this.A.Length; i++) 
      if (this.MaxA < this.A [i]) this.MaxA = this.A [i]; 
     for (int i = 0; i < this.R.Length; i++) 
      if (this.MaxR < this.R [i]) this.MaxR = this.R [i]; 
     for (int i = 0; i < this.G.Length; i++) 
      if (this.MaxG < this.G [i]) this.MaxG = this.G [i]; 
     for (int i = 0; i < this.B.Length; i++) 
      if (this.MaxB < this.B [i]) this.MaxB = this.B [i]; 

     if (this.MaxT < this.MaxA) this.MaxT = this.MaxA; 
     if (this.MaxT < this.MaxR) this.MaxT = this.MaxR; 
     if (this.MaxT < this.MaxG) this.MaxT = this.MaxG; 
     if (this.MaxT < this.MaxB) this.MaxT = this.MaxB; 
    } 
} 

Answer 1

Beh, prima di tutto, hai un enorme bug nel circuito parallelo:

Stai andando ad avere più thread accesso, incrementando, e aggiornare gli array condiviso - solo in esecuzione il codice di esempio sullo stesso l'immagine più volte produce risultati molto diversi a causa delle condizioni di gara.

Ma non è quello che hai chiesto.

Per quanto riguarda il motivo per cui si nota una diminuzione delle prestazioni utilizzando l'implementazione parallela, la risposta semplice è che probabilmente non si sta facendo abbastanza lavoro nel corpo di ogni attività parallela per compensare il "costo di avviamento" della creazione della nuova attività , programmandolo, ecc.

Probabilmente più critico è che io credo che tu stia sbattendo fuori dalla cache L1/L2 con tutti i salti in giro nella memoria - ogni thread di attività sta andando a provare e caricare ciò che pensa sarà necessario nella memoria cache, ma mentre si sta indicizzando dappertutto, non si sta più creando un modello di accesso coerente, quindi è probabile che si verifichino errori di cache ogni volta che si tenta di accedere al buffer bitmap o agli array interni .

C'è anche un modo altrettanto performante di ottenere i dati di sola lettura della bitmap senza l'utilizzo di codice non sicuro ... in realtà, cerchiamo di farlo prima:

in modo da avere, chiamando LockBits, un puntatore alla memoria non gestita . Facciamo una copia di esso:

System.Drawing.Imaging.BitmapData data = null; 
data = bitmap.LockBits 
(
    new System.Drawing.Rectangle(0, 0, bitmap.Width, bitmap.Height), 
    System.Drawing.Imaging.ImageLockMode.ReadOnly, 
    System.Drawing.Imaging.PixelFormat.Format32bppArgb 
); 

// For later usage 
var imageStride = data.Stride; 
var imageHeight = data.Height; 

// allocate space to hold the data 
byte[] buffer = new byte[data.Stride * data.Height]; 

// Source will be the bitmap scan data 
IntPtr pointer = data.Scan0; 

// the CLR marshalling system knows how to move blocks of bytes around, FAST. 
Marshal.Copy(pointer, buffer, 0, buffer.Length); 

// and now we can unlock this since we don't need it anymore 
bitmap.UnlockBits(data); 

ComputeHistogram(buffer, imageStride, imageHeight, parallel); 

Ora, per quanto riguarda la condizione di competizione - si può superare questo in una maniera ragionevolmente performante utilizzando le Interlocked chiamate per urtare i conteggi (NOTA !!! programmazione multithread è DURO, ed è del tutto possibile la mia soluzione qui non è perfetta!)

public void ComputeHistogram (byte[] data, int stride, int height, bool parallel = false) 
{ 
    this.Initialize(); 

    if (parallel) 
    { 
     System.Threading.Tasks.Parallel.For 
     (
      0, 
      height, 
      new ParallelOptions() { MaxDegreeOfParallelism = Environment.ProcessorCount }, 
      y => 
      { 
       int startIndex = (stride * y); 
       int endIndex = stride * (y+1); 
       for (int x = startIndex; x < endIndex; x += 4) 
       { 
        // Interlocked actions are more-or-less atomic 
        // (caveats abound, but this should work for us) 
        Interlocked.Increment(ref this.B[data[x]]); 
        Interlocked.Increment(ref this.G[data[x+1]]); 
        Interlocked.Increment(ref this.R[data[x+2]]); 
        Interlocked.Increment(ref this.A[data[x+3]]); 
       } 
      } 
     ); 
    } 
    else 
    { 
     // the original way is ok for non-parallel, since only one 
     // thread is mucking around with the data 
    } 

    // Sorry, couldn't help myself, this just looked "cleaner" to me 
    this.MaxA = this.A.Max(); 
    this.MaxR = this.R.Max(); 
    this.MaxG = this.G.Max(); 
    this.MaxB = this.B.Max(); 
    this.MaxT = new[] { this.MaxA, this.MaxB, this.MaxG, this.MaxR }.Max(); 
} 

Così, che cosa fa questo per il comportamento di runtime?

Non molto, ma almeno la forcella parallela calcola i risultati corretti ora.:)

Utilizzando un veramente cheapo banco di prova:

void Main() 
{  
    foreach(var useParallel in new[]{false, true}) 
    { 
     var totalRunTime = TimeSpan.Zero; 
     var sw = new Stopwatch(); 
     var runCount = 10; 
     for(int run=0; run < runCount; run++) 
     { 
      GC.Collect(); 
      GC.WaitForPendingFinalizers(); 
      GC.Collect(); 
      sw.Reset(); 
      sw.Start(); 
      var bmp = Bitmap.FromFile(@"c:\temp\banner.bmp") as Bitmap; 
      var hist = new Histogram(); 
      hist.ComputeHistogram(bmp, useParallel); 
      sw.Stop(); 
      totalRunTime = totalRunTime.Add(sw.Elapsed); 
     } 
     Console.WriteLine("Parallel={0}, Avg={1} ms", useParallel, totalRunTime.TotalMilliseconds/runCount); 
    } 
} 

ottengo risultati come questo:

Parallel=False, Avg=1.69777 ms 
Parallel=True, Avg=5.33584 ms 

Come si può vedere, non abbiamo ancora affrontato tua domanda iniziale. :)

Così diamo una pugnalata a rendere il lavoro in parallelo "più migliore":

Vediamo cosa "dare più lavoro" per i compiti fa:

if (parallel) 
{ 
    var batchSize = 2; 
    System.Threading.Tasks.Parallel.For 
    (
     0, 
     height/batchSize, 
     new ParallelOptions() { MaxDegreeOfParallelism = Environment.ProcessorCount }, 
     y => 
     { 
      int startIndex = (stride * y * batchSize); 
      int endIndex = startIndex + (stride * batchSize); 
      for (int x = startIndex; x < endIndex; x += 4) 
      { 
       // Interlocked actions are more-or-less atomic 
       // (caveats abound, but this should work for us) 
       Interlocked.Increment(ref this.B[data[x]]); 
       Interlocked.Increment(ref this.G[data[x+1]]); 
       Interlocked.Increment(ref this.R[data[x+2]]); 
       Interlocked.Increment(ref this.A[data[x+3]]); 
      } 
     } 
    ); 
} 

Risultati:

Parallel=False, Avg=1.70273 ms 
Parallel=True, Avg=4.82591 ms 

Ooh, sembra promettente ... Mi chiedo che cosa succede quando cambiamo batchSize?

Cambiamo il nostro banco di prova così:

void Main() 
{  
    foreach(var useParallel in new[]{false, true}) 
    { 
     for(int batchSize = 1; batchSize < 1024; batchSize <<= 1) 
     { 
      var totalRunTime = TimeSpan.Zero; 
      var sw = new Stopwatch(); 
      var runCount = 10; 
      for(int run=0; run < runCount; run++) 
      { 
       GC.Collect(); 
       GC.WaitForPendingFinalizers(); 
       GC.Collect(); 
       sw.Reset(); 
       sw.Start(); 
       var bmp = Bitmap.FromFile(@"c:\temp\banner.bmp") as Bitmap; 
       var hist = new Histogram(); 
       hist.ComputeHistogram(bmp, useParallel, batchSize); 
       sw.Stop(); 
       totalRunTime = totalRunTime.Add(sw.Elapsed); 
      } 
      Console.WriteLine("Parallel={0}, BatchSize={1} Avg={2} ms", useParallel, batchSize, totalRunTime.TotalMilliseconds/runCount); 
     }   
    } 
} 

Risultati: (solo mostrando in parallelo = true, dal momento che non parallele non cambierà)

Parallel=True, BatchSize=1 Avg=5.57644 ms 
Parallel=True, BatchSize=2 Avg=5.49982 ms 
Parallel=True, BatchSize=4 Avg=5.20434 ms 
Parallel=True, BatchSize=8 Avg=5.1721 ms 
Parallel=True, BatchSize=16 Avg=5.00405 ms 
Parallel=True, BatchSize=32 Avg=4.44973 ms 
Parallel=True, BatchSize=64 Avg=2.28332 ms 
Parallel=True, BatchSize=128 Avg=1.39957 ms 
Parallel=True, BatchSize=256 Avg=1.29156 ms 
Parallel=True, BatchSize=512 Avg=1.28656 ms 

ci sembra di essere avvicinando un asintoto di specie una volta crestiamo la gamma 64-128 in dimensione batch, anche se ovviamente il tuo chilometraggio può variare a seconda delle dimensioni della tua bitmap, ecc.

Spero che questo aiuti! È stata una distrazione divertente dal mio giorno di attesa per il completamento delle build di produzione! :)

Answer 2

Creazione di discussioni ha un bel notevole sovraccarico. L'esecuzione potrebbe essere molto più veloce rispetto alla versione a thread singolo, ma completata troppo velocemente per compensare questo sovraccarico iniziale.

Se lo fai ogni fotogramma, ti rallenterà.

Tuttavia, se si crea manualmente un pool di thread, si assegna manualmente il lavoro e si riutilizzano i thread per ciascun frame, è possibile che per il frame due o tre il codice passi oltre la singola versione con thread.