Écrire du code Javascript haute performance sans se désoptimiser

10

Lors de l'écriture de code sensible aux performances en Javascript qui fonctionne sur de grands tableaux numériques (pensez à un package d'algèbre linéaire, fonctionnant sur des nombres entiers ou à virgule flottante), on veut toujours que le JIT aide autant que possible. En gros, cela signifie:

  1. Nous voulons toujours que nos tableaux soient des SMI compressés (petits entiers) ou des doublons compressés, selon que nous effectuons des calculs entiers ou à virgule flottante.
  2. Nous voulons toujours transmettre le même type de chose aux fonctions, afin qu'elles ne soient pas étiquetées "mégamorphiques" et désoptimisées. Par exemple, nous voulons toujours appeler vec.add(x, y)avec les deux xet yêtre des tableaux SMI compressés, ou les deux tableaux doubles compressés.
  3. Nous voulons que les fonctions soient intégrées autant que possible.

Lorsque l'on s'éloigne de ces cas, une baisse soudaine et drastique des performances se produit. Cela peut se produire pour diverses raisons anodines:

  1. Vous pouvez transformer une baie SMI compressée en une baie Double compressée via une opération apparemment inoffensive, comme l'équivalent de myArray.map(x => -x). Il s'agit en fait du "meilleur" mauvais cas, car les tableaux doubles compressés sont toujours très rapides.
  2. Vous pouvez transformer un tableau compressé en un tableau générique encadré, par exemple en mappant le tableau sur une fonction qui (de manière inattendue) a renvoyé nullou undefined. Ce mauvais cas est assez facile à éviter.
  3. Vous pouvez désoptimiser une fonction entière, par exemple vec.add()en passant trop de types de choses et en les rendant mégamorphiques. Cela peut arriver si vous voulez faire de la "programmation générique", où vec.add()est utilisé à la fois dans les cas où vous ne faites pas attention aux types (donc il voit beaucoup de types entrer) et dans les cas où vous voulez augmenter les performances maximales (par exemple, il ne devrait recevoir que des doubles en boîte).

Ma question est plus une question douce, sur la façon dont on écrit du code Javascript haute performance à la lumière des considérations ci-dessus, tout en gardant le code agréable et lisible. Quelques sous-questions spécifiques pour que vous sachiez quel type de réponse je vise:

  • Existe-t-il un ensemble de directives sur la façon de programmer tout en restant dans le monde des baies SMI emballées (par exemple)?
  • Est-il possible de faire de la programmation générique haute performance en Javascript sans utiliser quelque chose comme un système de macro pour incorporer des choses comme vec.add()dans les sites d'appels?
  • Comment peut-on modulariser du code haute performance en bibliothèques à la lumière de choses comme les sites d'appel mégamorphiques et les désoptimisations? Par exemple, si j'utilise avec bonheur le package d'algèbre linéaire Aà haute vitesse, puis que j'importe un package Bqui en dépend A, mais l' Bappelle avec d'autres types et le désoptimise, soudainement (sans que mon code change), mon code s'exécute plus lentement.
  • Existe-t-il de bons outils de mesure faciles à utiliser pour vérifier ce que le moteur Javascript fait en interne avec les types?
Joppy
la source
1
C'est un sujet très intéressant et un article très bien écrit qui montre que vous avez correctement fait votre part de recherche. Cependant, je crains que la ou les questions soient beaucoup trop larges pour le format SO, et qu'elles attireront inévitablement plus d'opinions que de faits. L'optimisation du code est une question très compliquée, et deux versions d'un moteur peuvent ne pas se comporter de la même manière. Je pense qu'il y a une des personnes responsables du V8 JIT qui traîne parfois, alors peut-être qu'ils pourraient donner une bonne réponse pour leur moteur, mais même pour eux, je pense que ce serait trop large d'un sujet pour un seul Q / A .
Kaiido
"Ma question est plus une question douce, sur la façon dont on écrit du code Javascript haute performance ..." En passant, notez que javascript prévoit la génération de processus d'arrière-plan (travailleurs Web), et il existe également des bibliothèques qui le GPU (tensorflow.js et gpu.js) offrant des moyens autres que de s'appuyer uniquement sur la compilation pour augmenter le débit de calcul d'une application basée sur javascript ...
Jon Trent
@JonTrent En fait, j'ai menti un peu dans mon post, je ne me soucie pas tellement des applications d'algèbre linéaire classique, mais plus de l'algèbre informatique sur les entiers. Cela signifie que de nombreux packages numériques existants sont immédiatement exclus, car (par exemple) lors de la réduction d'une ligne d'une matrice, ils peuvent être divisés par 2, ce qui n'est "pas autorisé" dans le monde dans lequel je travaille depuis (1/2) n'est pas un entier. J'ai pris en compte les travailleurs du Web (en particulier pour quelques calculs de longue durée que je souhaite annuler), mais le problème que je résout ici est de réduire suffisamment la latence pour être réactif à l'interaction.
Joppy
Pour l'arithmétique entière en JavaScript, vous regardez probablement le code de style asm.js, à peu près "mettant une |0derrière chaque opération". Ce n'est pas joli, mais le mieux que vous puissiez faire dans un langage qui n'a pas de nombres entiers appropriés. Vous pouvez également utiliser BigInts, mais à ce jour, ils ne sont pas très rapides dans aucun des moteurs courants (principalement en raison du manque de demande).
jmrk

Réponses:

8

Développeur V8 ici. Compte tenu de l'intérêt suscité par cette question et du manque d'autres réponses, je peux tenter le coup; J'ai bien peur que ce ne soit pas la réponse que vous espériez.

Existe-t-il un ensemble de directives sur la façon de programmer tout en restant dans le monde des baies SMI emballées (par exemple)?

Réponse courte: il est ici: const guidelines = ["keep your integers small enough"].

Réponse plus longue: il est difficile de donner un ensemble complet de directives pour diverses raisons. En général, nous pensons que les développeurs JavaScript doivent écrire du code qui a du sens pour eux et leur cas d'utilisation, et les développeurs de moteurs JavaScript doivent comprendre comment exécuter ce code rapidement sur leurs moteurs. D'un autre côté, il y a évidemment des limites à cet idéal, dans le sens où certains modèles de codage auront toujours des coûts de performance plus élevés que d'autres, quels que soient les choix d'implémentation du moteur et les efforts d'optimisation.

Lorsque nous parlons de conseils sur les performances, nous essayons de garder cela à l'esprit et d'estimer soigneusement les recommandations qui ont une forte probabilité de rester valables sur de nombreux moteurs et de nombreuses années, et sont également raisonnablement idiomatiques / non intrusives.

Revenons à l'exemple: l'utilisation de Smis en interne est censée être un détail d'implémentation que le code utilisateur n'a pas besoin de connaître. Cela rendra certains cas plus efficaces et ne devrait pas faire de mal dans d'autres cas. Tous les moteurs n'utilisent pas Smis (par exemple, AFAIK Firefox / Spidermonkey n'a pas historiquement; j'ai entendu dire que dans certains cas, ils utilisent Smis de nos jours; mais je ne connais aucun détail et je ne peux parler avec aucune autorité sur la question). Dans V8, la taille de Smis est un détail interne et a en fait changé au fil du temps et des versions. Sur les plates-formes 32 bits, qui étaient le cas d'utilisation majoritaire, les Smis ont toujours été des entiers signés 31 bits; sur les plates-formes 64 bits, il s'agissait auparavant d'entiers signés 32 bits, ce qui semblait récemment être le cas le plus courant, jusqu'à ce que dans Chrome 80, nous livrions la "compression de pointeur" pour les architectures 64 bits, qui nécessitaient de réduire la taille Smi aux 31 bits connus des plates-formes 32 bits. S'il vous arrivait d'avoir basé une implémentation sur l'hypothèse que les Smis sont généralement 32 bits, vous auriez des situations malheureuses commeça .

Heureusement, comme vous l'avez noté, les tableaux doubles sont toujours très rapides. Pour le code lourd en chiffres, il est probablement logique de supposer / cibler des tableaux doubles. Étant donné la prévalence des doubles en JavaScript, il est raisonnable de supposer que tous les moteurs ont un bon support pour les doubles et les doubles tableaux.

Est-il possible de faire de la programmation générique haute performance en Javascript sans utiliser quelque chose comme un système de macro pour intégrer des choses comme vec.add () dans les sites d'appels?

«générique» est généralement en contradiction avec «haute performance». Ceci n'est pas lié à JavaScript ou à des implémentations de moteur spécifiques.

Le code "générique" signifie que les décisions doivent être prises au moment de l'exécution. Chaque fois que vous exécutez une fonction, le code doit s'exécuter pour déterminer, par exemple, "est xun entier? Si c'est le cas, prenez ce chemin de code. Est-ce xune chaîne? Sautez par-dessus ici. Est-ce un objet? Est-ce qu'il a .valueOf? Non? Alors Peut .toString()- être ? Peut-être sur sa chaîne prototype? Appelez ça, et recommencez depuis le début avec son résultat ". Le code optimisé "hautes performances" repose essentiellement sur l'idée de supprimer tous ces contrôles dynamiques; cela n'est possible que lorsque le moteur / compilateur a un moyen d'inférer les types à l'avance: s'il peut prouver (ou supposer avec une probabilité suffisamment élevée) qu'il xva toujours être un entier, alors il n'a qu'à générer du code pour ce cas ( gardé par une vérification de type si des hypothèses non prouvées étaient impliquées).

L'incrustation est orthogonale à tout cela. Une fonction "générique" peut toujours être intégrée. Dans certains cas, le compilateur peut être capable de propager des informations de type dans la fonction en ligne pour y réduire le polymorphisme.

(À titre de comparaison: C ++, étant un langage compilé statiquement, possède des modèles pour résoudre un problème connexe. En bref, ils permettent au programmeur de demander explicitement au compilateur de créer des copies spécialisées de fonctions (ou de classes entières), paramétrées sur des types donnés. belle solution dans certains cas, mais pas sans son propre ensemble d'inconvénients, par exemple de longs temps de compilation et de gros fichiers binaires. JavaScript, bien sûr, n'a pas de modèles. Vous pouvez utiliser evalpour construire un système quelque peu similaire, mais ensuite vous aurait des inconvénients similaires: vous devriez faire l'équivalent du travail du compilateur C ++ lors de l'exécution, et vous devriez vous soucier de la quantité de code que vous générez.)

Comment peut-on modulariser du code haute performance en librairies à la lumière de choses comme les sites d'appel mégamorphiques et les désoptimisations? Par exemple, si j'utilise avec bonheur le package d'algèbre linéaire A à grande vitesse, puis que j'importe un package B qui dépend de A, mais B l'appelle avec d'autres types et le désoptimise, soudainement (sans que mon code change), mon code s'exécute plus lentement .

Oui, c'est un problème général avec JavaScript. La V8 avait l'habitude d'implémenter certaines fonctions internes (des choses comme Array.sort) en JavaScript en interne, et ce problème (que nous appelons "pollution par rétroaction de type") était l'une des principales raisons pour lesquelles nous nous sommes complètement éloignés de cette technique.

Cela dit, pour le code numérique, il n'y a pas beaucoup de types (seulement Smis et doubles), et comme vous l'avez noté, ils devraient avoir des performances similaires dans la pratique, donc bien que la pollution par rétroaction de type soit en effet une préoccupation théorique, et dans certains cas, peut avoir un impact significatif, il est également assez probable que dans les scénarios d'algèbre linéaire, vous ne verrez pas de différence mesurable.

De plus, à l'intérieur du moteur, il y a beaucoup plus de situations que "un type == rapide" et "plus d'un type == lent". Si une opération donnée a vu à la fois des Smis et des doubles, c'est très bien. Le chargement d'éléments à partir de deux types de tableaux convient également. Nous utilisons le terme "mégamorphique" pour la situation où une charge a vu tellement de types différents qu'elle est abandonnée pour les suivre individuellement et utilise à la place un mécanisme plus générique qui s'adapte mieux à un grand nombre de types - une fonction contenant de telles charges peut toujours optimisé. Une "désoptimisation" est l'acte très spécifique d'avoir à jeter du code optimisé pour une fonction parce qu'un nouveau type est vu qui n'a pas été vu auparavant, et que le code optimisé n'est donc pas équipé pour gérer. Mais même ça va: il suffit de revenir au code non optimisé pour collecter plus de commentaires de type et d'optimiser à nouveau plus tard. Si cela se produit plusieurs fois, il n'y a rien à craindre; cela ne devient un problème que dans les cas pathologiquement mauvais.

Donc, le résumé de tout cela: ne vous inquiétez pas . Écrivez simplement du code raisonnable, laissez le moteur s'en occuper. Et par "raisonnable", je veux dire: ce qui a du sens pour votre cas d'utilisation, est lisible, maintenable, utilise des algorithmes efficaces, ne contient pas de bogues comme la lecture au-delà de la longueur des tableaux. Idéalement, c'est tout ce qu'il y a à faire et vous n'avez rien d'autre à faire. Si cela vous fait vous sentir mieux de faire quelque chose et / ou si vous observez réellement des problèmes de performance, je peux vous proposer deux idées:

L'utilisation de TypeScript peut vous aider. Gros avertissement: les types de TypeScript visent la productivité du développeur et non les performances d'exécution (et il s'avère que ces deux perspectives ont des exigences très différentes d'un système de type). Cela dit, il y a un certain chevauchement: par exemple, si vous annotez régulièrement des choses comme number, le compilateur TS vous avertira si vous mettez accidentellement nulldans un tableau ou une fonction qui est censée contenir / fonctionner uniquement sur des nombres. Bien sûr, la discipline est toujours requise: une seule number_func(random_object as number)trappe d'échappement peut saper tout silencieusement, car l'exactitude des annotations de type n'est appliquée nulle part.

L'utilisation de TypedArrays peut également vous aider. Ils ont un peu plus de surcharge (consommation de mémoire et vitesse d'allocation) par baie par rapport aux baies JavaScript standard (donc si vous avez besoin de plusieurs petites baies, alors les baies régulières sont probablement plus efficaces), et elles sont moins flexibles car elles ne peuvent pas grandir ou rétrécir après allocation, mais ils garantissent que tous les éléments ont exactement un type.

Existe-t-il de bons outils de mesure faciles à utiliser pour vérifier ce que le moteur Javascript fait en interne avec les types?

Non, et c'est intentionnel. Comme expliqué ci-dessus, nous ne voulons pas que vous adaptiez spécifiquement votre code aux modèles que V8 peut optimiser particulièrement bien aujourd'hui, et nous ne pensons pas que vous souhaitiez vraiment le faire non plus. Cet ensemble de choses peut changer dans les deux sens: s'il y a un modèle que vous aimeriez utiliser, nous pourrions l'optimiser pour cela dans une future version (nous avons déjà joué avec l'idée de stocker des entiers 32 bits non mis en boîte comme éléments de tableau .. . mais le travail sur ce point n'a pas encore commencé, donc aucune promesse); et parfois, s'il y a un modèle que nous avons utilisé pour l'optimisation dans le passé, nous pourrions décider de l'abandonner s'il gêne d'autres optimisations plus importantes / ayant un impact. En outre, des choses comme l'heuristique en ligne sont notoirement difficiles à obtenir correctement, ainsi, prendre la bonne décision en ligne au bon moment est un domaine de recherche continue et des changements correspondants dans le comportement du moteur / compilateur; ce qui en fait un autre cas où il serait regrettable pour tout le monde (vouset nous) si vous avez passé beaucoup de temps à peaufiner votre code jusqu'à ce qu'un certain ensemble de versions de navigateur actuelles fasse à peu près les décisions en ligne que vous pensez (ou savez?) sont les meilleures, pour revenir une demi-année plus tard pour réaliser que les navigateurs actuels ont changé leur heuristique.

Bien sûr, vous pouvez toujours mesurer les performances de votre application dans son ensemble - c'est ce qui compte en fin de compte, et non les choix spécifiques du moteur effectués en interne. Méfiez-vous des microbenchmarks, car ils sont trompeurs: si vous extrayez seulement deux lignes de code et que vous les comparez, il y a de fortes chances que le scénario soit suffisamment différent (par exemple, un type de rétroaction différent) pour que le moteur prenne des décisions très différentes.

jmrk
la source
2
Merci pour cette excellente réponse, elle confirme bon nombre de mes soupçons sur la façon dont les choses fonctionnent, et surtout sur la façon dont elles sont censées fonctionner. Soit dit en passant, y a-t-il des articles de blog, etc. sur le problème de "rétroaction de type" dont vous avez parlé Array.sort()? J'aimerais lire un peu plus à ce sujet.
Joppy
Je ne pense pas que nous ayons blogué sur cet aspect particulier. C'est essentiellement ce que vous avez décrit dans votre question vous-même: lorsque les buildins sont implémentés en JavaScript, ils sont "comme une bibliothèque" dans le sens où si différents morceaux de code les appellent avec différents types, alors les performances peuvent en souffrir - parfois juste un peu, parfois plus. Ce n'était pas le seul, et sans doute même pas le plus gros problème avec cette technique; Je voulais surtout dire que je connais bien la question générale.
jmrk