Christofs Blog

Duff’s Device selber habe ich in drei Ausführungen geschrieben, die verschiedene Unrolling Längen ermöglichen. Der Einfachheit halber möchte ich hier nur die Vierstufige Variante veröffentlichen. Die 16 Stufige und die 256 Stufige funktionieren analog, nur dass sie eben entsprechend länger werden:

template<typename INT_T, typename CALL_T> inline void duff4(INT_T &n, CALL_T &c) {
    if( n <= 0 ) return;
    while( true ) {
        if( n == 0 ) goto DUFF4_END;
        switch( 4 - n ) {
            case 1: goto DUFF4_1; break;
            case 2: goto DUFF4_2; break;
            case 3: goto DUFF4_3; break;
        }
        c();
DUFF4_1:    c();
DUFF4_2:    c();
DUFF4_3:    c();
        n -= 4;
    }
DUFF4_END:
    return;
}

Als Schleifenkörper gibt es einen inline functor, der wie folgt aussieht:

struct MyLoop {
    int &i;
    inline MyLoop(int &j):i(j) {};
    inline void operator() (int &n) {
        if( i % 16777216 == 0 )             { cout << “\x8-”;  cout.flush(); }
        else if( i % 16777216 == 4194304 )  { cout << “\x8/”;  cout.flush(); }
        else if( i % 16777216 == 8388608 )  { cout << “\x8|”;  cout.flush(); }
        else if( i % 16777216 == 12582912 ) { cout << “\x8\\”; cout.flush(); }
        i++;
    }
};

Und dann noch die Main Funktion:

int main(int argc, char** argv) {
    int counter = 0;
    int i;
    int j;
    int k;
    int n;

    ptime t = microsec_clock::local_time();
    ptime t2 = t;
    time_duration average_loop(not_a_date_time);
    time_duration average_duff4(not_a_date_time);
    time_duration average_duff16(not_a_date_time);
    time_duration average_duff256(not_a_date_time);

    MyLoop l(counter);
    for( j = TESTS; j; --j ) {
        // reset counter
        counter = 0;
        // flush output - buffer may make tests unfair
        cout.flush();

        // measure loop
        cout << “\r   Loop Test ” << (TESTS + 1 - j) << “ running:  ”;
        t = microsec_clock::local_time();
        for( k = LOOPRUNS; k; --k ) for( i = LOOPROUNDS; i; --i ) l();
        t2 = microsec_clock::local_time();

        if( average_loop.is_not_a_date_time() )
            average_loop = t2 - t;
        else
            average_loop = average_loop + (t2 - t);

        // reset counter
        counter = 0;
        // flush output - buffer may make tests unfair
        cout.flush();
   
        // measuer duff device
        cout << “\r  Duff4 Test ” << (TESTS + 1 - j) << “ running:  ”;
        t = microsec_clock::local_time();
        for( k = LOOPRUNS; k ; --k ) {
            n = LOOPROUNDS;
            duff4(n, l);
        }
        t2 = microsec_clock::local_time();

        if( average_duff4.is_not_a_date_time() )
            average_duff4 = t2 - t;
        else
            average_duff4 = average_duff4 + (t2 - t);

        // reset counter
        counter = 0;
        // flush output - buffer may make tests unfair
        cout.flush();
   
        // measuer duff device
        cout << “\r Duff16 Test ” << (TESTS + 1 - j) << “ running:  ”;
        t = microsec_clock::local_time();
        for( k = LOOPRUNS; k ; --k ) {
            n = LOOPROUNDS;
            duff16(n, l);
        }
        t2 = microsec_clock::local_time();

        if( average_duff16.is_not_a_date_time() )
            average_duff16 = t2 - t;
        else
            average_duff16 = average_duff16 + (t2 - t);

        // reset counter
        counter = 0;
        // flush output - buffer may make tests unfair
        cout.flush();
   
        // measuer duff device
        cout << “\rDuff256 Test ” << (TESTS + 1 - j) << “ running:  ”;
        t = microsec_clock::local_time();
        for( k = LOOPRUNS; k ; --k ) {
            n = LOOPROUNDS;
            duff256(n, l);
        }
        t2 = microsec_clock::local_time();

        if( average_duff256.is_not_a_date_time() )
            average_duff256 = t2 - t;
        else
            average_duff256 = average_duff256 + (t2 - t);

    }

    average_loop = average_loop / TESTS;
    average_duff4 = average_duff4 / TESTS;
    average_duff16 = average_duff16 / TESTS;
    average_duff256 = average_duff256 / TESTS;

    cout << ‘\r’;
    cout << “   Loop average time: ” << average_loop << endl;
    cout << “  Duff4 average time: ” << average_duff4 << endl;
    cout << “ Duff16 average time: ” << average_duff16 << endl;
    cout << “Duff256 average time: ” << average_duff256 << endl;
}

Die Konstanten LOOPROUNDS, LOOPRUNS und TESTS habe ich natürlich für die verschiedenen Testläufe geändert. Dabei ist LOOPRUNS dazu da, dass bei niedrigen LOOPROUNDS noch sinnvolle Messwerte herauskommen. Mit TESTS wird das statistische Rauschen nach Möglichkeit weggemittelt. TESTS steht bei allen Experimenten auf 100. Hier meine Ergebnisse:

Auf der X-Achse ist der Logarithmus zur Basis 2 von LOOPROUNDS, während LOOPRUNS immer auf 2²⁴/LOOPROUNDS  gesetzt wird. Auf der y-Achse ist die durchschnittliche Laufzeit in ms angegeben. Die Testmaschine war mein Laptop.

Bei dieser Skala sind die Messungen mit Compiler Optimierungen kaum zu Unterscheiden, darum hier noch einmal genauer:

Einerseits ist das Rauschen der Messergebnisse noch bei 12 und 17 auf der X-Achse schön zu sehen, andererseits ergeben sich dennoch bereits gute Aussagen:

1. Im Vergleich zur normalen Schleifenkonstruktion des gcc bringt Duff mit vier Stufen praktisch keine Verbesserung. Darf der Compiler nicht optimieren, ist Duff sogar mit sechzehn Stufen noch schlechter.
2. Bei wenigen Durchläufen ist Duff - wenig überraschend - schlechter als das normale Schleifenkonstrukt. Je mehr Stufen die Duff Implementation kann, desto dramatischer ist dieser Effekt.

1. Bei kurzen Schleifen bringt Duff eigentlich nichts - unter 16 Durchläufen sollte er gar nicht erst anfangen.
2. Wo immer das übliche Loop Unrolling des gcc zuschlagen würde, sollte man ihm den Vortritt lassen. Für Duff bleiben immer noch all die Schleifen, die keine zur compile-Zeit bekannte Zahl von Durchläufen haben.
3. Schleifen mit zur compile-Zeit bekannter Zahl von Durchläufen, die dem üblichen Loop Unrolling zu lang sind, kann das Duff Device noch etwas beschleunigen. In solchen Fällen erscheint es mir aber doch noch sinnvoller, die Schleife teilweise auszurollen, also mehrer Durchläufe zu einem zusammenzufassen. In solchen Fällen ist die Fähigkeit des Duffs Device auch erst zur Laufzeit bestimmen zu können, wie oft die Schleife durchlaufen werden muss, nicht nötig und es ist eine bessere Lösung möglich.

In erster Linie ist Duff also tatsächlich für Schleifen Interessant, von denen der Compiler noch nicht weiß, wie oft sie durchlaufen werden müssen.

Ach ja, noch was: Ich weiß, dass Duffs Code anders aussieht. Sein Code ist kürzer und ohne Goto. Für mich ist aber in diesem extrem seltenen Fall tatsächlich die Variante mit Goto leichter zu durchschauen als Duffs Original. Der Ablauf des Originals ist identisch zu meinem und ich vermute, dass auch der generierte Maschinen Code sich nicht nennenswert unterscheidet. Deshalb bin ich von der originalen Syntax abgewichen. Ich habe auch mit dem Original Duff’s Device mit vier Stufen getestet. Die Ergebnisse waren bis auf statistisches Rauschen mit meiner Implementation identisch.