Le moyen le plus rapide de vérifier si un tableau d’octets est composé de zéros

J’ai un byte[4096] et je me demandais quel est le moyen le plus rapide de vérifier si toutes les valeurs sont nulles?

Y a-t-il un moyen plus rapide que de faire:

 byte[] b = new byte[4096]; b[4095] = 1; for(int i=0;i<b.length;i++) if(b[i] != 0) return false; // Not Empty 

J’ai réécrit cette réponse car je commençais par faire la sum de tous les octets. Ceci est cependant incorrect car Java a signé des octets, donc je dois ou. J’ai également modifié le préchauffage de la JVM pour qu’il soit correct maintenant.

Votre meilleur pari est de simplement faire une boucle sur toutes les valeurs.

Je suppose que vous avez trois options principales disponibles:

  1. Ou tous les éléments et vérifiez la sum.
  2. Faites des comparaisons sans agence.
  3. Faites des comparaisons avec une twig.

Je ne sais pas si les performances de l’ajout d’octets à l’aide de Java (performances de bas niveau) sont bonnes, je sais que Java utilise des prédicteurs de twig (de bas niveau) si vous effectuez des comparaisons ramifiées.

Par conséquent, je m’attends à ce que les événements suivants se produisent:

 byte[] array = new byte[4096]; for (byte b : array) { if (b != 0) { return false; } } 
  1. Comparaison relativement lente dans les premières itérations lorsque le prédicteur de twig continue à se propager.
  2. Comparaison de twig très rapide due à la prédiction de twig car chaque valeur doit être nulle de toute façon.

S’il atteignait une valeur différente de zéro, le prédicteur de twig échouerait, provoquant un ralentissement de la comparaison, mais vous êtes également à la fin de votre calcul, car vous souhaitez renvoyer une valeur fausse dans les deux cas. Je pense que le coût d’une prévision de twig défaillante est un ordre de grandeur inférieur au coût de la poursuite de l’itération sur la masortingce.

Je pense en outre que for (byte b : array) devrait être autorisé car il doit être compilé directement dans l’itération de tableaux indexés, pour autant que je sache, il n’existe pas de PrimitiveArrayIterator qui provoquerait des appels de méthodes supplémentaires (comme une itération sur un liste) jusqu’à ce que le code soit intégré.

Mettre à jour

J’ai écrit mes propres benchmarks qui donnent des résultats intéressants … Malheureusement, je ne pouvais utiliser aucun des outils de benchmark existants car ils sont assez difficiles à installer correctement.

J’ai également décidé de regrouper les options 1 et 2, car je pense qu’elles sont en fait les mêmes que pour les twigs sans twigment ou moins (moins la condition) et que vous vérifiez ensuite le résultat final. Et la condition ici est x > 0 et donc a ou de zéro est un noop présumé.

Le code:

 public class Benchmark { private void start() { //setup byte arrays List 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 arrays, final Consumer method, final Ssortingng 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 createByteArrays(final int amount) { Random random = new Random(); List 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(Ssortingng[] args) { new Benchmark().start(); } } 

Les résultats surprenants:

Indicateur de référence: byteArrayCheck12 / itérations: 700000 / heure par itération: 50.18817142857143ns
Indicateur de référence: byteArrayCheck3 / itérations: 700000 / heure par itération: 767.7371985714286ns
Indicateur de référence: byteArrayCheck4 / itérations: 700000 / heure par itération: 21145.03219857143ns
Indicateur de référence: byteArrayCheck5 / itérations: 700000 / heure par itération: 10376.119144285714ns

Cela montre que orring est beaucoup plus rapide que le prédicteur de twig, ce qui est plutôt surprenant, donc je suppose que certaines optimisations de bas niveau sont en cours.

En plus, j’ai inclus les variantes de stream que je ne m’attendais pas à être aussi rapides de toute façon.

Ran sur un Intel i7-3770, 16 Go 1600MHz RAM stockée.

Donc, je pense que la réponse finale est: cela dépend. Cela dépend du nombre de fois que vous allez vérifier le tableau consécutivement. La solution “byteArrayCheck3” est toujours constante à 700 ~ 800ns.

Mise à jour de suivi

Les choses prennent une autre approche intéressante, il s’avère que JIT optimisait presque tous les calculs en raison du fait que les variables résultantes n’étaient pas utilisées du tout.

J’ai donc la nouvelle méthode de benchmark suivante:

 private void benchmark(final List arrays, final Predicate method, final Ssortingng 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"); } 

Cela garantit que le résultat des byteArrayCheck12 ne peut pas être optimisé, le problème majeur étant que la méthode byteArrayCheck12 était vide, car elle remarquait que le (sum == 0) n’était pas utilisé, donc il a optimisé la méthode entière.

Nous avons donc le nouveau résultat suivant (omis le résultat imprime pour plus de clarté):

Repère: byteArrayCheck12 / itérations: 700000 / heure par itération: 1370.6987942857143ns
Indicateur de référence: byteArrayCheck3 / itérations: 700000 / heure par itération: 736.1096242857143ns
Indicateur de référence: byteArrayCheck4 / itérations: 700000 / heure par itération: 20671.230327142857ns
Indicateur de référence: byteArrayCheck5 / itérations: 700000 / heure par itération: 9845.388841428572ns

Nous pensons donc que nous pouvons finalement conclure que la prédiction de twig gagne. Cela pourrait cependant aussi se produire à cause des premiers retours, car en moyenne l’octet incriminé sera au milieu du tableau d’octets, il est donc temps pour une autre méthode qui ne retourne pas plus tôt:

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

De cette manière, nous continuons à bénéficier de la prévision de la succursale, mais nous nous assurons que nous ne pouvons pas revenir plus tôt.

Ce qui nous donne à nouveau des résultats plus intéressants!

Indicateur de référence: byteArrayCheck12 / itérations: 700000 / heure par itération: 1327.2817714285713ns
Indicateur de référence: byteArrayCheck3 / itérations: 700000 / heure par itération: 753.31376ns
Indicateur de référence: byteArrayCheck3b / itérations: 700000 / heure par itération: 1506.6772842857142ns
Indicateur de référence: byteArrayCheck4 / itérations: 700000 / heure par itération: 21655.950115714284ns
Repère: byteArrayCheck5 / itérations: 700000 / heure par itération: 10608.70917857143ns

Je pense que nous pouvons cependant conclure que le moyen le plus rapide consiste à utiliser à la fois la prédiction de retour anticipé et celle de twig, suivie de orring, suivie d’une prédiction purement ramifiée. Je pense que toutes ces opérations sont hautement optimisées en code natif.

Mise à jour , une parsing comparative supplémentaire utilisant des tableaux longs et int.

Après avoir vu des suggestions sur l’utilisation de long[] et int[] j’ai décidé que cela valait la peine d’être étudié. Cependant, ces tentatives ne sont peut-être plus tout à fait conformes aux réponses originales, mais peuvent néanmoins être intéressantes.

Premièrement, j’ai changé la méthode de benchmark pour utiliser les génériques:

 private  void benchmark(final List arrays, final Predicate method, final Ssortingng 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"); } 

Ensuite, j’ai effectué des conversions d’ byte[] à long[] et d’ int[] respectivement avant les tests, il était également nécessaire de définir la taille maximale du segment de mémoire à 10 Go.

 List 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 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; } 

Ce qui a donné les résultats suivants:

Repère: byteArrayCheck8 / itérations: 700000 / heure par itération: 259.8157614285714ns
Indicateur de référence: byteArrayCheck9 / itérations: 700000 / heure par itération: 266.38013714285717ns

Ce chemin peut être intéressant s’il est possible d’obtenir les octets dans un tel format. Cependant, lorsque vous effectuez les transformations à l’intérieur de la méthode de référence, les temps étaient d’environ 2000 nanosecondes par itération, donc cela ne vaut pas la peine de faire les conversions vous-même.

Ce n’est peut-être pas la solution la plus rapide ou la plus performante en termes de mémoire, mais c’est une solution unique:

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

Pour Java 8, vous pouvez simplement utiliser ceci:

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

Je pense que théoriquement votre façon la plus rapide, dans la pratique, vous pourriez être en mesure d’utiliser des comparaisons plus larges comme suggéré par l’un des commentateurs (une comparaison de 1 octet prend 1 instruction, mais il en va de même pour une comparaison de 64 octets). système de bits).

De même, dans les langues plus proches du matériel (C et variantes), vous pouvez utiliser quelque chose appelé vectorisation pour effectuer plusieurs comparaisons / ajouts simultanément. Il semble que Java n’ait toujours pas de support natif, mais sur la base de cette réponse, vous pourrez peut-être vous en servir.

Toujours dans la lignée des autres commentaires, je dirais qu’avec un tampon 4k, cela ne vaut probablement pas la peine d’essayer de l’optimiser (à moins qu’il ne soit appelé très souvent)

Quelqu’un a suggéré de vérifier 4 ou 8 octets à la fois. Vous pouvez réellement le faire en Java:

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

Il est incertain si cela est plus rapide que de vérifier les valeurs d’octet, car il y a beaucoup de potentiel d’optimisation.