Lepsza alokacja jako cel

W poprzednim artykule zapowiedziałem prezentację wysiłków w kierunku opracowania autorskich metod alokacji pamięci. Metody mają być oparte o statyczną analizę kodu, a wszystko w ramach budowy kompilatora własnego eksperymentalnego języka Mediolan. Czy jednak gra jest warta świeczki? Czy warto rozwijać skomplikowaną teorię po to, żeby uzyskać mityczne usprawnienie kodu? W dzisiejszym artykule postaram się odpowiedzieć na to pytanie, prezentując eksperymenty, które doprowadziły mnie do silnego przekonania, że tak jest.

Nie skupiam się na warstwie składniowej, zakładając, że techniki, które tu opisuję będą miały zastosowanie w językach wysokiego poziomu opartych o abstrakcyjne typy danych, kontrolę sterowania przez dopasowywanie wzorców i programowanie funkcji rekurencyjnych. W duchu ML, a współcześniej - Haskella, Scali. Pythoniści powinni też wiedzieć o czym mówię, przytulili te idee parę lat temu, w Pythonie mamy też match/case.

Takie języki mają konstruktory i dekonstruktory, to jest bardzo wygodne, ale wymaga dynamicznej alokacji. Jeśli sprowadzić to do operacji podstawowych, możemy myśleć o lispowej trójce car/cdr/cons, jako o minimalnym modelu takiego zestawu.

Żeby zobaczyć, na ile alokacja pamięci na zasadzie „bierz i zapomnij” może być szybsza chociażby od nowocześnie zaimplementowanego zliczania referencji, napisałem mały kawałek kodu, implementujący te trzy - właśnie car/cdr/cons - na dwa sposoby: za pomocą alokowania przez std::shared_ptr - co odpowiada zliczaniu referencji, oraz - za pomocą pobierania pamięci z nieskończonego („mentalnie!”) bufora.

Kod

Kod jest dość prosty. Funkcja cons odpowiada tutaj konstruktorowi, który z dwóch obiektów tworzy parę. car i cdr pobierają odpowiednio pierwszy - i drugi element. Sama trójka car/cdr/cons nie wystarczy, żeby pisać jakiekolwiek programy, trzeba jeszcze móc operować na tych danych, pobierać je, czytać, wypisywać. Dodajemy więc założenie, że naszymi atomami są zawsze liczby int (będziemy mogli je wypisywać, sortować, ale także dostaniemy za darmo arytmetykę), a dodatkowe operacje, których potrzebujemy to sprawdzenie danych (is_cons) i pobranie (get_atom).

To wszystko, czego potrzebujemy, żeby pisać proste benchmarki:

Dwojaka implementacja opiera się - po pierwsze na std::shared_ptr:

struct data {
        using ptr = std::shared_ptr<std::pair<data, data>>;
        std::variant<ptr, int> value;
        
        data(int x) : value(x) {}
        data(const data& x, const data& y) : value(std::make_shared<std::pair<data, data>>(x, y)) {};
    };

    data cons(const data& x, const data& y)
    {
        return data(x, y); // Wywołuje konstruktor pary
    }

a po drugie na unii:

struct data {
        int  type_tag;
        
        union {
            int  i;
            data *ptr;
        }  value;
        
        data() = default;
        data( int x ): type_tag(0) { value.i = x; };
    };

    data      pseudo_heap[ 12000000 ];
    data     *first_free = pseudo_heap;

    data  *alloc_new()
    {
        data  *result = first_free;
        first_free += 2;
        return  result;
    }

    data cons( const data& x, const data& y )
    {
        data  result;
        result.type_tag = 1;
        result.value.ptr = alloc_new();
        result.value.ptr[ 0 ] = x;
        result.value.ptr[ 1 ] = y;
        return  result;
    }

Gdy już mamy te mechanizmy, można przystąpić do porównania szybkości ich działania, przykładowo odwracając listę. Stosowałem taki oto przykład:

//  Rekursywna funkcja budująca długą listę
    data  mklist( data len, data acc )
    {
        if ( get_atom(len) == 0 )
            return  acc;
                       
        data  next = get_atom(len) - 1;
        data  acc1 = cons( next, acc );
        return  mklist( next, acc1 );
    }

    //  Rekursywna funkcja odwracająca listę - pomocnicza funkcja
    data  reverse_helper( data list, data acc )
    {
        if ( !is_cons(list) )
            return  acc;
        return  reverse_helper( cdr(list), cons(car(list), acc) );
    }

    //  Funkcja odwracająca listę
    data  reverse( data list )
    {
        return  reverse_helper( list, 0 );
    }

    int main()
    {
        data list = mklist( 160, 0 );

        for ( int i=0; i<20001; i++ ) 
            list = reverse( list );

        std::cout << show(list) << '\n';

        std::cout << first_free - pseudo_heap << '\n';
        return 0;
    }

To tylko tyle - i aż tyle.

Pierwsze wyniki

Po skompilowaniu w trybie g++ -O4 otrzymujemy dwukrotne przyspieszenie kodu z „pseudostertą” w stosunku do kodu opartego na nowoczesnych inteligentnych wskaźnikach ze standardowej biblioteki Gnu C++.

Czy to dużo, czy mało?

Z jednej strony - marzymy o jeszcze większym przyroście! Przecież zliczanie referencji to niekoniecznie najnowocześniejsza strategia alokacji pamięci.

Ale - dużo mniej niż dwukrotny „kop” to jest coś, o co często właśnie walczy się podczas tuningu mechanizmów kompilacji.

Niepokoił mnie jednak ten wynik, intuicyjnie odbierałem go jako zbyt słaby. Postanowiłem się więc przyjrzeć dokładniej metodzie badań i znaczeniu liczb, które się tu pojawiły. Do pomiaru używałem systemowego narzędzia time, które pokazuje zużycie czasu w podziale na czas systemowy i czas w przestrzeni użytkownika:

Czas Pseudosterta (z resetem) std::shared_ptr
real 0m0,087s 0m0,151s
user 0m0,033s 0m0,147s
sys 0m0,054s 0m0,004s

Co prawda mamy widoczny zysk 73.5% rzeczywistego czasu, ale dlaczego czas systemowy jest gorszy ?

Poprawka !

Po chwili zastanowienia (i po przedyskutowaniu sprawy z Gemini, a jakże), doszedłem do wniosku, że moja ogromna tablica, alokowana na zapas, jako właśnie ta „pseudosterta” stanowi pewien problem dla systemu, bo - po prostu - musi ją zaalokować. Co prawda tylko raz, ale - pomyślałem - skonstruujmy ten benchmark inaczej, dajmy mu szanse!.

Wprowadziłem więc szybko następującą zmianę:

int main()
    {
        data list = 0;

        for ( int i=0; i<41; i++ ) 
        {       
            list = mklist( 160, 0 );

            for ( int i=0; i<20001; i++ ) 
                list = reverse( list );

            //  Oszustwo, żeby udawać nieskończenie wielką pamięć ...
            //  W rzeczywistości, w prawdziwym "Mediolanie" będzie to odpowiadać 
            //  resetowaniu regionów.
            first_free = pseudo_heap;
        }

        std::cout << show(list) << '\n';
        return 0;
    }

Zmiana powinna pomóc – myślałem – pamięć nie będzie alokowana w tak wielkim kawałku, nie wymaga to dostępu do wielu stron pamięci systemowej, będzie szybsze.

Nie pomyliłem się. Wyniki były wyraźnie lepsze:

Czas Pseudosterta (z resetem) std::shared_ptr
real 0m0,711s 0m5,491s
user 0m0,661s 0m5,487s
sys 0m0,050s 0m0,004s

Teraz zysk jest już imponujący i wynosi 673% czasu rzeczywistego. Niemal siedmiokrotne przyspieszenie. Odetchnąłem szczęśliwy - warto to dalej badać!.

Interpretacja i wnioski

Gigantyczna różnica czasu alokacji wynika z narzutu, jaki jest potrzebny dla std::shared_ptr przy inkrementowaniu liczników i sprawdzaniu ich oraz oczywiście przy alokacji i dealokacji małych kawałków pamięci. Tego właśnie oczekiwaliśmy.

Z kolei wersja z „pseudostertą”, czyli bump-pointer alokuje pamięć dużym blokiem, robi to rzadziej, a operacja pojedynczej alokacji jest superszybka (inkrementacja licznika).

Oczywiście czas systemowy nadal jest obecny, ale staje się nieistotnym ułamkiem. Zresztą przecież nie da się go uniknąć.

Taki styl działania jest celem dla Mediolanu. Alokacja w regionach ma to umożliwić, tutaj mamy tego przedsmak. Żeby to było możliwe, kompilator musi umieć sam stwierdzić, jak, kiedy i gdzie tworzyć i usuwać regiony. To trudne zagadnienie, ale podejmuję się w dalszym ciągu zaprezentować pomysły teoretyczne, które doprowadzą do tego celu. Kompilator ma bez udziału programisty zbudować optymalną strategię alokacji regionami.

Co dalej ?

Idziemy więc dalej. Może skonstruowanie bardziej złożonych benchmarków (pomyśl o sortowaniu list!) pokaże jakieś dodatkowe wnioski? A może porównanie tego kodu z odpowiednikiem w Pythonie, Haskellu (ten jest znakomity jeśli chodzi o wydajność, w dużym stopniu ze względu właśnie na kompilowany kod ze statycznym systemem typów!), w Clojure (skoro car/cdr/cons), albo innych Lispach ? Może wykonam takie porównania.

W kolejnych odcinkach pokażę próby rozszerzenia tych benchmarków na większe algorytmy (jak już mówiłem - myślę o sortowaniu) i na inne języki (Roboty są w stanie napisać analogiczny kod w dowolnym języku programowania).

Będę też prezentować kolejny logiczny krok w toku rozumowania, który prowadzi do statycznej analizy kodu, jakim jest eliminacja rekurencji.

◅   powrót do strony głównej