栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

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

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

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

我先将所有字节加总后就重写了这个答案,但是这是不正确的,因为Java已经对字节进行了签名,因此我需要or。 另外,我已将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
,因此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比分支预测器快很多,这非常令人惊讶,因此我假设正在执行一些底层优化。

另外,我包括了流变种,但我没想到它会这么快。

运行有时钟的Intel i7-3770、16GB 1600MHz RAM。

所以我认为最终答案是:这取决于。这取决于要连续检查阵列的次数。“ 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 /迭代: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数组进行一些其他基准测试。

看到使用建议后

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 /迭代:700000 /每次迭代时间:259.8157614285714ns
基准:byteArrayCheck9 /迭代:700000 /每次迭代时间:266.38013714285717ns

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



转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/404486.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号