最快的方法来检查一个字节数组是否全为零
我有一个byte[4096] ，想知道最快的方法是检查所有值是否为零？
有没有办法比做更快：
byte[] b = new byte[4096]; b[4095] = 1; for(int i=0;i<b.length;i++) if(b[i] != 0) return false; // Not Empty
我已经重写了这个答案，因为我是第一次总结所有字节，但这是不正确的，因为Java已签署字节，因此我需要或。 此外，我已经改变了JVM热身，现在是正确的。
你最好的select就是简单地遍历所有的值。
我想你有三个主要的select：
- 或所有元素，并检查总和。
- 做无比的比较。
- 做一个分支比较。
我不知道使用Java（低级性能）添加字节的性能有多好，我知道如果给出分支比较，Java使用（低级别）分支预测器。
所以我期待以下事情发生：
byte[] array = new byte[4096]; for (byte b : array) { if (b != 0) { return false; } }
- 当分支预测器仍在播种时，在前几次迭代中比较相对较慢。
- 由于分支预测非常快的分支比较，因为每个值都应该是零。
如果它会碰到一个非零值，那么分支预测器将会失败，导致比较速度减慢，但是随着您希望以任何方式返回false，您也将处于计算结束时。 我认为，一个失败的分支预测的成本是一个数量级，作为继续迭代数组的成本。
我还认为 ，应该允许for (byte b : array)因为它应该被直接编译到索引数组迭代中，据我所知没有像PrimitiveArrayIterator这样的事情会导致一些额外的方法调用（如迭代列表），直到代码被内联。
更新
我写了自己的基准testing，得出了一些有趣的结果……不幸的是，我不能使用任何现有的基准testing工具，因为它们很难正确安装。
我也决定将选项1和选项2组合在一起，因为我认为它们实际上与通常或全部无网分支（减去条件）相同，然后检查最终结果。 而这里的条件是x > 0 ，因此a或者0是一个noop推测。
代码：
public class Benchmark { private void start() { //setup byte arrays List<byte[]> arrays = createByteArrays(700_000); //warmup and benchmark repeated arrays.forEach(this::byteArrayCheck12); benchmark(arrays, this::byteArrayCheck12, "byteArrayCheck12"); arrays.forEach(this::byteArrayCheck3); benchmark(arrays, this::byteArrayCheck3, "byteArrayCheck3"); arrays.forEach(this::byteArrayCheck4); benchmark(arrays, this::byteArrayCheck4, "byteArrayCheck4"); arrays.forEach(this::byteArrayCheck5); benchmark(arrays, this::byteArrayCheck5, "byteArrayCheck5"); } private void benchmark(final List<byte[]> arrays, final Consumer<byte[]> method, final String name) { long start = System.nanoTime(); arrays.forEach(method); long end = System.nanoTime(); double nanosecondsPerIteration = (end - start) * 1d / arrays.size(); System.out.println("Benchmark: " + name + " / iterations: " + arrays.size() + " / time per iteration: " + nanosecondsPerIteration + "ns"); } private List<byte[]> createByteArrays(final int amount) { Random random = new Random(); List<byte[]> resultList = new ArrayList<>(); for (int i = 0; i < amount; i++) { byte[] byteArray = new byte[4096]; byteArray[random.nextInt(4096)] = 1; resultList.add(byteArray); } return resultList; } private boolean byteArrayCheck12(final byte[] array) { int sum = 0; for (byte b : array) { sum |= b; } return (sum == 0); } private boolean byteArrayCheck3(final byte[] array) { for (byte b : array) { if (b != 0) { return false; } } return true; } private boolean byteArrayCheck4(final byte[] array) { return (IntStream.range(0, array.length).map(i -> array[i]).reduce(0, (a, b) -> a | b) != 0); } private boolean byteArrayCheck5(final byte[] array) { return IntStream.range(0, array.length).map(i -> array[i]).anyMatch(i -> i != 0); } public static void main(String[] args) { new Benchmark().start(); } }
令人惊讶的结果：
基准：byteArrayCheck12 /迭代：每次迭代700000次/次：50.18817142857143ns
基准：byteArrayCheck3 /迭代：每次迭代700000次/次：767.7371985714286ns
基准：byteArrayCheck4 /迭代：每次迭代700000次/次：21145.03219857143ns
基准：byteArrayCheck5 /迭代：每次迭代700000次/次：10376.119144285714ns
这表明orring比分支预测器快很多，这是相当令人惊讶的，所以我假定正在进行一些低级别的优化。
作为额外的我已经包括stream变种，我不希望这么快，无论如何。
跑在一个股票主频英特尔i7-3770,16GB 1600MHz的RAM。
所以我想最后的答案是：这取决于。 这取决于你要连续检查数组的次数。 “byteArrayCheck3”解决scheme始终稳定在700〜800ns。
跟进更新
事情实际上采取了另一种有趣的方法，结果JIT正在优化几乎所有的计算，因为结果variables根本没有被使用。
因此我有以下新的benchmark方法：
private void benchmark(final List<byte[]> arrays, final Predicate<byte[]> method, final String name) { long start = System.nanoTime(); boolean someUnrelatedResult = false; for (byte[] array : arrays) { someUnrelatedResult |= method.test(array); } long end = System.nanoTime(); double nanosecondsPerIteration = (end - start) * 1d / arrays.size(); System.out.println("Result: " + someUnrelatedResult); System.out.println("Benchmark: " + name + " / iterations: " + arrays.size() + " / time per iteration: " + nanosecondsPerIteration + "ns"); }
这确保了基准testing的结果不能被优化掉，所以主要的问题是byteArrayCheck12方法是无效的，因为它注意到(sum == 0)没有被使用，所以它优化了整个方法。
因此，我们有以下新的结果（省略结果打印清晰）：
基准：byteArrayCheck12 /迭代：每次迭代700000次/次：1370.6987942857143ns
基准：byteArrayCheck3 /迭代：每次迭代700000次/次：736.1096242857143ns
基准：byteArrayCheck4 /迭代：每次迭代700000次/次：20671.230327142857ns
基准：byteArrayCheck5 /迭代：每次迭代700000次/次：9845.388841428572ns
因此我们认为我们可以最终得出结论：分支预测获胜。 但也可能因为早期返回而发生，因为平均而言，违规字节将位于字节数组的中间，因此现在是另一种不能及时返回的方法：
private boolean byteArrayCheck3b(final byte[] array) { int hits = 0; for (byte b : array) { if (b != 0) { hits++; } } return (hits == 0); }
这样我们仍然可以从分支预测中受益，但是我们确保我们不能早日返回。
这反过来给我们更有趣的结果！
基准：byteArrayCheck12 /迭代：每次迭代700000次/次：1327.2817714285713ns
基准：byteArrayCheck3 /迭代：每次迭代700000次/次：753.31376ns
基准：byteArrayCheck3b /迭代：每次迭代700000次/次：1506.6772842857142ns
基准：byteArrayCheck4 /迭代：每次迭代700000次/时：21655.950115714284ns
基准：byteArrayCheck5 /迭代：每次迭代700000次/次：10608.70917857143ns
我想我们可以最后得出结论：最快的方法是使用早期收益和分支预测，然后是orring，然后是纯粹的分支预测。 我怀疑所有这些操作都是在本地代码中高度优化的。
更新 ，使用long和int数组进行一些额外的基准testing。
看到使用long[]和int[]build议后，我决定值得研究。 然而，这些尝试可能不完全符合原来的答案，但仍然可能是有趣的。
首先，我改变了使用generics的benchmark方法：
private <T> void benchmark(final List<T> arrays, final Predicate<T> method, final String name) { long start = System.nanoTime(); boolean someUnrelatedResult = false; for (T array : arrays) { someUnrelatedResult |= method.test(array); } long end = System.nanoTime(); double nanosecondsPerIteration = (end - start) * 1d / arrays.size(); System.out.println("Result: " + someUnrelatedResult); System.out.println("Benchmark: " + name + " / iterations: " + arrays.size() + " / time per iteration: " + nanosecondsPerIteration + "ns"); }
然后，我在基准testing之前分别执行了从byte[]到long[]和int[]的转换，还需要将最大堆大小设置为10 GB。
List<long[]> longArrays = arrays.stream().map(byteArray -> { long[] longArray = new long[4096 / 8]; ByteBuffer.wrap(byteArray).asLongBuffer().get(longArray); return longArray; }).collect(Collectors.toList()); longArrays.forEach(this::byteArrayCheck8); benchmark(longArrays, this::byteArrayCheck8, "byteArrayCheck8"); List<int[]> intArrays = arrays.stream().map(byteArray -> { int[] intArray = new int[4096 / 4]; ByteBuffer.wrap(byteArray).asIntBuffer().get(intArray); return intArray; }).collect(Collectors.toList()); intArrays.forEach(this::byteArrayCheck9); benchmark(intArrays, this::byteArrayCheck9, "byteArrayCheck9"); private boolean byteArrayCheck8(final long[] array) { for (long l : array) { if (l != 0) { return false; } } return true; } private boolean byteArrayCheck9(final int[] array) { for (int i : array) { if (i != 0) { return false; } } return true; }
结果如下：
基准：byteArrayCheck8 /迭代：每次迭代700000次/次：259.8157614285714ns
基准：byteArrayCheck9 /迭代：每次迭代700000次/时：266.38013714285717ns
如果可能以这种格式获取字节，这个path可能是值得探索的。 但是，在基准testing方法中进行转换时，每次迭代的时间大约为2000纳秒，所以当您需要自己完成转换时，这是不值得的。
这可能不是最快或最高性能的解决scheme，但它是一个class轮：
byte[] arr = randomByteArray(); assert Arrays.equals(arr, new byte[arr.length]);
对于Java 8，你可以简单地使用这个：
public static boolean isEmpty(final byte[] data){ return IntStream.range(0, data.length).parallel().allMatch(i -> data[i] == 0); }
我认为在理论上你的方法是以最快的方式，实际上你可以利用一个评论者所build议的较大的比较（1字节的比较需要1条指令，但是64位的比较也是如此）位系统）。
在靠近硬件（C和变体）的语言中，也可以使用称为vector化的东西，在这里可以同时执行一些比较/添加。 它看起来像Java仍然没有本地支持，但基于这个答案，你可能会得到一些使用它。
也符合其他意见，我会说，使用4k缓冲区可能不值得花时间去尝试和优化它（除非它经常被调用）
有人build议一次检查4或8个字节。 你实际上可以在Java中做到这一点：
LongBuffer longBuffer = ByteBuffer.wrap(b).asLongBuffer(); while (longBuffer.hasRemaining()) { if (longBuffer.get() != 0) { return false; } } return true;
这是否比检查字节值更快是不确定的，因为优化的潜力非常大。
