У меня есть 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, чтобы быть прав.
Лучше всего просто просто перебрать все значения.
Я предполагаю, что у вас есть три основных варианта:
Я не знаю, насколько хороша производительность добавления байтов с использованием 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 наносекунд на итерацию, поэтому оно не стоит, когда вам нужно делать преобразования самостоятельно.
Это не может быть самым быстрым или наиболее эффективным решением для работы с памятью, но это один лайнер:
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);
}
Я думаю, что теоретически ваш путь самым быстрым способом, на практике вы могли бы использовать более крупные сравнения, как это было предложено одним из комментаторов (1 байтовое сравнение принимает 1 инструкцию, но так же 8-байтное сравнение на 64-битная система).
Также на языках, близких к аппаратным средствам (C и вариантам), вы можете использовать нечто, называемое векторизацией, в котором вы могли бы одновременно выполнять ряд сравнений/дополнений. Похоже, что у Java по-прежнему нет встроенной поддержки, но на основе этого ответа вы могли бы использовать ее.
Также в соответствии с другими комментариями я бы сказал, что с 4-килобайтным буфером, вероятно, не стоит тратить время на его оптимизацию (если только это не вызвано очень часто)
Кто-то предложил проверить 4 или 8 байтов за раз. Вы действительно можете сделать это в Java:
LongBuffer longBuffer = ByteBuffer.wrap(b).asLongBuffer();
while (longBuffer.hasRemaining()) {
if (longBuffer.get() != 0) {
return false;
}
}
return true;
Является ли это быстрее, чем проверка байтовых значений, является неопределенным, так как существует большой потенциал для оптимизации.