最快的方式，如果一個字節數組只包含一個價值

Question

奧凱現在很明顯，我可以檢查一個字節數組只包含一個值，但我不知道這是否是做的最快方式。問題是，有時我會得到只有FF（255）值的字節數組，如果這種情況發生，我需要忽略它在隨之而來的代碼，所以我要做的事情如下：

var onlyFF = true; 
foreach(var value in programCode) 
{ 
    if (value != 0xFF) 
    { 
     onlyFF = false; 
     break; 
    } 
} 

但這是最快的方式嗎？我將不得不檢查數組的一個極大數量（所有陣列是相當小的，但（350））

所以這是最快的方法還是有這樣做的更好的方法？

Answer 1

當然有更快的方法來優化您正在執行的特定檢查。一些評論已經表明真正的問題是它是否真的有必要？優化查詢是否值得真的取決於幾個問題，你必須首先問自己。

1. 您的績效標準是什麼？

   您應該能夠處理多少個陣列？如果 答案是1000或更少，那麼我絕對不會打擾 試圖優化代碼。如果答案是數百萬個陣列，那麼您可能需要考慮對代碼進行一些性能測試 。

2. 你期待什麼類型的數據？

   如果處理緩衝區的99％是有效的（不是所有0xFF的字節），那麼你的循環將最有可能在最初的幾個檢查，在大多數情況下存在了。如果它只適用於工作負載的1％，那麼在最壞情況下優化算法是否有意義？

3. 我通過更改比較方法向代碼引入了哪些風險，並且好處是否大於風險？

Adwaenyth提到的常見優化技術可以應用於您的情況。您可以將您的字節數組視爲long數組，然後使用XOR位邏輯運算符一次比較8個字節。爲了有效地使用這種方法而不需要複製緩衝區，你必須使用不安全的代碼。下面的例子顯示了一個快速和骯髒的實施如何可以做到這一點（注意我沒有測試此代碼，所以請不要不正確的測試第一次使用）：

public static bool IsBufferValidUnSafeXOR(byte[] buffer) 
    { 
     bool isValid = false; 

     int byteLength = buffer.Length; 
     int base64Length = byteLength >> 3; // same as -- > (int)(byteLength/8); 
     int remainingBytes = byteLength - (base64Length << 3); 
     ulong toggleMask = 0xFFFFFFFFFFFFFFFF; 

     unsafe 
     { 
      fixed (byte* pByteBuffer = buffer) 
      { 
       ulong* pBuffer = (ulong*)pByteBuffer; 
       int index = 0; 

       while (index < base64Length) 
       { 
        if ((pBuffer[index]^toggleMask) > 0) 
        { 
         isValid = true; 
         break; 
        } 

        index++; 
       } 

      } 
     } 

     // Check remainder of byte array 
     if (!isValid) 
     { 
      int index = (base64Length << 3); 

      while(index < byteLength) 
      { 
       if (buffer[index] != 0xFF) 
       { 
        isValid = true; 
        break; 
       } 

       index++; 
      } 

     } 

     return isValid; 
    } 

我跑了幾個性能比較您當前的非優化方法和優化方法。我在循環中執行每個方法，檢查150萬個緩衝區的有效性。對於第一次測試，只有5％的緩衝區檢查無效。第二次檢查33％的緩衝區對於第三個50％和第四個100％是無效的。 下表顯示了兩種方法如何進行比較：

--------------------------------------------------------------------------------------------- 
| Nr | Total Nr.  | Valid Buffer | Invalid Buffer | Std Method | XOR Unsafe | 
| | Buffers Checked | Count   | Count    | Execution Time| Execution Time| 
--------------------------------------------------------------------------------------------- 
| 1 | 1,500,00   | 1,425,000  | 75,000   | 183 ms  | 124 ms  | 
--------------------------------------------------------------------------------------------- 
| 2 | 1,500,00   | 1,000,000  | 500,000   | 566 ms  | 226 ms  | 
--------------------------------------------------------------------------------------------- 
| 3 | 1,500,00   | 750,000  | 750,000   | 800 ms  | 259 ms  | 
--------------------------------------------------------------------------------------------- 
| 4 | 1,500,00   | 0    | 1,500,000   | 1574 ms  | 431 ms  | 
--------------------------------------------------------------------------------------------- 

從上表可以看出，同時不安全（XOR）方法更快的速度差不顯着，如果只有5％的緩衝劑的檢查是無效的，而如果100％的緩衝區無效，則獲得最大的性能改善。這使我們回到原來的問題是真正值得優化代碼嗎？

Answer 2

使其更快的一種相當簡單的方法是獲取陣列的ulong*，並且每次比較8個字節的塊和0xFFFFFFFFFFFFFFFFUL。您可能需要通過比較字節方式來處理陣列開始和結束時的錯位。

然後，您可以展開循環，也許4倍，以減少循環開銷幾乎沒有。這會很難（但可能）做得更快。

另一個相當容易的選擇是C和PInvoke的寫這個。 C編譯器具有快速實現這一功能的複雜方法。 .NET JIT不。雖然我很驚訝，neither GCC nor LLVM do any particular tricks here。

不同的代碼模式播放LLVM提供了以下優化：

if (array[i + 0] & array[i + 1] & array[i + 2] & array[i + 3] == 0xFF) 
return true; 

這節省了大量的指令和分支指令。

Answer 3

對我來說，這聽起來像一個可並行化的問題。 如果你有數百個這樣的陣列，裏面有數百個字節，我會考慮使用GPU

你可以使用CUDA「只在Nvidia卡上工作」或OpenCL「在所有卡上工作」來解決這個任務。

爲C＃有一個很好的LIB（針對OpenCL）呼籲cloo這是很容易使用