Wie nützlich ist Loop Unrolling in php?

Loop Unrolling ist eine Methode zur Leistungsverbesserung von großen Schleifen. Das Prinzip dahinter ist denkbar einfach.
Statt eine Funktion einmal pro Schleifendurchlauf auszuführen wird sie z.B. acht mal nacheinander ausgeführt und somit die Schleifendurchläufe um den selben Faktor verkürzt. Bei Schleifen, deren Durchläufe nicht genau durch acht teilbar sind, muss der Rest dann noch als normaler Loop durchlaufen werden. Der Duff-Apparat (engl. Duff’s Device) ist eine spezielle Form, die meines Wissens nach nur in C funktioniert, um den „Rest-Loop“ auch noch weg zu bekommen.
Das Loop Unrolling ist allerdings nicht für jede Schleife geeignet und kann die Leistung sogar verschlechtern.

Triviale Demo

/* Definiert wieviele Durchläufe zusammengefasst werden */
define('PACK', 8);
function SimpleLoopPack8($iterations) {

    /* Iterator */
    $n = 0;
    /* Variable mit der was gemacht wird */
    $toBeChanged = 0;

    /* Rest */
    $left = $iterations % PACK;

    /* 8er Durchläufe */
    $nLoop = $iterations - $left;

    /* 8er Loop(s) */
    while ($n < $nLoop) {

        /* 8x gewünschte Operation/Funktion ausführen */
        $toBeChanged++;
        $toBeChanged++;
        $toBeChanged++;
        $toBeChanged++;
        $toBeChanged++;
        $toBeChanged++;
        $toBeChanged++;
        $toBeChanged++;

        /* Iterator um 8 erhöhen */
        $n+=PACK;
    };

    /* Den Rest abarbeiten, wenn einer da is */
    while ($n < $iterations) {
        $toBeChanged++;
        ++$n;
    };
}

Dieser Aufbau ist erheblich schneller als der normale (deutlich kürzere) Loop

function defaultLoop($iterations) {
    $toBeChanged = 0;
    for ($i = 0; $i < $iterations; ++$i) {
        $toBeChanged++;
    }
}

Resultat

  • simpleLoopPack8 : 100.000 loops in 0,0048627853393555 sek.
  • defaultLoop: 100.000 loops in 0,0060989856719971 sek.
  • macht: 20% bessere Leistung für den 8fach gepackten Loop.

Da sind wir alle ganz aus dem Häuschen und verneigen unser Haupt in Ehrfurcht, denn wir haben es hier ja mit einem Problem zu tun, mit dem wir täglich konfrontiert werden… Naja, soll ja nur das Konzept zeigen.

Gehen wir jetzt aber her und iterieren über ein Array um mit dessen Inhalt irgenwas zu machen, was in einem nicht weniger trivialen Beispiel so aussehen könnte

function simpleChangeItems(&$items) {
    $nLoop = sizeof($items);
    for ($i = 0; $i < $nLoop; ++$i) {
        $items[$i] = 'changed';
    }
}

oder in der Loop Unroll Variante

function changeItems(&$lines) {
    /* Iterator, Iterations */
    $n = 0; $iterations = sizeof($lines);

    /* Rest */
    $left = $iterations % PACK;

    /* 8er Durchläufe */
    $nLoop = $iterations - $left;

    /* 8er Loop(s) */
    while ($n < $nLoop) {

        /* 8x gewünschte Operation/Funktion ausführen */
        $lines[$n] = 'changed';
        $lines[$n + 1] = 'changed';
        $lines[$n + 2] = 'changed';
        $lines[$n + 3] = 'changed';
        $lines[$n + 4] = 'changed';
        $lines[$n + 5] = 'changed';
        $lines[$n + 6] = 'changed';
        $lines[$n + 7] = 'changed';

        /* Iterator um 8 erhöhen */
        $n+=PACK;
    };

    /* Den Rest abarbeiten, wenn einer da is */
    while ($n < $iterations) {
        $lines[$n++] = 'changed';
    };
}

Resultat

  • changeItems : 100.000 loops in 0,042221069335938 sek.
  • simpleChangeItems: 100.000 loops in 0,0000017881393432617 sek.
  • macht: 99% miesere Leistung für den 8fach gepackten Loop.

Warum ist das so?

Rechner können verhältnismäßig viel schlechter rechnen als zählen. Da in dem gepackten Loop jedes mal der richtige Array-Index ausgerechnet werden muss zieht das die Leistung so enorm in den Keller.

Fazit, oder: Wann ist Loop Unrolling sinnvoll?

Wenn man eine große Menge der gleichen Funktionen ausführen muss oder will, die keine zu berechnende Reihenfolge hat.
Ooooder, wenn das Ergebnis der funktion jeweils als Eingangswert für die nächste verwendet werden kann oder soll. Das beste was ich dabei hab rausholen können lag bei einer Steigerung von knapp 4%.

2 Bemerkungen zu “Wie nützlich ist Loop Unrolling in php?

  1. David

    Ungeachtet deiner Messungen, macht Loop Unrolling nur dann Sinn, wenn hinterher im Maschinencode (PHP hat keinen JIT-Compiler) weniger Spruenge sind. Ansonsten wird das Programm schlicht und ergreifend groesser ohne wirklichen Gewinn

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.