Bonjour, Habr! Je vous présente la traduction de l'article "Trous de ver en JavaScript" de Mathius Buus.
Les ordinateurs sont des machines intéressantes. En théorie, ils nous semblent être des mathématiciens mécaniques idéaux travaillant avec des nombres et effectuant bien des opérations d'addition, de multiplication et de soustraction.
Cependant, une telle abstraction est assez trompeuse. Cela nous éloigne de la compréhension qu'un ordinateur traite différentes opérations mathématiques à différentes vitesses. Si vous écrivez en JavaScript (ou dans tout autre langage) et que vous vous souciez des performances des algorithmes que vous avez écrits, il est très important de comprendre comment les ordinateurs fonctionnent sous le capot.
Si nous savons de quoi l'ordinateur est capable, nous pouvons utiliser les chemins les plus courts ou les trous de ver pour rendre nos programmes beaucoup plus rapides que prévu.
Wormhole dans l'opération d'obtention du reste de la division
Qu'est-ce que cela signifie exactement? Regardons un exemple: imaginons que nous voulons implémenter une liste de sonnerie . Une liste en anneau est une liste de taille fixe dans laquelle des insertions plus grandes que la taille de la liste sont déplacées vers le haut de la liste et dans un cercle. Les listes de sonnerie sont très pratiques pour de nombreuses choses - telles que la collecte de statistiques pour des intervalles de temps spécifiques, la mise en mémoire tampon des données, etc., mais regardez cette implémentation:
const list = new Array(15000) function set (i, item) {
À quelle vitesse ce code s'exécute-t-il? Lançons un test de vitesse simple
console.time() for (var i = 0; i < 1e9; i++) { set(i, i) } console.timeEnd()
Sur mon ordinateur, il a fallu environ 4 secondes pour 1 milliard d'inserts. Pas mal.
Cependant, appliquons un trou de ver de calcul et changeons la taille du tableau en nombre magique:
// 15000 16384 const list = new Array(16384) function set (i, item) { // % - , // // , i list[i % list.length] = item }
Essayons de relancer le test de performances. Sur mon ordinateur, le test s'est terminé en environ 1,5 seconde. Plus du double d'augmentation grâce à un simple redimensionnement. Afin de comprendre pourquoi cela se produit, nous devons comprendre ce qui suit, sous le capot, l'ordinateur fonctionne avec des nombres de base 2. Il est important de savoir si nous obtenons le reste de la division (% d'opération). Un tel calcul est beaucoup plus simple si le nombre est un multiple de 2 (2 ^ n) b 16384 c'est 2 ^ 14. En fait, l'ordinateur regarde le nombre sous forme binaire et prend simplement les n derniers bits.
Par exemple: que se passera-t-il lorsqu'une telle opération sera effectuée 353 500% 16 384? 353 500 en représentation binaire ressemblera à 1010110010011011100. Depuis 16384 == 2 ^ 14 - nous devons prendre les 14 derniers bits - 10101 (10010011011100) ou 9 346.
Nous pouvons utiliser ces connaissances par rapport à un autre trou de ver. Pour un ordinateur, il est très simple et rapide de prendre les n derniers bits. En fait, il suffit de produire binaire et (opération &) avec le nombre (2 ^ n) - 1
const list = new Array(16384) function set (i, item) {
En exécutant à nouveau le test de performances sur mon ordinateur, nous verrons que le temps d'exécution diminuera à ~ 1 s ou qu'il y aura une multiplication par quatre des performances par rapport à la première exécution. Et tout cela grâce à une compréhension du fonctionnement de l'ordinateur.
Les compilateurs intelligents ou les machines virtuelles peuvent effectuer ce type d'optimisation en transformant l'opération consistant à obtenir le reste dans les coulisses en une opération au niveau du bit et vice versa. En fait, la dernière machine virtuelle V8 Javascript (non implémentée dans NodeJS) fait exactement cela.
Trou de ver numérique
Une autre taupe utile est de comprendre comment fonctionne la lecture et l'écriture des nombres. Rappelez-vous comment nous avons utilisé des ordinateurs 32 bits et comment nous avons obtenu 64 bits? Et jusqu'à 32 bits, nous avions 16 bits. Qu'est-ce que cela signifie exactement? Habituellement, nous pensons à cela de cette façon - combien de RAM nous avons sur l'ordinateur. 2 ^ 32 = 4294967296 ou 4 Go, ce qui signifie que nous ne pouvons accéder qu'à 4 Go de mémoire sur un ordinateur 32 bits. Lorsque nous écrivons un programme JS, nous n'avons généralement pas besoin d'y penser, car nous n'utilisons généralement pas autant de mémoire.
Cependant, il est très important de comprendre la différence entre les ordinateurs 32 bits et 64 bits. Étant donné que les processeurs ont reçu des registres 64 bits sur les ordinateurs 64 bits, les opérations sont devenues 2 fois plus rapides que sur les ordinateurs 32 bits, où vous n'aviez que des registres 32 bits.
Comment pouvons-nous utiliser les informations sur ce trou de ver?
Écrivons un programme simple qui copie un Uint8Array dans un autre. Si vous n'êtes pas familier avec les tableaux Unit8Arrays, ils sont très similaires aux tampons dans NodeJS, ou tout simplement "nettoyer" la mémoire.
function copy (input, output) { // input.length <= output.length for (var i = 0; i < input.length; i++) { // 8- (byte) output[i] = input[i] } }
Encore une fois, mesurons la vitesse en exécutant un test de performances.
// 1MB Uint8Arrays const input = new Uint8Array(1024 * 1024) const output = new Uint8Array(1024 * 1024) console.time() for (var i = 0; i < 1e4; i++) { copy(input, output) } console.timeEnd()
Sur mon ordinateur, le programme s'est terminé en environ 7,5 secondes. Comment pouvons-nous utiliser un trou de ver pour accélérer? En utilisant Uint8Array, nous ne copions que 8 bits à la fois, mais ayant un ordinateur 64 bits, nous pouvons copier 64 bits d'informations en même temps. Nous pouvons le faire en JavaScript en convertissant notre Uint8Array en Float64Array avant la copie, ce qui ne nous coûtera rien.
function copy (input, output) { // input.length <= output.length // 64- // , // 64- // BigInts JavaScript, BigInt64Array. const input64 = new Float64Array(input.buffer, input.byteOffset, input.length / 8) const output64 = new Float64Array(output.buffer, output.byteOffset, output.length / 8) for (var i = 0; i < input64.length; i++) { // 64- output64[i] = input64[i] } }
En exécutant à nouveau des tests de performances, nous obtenons un temps d'exécution de 1 seconde, ce qui donne une augmentation de 8 fois la vitesse.
Pour la copie, une solution acceptable serait d'utiliser la méthode array.set (otherArray) pour Uint8Array, qui nous permet de copier en code natif - ce qui est beaucoup plus rapide que tout autre trou de ver. Pour référence, cela donnera un résultat de ~ 0,2 sec d'exécution dans notre test sur mon ordinateur, ce qui est 5 fois plus rapide que la solution précédente.
Une galaxie de JavaScript regorge de trous de ver
L'utilisation des trous de ver ci-dessus vous aidera à rendre beaucoup plus rapide des tonnes d'algorithmes du monde réel. Il existe de nombreux autres trous de ver. Mon préféré est Math.clz32 , une méthode qui renvoie le nombre de bits de début zéro dans une représentation binaire 32 bits d'un nombre. Nous pouvons utiliser cette méthode pour de nombreux algorithmes intéressants. Je l'ai utilisé pour accélérer la mise en œuvre des champs de bits de 4 fois, ce qui a entraîné une diminution de la consommation de mémoire de 4 fois et m'a permis de trier les nombres dans certaines situations beaucoup plus rapidement.
Comprendre les principes de base de l'ordinateur vous permet d'Ă©crire les programmes les plus rapides dont nous avons besoin. Cette connaissance est importante mĂŞme lorsque vous Ă©crivez dans un langage de haut niveau tel que JavaScript.
PS:
Remerciements particuliers pour l'aide Ă la traduction et Ă l'ajustement de la traduction vers Olga Pereverzeva