Quel est le coût de performance de l'itération sur une liste plusieurs fois ?

Question

J'ai une liste que je dois itérer et sur laquelle je dois effectuer un travail en cours de route. Mon problème est que, pour mon programme, il est difficile d'effectuer tout le travail nécessaire sur la liste à chaque boucle en raison de la concurrence. Ma solution a été d'itérer sur la boucle autant de fois que nécessaire et d'effectuer une partie du travail à chaque itération. Cet exemple devrait illustrer ce que je veux dire :

List<String> list = new ArrayList<>();
    list.add("A");
    list.add("B");
    list.add("C");
    list.add("D");

    // Method A
    for (String item : list) {
        doWorkThing1(item);
        doWorkThing2(item);
    }

    // Method B
    for (String item : list) {
        doWorkThing1(item);
    }
    for (String item : list) {
        doWorkThing2(item);
    }

La méthode B est celle qui m'intrigue. Y a-t-il un coût notable à itérer plusieurs fois sur une boucle ? Puisque je suppose que la plupart des coûts de performance iront aux méthodes de "travail", je me demandais s'il était juste de dire que la différence entre la méthode A et la méthode B serait négligeable ?

Answer 1

Tout d'abord, vous devez définir ce que vous entendez par performance.

Si vous parlez de complexité temporelle de votre algorithme, nous pouvons dire qu'un algorithme qui itère sur une liste de taille n a une complexité temporelle de O(n). Ainsi, si vous faites c itérations de votre liste (où c est un nombre constant), la complexité temporelle reste la même. En d'autres termes, les costants ne sont pas importants, donc si vous itérez 3 fois sur une liste de taille n, vous aurez une complexité en temps de

3 * O(n) ~= O(n) .

Il est maintenant très important de définir ce que font vos méthodes. Si elles effectuent une opération qui nécessite un temps coûteux (par exemple, imprimer la valeur de l'objet), la complexité reste la même -> O(n).

Vous pouvez trouver d'autres informations sur l'extimation du temps aquí .

Il existe une autre façon de mesurer la performance d'un algorithme, le complexité de l'espace . Je n'ai pas abordé ce sujet car il n'y a qu'une simple structure de données définie dans votre code mais vous pouvez trouver des informations utiles à ce sujet aquí .

Answer 2

La différence de performance serait probablement mesurable, mais dans votre exemple, elle serait la suivante moins de une microseconde. Mon intuition me dit qu'elle est de l'ordre de 100 nanosecondes ... une fois que le code a été compilé par JIT.

C'est possible, mais peu probable que la différence de performance de cette taille est important . Pour que la différence soit significative, il faut qu'un ou plusieurs des éléments suivants soient vrais :

• Les méthodes sont appelées de très nombreuses fois.
• L'application a des exigences strictes en matière de temps réel ; par exemple, un appel à l'une des méthodes doit se terminer dans un délai très court.

Et même si l'un de ces critères est rempli, si le temps nécessaire pour effectuer le travail est de l'ordre de la microseconde, de la milliseconde ou plus, alors le temps nécessaire pour effectuer le travail sera de l'ordre de la microseconde, de la milliseconde ou plus. dominer le temps "perdu" lors d'une deuxième itération.

---

Voici mon conseil.

1. Avant de commencer réflexion Avant de procéder à l'optimisation, il faut bien comprendre les exigences de performance. S'il n'y a pas d'exigences de performance énoncées ou implicites, alors ne perdez pas votre temps (Il n'y a pas d'impératif moral à rendre votre code aussi rapide que possible).

2. Il est plus important d'obtenir la bonne réponse (suffisante) que d'obtenir la réponse rapidement. Ne passez donc pas de temps à optimiser tant que votre code n'est pas écrit et testé.

3. Construisez vous-même un benchmark (en utilisant des données d'entrée réalistes, etc.) que vous pouvez utiliser pour juger si le code tourne suffisamment vite, et faites des comparaisons avant/après de vos optimisations candidates. (Attention aux pièges habituels de l'analyse comparative du code Java).

4. Utilisez le profilage pour déterminer les parties de votre code qu'il vaut la peine d'optimiser. Recherchez les points chauds, c'est-à-dire les méthodes/sections où l'on passe le plus de temps. (L'optimisation du code qui n'est pas un hotspot est peu probable pour faire une différence significative globale les performances de l'application).

5. Lorsque vous atteignez votre objectif, ou lorsque vous n'avez plus de points d'accès ... arrêter .

Answer 3

Pour ce cas d'utilisation particulier, vous pouvez exécuter un micro-benchmark pour comparer différentes approches de code qui mettent en œuvre la même logique et choisir la meilleure à utiliser.

public void methodA() {
    List<String> list = new ArrayList<>();
    list.add("A");
    list.add("B");
    list.add("C");
    list.add("D");

    for (String item : list) {
        doWorkThing1(item);
        doWorkThing2(item);
    }

}

public void methodB() {

    List<String> list = new ArrayList<>();
    list.add("A");
    list.add("B");
    list.add("C");
    list.add("D");

    for (String item : list) {
        doWorkThing1(item);
    }
    for (String item : list) {
        doWorkThing2(item);
    }

}

private void doWorkThing2(String item) {
    int j = 0;
    for (int i = 0; i < 10000; i++) {
        j = i + j;
    }
}

private void doWorkThing1(String item) {
    int j = 0;
    for (int i = 0; i < 10000; i++) {
        j = i + j;
    }
}

Lorsque j'exécute le code à l'aide de l'outil jmh (c'est-à-dire Java Microbenchmarking Harness). Le résultat suivant est produit ;

Benchmark               Mode  Cnt         Score         Error  Units
IterationCost.methodA  thrpt   20  56183172.456 ± 1388825.737  ops/s
IterationCost.methodB  thrpt   20  49693471.457 ±  777747.554  ops/s
IterationCost.methodA   avgt   20        ≈ 10⁻⁸                 s/op
IterationCost.methodB   avgt   20        ≈ 10⁻⁸                 s/op

Soyez conscient des autres facteurs qui peuvent avoir un impact sur les résultats.

Answer 4

Il y a trop de variables pour que l'on puisse vous dire lequel utiliser pour obtenir les meilleures performances, car celles-ci peuvent varier en fonction de ce qui se passe. Il n'existe pas de méthode unique qui donne les meilleurs résultats dans toutes les situations.

Parfois, le fractionnement de la boucle permet d'obtenir de meilleures performances (peut-être que le cache d'instructions du processeur n'aura pas besoin d'être rempli plusieurs fois à chaque itération). Parfois, le regroupement en une seule boucle permet d'obtenir de meilleures performances (le cache de données du processeur n'a peut-être pas besoin d'être rempli plusieurs fois à chaque itération). n fois plus qu'avec une seule boucle).

Le profilage à l'aide de données réelles est une solution. Profil avec des données réelles d'une autre manière. Utiliser la méthode la plus performante.

Answer 5

En général, le surcoût évident n'est dû qu'à l'incrémentation supplémentaire des compteurs additionnels et à l'extraction de données due aux boucles for supplémentaires. Ce surcoût n'est pas significatif s'il n'est pas significatif pour une seule boucle for, mais il est évident qu'il représente N fois le coût d'une seule boucle for.

Il peut également y avoir des problèmes de mise en cache et autres, mais vous ne devriez pas avoir trop de problèmes.

une boucle for est en fait (pseudo)

loop:
   x = list[k++];
   work1(x);
   work2(x);
goto loop;

Les 2 boucles sont donc

loop:
   x = list[k++];
   work1(x);
goto loop;

loop:
   x = list[k++];
   work2(x);
goto loop;

En fin de compte, pour savoir EXACTEMENT ce qui se passe, il faut profiler mais même dans ce cas, on ne sait pas exactement ce qui se passe. Si vous essayez d'exploiter les derniers 0,00001% de cycles du processeur, vous pouvez vous en préoccuper, sinon ne vous en préoccupez pas.

Si vos fonctions de travail ne sont pas "lourdes" (elles ne font pas grand-chose), il existe d'autres moyens d'optimiser les choses, comme le déroulement de la boucle, etc.