हिस्टोग्राम फ़ंक्शन

Question

समांतर करने के लिए मैंने एक साधारण फ़ंक्शन के सामान्य और समानांतर क्रिया को कार्यान्वित किया है जो 32bppArgb बिटमैप से हिस्टोग्राम की गणना करता है। सामान्य संस्करण को 1920x1080 छवि पर लगभग 0.03 सेकंड लगते हैं जबकि समांतर संस्करण 0.07 सेकंड लेता है।

क्या थ्रेडिंग ओवरहेड वास्तव में भारी है? क्या समांतर के अलावा कुछ और निर्माण है। इससे इस प्रक्रिया को तेज कर सकते हैं? मुझे इसे तेज करने की आवश्यकता है क्योंकि मैं 30fps वीडियो के साथ काम कर रहा हूं।

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

खैर, सबसे पहले, आप एक विशाल बग अपने समानांतर पाश में मिल गया है अंतर्निहित दौड़ की स्थिति के कारण कई बार छवियों में जंगली रूप से अलग-अलग परिणाम होते हैं।

लेकिन ऐसा नहीं है जो आपने पूछा था।

समानांतर कार्यान्वयन का उपयोग करके आप प्रदर्शन में कमी क्यों देख रहे हैं, सरल जवाब यह है कि आप शायद नए कार्य को बनाने के "स्पिनअप लागत" को ऑफ़सेट करने के लिए प्रत्येक समांतर कार्य के शरीर में पर्याप्त काम नहीं कर रहे हैं , इसे शेड्यूल करना, आदि

शायद अधिक महत्वपूर्ण यह है कि मेरा मानना ​​है कि आप स्मृति में चारों ओर कूदते हुए एल 1/एल 2 कैश से नरक को फेंक रहे हैं - प्रत्येक कार्य धागा इसे सोचने और लोड करने के लिए जा रहा है कैश मेमोरी में आवश्यकता होगी, लेकिन जैसा कि आप पूरे स्थान पर अनुक्रमणित कर रहे हैं, अब आप लगातार एक्सेस पैटर्न नहीं बना रहे हैं, इसलिए जब भी आप बिटमैप बफर या आंतरिक सरणी तक पहुंचने का प्रयास करेंगे तो आपको कैश मिस मिल जाएगा ।

वहाँ भी है असुरक्षित कोड का उपयोग किए बिना बिटमैप के केवल पढ़ने के लिए डेटा पर होने का एक समान रूप से performant तरीका ... वास्तव में, का पहला ऐसा करते हैं:

तो तुम हो, बुला LockBits, अप्रबंधित स्मृति के सूचक के द्वारा । यह की एक प्रतिलिपि बनाने करते हैं: रेस स्थिति के लिए के रूप में अब

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

, - आप गिनती तक सामने लाना (नोट Interlocked कॉल का उपयोग करके एक उचित performant ढंग से इस पर काबू पाने कर सकते हैं !!! थ्रेड प्रोग्रामिंग है मुश्किल है, और यह पूरी तरह से मेरी समाधान संभव यहाँ नहीं है एकदम सही है!)

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

तो, क्या इस क्रम व्यवहार करने के लिए क्या करता है?

बहुत कुछ नहीं, लेकिन कम से कम समानांतर कांटा अब सही परिणामों की गणना करता है।:)

एक बहुत cheapo परीक्षण रिग का उपयोग करना:

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

आप देख सकते हैं, हम अभी भी अपने मूल प्रश्न को संबोधित नहीं किया है:

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

मैं इस तरह के परिणाम प्राप्त। :)

तो चलो समानांतर काम "अधिक बेहतर" बनाने में एक चाकू डालें:

चलो देखते हैं क्या कार्य करने के लिए "अधिक काम दे रही है" करता है:

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

परिणाम:

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

ओह, यह आशाजनक लग रहा है ... मुझे आश्चर्य है कि क्या होता है क्योंकि हम batchSize बदलते हैं? (, केवल दिखा समानांतर = सच के बाद से गैर समानांतर परिवर्तन नहीं होगा)

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 

हम एक asymptote आ लग रहे:

के हमारे परीक्षण रिग thusly बदल डालते हैं:

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

परिणाम एक बार हम बैच आकार में 64-128 रेंज को क्रिस्ट करते हैं, हालांकि निश्चित रूप से आपका माइलेज आपके बिटमैप आकार आदि के आधार पर भिन्न हो सकता है।

मुझे उम्मीद है कि इससे मदद मिलती है! उत्पादन के इंतजार के इंतजार के अपने दिन से यह एक मजेदार व्याकुलता थी! :)

Answer 2

बनाना धागे काफी महत्वपूर्ण ओवरहेड है:

यहाँ सरलीकृत कोड है। निष्पादन एकल थ्रेडेड संस्करण की तुलना में काफी तेज हो सकता है, लेकिन इस प्रारंभिक ओवरहेड के लिए तैयार करने के लिए बहुत तेज़ हो जाता है।

यदि आप यह हर फ्रेम करते हैं, तो यह आपको धीमा कर देगा।

हालांकि, यदि आप मैन्युअल रूप से थ्रेडपूल बनाते हैं, मैन्युअल रूप से कार्य असाइन करते हैं, और प्रत्येक फ्रेम के लिए धागे का पुन: उपयोग करते हैं, तो आप एक थ्रेड वाले संस्करण के पीछे दो या तीन कोड कोड रॉकेट कर सकते हैं। - सिर्फ एक ही पर अपने नमूना कोड चल

आप एक से अधिक थ्रेड, तक पहुँचने बढ़ाने, और साझा सरणियों को अद्यतन करने के लिए जा रहे हैं: