我有一个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
检查字节数组是否全为零的最快方法
44
- PureGero
18
5个回答
74
我已经重新编写了这个答案，因为我最初是将所有字节相加，但这是不正确的，因为Java具有有符号字节，因此我需要进行或运算。另外，我现在已经更正了JVM预热的问题。
你最好的选择就是简单地循环遍历所有值。
我想你有三个主要选项可供选择：
- 对所有元素进行或运算并检查总和。
- 执行无分支比较。
- 使用分支进行比较。
我不知道使用Java添加字节的性能有多好（低级性能），但我知道如果你使用分支比较，Java会使用（低级）分支预测器。
因此，我期望以下情况发生：
byte[] array = new byte[4096];
for (byte b : array) {
if (b != 0) {
return false;
}
}
- 在分支预测器仍在初始化时的前几次迭代中比较缓慢。
- 由于分支预测，分支比较非常快，因为每个值都应该是零。
如果它命中了一个非零值，那么分支预测器就会失败，导致比较变慢，但是无论如何你都已经到达了计算的结尾，因为你想要返回false。我认为一个失败的分支预测的成本比继续迭代数组的成本小一个数量级。
此外，我认为for (byte b : array)应该被允许，因为根据我所知，没有PrimitiveArrayIterator这样的东西，它会导致一些额外的方法调用（就像迭代列表一样），直到代码被内联。
更新
我编写了自己的基准测试，得出了一些有趣的结果......不幸的是，我不能使用任何现有的基准测试工具，因为它们很难正确安装。
我还决定将选项1和2分组在一起，因为我认为它们实际上与无分支相同，因为你通常会对所有内容进行或运算（减去条件），然后检查最终结果。这里的条件是x > 0，因此零的或运算是一个无操作。
代码：
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();
}
}
意外的结果：
这表明orring比分支预测器快得多，这真是令人惊讶，因此我认为进行了一些低级别的优化。基准测试：byteArrayCheck12 / 迭代次数：700000 / 每次迭代时间：50.18817142857143ns
基准测试：byteArrayCheck3 / 迭代次数：700000 / 每次迭代时间：767.7371985714286ns
基准测试：byteArrayCheck4 / 迭代次数：700000 / 每次迭代时间：21145.03219857143ns
基准测试：byteArrayCheck5 / 迭代次数：700000 / 每次迭代时间：10376.119144285714ns
另外，我还包括了流变量的变体，但我并不指望它们会如此快速。
在一个库存时钟的Intel i7-3770上运行，16GB 1600MHz RAM。
所以我想最终的答案是：这取决于你连续检查数组的次数。 “byteArrayCheck3”解决方案始终稳定在700〜800ns左右。
随后更新：
事实上，情况采取了另一种有趣的方法，结果JIT由于根本没有使用结果变量而将几乎所有计算都进行了优化。
因此，我有以下新的“基准”方法：
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");
}
这样可以确保基准测试结果不会被优化掉，主要问题在于
byteArrayCheck12方法是void类型的，因为它注意到(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
我认为我们最终可以得出结论，最快的方法是同时使用早期返回和分支预测，其次是或运算，其次是纯粹的分支预测。我怀疑所有这些操作都在本地代码中高度优化。
更新，一些额外的基准测试使用长整型数组和整型数组。
在看到使用long[]和int[]的建议后，我决定值得研究。然而，这些尝试可能不再完全符合原始答案，但仍然可能很有趣。
首先，我将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");
}
在进行基准测试之前，我需要将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
如果可以以这种格式获取字节，则可能值得探索此路径。但是，当在基准测试方法内进行转换时，每次迭代的时间约为2000纳秒，因此当您需要自己进行转换时，这并不值得。
- skiwi
31
2数学运算实际上只是重载为操作
int和long值;任何其他类型都会提升为int，因此byte加法与int加法一样快。而且您是正确的，for-each循环将被编译为常规循环。 - awksp3另外，对于添加代码的可能优化：也许可以将字节进行“或”运算？因为现在，正负字节可能会导致误报。而且“或”可能比加法更快... - awksp
XOR 是
^。你正在使用常规的按位 OR（正如应该的那样，因为 XOR 会产生误报）。值得注意的是，基于 OR 的解决方案如果早期出现非零元素，则不会提前退出，这可能会对其表现出的速度优势造成重大影响。混合方法可能值得考虑，其中你将字节进行 OR 运算并每隔一百次迭代检查一次值。 - user23571128你知道，如果我可以多次投票，我会花上一个小时或更长时间来投票。你在这个问题上花费的努力是疯狂的，仅仅投票不能展示我 (也许其他读者) 对你的努力表示的欣赏。关于结果，现在反转的结果是相当有趣的——看起来JIT编译器真的知道如何做它的事情。我想分支预测器毕竟是某种黑魔法。同时有趣的是，即使整个数组都被循环遍历，额外的 OR指令也会减慢评估速度。 - awksp
1@user3580294 你可以为一个特别有价值的回答提供赏金。 - 200_success
显示剩余26条评论
11
这可能不是最快或最节省内存的解决方案，但它是一行代码：
byte[] arr = randomByteArray();
assert Arrays.equals(arr, new byte[arr.length]);
- Mallox
2
事实上，这可能是最快的解决方案，因为您可以缓存用于比较的全零数组，因此您无需在每次调用时创建它。不幸的是，目前的JVMs（JDK 8 r111）没有将
Arrays.equals实现为内置函数。我对简单的“循环和if检查”版本进行了约0.7个周期/元素的时间测量，而对于Arrays.equals版本则是1.1个周期/迭代。两者都非常快-这意味着在没有某种类型的矢量化的情况下，循环版本平均每个周期约有~1.5个加载，非常接近理论最大值2。 - BeeOnRope事实上，在JDK8中，似乎只有
Arrays.equals(char[], char[])是内置的 [http://hg.openjdk.java.net/jdk8/jdk8/hotspot/file/87ee5ee27509/src/share/vm/classfile/vmSymbols.hpp]，但在JDK9中，`byte`和`char`版本都是内置的 [http://hg.openjdk.java.net/jdk9/jdk9/hotspot/file/tip/src/share/vm/classfile/vmSymbols.hpp#l905]。 - BeeOnRope3
对于Java 8，您可以简单地使用以下代码：
public static boolean isEmpty(final byte[] data){
return IntStream.range(0, data.length).parallel().allMatch(i -> data[i] == 0);
}
- Chalk
0
有人建议一次检查4或8个字节。实际上，您可以在Java中执行此操作：
LongBuffer longBuffer = ByteBuffer.wrap(b).asLongBuffer();
while (longBuffer.hasRemaining()) {
if (longBuffer.get() != 0) {
return false;
}
}
return true;
无法确定这是否比检查字节值更快，因为有很多优化的潜力。
- VGR
2
我对此进行了一些基准测试，可以得出结论，它的性能非常高，但无法击败
byteArrayCheck3b的代码。而且ByteBuffer等在JVM中直接映射到机器指令，因此似乎不起作用。不过，我也没有在C或C++中测试过这种类型的代码。 - skiwi此外，使用
IntBuffer 比使用 LongBuffer 更快。 - skiwi0
理论上，你的方法是最快的，但实际上，你可以像其中一位评论者建议的那样利用更大的比较（在64位系统上，1字节比较需要1个指令，但8字节比较也是如此）。
此外，在更接近硬件的语言（如C和其变体）中，你可以使用称为向量化的东西，可以同时执行多个比较/加法。看起来Java仍然没有本地支持它，但根据this answer，你可能会得到一些有用的东西。
另外，与其他评论相一致，我认为对于一个4k缓冲区，尝试优化它可能不值得时间（除非它被频繁调用）。
- Christophe
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
memcmp()函数来比较内存，你可以将其与预先创建的零4k数组进行比较吗？好的，我现在闭嘴！ - Mark Setchellint中，而int最多可以容纳2,147,483,647。 - Mark Setchell