Lua Conseils sur les performances en PDF


Télécharger Lua Conseils sur les performances en PDF

★★★★★★★★★★3.5 étoiles sur 5 basé sur 1 votes.
Votez ce document:

Télécharger aussi :


Lua Conseils sur les performances support de formation [Eng]

...

Dans Lua, comme dans tout autre langage de programmation, nous devrions toujours suivre les deux maximes de l'optimisation du programme:

Règle n ° 1: Ne le faites pas.

Règle n ° 2: Ne le faites pas encore. (pour les experts seulement)

Ces règles sont particulièrement pertinentes lors de la programmation en Lua. Lua est célèbre pour ses performances, et il mérite sa réputation parmi les langages de script.

Néanmoins, nous savons tous que la performance est un ingrédient clé du programme. Ce n'est pas un hasard si les problèmes liés à la complexité du temps exponentiel sont appelés intraitables. Un résultat trop tardif est un résultat inutile. Ainsi, tout bon programmeur doit toujours équilibrer les coûts de dépenser des ressources pour optimiser un morceau de code contre les gains d'économie de ressources lors de l'exécution de ce code.

La première question concernant l'optimisation d'un bon programmeur demande toujours: «Le programme doit-il être optimisé?» Si la réponse est positive (mais seulement alors), la deuxième question devrait être: ¢ â € "Où? Â ¢ â,¬

Pour répondre aux deux questions, nous avons besoin d'instruments. Nous ne devrions pas essayer d'optimiser le logiciel sans mesures appropriées. La différence entre les programmeurs expérimentés et les novices n'est pas que les programmeurs expérimentés sont mieux à repérer où un programme peut perdre son temps: La différence est que les programmeurs expérimentés savent qu'ils ne sont pas bons à cette tâche.

Il y a quelques années, Noemi Rodriguez et moi avons développé un prototype de CORBA ORB (Object Request Broker) à Lua, qui a ensuite évolué en OiL (Orb in Lua). En tant que premier prototype, la mise en œuvre visait la simplicité. Éviter

le besoin de bibliothèques C supplémentaires, les entiers sérialisés du prototype utilisant quelques opérations arithmétiques pour isoler chaque octet (conversion en base 256). Il n'a pas pris en charge les valeurs à virgule flottante. Parce que CORBA gère les chaînes comme des séquences de caractères, notre ORB convertit d'abord les chaînes Lua en une séquence (c'est-à-dire une table Lua) de caractères, puis gérait le résultat comme n'importe quelle autre séquence.

Lorsque nous avons terminé ce premier prototype, nous avons comparé ses performances avec un ORB professionnel implémenté en C ++. Nous nous attendions à ce que notre ORB soit un peu plus lent, car il a été implémenté à Lua, mais nous avons été déçus par la lenteur de son fonctionnement. Au début, nous venons de jeter le blâme sur Lua. Plus tard, nous avons soupçonné que le coupable pourrait être toutes ces opérations nécessaires pour sérialiser chaque numéro. Nous avons donc décidé de lancer le programme sous un profileur. Nous avons utilisé un profileur très simple, pas très différent de celui décrit au chapitre 23 de la programmation de Lua. Les résultats du profileur nous ont choqués. Contre notre intuition, la sérialisation des nombres n'avait aucun impact mesurable sur la performance, entre autres raisons parce qu'il n'y avait pas autant de nombres à sérialiser. La sérialisation des chaînes, cependant, était responsable d'une grande partie du temps total. Pratiquement chaque message CORBA a plusieurs chaînes, même lorsque nous ne manipulons pas explicitement les chaînes: les références d'objet, les noms de méthodes et certaines autres valeurs internes sont tous codés sous forme de chaînes. Et la sérialisation de chaque chaîne était une opération coûteuse, car elle devait créer une nouvelle table, la remplir avec chaque caractère individuel, puis sérialiser la séquence résultante, ce qui impliquait de sérialiser chaque caractère un par un. Une fois que nous avons réimplémenté la sérialisation des chaînes comme un cas particulier (au lieu d'utiliser le code générique pour les séquences), nous avons obtenu une accélération respectable. Avec quelques lignes de code supplémentaires, les performances de votre implémentation étaient comparables à celles de l'implémentation C ++.

Donc, nous devrions toujours mesurer lors de l'optimisation d'un programme pour la performance. Mesurez avant, pour savoir où optimiser. Et mesure après, pour savoir si l '«optimisation» a effectivement amélioré notre code.

Une fois que vous décidez que vous devez vraiment optimiser votre code Lua, ce texte peut vous aider à l'optimiser, principalement en montrant ce qui est lent et ce qui est rapide en Lua. Je ne discuterai pas ici de techniques générales d'optimisation, telles que de meilleurs algorithmes. Bien sûr, vous devez savoir et utiliser ces techniques, mais il existe plusieurs autres endroits où vous pouvez les apprendre. Dans cet article, je ne parlerai que des techniques propres à Lua. Le long de l'article, je vais constamment mesurer la performance dans le temps et l'espace de petits programmes. Sauf indication contraire, je fais toutes les mesures sur un Pentium IV 2.9 GHz avec 1 Go de mémoire principale, exécutant Ubuntu 7.10, Lua 5.1.1. Fréquemment, je donne des mesures réelles (par exemple, 7 secondes), mais ce qui est pertinent est la relation entre les différentes mesures. Quand je dis qu'un programme est "X% fois plus rapide" qu'un autre, cela signifie qu'il fonctionne dans X% moins de temps. (Un programme 100% plus rapide ne prendrait pas de temps à s'exécuter.) Quand je dis qu'un programme est «X fois moins rapide qu'un autre, je veux dire que l'autre est X% plus rapide. (Un programme 50% plus lent signifie que cela prend deux fois le temps.)

Faits basiques

Avant d'exécuter un code, Lua traduit (précompile) la source dans un format interne. Ce format est une séquence d'instructions pour une machine virtuelle, similaire au code machine pour une CPU réelle. Ce format interne est ensuite interprété par un code C qui est essentiellement une boucle while avec un gros commutateur à l'intérieur, un cas pour chaque instruction.

Peut-être avez-vous déjà lu quelque part que, depuis la version 5.0, Lua utilise une machine virtuelle basée sur un registre. Les "registres" de cette machine virtuelle ne correspondent pas à de vrais registres dans la CPU, car cette correspondance ne serait pas portable et assez limitée dans le nombre de registres disponibles. Au lieu de cela, Lua utilise une pile (implémentée sous la forme d'un tableau plus quelques index) pour accommoder ses registres. Chaque fonction active a un enregistrement d'activation, qui est une tranche de pile dans laquelle la fonction stocke ses registres. Ainsi, chaque fonction a ses propres registres2. Chaque fonction peut utiliser jusqu'à 250 registres, car chaque instruction n'a que 8 bits pour se référer à un registre.

Étant donné ce grand nombre de registres, le précompilateur Lua est capable de stocker toutes les variables locales dans les registres. Le résultat est que l'accès aux variables locales est très rapide à Lua. Par exemple, si a et b sont des variables locales, une instruction Lua comme a = a + b génère une seule instruction: ADD 0 0 1 (en supposant que a et b sont dans les registres 0 et 1, respectivement). Pour comparaison, si a et b étaient globaux, le code pour cette addition serait comme ceci:

GETGLOBAL 0 0 a

GETGLOBAL 1 1 b

AJOUTER 0 0 1

SETGLOBAL 0 0 a

Ainsi, il est facile de justifier l'une des règles les plus importantes pour améliorer la performance des programmes Lua: utiliser les locaux!

Si vous avez besoin de réduire les performances de votre programme, il existe plusieurs endroits où vous pouvez utiliser les locaux, en plus des locaux les plus évidents. Par exemple, si vous appelez une fonction dans une longue boucle, vous pouvez affecter la fonction à une variable locale. Par exemple, le code



pour i = 1, 1000000 fait le x local = math.sin (i)

court 30% plus lentement que celui-ci:

sin local = math.sin pour i = 1, 1000000 local x = sin (i) fin

L'accès aux locals externes (c'est-à-dire, les variables qui sont locales à une fonction englobante) n'est pas aussi rapide que l'accès aux variables locales, mais il est toujours plus rapide que l'accès aux globals. Considérez le fragment suivant:

fonction foo (x)

pour i = 1, 1000000 x = x + math.sin (i) fin

retour x

fin

imprimer (foo (10))

Nous pouvons l'optimiser en déclarant le péché une fois, en dehors de la fonction foo:

sin local = math.sin

fonction foo (x)

pour i = 1, 1000000

x = x + sin (i)

fin

retour x

fin

imprimer (foo (10))

Ce deuxième code est 30% plus rapide que l'original.

Bien que le compilateur Lua soit assez efficace comparé aux compilateurs pour d'autres langages, la compilation est une lourde tâche. Donc, vous devriez éviter de compiler du code dans votre programme (par exemple, la fonction loadstring) autant que possible. Sauf si vous devez exécuter du code réellement dynamique, tel qu'un code entré par un utilisateur final, il est rarement nécessaire de compiler du code dynamique.

A titre d'exemple, considérons le code suivant, qui crée une table avec des fonctions pour retourner des valeurs constantes de 1 à 100000:

Lim local = 10000

local a = {}

pour i = 1, lim faire

un [i] = loadstring (string.format ("return% d", i))

fin

impression (a [10] ()) -> 10

Ce code s'exécute en 1,4 secondes.

Avec les fermetures, nous évitons la compilation dynamique. Le code suivant crée les mêmes 100 000 fonctions dans 1 fois (0,14 secondes):

fonction fk (k)

return function () retourne k end end

19

local lim = 100000 local a = {}

pour i = 1, lim fais un [i] = fk (i) fin

impression (a [10] ()) -> 10

A propos des tables

Habituellement, vous n'avez pas besoin de savoir quoi que ce soit sur la façon dont Lua implémente des tables pour les utiliser. En fait, Lua fait de grands efforts pour s'assurer que les détails de mise en œuvre ne font pas surface à l'utilisateur. Cependant, ces détails se manifestent par l'exécution des opérations de table. Donc, pour optimiser les programmes qui utilisent des tables (c'est-à-dire pratiquement n'importe quel programme Lua), il est bon de savoir un peu comment Lua implémente les tables.

L'implémentation de tables dans Lua implique des algorithmes intelligents. Chaque table dans Lua a deux parties: la partie de tableau et la partie de hachage. La partie de tableau stocke des entrées avec des clés entières comprises entre 1 et n, pour un n particulier. (Nous discuterons de la façon dont ce n est calculé dans un instant.) Toutes les autres entrées (y compris les clés entières en dehors de cette plage) vont à la partie hash.

Comme son nom l'indique, la partie hash utilise un algorithme de hachage pour stocker et retrouver ses clés. Il utilise ce qu'on appelle une table d'adresses ouvertes, ce qui signifie que toutes les entrées sont stockées dans le tableau de hachage lui-même. Une fonction de hachage donne l'index primaire d'une clé; s'il y a une collision (c'est-à-dire si deux clés sont hachées à la même position), les clés sont liées dans une liste, chaque élément occupant une entrée de tableau.

Quand Lua doit insérer une nouvelle clé dans une table et que le tableau de hachage est plein, Lua fait un rehash. La première étape du rehash consiste à décider des tailles de la nouvelle partie de tableau et de la nouvelle partie de hachage. Ainsi, Lua parcourt toutes les entrées, les compte et les classe, puis choisit comme taille de la partie de tableau la plus grande puissance de 2, de sorte que plus de la moitié des éléments de la partie de tableau sont remplis. La taille de hachage est alors la plus petite puissance de 2 qui peut accueillir toutes les entrées restantes (c'est-à-dire celles qui ne rentrent pas dans la partie tableau).

Lorsque Lua crée une table vide, les deux parties ont la taille 0 et, par conséquent, aucun tableau n'est alloué pour elles. Voyons ce qui se passe lorsque nous exécutons le code suivant:

local a = {} fori = 1, 3 fait une [i] = fin vraie

Il commence par créer une table vide a. Dans la première itération de boucle, l'affectation a [1] = true déclenche un rehash; Lua définit alors la taille de la partie tableau de la table sur 1 et garde la partie hash vide. Dans l'itération de la deuxième boucle, l'assignation a [2] = true déclenche une autre rehash, de sorte que maintenant la partie array de la table a la taille 2. Enfin, la troisième itération déclenche encore une autre rehash, augmentant la taille de la partie array à 4 .

Un code comme

a = {~

a.x = 1; a.y = 2; a.z = 3

fait quelque chose de similaire, sauf qu'il pousse la partie de hachage de la table.

Pour les grandes tables, ce surcoût initial est amorti sur l'ensemble de la création: alors qu'une table avec trois éléments a besoin de trois rehashings, une table avec un million d'éléments n'en a besoin que de vingt. Mais lorsque vous créez des milliers de petites tables, les frais généraux combinés peuvent être significatifs.

Les anciennes versions de Lua créaient des tables vides avec des emplacements pré-alloués (quatre, si je me souviens bien), pour éviter cette surcharge lors de l'initialisation de petites tables. Cependant, cette approche gaspille de la mémoire. Par exemple, si vous créez des millions de points (représentés sous forme de tables avec seulement deux entrées) et que chacun utilise deux fois la mémoire dont il a vraiment besoin, vous pouvez payer un prix élevé. C'est pourquoi Lua crée actuellement des tables vides sans emplacements pré-alloués.

Si vous programmez en C, vous pouvez éviter ces rehashings avec la fonction Lua API lua_createtable. Il reçoit deux arguments après l'omniprésent lua_State: la taille initiale de la partie array et la taille initiale de la partie hash de la nouvelle table.3 En donnant des tailles appropriées à la nouvelle table, il est facile d'éviter ces rechutes initiales. Méfiez-vous, cependant, que Lua ne peut que rétrécir une table en la ressassant. Donc, si vos tailles initiales sont plus grandes que nécessaire, Lua pourrait ne jamais corriger votre gaspillage d'espace.

Lorsque vous programmez en Lua, vous pouvez utiliser des constructeurs pour éviter ces ré-initialisations. Quand vous écrivez {true, true, truel, Lua sait à l'avance que la table aura besoin de trois slots dans sa partie array, donc Lua crée la table avec cette taille. De même, si vous écrivez {x = 1, y = 2, z = 31, Lua va créer une table avec quatre emplacements dans sa partie de hachage. A titre d'exemple, la boucle suivante s'exécute en 2.0 secondes:



pour i = 1, 1000000

local a = {~

a [1] = 1; a [2] = 2; a [3] = 3 fin

Si nous créons les tables avec la bonne taille, nous réduisons le temps d'exécution à 0,7 secondes:

pour i = 1, 1000000

local a = {vrai, vrai, truel a [1] = 1; a [2] = 2; a [3] = 3 fin

Si vous écrivez quelque chose comme {[1] = true, [2] = true, [3] = truel, quoi qu'il en soit, Lua n'est pas assez intelligent pour détecter que les expressions données (littéral numì¬bers, in ce cas) décrivent des indices de tableau, de sorte qu'il crée une table avec quatre emplacements dans sa partie de hachage, gaspillant de la mémoire et du temps CPU.

La taille des deux parties d'une table n'est recalculée que lorsque la table se répète, ce qui n'arrive que lorsque la table est complètement pleine et que Lua doit insérer un nouvel élément. Par conséquent, si vous parcourez une table en effaçant tous ses champs (c'est-à-dire en les mettant tous à zéro), la table ne rétrécit pas. Cependant, si vous insérez de nouveaux éléments, la table devra éventuellement être redimensionnée. Habituellement, ce n'est pas un problème: si vous continuez à effacer des éléments et à en insérer de nouveaux (comme c'est souvent le cas dans de nombreux programmes), la taille de la table reste stable. Cependant, vous ne devriez pas vous attendre à récupérer la mémoire en effaçant les champs d'une grande table: il vaut mieux libérer la table elle-même.

Une astuce pour forcer un rehash consiste à insérer suffisamment d'éléments nuls dans la table. Voir l'exemple suivant:

a = *

lim = 10000000

pour i = 1, lim faire un [i] = i fin - créer une énorme table

print (collectgarbage ("count")) -> 196626

pour i = 1, lim faire un [i] = fin nil - effacer tous ses éléments

print (collectgarbage ("count")) -> 196626

pour i = lim + 1, 2 * lim faire une [i] = fin nulle - créer beaucoup d'éléments nuls

print (collectgarbage ("count")) -> 17

Je ne recommande pas cette astuce, sauf dans des circonstances exceptionnelles: Il est lent et il n'y a pas de moyen facile de savoir combien d'éléments sont «assez».

Vous pouvez vous demander pourquoi Lua ne réduit pas les tables lorsque nous insérons nils. Premièrement, pour éviter de tester ce que nous insérons dans une table; une vérification des assignations nulles ralentirait toutes les affectations. Deuxièmement, et plus important, de permettre des affectations nulles lors de la traversée d'une table. Considérez la prochaine boucle:

pour k, v dans les paires (t) faire si some_property (v) alors

t [k] = nil - efface cet élément

fin

fin

Si Lua remettait la table à zéro après une affectation nulle, cela aurait détruit la traversée. Si vous voulez effacer tous les éléments d'une table, une simple traversée est la bonne façon de le faire:

pour k par paires (t) faire t [k] = fin nulle

Une alternative "smartâ €" serait cette boucle:

alors que vrai

local k = suivant (t)

sinon k, puis casser la fin

t [k] = néant

fin

Cependant, cette boucle est très lente pour les grandes tables. La fonction suivante, lorsqu'elle est appelée sans clé précédente, renvoie le «premier élément» d'une table (dans un ordre aléatoire). Pour ce faire, il parcourt ensuite les tableaux de table depuis le début, en recherchant un élément non-nul. Comme la boucle met les premiers éléments à zéro, la suivante prend de plus en plus de temps pour trouver le premier élément non-nul. En conséquence, la boucle «intelligente» prend 20 secondes pour effacer une table avec 100 000 éléments; la boucle de traversée utilisant des paires prend 0.04 secondes.

A propos des chaînes

Comme pour les tables, il est bon de savoir comment Lua implémente les chaînes pour les utiliser plus efficacement.

La façon dont Lua implémente les chaînes diffère de deux façons importantes de ce qui est fait dans la plupart des autres langages de script. Premièrement, toutes les chaînes de Lua sont internalisées; Cela signifie que Lua conserve une seule copie de n'importe quelle chaîne. Chaque fois qu'une nouvelle chaîne apparaît, Lua vérifie si elle possède déjà une copie de cette chaîne et, si c'est le cas, réutilise cette copie. L'internalisation rend les opérations comme la comparaison de chaînes et l'indexation de tables très rapides, mais elle ralentit la création de chaînes.

Deuxièmement, les variables de Lua ne contiennent jamais de chaînes, mais seulement des références à celles-ci. Cette implémentation accélère plusieurs manipulations de chaînes. Par exemple, en Perl, lorsque vous écrivez quelque chose comme $ x = $ y, où $ y contient une chaîne, l'affectation copie le contenu de la chaîne du tampon $ y dans le tampon $ x. Si la chaîne est longue, cela devient une opération coûteuse. Dans Lua, cette affectation implique seulement de copier un pointeur sur la chaîne actuelle.

Cette implémentation avec des références ralentit toutefois une forme particulière de concaténation de chaînes. En Perl, les opérations $ s = $ s. "x" et $ s. = "x" sont assez différents. Dans le premier, vous obtenez une copie de $ s et ajoute "x" à sa fin. Dans le second, le "x" est simplement ajouté au buffer interne conservé par la variable $ s. Ainsi, la seconde forme est indépendante de la taille de la chaîne (en supposant que le tampon dispose de l'espace pour le texte supplémentaire). Si vous avez ces commandes à l'intérieur des boucles, leur différence est la différence entre un algorithme linéaire et un algorithme quadratique. Par exemple, la prochaine boucle prend presque cinq minutes pour lire un fichier de 5 Mo:

$ x = "".

alors que  «Â» {$ x = $ x. $ _ ~ 1

Si nous changeons $ x = $ x. $ _ à $ x. = $ _, cette fois-ci descend à 0,1 seconde!

Lua n'offre pas la deuxième option, plus rapide, parce que ses variables n'ont pas de tampons qui leur sont associés. Donc, nous devons utiliser un tampon explicite: une table avec les morceaux de chaîne fait le travail. La prochaine boucle lit ce même fichier 5MByte en 0.28 secondes. Pas aussi vite que Perl, mais plutôt bien.



105