keemor.com - Surfin' JavaScript Wave

Szybkie iteracje czyli przyspieszanie pętli

We wpisie Wydajne tworzenie elementów DOM C.D. pisałem o szybkim sposobie tworzenia elementów DOM w pętli. Zainspirowany częścią prezentacji Nicholasa Zakasa Speed Up Your JavaScript dotyczącą pętli przedstawie sposoby wydajnego iterowania po elementach.
Specyfikacja ecma-262, 3. edycja z grudnia 1999 roku wprowadza cztery rodzaje pętli: for, do-while, while oraz for-in.
Trzy pierwsze pętle służą do iteracji po listach, których klucze są kolejnymi liczbami całkowitymi zaczynając od 0.
For-in natomiast jest stworzony do przebiegania po tablicach asocjacyjnych, których klucze są łańcuchami znakowymi. Konstrukcja:


for (var key in arr) {
    arr[key];
}

w zmiennej key zwraca klucz i nie będę jej omawiać ze względu na niską wydajność.

Co jest ważne?

Dwa najważniejsze czynniki wpływające na prędkość pętli do ilość operacji w każdym przebiegu oraz liczba iteracji.

Czego unikać?

Jeżeli zależy nam na wydajności trzeba unikać metod iterujących dostępnych w popularnych frameworkach:

  • jQuery.each()
  • Y.each()
  • $each
  • Enumerable.each()
  • array.forEach() z najnowszej specyfikacji ecma-262, 5. edycja

Rozpatrzymy tablice values z pół milionem elementów.


var values = new Array(500000);
values.each(function(v){
})

Iteracja za pomocą metody each frameworku Prototype tworzy za każdym razem funkcję i jest wolniejsza od natywnych konstrukcji JavaScript około osiem razy we wszystkich przeglądarkach.

Podstawowa iteracja za pomocą trzech konstrukcji wygląda tak:


for (var i=0; i<values.length; i++){
	values[i];
}	
	
var j=0;
do {
	j++;
	values[j];
}while (j < values.length)

var k=0;
while (k < values.length) {
	k++;
	values[k];
}

Możemy ją łatwo przyspieszyć tworząc zmienną len na początku pętli:


var len=values.length;

for (var i=0; i<len; i++){
	values[i];
}	
	
var j=0;
do {
	values[j];
	j++;
}while (j < len)

var k=0;
while (k < len) {
	values[k];
	k++;
}

Ostatnim krokiem jest wyrzucenie z pętli linii zwiększającej licznik o jeden i zamiast tego iterować od ostatniego elementu do pierwszego:


var len=values.length;

for (var i=len; i--){
	values[i];
}	

var j=len-1;
do {
	values[j];
}while (j--)

var k=len;
while (k--) {
	values[k];
}	

Ostatnia opcja jest szybsza nawet do 50% w różnych przeglądarkach.

Poniżej przedstawiam przykładowe wyniki w od lewej: IE7, IE8, Chrome 2, Firefox 3 i Opera 10.

  1. each z Prototype
  2. do { } while podstawowe
  3. do { } while z wyliczoną wcześniej liczbą elementów
  4. do { } while z iteracją od końca do początku

Wyniki prędkości pętli