Arrays.stream (nom_ array) .sum () est-il plus lent que l’approche itérative?

Je codais un problème avec le code code: https://oj.leetcode.com/problems/gas-station/ en utilisant Java 8.

Ma solution a eu TLE lorsque j’ai utilisé Arrays.stream(integer_array).sum() pour calculer la sum alors que la même solution a été acceptée en utilisant l’itération pour calculer la sum des éléments d’un tableau. La meilleure complexité temporelle possible pour ce problème est O (n) et je suis surpris de pouvoir obtenir TLE lors de l’utilisation d’API de streaming de Java 8. J’ai implémenté la solution dans O (n) uniquement.

 import java.util.Arrays; public class GasStation { public int canCompleteCircuit(int[] gas, int[] cost) { int start = 0, i = 0, runningCost = 0, totalGas = 0, totalCost = 0; totalGas = Arrays.stream(gas).sum(); totalCost = Arrays.stream(cost).sum(); // for (int item : gas) totalGas += item; // for (int item : cost) totalCost += item; if (totalGas  i || (start == 0 && i = cost[i]) { runningCost -= cost[i++]; } else { runningCost -= gas[i]; if (--start < 0) start = gas.length - 1; runningCost += (gas[start] - cost[start]); } } return start; } public static void main(String[] args) { GasStation sol = new GasStation(); int[] gas = new int[] { 10, 5, 7, 14, 9 }; int[] cost = new int[] { 8, 5, 14, 3, 1 }; System.out.println(sol.canCompleteCircuit(gas, cost)); gas = new int[] { 10 }; cost = new int[] { 8 }; System.out.println(sol.canCompleteCircuit(gas, cost)); } } 

La solution est acceptée lorsque, je commente les deux lignes suivantes: (calcul de la sum à l’aide de la diffusion en continu)

 totalGas = Arrays.stream(gas).sum(); totalCost = Arrays.stream(cost).sum(); 

et décommentez les deux lignes suivantes (calculant la sum par itération):

 //for (int item : gas) totalGas += item; //for (int item : cost) totalCost += item; 

Maintenant, la solution est acceptée. Pourquoi le streaming d’API dans Java 8 est-il plus lent pour les entrées volumineuses que l’itération pour les primitives ?

La première étape pour traiter de tels problèmes consiste à intégrer le code dans un environnement contrôlé. Cela signifie que vous devez l’exécuter dans la machine virtuelle que vous contrôlez (et que vous pouvez l’invoquer), ainsi que l’exécution de tests dans un bon faisceau de points de référence comme JMH . Analysez, ne spéculez pas.

Voici un sharepoint repère que j’ai préparé avec JMH pour effectuer une parsing à ce sujet:

 @BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.MICROSECONDS) @State(Scope.Benchmark) public class ArraySum { static final long SEED = -897234L; @Param({"1000000"}) int sz; int[] array; @Setup public void setup() { Random random = new Random(SEED); array = new int[sz]; Arrays.setAll(array, i -> random.nextInt()); } @Benchmark public int sumForLoop() { int sum = 0; for (int a : array) sum += a; return sum; } @Benchmark public int sumStream() { return Arrays.stream(array).sum(); } } 

Fondamentalement, cela crée un tableau d’un million de bits et les additionne deux fois: une fois en utilisant une boucle for et une fois en utilisant des stream. L’exécution de la référence produit une quantité de sortie (optimisée pour la brièveté et l’effet spectaculaire), mais les résultats récapitulatifs sont les suivants:

 Benchmark (sz) Mode Samples Score Score error Units ArraySum.sumForLoop 1000000 avgt 3 514.473 398.512 us/op ArraySum.sumStream 1000000 avgt 3 7355.971 3170.697 us/op 

Whoa! Ce stream Java 8 est le SUXX0R! C’est 14 fois plus lent qu’une boucle, ne l’utilisez pas !!! 1!

Et bien non. Commençons par examiner ces résultats, puis examinons de plus près si nous pouvons comprendre ce qui se passe.

Le résumé présente les deux méthodes de référence, avec le paramètre “sz” d’un million. Il est possible de faire varier ce paramètre mais cela ne change rien dans ce cas. De plus, je n’ai exécuté que 3 fois les méthodes de référence, comme le montre la colonne “exemples”. (Il n’y avait également que 3 itérations de réchauffement, non visibles ici.) Le score est en microsecondes par opération, et le code du stream est clairement beaucoup plus lent que le code de la boucle for. Mais notez également l’erreur de score: c’est la quantité de variabilité dans les différentes exécutions. JMH imprime utilement l’écart type des résultats (non présenté ici), mais vous pouvez facilement voir que l’erreur de score est une fraction significative du score rapporté. Cela réduit notre confiance dans le score.

Lancer plus d’itérations devrait aider. Un plus grand nombre d’itérations de réchauffement laissera le JIT faire plus de travail et de se calmer avant d’exécuter les tests de performance. De plus, l’exécution d’itérations de tests de performance lisseront les erreurs résultant d’activités transitoires ailleurs sur mon système. Essayons donc 10 itérations d’échauffement et 10 itérations de référence:

 Benchmark (sz) Mode Samples Score Score error Units ArraySum.sumForLoop 1000000 avgt 10 504.803 34.010 us/op ArraySum.sumStream 1000000 avgt 10 7128.942 178.688 us/op 

Dans l’ensemble, les performances sont un peu plus rapides et l’erreur de mesure est également un peu plus petite. L’exécution de plusieurs itérations a donc eu l’effet souhaité. Mais le code des stream est toujours beaucoup plus lent que le code de la boucle for. Que se passe-t-il?

Un indice important peut être obtenu en regardant les timings individuels de la méthode des stream:

 # Warmup Iteration 1: 570.490 us/op # Warmup Iteration 2: 491.765 us/op # Warmup Iteration 3: 756.951 us/op # Warmup Iteration 4: 7033.500 us/op # Warmup Iteration 5: 7350.080 us/op # Warmup Iteration 6: 7425.829 us/op # Warmup Iteration 7: 7029.441 us/op # Warmup Iteration 8: 7208.584 us/op # Warmup Iteration 9: 7104.160 us/op # Warmup Iteration 10: 7372.298 us/op 

Qu’est-il arrivé? Les premières itérations étaient assez rapides, mais ensuite les 4èmes et suivantes (et toutes les itérations de référence qui suivent) étaient soudainement beaucoup plus lentes.

J’ai déjà vu ça. C’était dans cette question et cette réponse ailleurs sur SO. Je recommande de lire cette réponse; il explique comment les décisions en ligne de la JVM dans ce cas entraînent une baisse des performances.

Un peu d’arrière-plan ici: une boucle for est compilée en une boucle d’incrémentation et de test très simple, et peut facilement être gérée par les techniques d’optimisation habituelles telles que le peeling et le déroulement de boucles. Le code de stream, bien que peu complexe dans ce cas, est en réalité assez complexe comparé au code for-loop; il y a pas mal de configuration, et chaque boucle nécessite au moins un appel de méthode. Ainsi, les optimisations de JIT, en particulier ses décisions en ligne, sont essentielles à la rapidité du code des stream. Et il est possible que ça tourne mal.

Un autre point d’arrière-plan est que la sum d’entiers est l’opération la plus simple possible dans une boucle ou un stream. Cela aura tendance à faire paraître le surcoût de la configuration du stream relativement plus coûteux. C’est aussi si simple que cela peut déclencher des pathologies dans la politique en ligne.

L’autre réponse proposée consistait à append l’option JVM -XX:MaxInlineLevel=12 pour augmenter la quantité de code pouvant être insérée. Réexécuter le repère avec cette option donne:

 Benchmark (sz) Mode Samples Score Score error Units ArraySum.sumForLoop 1000000 avgt 10 502.379 27.859 us/op ArraySum.sumStream 1000000 avgt 10 498.572 24.195 us/op 

Ah, beaucoup plus gentil. La désactivation de la compilation hiérarchisée à l’aide de -XX:-TieredCompilation également eu pour effet d’éviter le comportement pathologique. J’ai également constaté que rendre le calcul de boucle encore un peu plus cher, par exemple, en additionnant des carrés d’entiers – c’est-à-dire en ajoutant une seule multiplication – évite également le comportement pathologique.

Maintenant, votre question concerne l’exécution dans le contexte de l’environnement leetcode , qui semble exécuter le code dans une machine virtuelle que vous n’avez aucun contrôle, vous ne pouvez donc pas modifier les options d’inclusion ou de compilation. Et vous ne voulez probablement pas rendre votre calcul plus complexe pour éviter la pathologie. Donc, dans ce cas, vous pourriez aussi bien vous en tenir au bon vieux-for-loop. Mais n’ayez pas peur d’utiliser des stream, même pour gérer des tableaux primitifs. Il peut très bien fonctionner, mis à part certains cas très ressortingctifs.

L’approche d’itération normale sera à peu près aussi rapide que possible, mais les stream ont une variété de frais généraux: même s’ils proviennent directement d’un stream, il y aura probablement un Spliterator primitif impliqué et beaucoup d’autres objects générés .

En général, vous devriez vous attendre à une “approche normale” plus rapide que les stream, sauf si vous utilisez tous les deux la parallélisation et que vos données sont très volumineuses.

Mon repère (voir le code ci-dessous) montre que l’approche de la diffusion en continu est environ 10-15% plus lente qu’itérative. Il est intéressant de noter que les résultats des stream parallèles varient considérablement sur mon MacBook Pro 4 core (i7), mais, même si je les ai vus à quelques resockets être environ 30% plus rapides qu’itératifs, le résultat le plus commun est presque trois fois plus lent que séquentiel.

Voici le code de référence:

 import java.util.*; import java.util.function.*; public class StreamingBenchmark { private static void benchmark(Ssortingng name, LongSupplier f) { long start = System.currentTimeMillis(), sum = 0; for(int count = 0; count < 1000; count ++) sum += f.getAsLong(); System.out.println(String.format( "%10s in %d millis. Sum = %d", name, System.currentTimeMillis() - start, sum )); } public static void main(String argv[]) { int data[] = new int[1000000]; Random randy = new Random(); for(int i = 0; i < data.length; i++) data[i] = randy.nextInt(); benchmark("iterative", () -> { int s = 0; for(int n: data) s+=n; return s; }); benchmark("stream", () -> Arrays.stream(data).sum()); benchmark("parallel", () -> Arrays.stream(data).parallel().sum()); } } 

Voici le résultat de quelques exécutions:

  iterative in 350 millis. Sum = 564821058000 stream in 394 millis. Sum = 564821058000 parallel in 883 millis. Sum = 564821058000 iterative in 340 millis. Sum = -295411382000 stream in 376 millis. Sum = -295411382000 parallel in 1031 millis. Sum = -295411382000 iterative in 365 millis. Sum = 1205763898000 stream in 379 millis. Sum = 1205763898000 parallel in 1053 millis. Sum = 1205763898000 

etc.

Cela m’a rendu curieux, et j’ai également essayé d’exécuter une logique équivalente dans scala:

 object Scarr { def main(argv: Array[Ssortingng]) = { val randy = new java.util.Random val data = (1 to 1000000).map { _ => randy.nextInt }.toArray val start = System.currentTimeMillis var sum = 0l; for ( _ <- 1 to 1000 ) sum += data.sum println(sum + " in " + (System.currentTimeMillis - start) + " millis.") } } 

Cela a pris 14 secondes ! Environ 40 fois plus longtemps (!) Que le streaming en java. Aie!

La méthode sum () est syntaxiquement équivalente à return reduce(0, Integer::sum); Dans une grande liste, il y aura plus de temps pour faire tous les appels de méthode que l’itération manuelle de base pour boucle. Le code d’octet pour l’itération for(int i : numbers) n’est que très légèrement plus compliqué que celui généré par la boucle for for manuellement. Le stream est peut-être plus rapide dans les environnements parallèles (mais pas pour les méthodes primitives), mais à moins que nous ne sachions que l’environnement est parallèle (et ce n’est peut-être pas le cas, car le code lui-même est probablement conçu pour favoriser les niveaux bas puisqu’il s’agit de mesurer l’efficacité plutôt que la lisibilité).

L’opération sum effectuée de l’une des trois manières ( Arrays.stream(int[]).sum , for (int i : ints){total+=i;} et for(int i = 0; i < ints.length; i++){total+=i;} devrait être relativement similaire en termes d’efficacité. J’ai utilisé la classe de test suivante (qui représente cent millions d’entiers entre 0 et 4096 fois et enregistre les temps moyens). Il tente même de limiter le traitement en parallèle en occupant la totalité des cœurs disponibles sauf un (vrai) en boucle, mais je n’ai toujours trouvé aucune différence particulière:

 public class SumTester { private static final int ARRAY_SIZE = 100_000_000; private static final int ITERATION_LIMIT = 100; private static final int INT_VALUE_LIMIT = 4096; public static void main(Ssortingng[] args) { Random random = new Random(); int[] numbers = new int[ARRAY_SIZE]; IntStream.range(0, ARRAY_SIZE).forEach(i->numbers[i] = random.nextInt(INT_VALUE_LIMIT)); Map> inputs = new HashMap>(); NanoTimer initializer = NanoTimer.start(); System.out.println("initialized NanoTimer in " + initializer.microEnd() + " microseconds"); inputs.put("sumByStream", SumTester::sumByStream); inputs.put("sumByIteration", SumTester::sumByIteration); inputs.put("sumByForLoop", SumTester::sumByForLoop); System.out.println("Parallelables: "); averageTimeFor(ITERATION_LIMIT, inputs, Arrays.copyOf(numbers, numbers.length)); int cores = Runtime.getRuntime().availableProcessors(); List threadEaters = new ArrayList(); if (cores > 1){ threadEaters = occupyThreads(cores - 1); } // Only one core should be left to our class System.out.println("\nSingleCore (" + threadEaters.size() + " of " + cores + " cores occupied)"); averageTimeFor(ITERATION_LIMIT, inputs, Arrays.copyOf(numbers, numbers.length)); for (CancelableThreadEater cte : threadEaters){ cte.end(); } System.out.println("Complete!"); } public static long sumByStream(int[] numbers){ return Arrays.stream(numbers).sum(); } public static long sumByIteration(int[] numbers){ int total = 0; for (int i : numbers){ total += i; } return total; } public static long sumByForLoop(int[] numbers){ int total = 0; for (int i = 0; i < numbers.length; i++){ total += numbers[i]; } return total; } public static void averageTimeFor(int iterations, Map> testMap, int[] numbers){ Map durationMap = new HashMap(); Map sumMap = new HashMap(); for (Ssortingng methodName : testMap.keySet()){ durationMap.put(methodName, 0L); sumMap.put(methodName, 0L); } for (int i = 0; i < iterations; i++){ for (String methodName : testMap.keySet()){ int[] newNumbers = Arrays.copyOf(numbers, ARRAY_SIZE); ToLongFunction function = testMap.get(methodName); NanoTimer nt = NanoTimer.start(); long sum = function.applyAsLong(newNumbers); long duration = nt.microEnd(); sumMap.put(methodName, sum); durationMap.put(methodName, durationMap.get(methodName) + duration); } } for (Ssortingng methodName : testMap.keySet()){ long duration = durationMap.get(methodName) / iterations; long sum = sumMap.get(methodName); System.out.println(methodName + ": result '" + sum + "', elapsed time: " + duration + " milliseconds on average over " + iterations + " iterations"); } } private static List occupyThreads(int numThreads){ List result = new ArrayList(); for (int i = 0; i < numThreads; i++){ CancelableThreadEater cte = new CancelableThreadEater(); result.add(cte); new Thread(cte).start(); } return result; } private static class CancelableThreadEater implements Runnable { private Boolean stop = false; public void run(){ boolean canContinue = true; while (canContinue){ synchronized(stop){ if (stop){ canContinue = false; } } } } public void end(){ synchronized(stop){ stop = true; } } } } 

qui est revenu

 initialized NanoTimer in 22 microseconds Parallelables: sumByIteration: result '-1413860413', elapsed time: 35844 milliseconds on average over 100 iterations sumByStream: result '-1413860413', elapsed time: 35414 milliseconds on average over 100 iterations sumByForLoop: result '-1413860413', elapsed time: 35218 milliseconds on average over 100 iterations SingleCore (3 of 4 cores occupied) sumByIteration: result '-1413860413', elapsed time: 37010 milliseconds on average over 100 iterations sumByStream: result '-1413860413', elapsed time: 38375 milliseconds on average over 100 iterations sumByForLoop: result '-1413860413', elapsed time: 37990 milliseconds on average over 100 iterations Complete! 

Cela dit, il n'y a pas de vraie raison de faire l'opération sum () dans ce cas. Vous effectuez une itération dans chaque tableau, pour un total de trois itérations. La dernière peut être une itération plus longue que la normale. Il est possible de calculer correctement avec une itération simultanée complète des tableaux et une itération en court-circuit. Il serait peut-être possible de le faire encore plus efficacement, mais je ne pouvais pas trouver un meilleur moyen de le faire. Ma solution s’est avérée être l’une des solutions java les plus rapides du tableau: elle a fonctionné en 223 ms, soit la moyenne des solutions Python.

J'appendai ma solution au problème si vous le souhaitez, mais j'espère que la question est résolue ici.