检查字节数组是否仅包含 1 个值的最快方法

Question

好的，现在显然我可以检查一个字节数组是否只包含 1 个值，但我不知道这是否是最快的方法。问题是有时我会得到一个只有 FF (255) 值的字节数组，如果发生这种情况我需要在接下来的代码中忽略它，所以我所做的事情如下：

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

但这是最快的方法吗？我将不得不检查大量数组（尽管所有数组都很小 (350) ）

这是最快的方法还是有更好的方法？

Answer 1

一个相当简单的方法可以使这个速度更快，即获取数组的 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 2

对我来说，这听起来像是一个可并行化的问题。如果你有数百个这样的数组，里面有数百个字节，我会考虑使用 GPU

您可以使用 CUDA "only working on Nvidia cards" 或 OpenCL "working on all cards" 来解决此任务。

对于 c#，有一个名为 cloo 的好库（用于 OpenCL），它易于使用

Answer 3

肯定有更快的方法来优化您正在执行的特定检查。正如一些评论已经指出的那样，真正的问题是它是否真的有必要？是否值得优化查询实际上取决于您必须首先问自己的几个问题。

你的表现标准是什么？

您应该能够每秒处理多少个数组？如果答案是 1000 或更少，那我肯定不会理会试图优化代码。如果答案是数百万个数组其次，那么你可能要考虑做一些表演测试您的代码。
您希望得到什么类型的数据？

如果您处理的 99% 的缓冲区都是有效的（并非所有 0xFF 字节），那么在大多数情况下，您的循环很可能在前几次检查中就已经存在。如果算法仅适用于 1% 的工作负载，那么针对最坏情况优化算法是否有意义。
我改变比较方法会给你的代码带来什么风险，收益是否大于风险？

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% 无效。下面的 table 显示了两种方法的比较：

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

从上面table我们可以看出，虽然不安全 (XOR) 方法速度更快，但如果只有 5% 的检查缓冲区无效，则速度差异微不足道，而如果获得最大的性能提升， a 100% 的缓冲区无效。这让我们回到最初的问题，优化代码真的值得吗？

检查字节数组是否仅包含 1 个值的最快方法

Fastest way to check if a byte array contains only 1 value

c#

performance

bytearray