Optymalizacja przez TMP

TMP (template metaprogramming – metaprogramowanie szablonowe) nie jest już nowinką techniczną w świecie C++ (lepsze języki znały to od dawna). Nie jest także nowością, że można to użyć jako podpowiedź dla kompilatora “jak optymalizować operacje matematyczne”. Książka “Perełki Programowania Gier: Tom 1″ zawierająca opis m.in. tej techniki została wydana w 2002-gim roku.

3 lata później wydana została książka poświęcona w całości TMP, “Język C++. Metaprogramowanie za pomocą szablonów”. Powiedziano więc już na ten temat prawie wszystko, co można powiedzieć. Stąd moja wiadomość nie powinna uchodzić za odkrywczą.

// MULPROC = TRADITIONAL lub TMP
// MAT_SZ = bok macierzy
// REPEAT = ilosc powtorzen testu


template
class Mtx;


// makro do definiowania funkcji metaprogramu ;-)
#define FO(X...)                                                \
    {                                                           \
    public:                                                     \
        template                                                \
            static inline void _do(const Mtx & left,            \
                                   const Mtx & right,           \
                                   Mtx & result)                \
        {                                                       \
            X;                                                  \
        }                                                       \
    }
// C++ Template metaprogram lub normalnie
namespace MtxMul
{
    template
    class for_each_element
    FO(result.a[i-1][j-1]+=left.a[i-1][k-1]*right.a[k-1][j-1];
       for_each_element::_do(left,right,result));
 
    template
    class for_each_element
    FO();
    template
    class for_each_column
    FO(result.a[i-1][j-1]=left.a[i-1][size-1]*right.a[size-1][j-1];
       for_each_element::_do(left,right,result);
       for_each_column::_do(left,right,result));
    template
    class for_each_column
    FO();
 
    template
    class for_each_row
    FO(for_each_column::_do(left,right,result);
       for_each_row::_do(left,right,result));
    template<>
    class for_each_row<0>
    FO();
    template
    static inline void TMP(const Mtx & left,
               const Mtx & right,
               Mtx & result)
    {
    for_each_row::_do(left,right,result);
    }
    // podejscie tradycyjne
    template
    static inline void TRADITIONAL(const Mtx & left,
                const Mtx & right,
                Mtx & result)
    {
    for (long i = size; i ; i--)
        for (long j = size; j ; j--)
        {
        result.a[i-1][j-1]=left.a[i-1][size-1]*right.a[size-1][j-1];
        for (long k = size-1; k ; k--)
            result.a[i-1][j-1]+=left.a[i-1][k-1]*right.a[k-1][j-1];
        }
    }
};// namespace MtxMul
#undef FO
 
template
class Mtx // square matrix
{
public:
    F a[size][size];// elementy
    Mtx(){;}
    Mtx operator* (const Mtx & right)
    {
        Mtx result;
        MtxMul::MULPROC(*this, right, result);
        return result;
    }
private:
};// class Mtx
 
int main (int argc,char ** argv)
{
    Mtx A;
    for (long i = 0 ; i!= MAT_SZ ; i++ )
    for (long j = 0 ; j!= MAT_SZ ; j++ )
        A.a[i][j]=0;
    for (long i = 0 ; i!=REPEAT ; i++)
    A=A*A;


    assert(A.a[0][0]<2);
    return 0;
}

/*main*/

Przeprowadzony test polegał na wielokrotnym mnożeniu macierzy N*N (naiwnym algorytmem o złożoności czasowen O(n^3) – są lepsze). Test był powtarzany dla różnych opcji kompilacji i dla różnych kompilatorów (konkretniej: tych trzech, które sprawdzałem również w poprzedniej wiadomości). Można powiedzieć: sprawdzam znów kompilatory, tylko pod innym kątem. Program testowy mnożył używając operatora * (a nie *=), co teoretycznie nie jest optymalne(wymaga dodatkowego kopiowania – kompilator powinien to zainlineować i zoptymalizować) ;-)

Wykres przedstawia czas wykonania testu w sekundach w zależności od wielkości macierzy (2 oznacza macierz 2×2, 13 oznacza macierz 13×13).

Wnioski? Szablonowe metaprogramowanie funduje dobre podpowiedzi kompilatorowi GCC dla macierzy 2×2, 3×3 oraz 4×4. Dla większych tylko wprowadza zamęt: z opcją -funroll-loops powstaje szybszy program mniejszym nakładem pracy (człowieka i komputera: skomplikowane programy TMP długo się kompilują) ;-) Dodatkowo nabroił tu kompilator Sun Studio: pomijając kwestię taką, że nie za bardzo wychodzi mu robienie programów z TMP, dla macierzy 4×4-elementowych i większych… miażdży on GCC ;-) Doskonale widać to na wykresie poniżej (prezentującym dla każdego z kompilatorów najlepszy wynik za jego pomocą uzyskany):