Самый быстрый способ проверить, является ли массив байтов всеми нулями

У меня есть 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

Ответы

Ответ 1

Я переписал этот ответ, поскольку я сначала суммировал все байты, это, однако, неверно, поскольку 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, и, следовательно, a или нуль предположительно является 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

Это показывает, что оправа целая серия быстрее, чем предсказатель ветвления, что довольно удивительно, поэтому я предполагаю, что выполняется небольшая оптимизация.

В качестве дополнительных я включил варианты потока, которые я не ожидал, что так быстро.

Отладка на тактовой частоте Intel i7-3770, 16 ГБ с частотой 1600 МГц.

Итак, я думаю, что окончательный ответ: это зависит. Это зависит от того, сколько раз вы будете последовательно проверять массив. Решение "byteArrayCheck3" всегда находится на уровне 700 ~ 800 нс.

Последующее обновление

Вещи действительно занимают еще один интересный подход, оказывается, что 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
Benchmark: byteArrayCheck5/итерации: 700000/время на итерацию: 10608.70917857143ns

Я думаю, мы можем, наконец, заключить, что самым быстрым способом является использование как раннего возвращения, так и предсказания ветвлений, за которым следует орринга, а затем чисто предсказание ветвления. Я подозреваю, что все эти операции сильно оптимизированы в собственном коде.

Обновить, некоторый дополнительный бенчмаркинг с использованием массивов 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[] соответственно до тестов, также необходимо установить максимальный размер кучи до 10 ГБ.

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 наносекунд на итерацию, поэтому оно не стоит, когда вам нужно делать преобразования самостоятельно.

Ответ 2

Это не может быть самым быстрым или наиболее эффективным решением для работы с памятью, но это один лайнер:

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

Ответ 3

Для Java 8 вы можете просто использовать это:

public static boolean isEmpty(final byte[] data){
    return IntStream.range(0, data.length).parallel().allMatch(i -> data[i] == 0);
}

Ответ 4

Я думаю, что теоретически ваш путь самым быстрым способом, на практике вы могли бы использовать более крупные сравнения, как это было предложено одним из комментаторов (1 байтовое сравнение принимает 1 инструкцию, но так же 8-байтное сравнение на 64-битная система).

Также на языках, близких к аппаратным средствам (C и вариантам), вы можете использовать нечто, называемое векторизацией, в котором вы могли бы одновременно выполнять ряд сравнений/дополнений. Похоже, что у Java по-прежнему нет встроенной поддержки, но на основе этого ответа вы могли бы использовать ее.

Также в соответствии с другими комментариями я бы сказал, что с 4-килобайтным буфером, вероятно, не стоит тратить время на его оптимизацию (если только это не вызвано очень часто)

Ответ 5

Кто-то предложил проверить 4 или 8 байтов за раз. Вы действительно можете сделать это в Java:

LongBuffer longBuffer = ByteBuffer.wrap(b).asLongBuffer();
while (longBuffer.hasRemaining()) {
    if (longBuffer.get() != 0) {
        return false;
    }
}
return true;

Является ли это быстрее, чем проверка байтовых значений, является неопределенным, так как существует большой потенциал для оптимизации.