Pourquoi est <= plus lent que <en utilisant cet extrait de code dans V8?

Je lis les diapositives Briser la limite de vitesse Javascript avec V8 , et il y a un exemple comme le code ci-dessous. Je ne peux pas comprendre pourquoi <=est plus lent que <dans ce cas, quelqu'un peut-il expliquer cela? Tous les commentaires sont appréciés.

Lent:

this.isPrimeDivisible = function(candidate) {
    for (var i = 1; i <= this.prime_count; ++i) {
        if (candidate % this.primes[i] == 0) return true;
    }
    return false;
} 

(Indice: nombres premiers est un tableau de longueur prime_count)

Plus rapide:

this.isPrimeDivisible = function(candidate) {
    for (var i = 1; i < this.prime_count; ++i) {
        if (candidate % this.primes[i] == 0) return true;
    }
    return false;
} 

[Plus d'infos] l'amélioration de la vitesse est significative, dans mon test d'environnement local, les résultats sont les suivants:

V8 version 7.3.0 (candidate) 

Lent:

 time d8 prime.js
 287107
 12.71 user 
 0.05 system 
 0:12.84 elapsed 

Plus rapide:

time d8 prime.js
287107
1.82 user 
0.01 system 
0:01.84 elapsed

Je travaille sur V8 chez Google et je voulais fournir des informations supplémentaires en plus des réponses et des commentaires existants.

Pour référence, voici l'exemple de code complet des diapositives :

var iterations = 25000;

function Primes() {
  this.prime_count = 0;
  this.primes = new Array(iterations);
  this.getPrimeCount = function() { return this.prime_count; }
  this.getPrime = function(i) { return this.primes[i]; }
  this.addPrime = function(i) {
    this.primes[this.prime_count++] = i;
  }
  this.isPrimeDivisible = function(candidate) {
    for (var i = 1; i <= this.prime_count; ++i) {
      if ((candidate % this.primes[i]) == 0) return true;
    }
    return false;
  }
};

function main() {
  var p = new Primes();
  var c = 1;
  while (p.getPrimeCount() < iterations) {
    if (!p.isPrimeDivisible(c)) {
      p.addPrime(c);
    }
    c++;
  }
  console.log(p.getPrime(p.getPrimeCount() - 1));
}

main();

D'abord et avant tout, la différence de performances n'a rien à voir directement avec les opérateurs <et <=. Alors s'il vous plaît, ne sautez pas à travers les cerceaux juste pour éviter <=dans votre code, car vous lisez sur Stack Overflow que c'est lent - ce n'est pas le cas!

Deuxièmement, les gens ont souligné que le tableau était «troué». Ce n'était pas clair à partir de l'extrait de code dans la publication d'OP, mais c'est clair lorsque vous regardez le code qui s'initialise this.primes:

this.primes = new Array(iterations);

Il en résulte un tableau avec un HOLEYtype d'éléments dans V8, même si le tableau finit par être complètement rempli / compacté / contigu. En général, les opérations sur les tableaux troués sont plus lentes que les opérations sur les tableaux compressés, mais dans ce cas, la différence est négligeable: cela équivaut à 1 contrôle Smi ( petit entier ) supplémentaire (pour se prémunir contre les trous) chaque fois que nous frappons this.primes[i]dans la boucle à l'intérieur isPrimeDivisible. Pas grave!

TL; DR Le tableau HOLEYn'est pas le problème ici.

D'autres ont souligné que le code se lit hors des limites. Il est généralement recommandé d' éviter de lire au-delà de la longueur des tableaux , et dans ce cas, cela aurait en effet évité la baisse massive des performances. Mais pourquoi alors? La V8 peut gérer certains de ces scénarios hors limites avec un impact mineur sur les performances. Qu'est-ce donc si spécial dans ce cas particulier?

La lecture hors limites a pour résultat d' this.primes[i]être undefinedsur cette ligne:

if ((candidate % this.primes[i]) == 0) return true;

Et cela nous amène au vrai problème : l' %opérateur est maintenant utilisé avec des opérandes non entiers!

• integer % someOtherIntegerpeut être calculé très efficacement; Les moteurs JavaScript peuvent produire un code machine hautement optimisé pour ce cas.

• integer % undefinedpar contre, cela revient à un moyen moins efficace Float64Mod, puisqu'il undefinedest représenté comme un double.

L'extrait de code peut en effet être amélioré en changeant le <=en <sur cette ligne:

for (var i = 1; i <= this.prime_count; ++i) {

... non pas parce que <=c'est en quelque sorte un opérateur supérieur à <, mais simplement parce que cela évite la lecture hors limites dans ce cas particulier.

D'autres réponses et commentaires mentionnent que la différence entre les deux boucles est que la première exécute une itération de plus que la seconde. C'est vrai, mais dans un tableau qui atteint 25 000 éléments, une itération plus ou moins ne ferait qu'une infime différence. En gros, si nous supposons que la longueur moyenne à mesure qu'elle grandit est de 12500, alors la différence à laquelle nous pouvons nous attendre devrait être d'environ 1/12 500, soit seulement 0,008%.

La différence de performance ici est beaucoup plus grande que ce qui serait expliqué par cette itération supplémentaire, et le problème est expliqué vers la fin de la présentation.

this.primes est un tableau contigu (chaque élément contient une valeur) et les éléments sont tous des nombres.

Un moteur JavaScript peut optimiser un tel tableau pour qu'il soit un simple tableau de nombres réels, au lieu d'un tableau d'objets qui contiennent des nombres mais pourraient contenir d'autres valeurs ou aucune valeur. Le premier format est beaucoup plus rapide d'accès: il prend moins de code, et le tableau est beaucoup plus petit donc il s'intégrera mieux dans le cache. Mais certaines conditions peuvent empêcher l'utilisation de ce format optimisé.

Une condition serait si certains des éléments du tableau sont manquants. Par exemple:

let array = [];
a[0] = 10;
a[2] = 20;

Maintenant quelle est la valeur de a[1]? Cela n'a aucune valeur . (Il n'est même pas correct de dire qu'il a la valeur undefined- un élément de tableau contenant la undefinedvaleur est différent d'un élément de tableau qui manque entièrement.)

Il n'y a pas moyen de représenter cela uniquement avec des chiffres, le moteur JavaScript est donc obligé d'utiliser le format le moins optimisé. S'il a[1]contenait une valeur numérique comme les deux autres éléments, le tableau pourrait potentiellement être optimisé en un tableau de nombres uniquement.

Une autre raison pour laquelle un tableau doit être forcé dans le format désoptimisé peut être si vous essayez d'accéder à un élément en dehors des limites du tableau, comme indiqué dans la présentation.

La première boucle <=tente de lire un élément au-delà de la fin du tableau. L'algorithme fonctionne toujours correctement, car dans la dernière itération supplémentaire:

• this.primes[i]évalue undefinedcomme iétant au-delà de la fin du tableau.
• candidate % undefined(pour toute valeur de candidate) prend la valeur NaN.
• NaN == 0évalue à false.
• Par conséquent, le return truen'est pas exécuté.

C'est comme si l'itération supplémentaire ne s'était jamais produite - cela n'a aucun effet sur le reste de la logique. Le code produit le même résultat que sans l'itération supplémentaire.

Mais pour y arriver, il a essayé de lire un élément inexistant au-delà de la fin du tableau. Cela force le tableau à sortir de l'optimisation - ou du moins l'a fait au moment de cet entretien.

La deuxième boucle <ne lit que les éléments qui existent dans le tableau, ce qui permet un tableau et un code optimisés.

Le problème est décrit dans les pages 90-91 de l'exposé, avec une discussion connexe dans les pages avant et après.

Il m'est arrivé d'assister à cette présentation très Google I / O et de parler avec l'orateur (l'un des auteurs du V8) par la suite. J'avais utilisé une technique dans mon propre code qui impliquait de lire au-delà de la fin d'un tableau comme une tentative malavisée (avec le recul) d'optimiser une situation particulière. Il a confirmé que si vous essayiez de lire même au- delà de la fin d'un tableau, cela empêcherait l'utilisation du simple format optimisé.

Si ce que l'auteur du V8 a dit est toujours vrai, alors la lecture au-delà de la fin du tableau l'empêcherait d'être optimisé et il devrait revenir au format plus lent.

Maintenant, il est possible que V8 ait été amélioré entre-temps pour gérer efficacement ce cas, ou que d'autres moteurs JavaScript le gèrent différemment. Je ne sais pas d'une manière ou d'une autre à ce sujet, mais c'est de cette désoptimisation que parlait la présentation.

TL; DR La boucle plus lente est due à l'accès au tableau `` hors limites '', ce qui oblige le moteur à recompiler la fonction avec moins ou même pas d'optimisations OU à ne pas compiler la fonction avec l'une de ces optimisations pour commencer ( si le compilateur (JIT-) a détecté / suspecté cette condition avant la première compilation 'version'), lisez ci-dessous pourquoi;

Exemple 1:
un Dense Array(étant contigu (signifie sans espaces entre les index) ET en fait un élément à chaque index) de 5 éléments utilisant une indexation basée sur 0 (toujours dans ES262).

var arr_five_char=['a', 'b', 'c', 'd', 'e']; // arr_five_char.length === 5
//  indexes are:    0 ,  1 ,  2 ,  3 ,  4    // there is NO index number 5

Ainsi, nous ne parlons pas vraiment de différence de performance entre <vs <=(ou «une itération supplémentaire»), mais nous parlons:
«pourquoi l'extrait correct (b) est-il plus rapide que l'extrait erroné (a)»?

La réponse est double (bien que du point de vue d'un réalisateur de langage ES262, les deux sont des formes d'optimisation):

1. Représentation de données: comment représenter / stocker le tableau en interne en mémoire (objet, hashmap, tableau numérique `` réel '', etc.)
2. Code-machine fonctionnel: comment compiler le code qui accède / gère (lire / modifier) ​​ces 'tableaux'

Le point 1 est suffisamment (et correctement IMHO) expliqué par la réponse acceptée , mais cela ne passe que 2 mots («le code») sur le point 2: compilation .

Plus précisément: JIT-Compilation et encore plus JIT- RE -Compilation!

La spécification du langage est essentiellement une description d'un ensemble d'algorithmes («étapes à effectuer pour obtenir un résultat final défini»). Ce qui, en fait, est une très belle façon de décrire une langue. Et cela laisse la méthode utilisée par un moteur pour obtenir des résultats spécifiés ouverte aux implémenteurs, ce qui donne amplement l'occasion de trouver des moyens plus efficaces pour produire des résultats définis. Un moteur conforme aux spécifications doit donner des résultats conformes aux spécifications pour toute entrée définie.

Maintenant, avec l'augmentation du code javascript / bibliothèques / utilisation et en se souvenant de la quantité de ressources (temps / mémoire / etc) qu'un `` vrai '' compilateur utilise, il est clair que nous ne pouvons pas obliger les utilisateurs visitant une page Web à attendre aussi longtemps (et à en avoir besoin d'avoir autant de ressources disponibles).

Imaginez la fonction simple suivante:

function sum(arr){
  var r=0, i=0;
  for(;i<arr.length;) r+=arr[i++];
  return r;
}

Parfaitement clair, non? Ne nécessite AUCUNE clarification supplémentaire, non? Le type de retour est Number, non?
Eh bien ... non, non et non ... Cela dépend de l'argument que vous passez au paramètre de fonction nommée arr...

sum('abcde');   // String('0abcde')
sum([1,2,3]);   // Number(6)
sum([1,,3]);    // Number(NaN)
sum(['1',,3]);  // String('01undefined3')
sum([1,,'3']);  // String('NaN3')
sum([1,2,{valueOf:function(){return this.val}, val:6}]);  // Number(9)
var val=5; sum([1,2,{valueOf:function(){return val}}]);   // Number(8)

Vous voyez le problème? Alors considérez que c'est à peine gratter les permutations massives possibles ... Nous ne savons même pas quel type de TYPE la fonction RETURN jusqu'à ce que nous ayons terminé ...

Maintenant, imaginez que ce même code de fonction soit réellement utilisé sur différents types ou même des variations d'entrée, à la fois complètement littéralement (dans le code source) décrites et dynamiquement générées dans le programme.

Ainsi, si vous deviez compiler la fonction sumJUSTE UNE FOIS, alors la seule façon qui renvoie toujours le résultat défini par les spécifications pour tous les types d'entrée, alors, évidemment, seulement en exécutant TOUTES les sous-étapes principales ET prescrites par les spécifications peuvent garantir des résultats conformes aux spécifications. (comme un navigateur pré-y2k sans nom). Aucune optimisation (car aucune hypothèse) et le langage de script interprété très lent reste.

JIT-Compilation (JIT comme dans Just In Time) est la solution actuellement populaire.

Ainsi, vous commencez à compiler la fonction en utilisant des hypothèses concernant ce qu'elle fait, retourne et accepte.
vous proposez des vérifications aussi simples que possible pour détecter si la fonction peut commencer à renvoyer des résultats non conformes aux spécifications (comme parce qu'elle reçoit une entrée inattendue). Ensuite, jetez le résultat compilé précédent et recompilez-le en quelque chose de plus élaboré, décidez quoi faire avec le résultat partiel que vous avez déjà (est-il valide d'être approuvé ou de calculer à nouveau pour être sûr), reliez la fonction au programme et réessayer. En fin de compte, revenir à l'interprétation de script pas à pas comme dans les spécifications

Tout cela prend du temps!

Tous les navigateurs fonctionnent sur leurs moteurs, pour chaque sous-version, vous verrez les choses s'améliorer et régresser. Les chaînes étaient à un moment donné de l'histoire des chaînes vraiment immuables (donc array.join était plus rapide que la concaténation de chaînes), maintenant nous utilisons des cordes (ou similaires) qui atténuent le problème. Les deux renvoient des résultats conformes aux spécifications et c'est ce qui compte!

Pour faire court: ce n'est pas parce que la sémantique du langage javascript nous a souvent soutenu (comme avec ce bogue silencieux dans l'exemple de l'OP) que des erreurs «stupides» augmentent nos chances que le compilateur crache du code machine rapide. Cela suppose que nous avons écrit les instructions `` généralement '' correctes: le mantra actuel que nous `` utilisateurs '' (du langage de programmation) devons avoir est: aider le compilateur, décrire ce que nous voulons, privilégier les idiomes courants (prendre des indices d'asp.js pour une compréhension de base ce que les navigateurs peuvent essayer d'optimiser et pourquoi).

Pour cette raison, parler de performance est à la fois important MAIS AUSSI un champ de mines (et à cause de ce champ de mines, je veux vraiment terminer en pointant (et en citant) des informations pertinentes:

L'accès aux propriétés d'objet inexistantes et aux éléments de tableau hors limites renvoie la undefinedvaleur au lieu de déclencher une exception. Ces fonctionnalités dynamiques rendent la programmation en JavaScript pratique, mais elles rendent également difficile la compilation de JavaScript en code machine efficace.

...

Une prémisse importante pour une optimisation JIT efficace est que les programmeurs utilisent les fonctionnalités dynamiques de JavaScript de manière systématique. Par exemple, les compilateurs JIT exploitent le fait que les propriétés d'objet sont souvent ajoutées à un objet d'un type donné dans un ordre spécifique ou que les accès aux tableaux hors limites se produisent rarement. Les compilateurs JIT exploitent ces hypothèses de régularité pour générer un code machine efficace lors de l'exécution. Si un bloc de code satisfait les hypothèses, le moteur JavaScript exécute un code machine efficace et généré. Sinon, le moteur doit revenir à un code plus lent ou à interpréter le programme.

Source:
«JITProf: Pinpointing JIT-Unfriendly JavaScript Code»
, publication Berkeley, 2014, par Liang Gong, Michael Pradel, Koushik Sen.
http://software-lab.org/publications/jitprof_tr_aug3_2014.pdf

ASM.JS (n'aime pas non plus l'accès hors tableau lié):

Compilation d'avance

Comme asm.js est un sous-ensemble strict de JavaScript, cette spécification définit uniquement la logique de validation - la sémantique d'exécution est simplement celle de JavaScript. Cependant, asm.js validé peut être compilé à l'avance (AOT). De plus, le code généré par un compilateur AOT peut être assez efficace, avec:

• représentations sans boîte d'entiers et de nombres à virgule flottante;
• absence de vérification du type d'exécution;
• absence de collecte des ordures; et
• charges de tas et magasins efficaces (avec des stratégies de mise en œuvre variant selon la plate-forme).

Le code dont la validation échoue doit revenir à l'exécution par des moyens traditionnels, par exemple, interprétation et / ou compilation juste à temps (JIT).

http://asmjs.org/spec/latest/

et enfin https://blogs.windows.com/msedgedev/2015/05/07/bringing-asm-js-to-chakra-microsoft-edge/
il y a une petite sous-section sur les améliorations des performances internes du moteur lors de la suppression des limites- check (tout en soulevant simplement les limites-check en dehors de la boucle avait déjà une amélioration de 40%).

EDIT:
notez que plusieurs sources parlent de différents niveaux de JIT-Recompilation jusqu'à l'interprétation.

Exemple théorique basé sur les informations ci-dessus, concernant l'extrait de l'OP:

• Appel à isPrimeDivisible
• Compilez isPrimeDivisible en utilisant des hypothèses générales (comme aucun accès hors limites)
• Faire du travail
• BAM, tout à coup le tableau accède hors limites (juste à la fin).
• Merde, dit le moteur, recompilons ce isPrimeDivisible en utilisant différentes hypothèses (moins), et cet exemple de moteur n'essaie pas de déterminer s'il peut réutiliser le résultat partiel actuel, donc
• Recalculez tout le travail en utilisant une fonction plus lente (j'espère que cela se termine, sinon répétez et cette fois, interprétez simplement le code).
• Résultat de retour

Le temps était donc:
Première exécution (échec à la fin) + refaire tout le travail en utilisant un code machine plus lent pour chaque itération + la recompilation, etc. prend clairement> 2 fois plus de temps dans cet exemple théorique !

EDIT 2: (avertissement: conjecture basée sur les faits ci-dessous)
Plus j'y pense, plus je pense que cette réponse pourrait en fait expliquer la raison la plus dominante de cette `` pénalité '' sur l'extrait erroné a (ou bonus de performance sur l'extrait b , en fonction de la façon dont vous y pensez), précisément pourquoi j'adore l'appeler (extrait a) une erreur de programmation:

Il est assez tentant de supposer qu'il this.primess'agit d'un `` tableau dense '' numérique pur qui était soit

• Littéral codé en dur dans le code source (excellent candidat connu pour devenir un tableau `` réel '' car tout est déjà connu du compilateur avant la compilation) OU
• très probablement généré à l'aide d'une fonction numérique remplissant un pré-dimensionné ( new Array(/*size value*/)) dans un ordre séquentiel croissant (un autre candidat connu depuis longtemps pour devenir un tableau «réel»).

Nous savons également que la primeslongueur du tableau est mise en cache comme prime_count! (indiquant son intention et sa taille fixe).

Nous savons également que la plupart des moteurs transmettent initialement les tableaux en tant que copie lors de la modification (si nécessaire), ce qui rend leur gestion beaucoup plus rapide (si vous ne les modifiez pas).

Il est donc raisonnable de supposer que Array primesest très probablement déjà un tableau optimisé en interne qui ne sera pas changé après la création (simple à savoir pour le compilateur s'il n'y a pas de code modifiant le tableau après la création) et donc déjà (si applicable à le moteur) stocké de manière optimisée, à peu près comme s'il s'agissait d'un fichier Typed Array.

Comme j'ai essayé de le clarifier avec mon sumexemple de fonction, le ou les arguments qui sont passés influencent fortement ce qui doit réellement se produire et, en tant que tel, comment ce code particulier est compilé en code machine. Passer un Stringà la sumfonction ne devrait pas changer la chaîne mais changer la façon dont la fonction est compilée en JIT! Passer un tableau à sumdevrait compiler une version différente (peut-être même supplémentaire pour ce type, ou «forme» comme on l'appelle, de l'objet qui a été passé) du code machine.

Comme il semble un peu bonkus de convertir le tableau de type Typed_Array primesà la volée en quelque chose_else alors que le compilateur sait que cette fonction ne va même pas le modifier!

Sous ces hypothèses cela laisse 2 options:

1. Compilez comme number-cruncher en supposant qu'il n'y a pas de hors-limites, rencontrez un problème de hors-limites à la fin, recompilez et refaites le travail (comme indiqué dans l'exemple théorique de l'édition 1 ci-dessus)
2. Le compilateur a déjà détecté (ou suspecté?) Un accès lié à l'avance et la fonction a été compilée par JIT comme si l'argument passé était un objet clairsemé entraînant un code machine fonctionnel plus lent (car il aurait plus de vérifications / conversions / coercitions etc.). En d'autres termes: la fonction n'a jamais été éligible pour certaines optimisations, elle a été compilée comme si elle recevait un argument 'sparse array' (- like).

Je me demande maintenant vraiment lequel de ces 2 il s'agit!

Pour y ajouter un peu de science, voici un jsperf

https://jsperf.com/ints-values-in-out-of-array-bounds

Il teste le cas de contrôle d'un tableau rempli d'entiers et de boucles faisant de l'arithmétique modulaire tout en restant dans les limites. Il a 5 cas de test:

• 1. Boucle hors limites
• 2. Tableaux Holey
• 3. Arithmétique modulaire par rapport aux NaN
• 4. Valeurs totalement indéfinies
• 5. À l'aide d'un new Array()

Cela montre que les 4 premiers cas sont vraiment mauvais pour les performances. La boucle hors limites est un peu meilleure que les 3 autres, mais les 4 sont environ 98% plus lentes que le meilleur des cas.
Le new Array()boîtier est presque aussi bon que le tableau brut, juste quelques pour cent plus lent.