java - programacion - curso android desarrollo de aplicaciones móviles pdf

La forma más rápida de verificar si una matriz de bytes es todo ceros

Question

Tengo un byte[4096] y me preguntaba ¿cuál es la forma más rápida de verificar si todos los valores son cero?

¿Hay alguna manera más rápida que hacer?

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

Alguien sugirió verificar 4 u 8 bytes a la vez. Usted puede hacer esto en Java:

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

Si esto es más rápido que verificar los valores de bytes es incierto, ya que hay mucho potencial para la optimización.

Answer 2

Creo que teóricamente su camino de la manera más rápida, en la práctica es posible que pueda hacer uso de comparaciones más grandes según lo sugerido por uno de los comentaristas (la comparación de 1 byte toma 1 instrucción, pero también lo hace una comparación de 8 bytes en un 64- sistema de bits).

También en idiomas más cercanos al hardware (C y variantes) puede hacer uso de algo llamado vectorización donde podría realizar varias comparaciones / adiciones simultáneamente. Parece que Java aún no cuenta con soporte nativo, pero según esta respuesta, es posible que puedas utilizarlo.

También en línea con los otros comentarios diría que con un buffer 4k probablemente no valga la pena el tiempo para tratar de optimizarlo (a menos que se llame con mucha frecuencia)

Answer 3

Esta puede no ser la solución más rápida o con mayor rendimiento de memoria, pero es un trazador de líneas único:

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

Answer 4

Para Java 8, simplemente puede usar esto:

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

Answer 5

He reescrito esta respuesta ya que primero estaba sumando todos los bytes, sin embargo esto es incorrecto ya que Java tiene bytes firmados, por lo tanto, necesito o. También he cambiado el calentamiento de JVM para que sea correcto ahora.

Tu mejor opción es simplemente recorrer todos los valores.

Supongo que tienes tres opciones principales disponibles:

1. O todos los elementos y comprueba la suma.
2. Haga comparaciones sin sucursales.
3. Haga comparaciones con una sucursal.

No sé qué tan bueno es el rendimiento de agregar bytes usando Java (rendimiento de bajo nivel), sé que Java usa predictores de ramas (de bajo nivel) si se ofrecen comparaciones ramificadas.

Por lo tanto, espero que ocurra lo siguiente en:

byte[] array = new byte[4096];
for (byte b : array) {
if (b != 0) {
return false;
}
}

1. Comparación relativamente lenta en las primeras iteraciones cuando el predictor de bifurcación aún se está siembrando.
2. Las comparaciones de ramas muy rápidas debido a la predicción de ramificación, ya que cada valor debe ser cero de todos modos.

Si tocara un valor distinto de cero, entonces el predictor de bifurcación fallaría, lo que provocaría una desaceleración de la comparación, pero también estarás al final de tu cálculo, ya que quieres devolver el valor falso en ambos sentidos. Creo que el costo de una predicción de rama fallida es un orden de magnitud menor que el costo de continuar iterando sobre la matriz.

Además, creo que for (byte b : array) debería permitirse, ya que debería compilarse directamente en la iteración de matrices indexadas ya que, por lo que sé, no existe un PrimitiveArrayIterator que pueda causar algunas llamadas a métodos adicionales (como iterar sobre un lista) hasta que el código se inline.

Actualizar

Escribí mis propios puntos de referencia que dan algunos resultados interesantes ... Desafortunadamente no pude usar ninguna de las herramientas de referencia existentes, ya que son bastante difíciles de instalar correctamente.

También decidí agrupar las opciones 1 y 2, ya que creo que en realidad son las mismas que con las personas sin sucursales, por lo general o de todo (menos la condición) y luego verifico el resultado final. Y la condición aquí es x > 0 y, por lo tanto, a o de cero es presumiblemente un noop.

El código:

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();
}
}

Los resultados sorprendentes:

Punto de referencia: byteArrayCheck12 / iterations: 700000 / tiempo por iteración: 50.18817142857143ns
Punto de referencia: byteArrayCheck3 / iterations: 700000 / tiempo por iteración: 767.7371985714286ns
Punto de referencia: byteArrayCheck4 / iterations: 700000 / tiempo por iteración: 21145.03219857143ns
Punto de referencia: byteArrayCheck5 / iterations: 700000 / tiempo por iteración: 10376.119144285714ns

Esto muestra que orring es mucho más rápido que el predictor de bifurcación, lo que es bastante sorprendente, por lo que supongo que se están realizando algunas optimizaciones de bajo nivel.

Como extra he incluido las variantes de transmisión, que de todos modos no esperaba ser tan rápido.

Corrió en un reloj Intel i7-3770, 16GB 1600MHz de RAM.

Entonces creo que la respuesta final es: depende. Depende de cuántas veces va a verificar la matriz de forma consecutiva. La solución "byteArrayCheck3" siempre está constantemente en 700 ~ 800ns.

Actualización de seguimiento

Las cosas realmente toman otro enfoque interesante, resulta que el JIT estaba optimizando casi todos los cálculos debido a que las variables resultantes no se usan en absoluto.

Por lo tanto, tengo el siguiente nuevo método de 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");
}

Esto asegura que el resultado de los puntos de referencia no puede optimizarse, el principal problema fue que el método byteArrayCheck12 fue nulo, ya que notó que el (sum == 0) no se estaba utilizando, por lo tanto, optimizó todo el método.

Por lo tanto, tenemos el siguiente resultado nuevo (omitimos las impresiones del resultado para mayor claridad):

Punto de referencia: byteArrayCheck12 / iterations: 700000 / tiempo por iteración: 1370.6987942857143ns
Punto de referencia: byteArrayCheck3 / iteraciones: 700000 / tiempo por iteración: 736.1096242857143ns
Punto de referencia: byteArrayCheck4 / iteraciones: 700000 / tiempo por iteración: 20671.230327142857ns
Punto de referencia: byteArrayCheck5 / iterations: 700000 / tiempo por iteración: 9845.388841428572ns

Por lo tanto, creemos que finalmente podemos concluir que la predicción de rama gana. Sin embargo, también podría ocurrir debido a los retornos iniciales, ya que en promedio el byte infractor estará en el medio de la matriz de bytes, por lo tanto, es hora de que otro método no regrese pronto:

private boolean byteArrayCheck3b(final byte[] array) {
int hits = 0;
for (byte b : array) {
if (b != 0) {
hits++;
}
}
return (hits == 0);
}

De esta forma, seguimos beneficiándonos de la predicción de la sucursal; sin embargo, nos aseguramos de que no podamos regresar temprano.

¡Lo que a su vez nos da resultados más interesantes de nuevo!

Punto de referencia: byteArrayCheck12 / iterations: 700000 / tiempo por iteración: 1327.2817714285713ns
Punto de referencia: byteArrayCheck3 / iterations: 700000 / tiempo por iteración: 753.31376ns
Punto de referencia: byteArrayCheck3b / iterations: 700000 / tiempo por iteración: 1506.6772842857142ns
Punto de referencia: byteArrayCheck4 / iterations: 700000 / tiempo por iteración: 21655.950115714284ns
Punto de referencia: byteArrayCheck5 / iterations: 700000 / time per iteration: 10608.70917857143ns

Creo que finalmente podemos concluir que la forma más rápida es usar predicción de retorno temprano y bifurcación, seguido de orring, seguido de predicción puramente de bifurcación. Sospecho que todas esas operaciones están altamente optimizadas en código nativo.

Actualización , algunos benchmarking adicionales usando matrices largas e int.

Después de ver sugerencias sobre el uso de long[] y int[] , decidí que valía la pena investigar. Sin embargo, estos intentos pueden no estar totalmente en línea con las respuestas originales, sin embargo, pueden ser interesantes.

En primer lugar, cambié el método de benchmark para usar genéricos:

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");
}

Luego realicé las conversiones de byte[] a long[] e int[] respectivamente antes de los puntos de referencia, también fue necesario establecer el tamaño máximo de almacenamiento dinámico en 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;
}

Lo cual dio los siguientes resultados:

Punto de referencia: byteArrayCheck8 / iterations: 700000 / tiempo por iteración: 259.8157614285714ns
Punto de referencia: byteArrayCheck9 / iterations: 700000 / tiempo por iteración: 266.38013714285717ns

Vale la pena explorar esta ruta si es posible obtener los bytes en dicho formato. Sin embargo, al realizar las transformaciones dentro del método de evaluación comparativa, los tiempos fueron de alrededor de 2000 nanosegundos por iteración, por lo que no vale la pena cuando debe hacer las conversiones usted mismo.