27 mars 2010

AS3 Vector : loop performance

Parfois l’optimisation se fait à la milliseconde. Si l’on trouve beaucoup de tests de performance sur les tableaux, les tests complets sur les vecteurs (Vector) sont plus rares. En travaillant sur un moteur de particules maison, j’ai été amené à faire ces tests. Protocole et résultats dans la suite.

as3

Protocole

Le protocole de test est simple. Après avoir écarté les for each, foreach for(in) clairement en dessous en terme de performance, j’ai mis en place 11 boucles (5 for et 6 while) réalisant 50000000 d’itération sur un vecteur (vector dans le code) d’entier non signés (uint).

Ces tests ont été effectués vingt fois sur un Core 2 Duo T9800 à 2.93Ghz, 4Go RAM, Windows Vista 64bit et Flash CS4 :

private function _test1() : void
{
	/// TEST 1 //////////////////////////////////////
 
	time = getTimer();
 
	for (var i : uint = 0; i < vector.length; i++) 
	{ 
		vector[i]; 
	}
 
	result = getTimer() - time;
 
	trace("for (var i : uint = 0; i < vector.length; i++) : " + result + "ms");
 
	/// TEST 2 //////////////////////////////////////
 
	time = getTimer();
 
	var k : uint = vector.length;
 
	for (var j : uint = 0; j < k ; j++) 
	{ 
		vector[j]; 
	}
 
	result = getTimer() - time;
 
	trace("for (var j : uint = 0; j < k ; j++) : " + result + "ms");
 
	/// TEST 2 //////////////////////////////////////
 
	time = getTimer();
 
	var m : uint = vector.length;
	var l : uint = 0;
 
	for (l; l < m ; l++) 
	{ 
		vector[l]; 
	}
 
	result = getTimer() - time;
 
	trace("for (l; l < m ; l++) : " + result + "ms");
 
 
	/// TEST 3 //////////////////////////////////////
 
	time = getTimer();
 
	var n : int = vector.length - 1;
 
	for (n; n > -1 ; n--) 
	{ 
		vector[n]; 
	}
 
	result = getTimer() - time;
 
	trace("for (n; n > -1 ; n--)  : " + result + "ms");
 
	/// TEST 4 //////////////////////////////////////
 
	time = getTimer();
 
	var o : uint = vector.length;
	var p : uint = 0;
 
	for (p; p < o ; ++p) 
	{ 
		vector[p]; 
	}
 
	result = getTimer() - time;
 
	trace("for (p; p < o ; ++p) : " + result + "ms");
 
	/// TEST 5 //////////////////////////////////////
 
	time = getTimer();
 
	var q : int = vector.length - 1;
 
	for (q; q > -1 ; --q) 
	{ 
		vector[q]; 
	}
 
	result = getTimer() - time;
 
	trace("for (q; q > -1 ; --q) : " + result + "ms");
 
	_test2();
}
 
private function _test2() : void
{
 
	trace("-----------------------------------");
 
	/// TEST 1 //////////////////////////////////////
 
	time = getTimer();
 
	var i : uint = vector.length;
	var j : uint = 0;
 
	while(j < i)
	{ 
		vector[j];
		j++; 
	}
 
	result = getTimer() - time;
 
	trace("while(j < i) : " + result + "ms");
 
	/// TEST 2 //////////////////////////////////////
 
	time = getTimer();
 
	var k : int = vector.length - 1;
 
	while(k > -1 )
	{ 
		vector[k];
		k--; 
	}
 
	result = getTimer() - time;
 
	trace("while(k > -1 ) : " + (getTimer() - time) + "ms");
 
	/// TEST 3 //////////////////////////////////////
 
	time = getTimer();
 
	var l : uint = vector.length - 1;
	var m : int = -1;
 
	while(m++ < l)
	{ 
		vector[m];
	}
 
	result = getTimer() - time;
 
	trace("while(m++ < l) : " + (getTimer() - time) + "ms");
 
	/// TEST 4 //////////////////////////////////////
 
	time = getTimer();
 
	var n : int = vector.length;
 
	while(n-- > 0 )
	{ 
		vector[n];
	}
 
	result = getTimer() - time;
 
	trace("while(n-- > 0 ) : " + (getTimer() - time) + "ms");
 
	/// TEST 5 //////////////////////////////////////
 
	time = getTimer();
 
	var o : uint = vector.length - 1;
	var p : int = -1;
 
	while(++p < o)
	{ 
		vector[p];
	}
 
	result = getTimer() - time;
 
	trace("while(++p < l) : " + result + "ms");
 
	/// TEST 6 //////////////////////////////////////
 
	time = getTimer();
 
	var q : int = vector.length;
 
	while(--q > 0 )
	{ 
		vector[q];
	}
 
	result = getTimer() - time;
 
	trace("while(--q > 0 ) : " + result + "ms");
}

Résultats

Au final on obtient les résultats suivant après avoir fait une moyenne :

for (var i : uint = 0; i < vector.length; i++) : 2604 ms
for (var j : uint = 0; j < k ; j++) : 322,8 ms
for (l; l < m ; l++) : 327,7 ms
for (n; n > -1 ; n–) : 308,3 ms
for (p; p < o ; ++p) : 325,8 ms
for (q; q > -1 ; –q) : 325,6

while(j < i) : 325,7 ms
while(k > -1 ) : 326,3 ms
while(m++ < l) : 343,5 ms
while(n– > 0 ) : 307,8 ms
while(++p < l) : 328,7 ms
while(–q > 0 ) : 307,8 ms

En résumé, 3 boucles se détachent à 307,8 et 308,3ms :

var i : int = vector.length - 1;
 
for (i; i > -1 ; i--)
{ 
	vector[i]; 
}
 
// OU
 
var i : int = vector.length;
 
while(i-- > 0 )
{ 
	vector[i];
}
 
// OU
 
var i : int = vector.length;
 
while(--i > 0 )
{ 
	vector[i];
}

A noter que la première et la dernière boucle montre une plus grande constance.

Aller plus loin

Pour aller plus loin, j’ai isolé les deux boucles les plus performantes et constantes, cette fois-ci avec une affectation dans la boucle pour un test de typage :

private function _test3() : void
{
	time = getTimer();
 
	var i : int = vector.length - 1;
 
	for (i;i > -1 ;i--)
	{ 
		vector[i] = 0; 
	}
 
	result = getTimer() - time;
 
	trace("test 1 : " + result + "ms");
 
	/// TEST 2 //////////////////////////////////////
 
	time = getTimer();
 
	var j : int = vector.length;
 
	while(--j > 0 )
	{ 
		vector[j] = 1;
	}
 
	result = getTimer() - time;
 
	trace("test 2 : " + result + "ms");
 
	/// TEST 3 //////////////////////////////////////
 
	time = getTimer();
 
	var k : int = vector.length - 1;
 
	for (k;k > -1 ;k--)
	{ 
		vector[int(k)] = 2; 
	}
 
	result = getTimer() - time;
 
	trace("test 3 : " + result + "ms");
 
	/// TEST 4 //////////////////////////////////////
 
	time = getTimer();
 
	var l : int = vector.length;
 
	while(--l > 0 )
	{ 
		vector[int(l)] = 3;
	}
 
	result = getTimer() - time;
 
	trace("test 4 : " + result + "ms");
}

Cette fois les résultats sont les suivant :

test 1 : 374,6 ms
test 2 : 335,2 ms
test 3 : 334,8 ms
test 4 : 322,6 ms

Les boucles sont donc bien l’exception qui confirme la règle, et le transtypage du compteur permet de gagner en performance, particulièrement dans une boucle for. A noter que les temps sont plus élevés dans ce deuxième test car entre temps excel s’était invité aux logiciels ouverts.

Évidemment ces tests dépendent en partie de la machine, des processus en cours, du player… mais finalement, la boucle la plus rapide semble être la suivante :

var i : int = vector.length;
 
while(--i > 0 )
{ 
	vector[int(i)];
}

Laisser un commentaire

Commentaire