最快的方法来检查一个字节数组是否全为零

我有一个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:

  1. 或所有元素,并检查总和。
  2. 做无比的比较。
  3. 做一个分支比较。

我不知道使用Java(低级性能)添加字节的性能有多好,我知道如果给出分支比较,Java使用(低级别)分支预测器。

所以我期待以下事情发生:

 byte[] array = new byte[4096]; for (byte b : array) { if (b != 0) { return false; } } 
  1. 当分支预测器仍在播种时,在前几次迭代中比较相对较慢。
  2. 由于分支预测非常快的分支比较,因为每个值都应该是零。

如果它会碰到一个非零值,那么分支预测器将会失败,导致比较速度减慢,但是随着您希望以任何方式返回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; 

这是否比检查字节值更快是不确定的,因为优化的潜力非常大。