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 est0 == false
donc sii
finalement égale0
il est interprété commefalse
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").
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.
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
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.
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--;)
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.
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.
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.
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--)
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.
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.
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++) {
...
}