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

Question

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

Answer 1

我已经重写了这个答案,因为我是第一次总结所有字节,但这是不正确的,因为Java已经签名字节,因此我需要或.此外,我已将JVM热备改为现在正确.

你最好的选择就是简单地循环遍历所有值.

我想你有三个主要选择:

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,这将导致一些额外的方法调用(如迭代一个列表),直到代码被内联.

更新

我写了自己的基准测试,给出了一些有趣的结果......不幸的是我无法使用任何现有的基准测试工具,因为它们很难正确安装.

我还决定将选项1和2组合在一起,因为我认为它们实际上与您通常的无分支或一切(减去条件)相同,然后检查最终结果.这里的条件是x > 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/iterations:700000 /每次迭代的时间:50.18817142857143ns
基准:byteArrayCheck3 /迭代:700000 /每次迭代的时间:767.7371985714286ns
基准:byteArrayCheck4 /迭代:700000 /每次迭代的时间:21145.03219857143ns
基准:byteArrayCheck5/iterations:700000 /每次迭代的时间:10376.119144285714ns

这表明orring比分支预测器快很多,这是相当令人惊讶的,所以我假设正在进行一些低级优化.

作为额外的我已经包括了流变体,我无论如何都不希望它快.

搭载备有时钟的英特尔i7-3770,16GB 1600MHz内存.

所以我认为最终的答案是:这取决于.这取决于您要连续检查阵列的次数."byteArrayCheck3"解决方案始终稳定在700~800ns.

跟进更新

事情实际上采取了另一种有趣的方法,事实证明JIT几乎所有计算都在优化,因为根本没有使用结果变量.

因此,我有以下新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");
}

这确保了基准测试的结果无法被优化掉,因此主要问题是该byteArrayCheck12方法是无效的,因为它注意到(sum == 0)没有使用,因此它优化了整个方法.

因此,我们有以下新结果(为清晰起见省略了结果打印):

基准:byteArrayCheck12/iterations:700000 /每次迭代的时间:1370.6987942857143ns
基准:byteArrayCheck3 /迭代:700000 /每次迭代的时间:736.1096242857143ns
基准:byteArrayCheck4 /迭代:700000 /每次迭代的时间:20671.230327142857ns
基准:byteArrayCheck5/iterations: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/iterations:700000 /每次迭代的时间:21655.950115714284ns
基准:byteArrayCheck5/iterations:700000 /每次迭代的时间:10608.70917857143ns

我想我们终于可以得出结论,最快的方法是使用早期返回和分支预测,然后是orring,然后是纯粹的分支预测.我怀疑所有这些操作都在本机代码中进行了高度优化.

使用long和int数组更新,一些额外的基准测试.

在看到使用建议后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[]分别之前的基准,也有人neccessary到最大堆大小设置为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/iterations:700000 /每次迭代的时间:259.8157614285714ns
基准:byteArrayCheck9/iterations:700000 /每次迭代的时间:266.38013714285717ns

如果可能以这种格式获取字节,则可能值得探索此路径.但是,当在基准测试方法中进行转换时,每次迭代的时间大约为2000纳秒,因此当您需要自己进行转换时,这是不值得的.

Answer 2

这可能不是最快或最大的内存性能解决方案,但它是一个单线程:

byte[] arr = randomByteArray();
assert Arrays.equals(arr, new byte[arr.length]);