Performance de la boucle JavaScript - pourquoi décrémenter l'itérateur vers 0 plus rapidement que l'incrémentation

Dans son livre Encore plus Rapide des Sites Web de Steve Sounders écrit qu'un moyen simple d'améliorer les performances d'une boucle est de décrémenter l'itérateur vers 0 au lieu de l'incrémentation vers la longueur totale ( en fait, le chapitre a été écrit par Nicholas C. Zakas ). Ce changement peut entraîner des économies allant jusqu'à 50% sur le temps d'exécution initial, selon la complexité de chaque itération. Par exemple:

var values = [1,2,3,4,5];
var length = values.length;

for (var i=length; i--;) {
   process(values[i]);
}

c'est presque identique pour la boucle for , la boucle do-while et la boucle while .

je me demande, Quelle est la raison de cela? pourquoi décrémenter l'itérateur beaucoup plus rapidement? (je suis intéressé par le contexte technique de cette et non par des points de repère prouvant cette revendication.)


EDIT: À première vue, la boucle de la syntaxe utilisée ici semble incorrect. Il n'y a pas de length-1 ou i>=0 , nous allons donc préciser (j'ai été trop confus).

voici le général pour la syntaxe de boucle:

for ([initial-expression]; [condition]; [final-expression])
   statement
  • expression initiale - var i=length

    cette déclaration de variable est évaluée en premier.

  • condition - i--

    This l'expression est évaluée avant chaque itération de boucle. Il décrémentera la variable avant le premier passage à travers la boucle. Si cette expression est évaluée à false la boucle se termine. En JavaScript est 0 == false donc si i finalement égale 0 il est interprété comme false et la boucle se termine.

  • final-expression

    Cette expression est évaluée à la fin de chaque itération en boucle (avant la prochaine évaluation de condition ). Il n'est pas nécessaire ici, et est vide. Les trois expressions sont optionnelles dans une boucle for.

la syntaxe for loop ne fait pas partie de la question, mais parce qu'elle est un peu rare, je pense qu'il est intéressant de la clarifier. Et peut-être une raison pour laquelle il est plus rapide est, parce qu'il utilise moins d'expressions (le 0 == false "truc").

55
demandé sur Soundlink 2010-08-19 14:09:31

11 réponses

Je ne suis pas sûr de Javascript, et sous les compilateurs modernes, cela n'a probablement pas d'importance, mais dans les "vieux jours" ce code:

for (i = 0; i < n; i++){
  .. body..
}

générerait

move register, 0
L1:
compare register, n
jump-if-greater-or-equal L2
-- body ..
increment register
jump L1
L2:

alors que le code de comptage à rebours

for (i = n; --i>=0;){
  .. body ..
}

générerait

move register, n
L1:
decrement-and-jump-if-negative register, L2
.. body ..
jump L1
L2:

donc à l'intérieur de la boucle il ne fait que deux instructions supplémentaires au lieu de quatre.

58
répondu Mike Dunlavey 2015-11-06 14:49:25

je pense que la raison est parce que vous comparez le point final de boucle contre 0, qui est plus rapide que la comparaison à nouveau < length (ou une autre variable JS).

c'est parce que les opérateurs ordinaux <, <=, >, >= sont polymorphes, de sorte que ces opérateurs nécessitent des contrôles de type sur les deux côtés gauche et droite de l'opérateur pour déterminer quel comportement de comparaison devrait être utilisé.

il y a de très bons benchmarks disponibles ici:

Quelle est la façon la plus rapide de coder une boucle en JavaScript

22
répondu GenericTypeTea 2015-08-31 15:04:05

Il est facile de dire qu'une itération peut avoir moins d'instructions. Comparons ces deux-là:

for (var i=0; i<length; i++) {
}

for (var i=length; i--;) {
}

lorsque vous comptez chaque accès variable et chaque opérateur comme une seule instruction, le premier for boucle utilise 5 instructions (lire i , lire length , évaluer i<length , test (i<length) == true , incrément i ) tandis que le dernier n'utilise que 3 instructions (lire i , test i == true , décrément i ). C'est un ratio de 5:3.

13
répondu Gumbo 2014-12-15 09:55:04

Qu'en est-il de l'utilisation d'une boucle inverse alors que:

var values = [1,2,3,4,5]; 
var i = values.length; 

/* i is 1st evaluated and then decremented, when i is 1 the code inside the loop 
   is then processed for the last time with i = 0. */
while(i--)
{
   //1st time in here i is (length - 1) so it's ok!
   process(values[i]);
}

OMI celui-ci au moins est un code plus facile à lire que for(i=length; i--;)

6
répondu Marco Demaio 2010-08-23 21:05:45

j'ai exploré la vitesse de boucle aussi, et j'ai été intéressé de trouver cette info sur le fait de décrémenter plus vite que d'incrémenter. Cependant, je n'ai pas encore trouvé un test qui démontre. Il y a beaucoup de points de repère de boucle sur jsperf. En voici un qui teste la décrémentation:

http://jsperf.com/array-length-vs-cached/6

mise en cache de la longueur de votre tableau, cependant (également recommandé Livre de Steve Souders) ne semble pas être une optimisation gagnante.

3
répondu nabrown78 2012-07-10 00:20:15

il y a une version encore plus" performante " de cela. Puisque chaque argument est optionnel dans les boucles, vous pouvez sauter même le premier.

var array = [...];
var i = array.length;

for(;i--;) {
    do_teh_magic();
}

avec ceci vous sautez même le contrôle sur le [initial-expression] . Donc, vous vous retrouvez avec une seule opération.

2
répondu icanhazstring 2012-07-05 12:07:55

for incrémenter vs décrémenter en 2017

dans les moteurs js modernes incrémentant dans for boucles est généralement plus rapide que la décrémentation (basé sur des références personnelles.

for (let i = 0; i < array.length; i++) { ... }

cela dépend de la longueur de la plate-forme et du réseau si length = array.length a un effet positif considérable, mais généralement pas:

for (let i = 0, length = array.length; i < length; i++) { ... }

les versions récentes de V8 (Chrome, Node) ont les optimisations pour array.length , donc length = array.length peuvent être omises efficacement dans tous les cas.

2
répondu estus 2017-02-21 16:00:52

dans les moteurs js modernes, la différence entre les boucles avant et arrière est presque inexistante. Mais la différence de performance se résume à 2 choses:

a) Recherche supplémentaire chaque propriété de longueur chaque cycle

//example:
    for(var i = 0; src.length > i; i++)
//vs
    for(var i = 0, len = src.length; len > i; i++)

c'est le plus grand gain de performance d'une boucle inversée, et peut évidemment être appliqué aux boucles avant.

b) assignation de variable supplémentaire.

le gain le plus faible d'une boucle inversée est qu'elle ne nécessite qu'une seule assignation de variable au lieu de 2

//example:
    var i = src.length; while(i--)
2
répondu BenG 2017-03-16 17:27:35

j'ai réalisé un benchmark sur C# et C++ (syntaxe similaire). Là, en fait, la performance diffère essentiellement en for boucles, par rapport à do while ou while . En C++, la performance est plus grande en incrémentation. Il peut également dépendre du compilateur.

En Javascript, je pense, tout dépend du navigateur (moteur Javascript), mais ce comportement est attendu. Javascript est optimisé pour travailler avec DOM. Alors imaginez vous boucler à travers un collection D'éléments DOM vous obtenez à chaque itération, et vous incrémentez un compteur, quand vous devez les supprimer. Vous supprimez l'élément 0 , puis 1 , mais vous sautez celui qui prend la place de 0 . Si la boucle vers l'arrière que le problème disparaît. Je sais que l'exemple donné n'est pas seulement le bon, mais j'ai rencontré des situations où j'ai dû supprimer des articles d'une collection d'objets en constante évolution.

parce que la boucle arrière est plus souvent inévitable que la boucle avant, je devine que le moteur JS est optimisé juste pour cela.

1
répondu AlexanderMP 2010-08-19 10:17:41

avez-vous chronométré vous-même? M. Sounders pourrait avoir tort en ce qui concerne les interprètes modernes. C'est précisément le genre d'optimisation dans lequel un bon compilateur écrivain peut faire une grande différence.

1
répondu Crashworks 2010-08-19 10:21:56

Je ne suis pas sûr si c'est plus rapide mais une raison que je vois est que lorsque vous itérez sur un tableau de grands éléments en utilisant increment vous avez tendance à écrire:

for(var i = 0; i < array.length; i++) {
 ...
}

vous accédez essentiellement à la propriété length du tableau N (nombre d'éléments) fois. Alors que quand on décrémente, on n'y accède qu'une fois. Que pourrait être une raison.

mais vous pouvez aussi écrire boucle d'incrémentation comme suit:

for(var i = 0, len = array.length; i < len; i++) {
 ...
}
1
répondu naikus 2010-08-19 10:23:23