Optimisation de l'accés aux tableaux
Par -Alexandre LEGOUT aka LAlex- le 16 octobre 2003, 19:42 - AS2 - Lien permanent
Voici une petite astuce que je pratique depuis longtemps en me basant sur ma propre logique, mais je me suis décidé à la benchmarquer (euh ... ca s'écrit comme ca ? :roll:)
Il s'agit d'éviter le plus possible d'accéder à un élément de tableau (pendant une boucle par exemple) ou à sa longueur. Si l'on a besoin d'accéder plusieurs fois au même élément d'un tableau, il est plus performant de le mettre dans une variable, la modifier, puis la remettre dans le tableau (évidemment, si c'est un objet, vous n'avez pas besoin de la remettre dans le tableau ;)). Le principe est le même pour la longueur du tableau.
Voici le "bench" que j'ai fait// On crée un tableau de 100.000 cases
Ce qui nous donne en sortie
var tst = new Array(100000);
// On va accéder à un élément
// situé peu à prés au milieu (60.000)
tst[60000] = 10;
/** Accés au tableau à chaque boucle **/
var t = getTimer();
for (var i=0 ; i<200000 ; i++) {
// Accés à la longueur
tst.length;
// Accés à l'élément
tst[60000] += 1;
}
// Affichage du temps
trace("Accés au tableau : " + (getTimer() - t) + " ms.");
// Reinitialisation de la valeur
tst[60000] = 10;
/** Accés à une variable **/
t = getTimer();
// Initialisation de la variable
var elt = tst[60000];
// Initialisationde la longueur
var ln = tst.length;
for (var i=0 ; i<200000 ; i++) {
// Acces à la valeur de la longueur
ln;
// Modification de la valeur
elt += 1;
}
// On remet la valeur dans le tableau
tst[60000] = elt;
// Affichage du temps
trace("Accés aux variables : " + (getTimer() - t) + " ms.");Accés au tableau : 3217 ms.
Accés aux variables : 2367 ms.
Le gain est en général de l'ordre d'une seconde, ce qui est énorme ! 8O
Ca ne parait pas grand chose, mais réflechissez à toutes les boucles for que vous faites sur un tableau, en testant la longueur comme condition d'arrêt ...
Il accéde à la propriété length à chaque boucle !!! :roll:
Il vaut mieux mettre la longuer dans une variable qui va servir pour la condition du for. Sinon, si l'ordre vous importe peu, vous pouvez utiliser une boucle while qio commence par la longuer du tableau/**** Mauvaise utilisation ****/
for (var i=0 ; i<monTableau.length ; i++) {
// ...
}
/**** Bonne utilisation ****/
var len:Number = monTableau.length;
for (var i=0 ; i<len ; i++) {
// ...
}
/*** Autre bonne utilisation ****/
var i:Number = monTableau.length;
while (--i >= 0) {
// ...
}
Vous pouvez aussi utilise for ( ... in ...), mais je ne sais pas comment ca marche ...:P
Ce n'est certainement pas nouveau pour beaucoup d'entre vous, mais ca peut toujours servir ... ![]()
Commentaires
Waouhou ! tout ça ?!!!! 1 sec, c'est énorme ...
C'est pas la longueur qui prend le plus de temps de calcul mais bien l'affectation direct sur l'index du tableau ... ce qui semble somme toute logique.
si je remplace :
// Modification de la valeur
elt += 1;
par:
// Modification de la valeur
tst[60000] += 1;
j'obtiens plus que 100ms de différence :
Accés au tableau : 1458 ms.
Accés aux variables : 1351 ms.
ce qui est minime quand meme pour une loop à 200.000
Sinon les boucles for in ne sont pas adaptées aux arrays mais sont exclusivement réservées pour énumérer les membres d'un objets
Le bench qui est ici est fait sur un portable avec Celeron 1.3GHz et 256 Mo de RAM ...
Avant l'utilisation de la longueur, avec juste l'accés à l'index du tableau, j'avais prés de 600 ms. de décalage ... :roll:
petepx >> tu devrais nous donner le décalage si on utilise l'index ET la longueur? Etant donné que ca change selon la config, on ne peut pas comparer ...
Pour la combinaison index + longueur, sur l'ordi de la maison (P4 2.53GHz, 1Go de RAM), j'ai encore 400 ms. de décalage ... :roll:
Sinon, je pense que l'accés à l'index et celui à la longueur se valent a peu prés ... Si seulement on avait accés à l'opérateur [] (crochets) de la classe Array, on pourrait créer une classe SuperArray qui en hérite, et qui garderait en permanence la longueur en tant que propriété. La je pense qu'elle est calculée à chaque appel ... :?
Et pour les boucles for (... in ...), c'est vrai qu'on peut pas les utiliser, j'étais persuadé du contraire ...
Je traite tellement tous les objets comme des tableaux associatifs que je fini par avoir du mal à faire la différence !
Si, on peut parcourir les éléments d'un array avec for(variable in array).
En plus de membres de l'objet, la variable prend les valeurs "0","1","2", etc. Les index sont de type string et donnés dans l'ordre inverse (du dernier au premier).
D'ailleurs on peut accéder aux valeurs d'un array en donnant un index de type string : array["60000"] == array[60000].
Ca c'est juste du à un cast automatique de String vers Number je pense ...
Il faut benchmarker ça ! :p
> Ca c'est juste du à un cast automatique de String vers Number je pense ...
Nope, c'est l'inverse :). Meme dans un Array, les indexes sont stockes en string. Voila un thread qui contient quelques details:
http://chattyfig.figleaf.com/cgi-bin/ezmlm-cgi?1:sss:68094:200303:hllijjfkpgaoclabjhmc#b
(attention il est long :p et seulement la derniere partie aborde le type des indexes).
Sinon, pour une pauvre etude vite fait:
a = ["hello", "there"];for (var i in a) trace(i + " -> " typeof(i));
Oops, oublie un +:
a = ["hello", "there"];for (var i in a) trace(i + " -> " + typeof(i));
La c'est l'accés au indexs du tableau dont je parlais, pas vraiment des performances des boucles ...
Mais pour info, un des GROS interêts de for (... in ...) est qu'il ne semble pas parcourir les cases vides !!!
var tst = new Array(100000);var l:Number = 0;
tst[60000] = 10;
for (var i in tst) {
l++;
}
trace("nbLoops : " + l); // nbLoops : 1
Voila qui est interessant !
Merci Philippe pour cette piste ! 
Oui, merci Timothee !
En fait la demo est la : http://chattyfig.figleaf.com/cgi-bin/ezmlm-cgi?1:mss:68520:200303:hllijjfkpgaoclabjhmc. J'aime beaucoup la démonstration faite avec le booléen, je pense que c'est vraiment la qu'est la preuve irréfutable ! 
Sinon, j'avais fait mon test plus simplement :
var a:Array = new Array(1,2,3,4,5,6);Ce qui montre bien que les propriétés et les index sont au même niveaux ...a.prop = "maProp";
for (var p in a) {
trace(p + " : " + a[p]);
}
// prop : maProp
// 5 : 6
// 4 : 5
// 3 : 4
// 2 : 3
// 1 : 2
// 0 : 1
très juste ...
Accés au tableau : 1680 ms.
Accés aux variables : 1240 ms.
et
Accés au tableau : 1678 ms.
Accés aux variables : 1560 ms.
Et merci pour l'info pour le (for in),

carrément
la boucle for est carrément plus rapide :
for : 833 ms.
for in : 3199 ms.
a = new Array(100000);
for (var x=0; x<=100000; x++) a[x]=x;
t = getTimer();
for (var x=0; x<=100000; x++) a[x]++;
trace("for : " + (getTimer() - t) + " ms.");
t = getTimer();
for (var i in a) a[i]++;
trace("for in : " + (getTimer() - t) + " ms.");
avec une condition c'est l'hallu !!! Comme quoi les boucles for in ne sont pas du tout adaptées aux array ...
oui
for : 617 ms.
oui
for in : 3512 ms.
a = new Array(100000);
for (var x=0; x<=100000; x++) a[x]=x;
t = getTimer();
for (var x=0; x<=100000; x++) if (a[x] == 100000) trace("oui");
trace("for : " + (getTimer() - t) + " ms.");
t = getTimer();
for (var i in a) if (a[i] == 100000) trace("oui");
trace("for in : " + (getTimer() - t) + " ms.");
> quoi les boucles for in ne sont pas du tout adaptées aux array ...
Ca depend des cas, une boucle for..in place toutes les proprietes sur la pile et les fait sauter une par une apres ca. Ca peut aller beaucoup plus vite que de faire une boucle avec conditions sur la taille du tableau et incrementation de l'index pour un tableau de petite taille. Sur un tableau a 100000 elements, Flash doit utiliser un paquet de memoire et c'est ca qui doit ralentir tout, sans parler du risque de stack overflow. En Flash MX2004 l'utilisation des registres doit aussi rendre l'incrementation de l'index beaucoup plus rapide.
Teste sous Flash 5:
n = 1000;a = new Array(n);
for (var x=0; x<=n; x++) a[x]=x;
t = getTimer();
for (var x=0; x<=n; x++) if (a[x] == n) trace("oui");
trace("for : " + (getTimer() - t) + " ms.");
t = getTimer();
for (var i in a) if (a[i] == n) trace("oui");
trace("for in : " + (getTimer() - t) + " ms.");
resultats sur mon PC:
n = 100;
oui
for : 23 ms.
oui
for in : 4 ms. // <- ~6x faster
n = 1000;
oui
for : 82 ms.
oui
for in : 44 ms. // <- ~2x faster
n = 10000;
oui
for : 675 ms.
oui
for in : 462 ms. // <- ~1.5x faster
// a 100000 ma machine ne suit plus
Donc mefiance, MX2004 a peut etre change la donne mais sous 5/MX, for..in peut etre beaucoup plus performant qu'une boucle for.
Par contre, for(...in...) parcourt *toujours* tous les éléments, même si on arrête la boucle avec break !
En fait, le lecteur met *tous* les éléments de l'objet sur la pile et execute les instructions pour chaque valeur.
Oups, ça vient d'être dit...
> En fait, le lecteur met *tous* les éléments de l'objet sur la
> pile et execute les instructions pour chaque valeur.
Oui, for..in doit vider la pile de tous les elements un par un. Cela dit, en utilisant break, (ou return) dans la boucle, les elements sont justes poppes de la pile un par un sans executer les actions qui sont dans la boucle (heureusement d'ailleurs).
Pardon Philippe, je pense que c'est ce que tu as voulu dire de toute facon :O.
Ta version est plus juste
Effectivement c'est propre a 2004, c'est bon a savoir
Du portable du boulot :
2004 pour n=40 >>
oui
for : 0 ms.
oui
for in : 1 ms.
MX pour n=40 >>
oui
for : 2 ms.
oui
for in : 1 ms.
2004 pour n=1000 >>
oui
for : 15 ms.
oui
for in : 20 ms.
MX pour n=1000 >>
oui
for : 85 ms.
oui
for in : 41 ms.
On peut encore optimiser la boucle en parcourant les éléments dans l'ordre inverse et en comparant l'index avec 0 (c'est mieux que de comparer avec la longueur de l'array).
Ca donne :
for (var i=a.length-1; i>=0; i--) a[i];
ou en encore plus compact :
for (var i=a.length; i--;) a[i];
Pour n=100000 (MX)
for() incrémenté : 10.2s
for() décrémenté : 9.3s
for() déc. compact : 8.4s
Etrangement, c'est qq centièmes plus rapide compilé en Flash 5...
Hé hé !
Zut le bbcode.
Le for compact est :
for (var i=a.length; i--; ) a[i];
Philppe >> Ton dernier code correspond à la boucle while que j'ai donné dans mon post en fait ...
Bonjour à tous.
Je tenais juste à remercier tous les participant de cet article qui m'a pas mal aidé à comprendre pourquoi mes jeux flash ramaient autant.
Par exemple, sur Shoot Out Loud, mon premier site contenant du flash (et c'est aussi le dernier en date, je viens d'arriver là dedans ^^ ), le jeu qui n'est pourtant pas très gourmand en théorie, fonctionne au ralenti sur tout PC dont le processeur est en dessous d' 1.5GHz. Autant dire que je prive pas mal de monde des joies de mon jeu :s
Maintenant que j'ai lu cet article, ses commentaire, d'autres sur ce blog, ainsi que ceci, je comprend beaucoup mieux les erreurs que j'ai pu faire, et je m'attèle à la lourde tâche d'optimisation...
Première chose pour moi, remplacer mes :
for(var i:Number=0; i
par de somptueusement plus rapides :
var itemListlength=itemList.length;
for(var i:Number=0; i
ensuite je vous raconte pas le contenu de mes boucles, vous sauteriez au plafond... il y a tellement de chose à faire par item, et tout ca 50 fois par secondes... aïe, ca rame ^^
Bref, continuez à bencher, expliquer, tester, et si je peux vous aider, j'en serai ravi
En relisant, je me dis que je ferai encore mieux en mettant du :
var i=itemList.length;
for(i;i;i--){
non ?
Nouvelle lecture, nouvelle version, je vais utiliser un :
var i=itemList.length;
do{
} while(i--);
Désolé de flooder les commentaires, j'essaye de récapituler, mais y'a tellement de facons et de nuances... mais je lâcherais pas ^^
Le plus rapide c'est le while en principe
(pas besoin d'utiliser le do..while)
Sinon il est clair que la variable temporaire pour stocker la taille du tableau c'est indispensable pas faut voir si possible à avoir une variable pas trop grosse et bien explicite.. par exemple vaut mieux taper :
var len:number = myArray.length ;ou carrémentvar l:Number = ar.length ;que de taper :var itemListLength:Number = monTableauQuitue_mais_qui_a_un_nomtroplong.length ;Tu devrais lire par exemple cet article de Francis sur la : Notation hongroise
EKA+
Déjà merci de me répondre, si vite, sur un sujet, si vieux ^^
Pour le do while c'était à cause de ce que j'avais vu dans le lien que j'ai donné dans mon premier message. Il testait le do while face au for, donc forcément, le do while "gagnait" le bench !
Sinon je compte faire mes propres benches là dessus, just for fun, et si j'arrive à quelque chose d'intéressant, je mettrai peut-être le lien ici, même si le sujet a plusieurs années ^^
Merci pour l'article, j'y cours !
(au passage la boucle do while ne marche pas chez moi, elle s'effectue en boucle en faisant la même chose que sur la page en flash dont j'ai donné le lien plus haut Ôo)
Autres discussions intéressantes à ce sujet sur le blog de liguorien (bench en tout genre) :
* Légende urbaine ?
* Performance Primitive
* Accès aux données membres
Merci encore.
Une question en passant :
Est-il vraiment utile de faire des anim en 50fps ?
Je me suis rendu compte récemment que la personne m'ayant appris les notions de base de flash étant vraiment très très mauvaise, et je commence à remettre en cause mes bases...
Si je dois passer, par exemple, en 25fps, va falloir que je modifie toutes mes vitesses... argh !
normalement c'est 24fps et pas 25 (25 cela sert à rien)
PS : on n'est pas sur un forum ... tu as des forums comme sur mediabox pour trouver ce genre de réponse hein
Fil des commentaires de ce billet