RPH - blog

Blog programisty

C++, operatory pre i post inkrementacji w nowoczesnych kompilatorach

Opublikowany: Czwartek 07.01.2016
0

Bardzo popularnym zaleceniem dla programistów C++, jest rada, aby tam gdzie jest tylko możliwe używać operatora pre inkrementacji, zamiast post inkrementacji, szczególnie w pętlach.

Zalecenie to znajduje się w dokumencie Collaborative Collection of C++ Best Practices, w rozdziale przeznaczonym wydajności: https://github.com/lefticus/cppbestpractices/blob/master/08-Considering_Performance.md#prefer-i-to-i

Dobre wyjaśnienie dlaczego należy tak postępować znajduje się na blogu Gynvael Coldwind: C/C++ szybkość i++ oraz ++i once more, reply (niestety link do kodzimy.net, który jest tam umieszczony nie działa).

Zatem, operator pre inkrementacji, w przeciwieństwie do operatora post inkrementacji, nie tworzy tymczasowej kopii obiektu. Jest tak dla typów, które nie są typami podstawowymi, ale np. iteratorami.

Ponieważ nowoczesne kompilatory potrafią bardzo agresywnie optymalizować kod wynikowy, tak, że wygenerowanego kodu asemblerowego jest mniej niż kodu C++ z którego powstał (jaskrawy przykład tu: A flexible lexicographical comparator for C++ structs ), postanowiłem sprawdzić jak to dziś wygląda w praktyce.

TL;DR Wnioski znajdują się na końcu Wnioski

Kod do testów

Na to, jaki kompilator wygeneruje kod wpływ może mieć wiele czynników. Należy więc sprawdzić co wygeneruje kompilator dla typu iterator oraz const_iterator. Pod uwagę należy wziąć również sytuację, w której iterator będący terminatorem (inaczej wskazujący na koniec kontenera) jest definiowany przed pętlą for. Dlatego do porównania są cztery pary funkcji. Kod, który został poddany testom znajduje się poniżej:

#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <algorithm>

void test_non_const_postinc_endwithinfor(std::vector<int>& vec)
{
    for(std::vector<int>::iterator i = vec.begin(); i!= vec.end(); i++)
    {
        std::cout<<*i<<std::endl;
    }
}

void test_const_postinc_endwithinfor(const std::vector<int>& vec)
{
    for(std::vector<int>::const_iterator i = vec.begin(); i!= vec.end(); i++)
    {
        std::cout<<*i<<std::endl;
    }
}

void test_non_const_preinc_endwithinfor(std::vector<int>& vec)
{
    for(std::vector<int>::iterator i = vec.begin(); i!= vec.end(); ++i)
    {
        std::cout<<*i<<std::endl;
    }
}

void test_const_preinc_endwithinfor(const std::vector<int>& vec)
{
    for(std::vector<int>::const_iterator i = vec.begin(); i!= vec.end(); ++i)
    {
        std::cout<<*i<<std::endl;
    }
}


void test_non_const_preinc_endoutsidefor(std::vector<int>& vec)
{
    std::vector<int>::iterator end = vec.end();
    for(std::vector<int>::iterator i = vec.begin(); i!= end; ++i)
    {
        std::cout<<*i<<std::endl;
    }
}

void test_const_preinc_endoutsidefor(const std::vector<int>& vec)
{
    std::vector<int>::const_iterator end = vec.end();
    for(std::vector<int>::const_iterator i = vec.begin(); i!= end; ++i)
    {
        std::cout<<*i<<std::endl;
    }
}

void test_non_const_postinc_endoutsidefor(std::vector<int>& vec)
{
    std::vector<int>::iterator end = vec.end();
    for(std::vector<int>::iterator i = vec.begin(); i!= end; i++)
    {
        std::cout<<*i<<std::endl;
    }
}

void test_const_postinc_endoutsidefor(const std::vector<int>& vec)
{
    std::vector<int>::const_iterator end = vec.end();
    for(std::vector<int>::const_iterator i = vec.begin(); i!= end; i++)
    {
        std::cout<<*i<<std::endl;
    }
}

int main()
{
    std::vector<int> vec;
    vec.push_back(4);
    vec.push_back(5);
    vec.push_back(12);
    vec.push_back(44);
    vec.push_back(122);

    test_non_const_postinc_endwithinfor(vec);
    test_const_postinc_endwithinfor(vec);

    test_non_const_postinc_endoutsidefor(vec);
    test_const_postinc_endoutsidefor(vec);

    test_non_const_preinc_endwithinfor(vec);
    test_const_preinc_endwithinfor(vec);

    test_non_const_preinc_endoutsidefor(vec);
    test_const_preinc_endoutsidefor(vec);

    return 0;
}

Kolejną czynnikiem jest poziom optymalizacji kodu wynikowego. Wziąłem pod uwagę aż 4: -O0 -O1 -O2 -O3.

Na warsztat wziąłem dwa kompilatory: Clang oraz GCC, w wersjach, które domyślnie są zainstalowane w moim systemie (Debian testing).

Wersja GCC:

$ g++ --version
g++ (Debian 5.3.1-5) 5.3.1 20160101
Copyright (C) 2015 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Wersja Clang:

$ clang++ --version
Debian clang version 3.6.2-3 (tags/RELEASE_362/final) (based on LLVM 3.6.2)
Target: x86_64-pc-linux-gnu
Thread model: posix

Łącząc to wszystko (2 kompilatory, 4 pary funkcji, 4 poziomy optymalizacji), uzyskujemy 32 przypadki testowe. Badanie tego ręcznie byłoby bardzo żmudne, błędogenne oraz czasochłonne. Dlatego za pomocą GNU Make oraz Basha udało mi się zautomatyzować ten proces.

Automatyzacja procesu porównania

Założyłem, że jeżeli kompilator powinien wygenerować taki sam kod dla post inkrementacji oraz pre inkrementacji. Oczywiście różnice mogą być w nazwach funkcji, oraz adresach, jednak w procesie porównywania wziąłem to pod uwagę.

Kompilacja kodu

Fragment pliku Makefile, odpowiedzialny za wygenerowanie plików wykonywalnych przez różne kompilatory z różnym poziomem optymalizacji:

CFLAGS = -Wall -Wextra -std=c++11

gcc_o0: main.cpp
    g++ -O0 -o $@ $< $(CFLAGS)

gcc_o1: main.cpp
    g++ -O1 -o $@ $< $(CFLAGS)

gcc_o2: main.cpp
    g++ -O2 -o $@ $< $(CFLAGS)

gcc_o3: main.cpp
    g++ -O3 -o $@ $< $(CFLAGS)

clang_o0: main.cpp
    clang++ -O0 -o $@ $< $(CFLAGS)

clang_o1: main.cpp
    clang++ -O1 -o $@ $< $(CFLAGS)

clang_o2: main.cpp
    clang++ -O2 -o $@ $< $(CFLAGS)

clang_o3: main.cpp
    clang++ -O3 -o $@ $< $(CFLAGS)

Nazewnictwo plików

Dla każdej funkcji skrypt wygenerował zbiór plików o nazwach:

  • nazwa_funkcji.plik_wykonywalny.disassm
  • nazwa_funkcji.plik_wykonywalny.disassm.raw

W pliku z rozszerzeniem disassm znajduje się kod gotowy do porównania, natomiast w pliku raw nieprzetworzone wyjście disassemblera. Do tego procesu został wykorzystany gdb. Reguła do generowania znajduje się również w Makefile:

%.disassm: 
    @gdb -batch -ex 'file ./'$< \
    -ex 'disassemble '`echo $* | sed 's/^\(.*\)\..*$$/\1/'` \
    | c++filt \
    | tee $*.disassm.raw \
    | sed 's/^\s.*:\s*//' \
    | sed 's/'`echo $* | sed 's/^\(.*\)\..*$$/\1/'`'/test_function/g' > $*.disassm

c++filt jest to program który zamienia nazwy funkcji zmienione przez kompilator (Dekorowanie nazw) na nazwy czytelne dla programisty, np:

_ZNSt6vectorIiSaIiEE9push_backEOi

zostanie zamienione na:

std::vector<int, std::allocator<int> >::push_back(int&&)

Usuwane są także adresy instrukcji edytorem sed, a nazwa badanej funkcji jest zamieniana na test_function, aby była taka sama we wszystkich plikach i nie wpływała na wynik porównania.

Makefile generuje 128 plików - 64 pliki raw oraz 64 pliki disassm.

Porównywanie kodu

Mając wygenerowane pliki można automatycznie je porównać, czym zajmuje się ten skrypt bash:

#!/bin/bash

OBJECTS=(gcc_o0 gcc_o1 gcc_o2 gcc_o3 clang_o0 clang_o1 clang_o2 clang_o3)

FILE_PREFIXES=(test_non_const_  test_const_)

FILE_SUFFIXES=(inc_endwithinfor  inc_endoutsidefor)

for object in ${OBJECTS[*]}
do
    for prefix in ${FILE_PREFIXES[*]}
    do
        for suffix in ${FILE_SUFFIXES[*]}
        do
            file1="${prefix}pre${suffix}.$object.disassm"
            file2="${prefix}post${suffix}.$object.disassm"
            if cmp -s $file1 $file2
            then
                echo "$file1  $file2  SAME CONTENT" >> results.txt
            else
                echo  "$file1  $file2  DIFFERENT CONTENT" >>  results.txt
            fi
        done
    done
done

Wyniki

Clang

Dla optymalizacji -O2 oraz -O3 Clang wygenerował taki sam kod, niezależnie czy została użyta pre inkrementacja czy post inkrementacja.

Dla optymalizacji -O0 oraz -O1 Clang wygenerował kod, który różni się tylko wywołaniem operatora inkrementacji, w jednym przypadku jest wywoływana funkcja operator++(int) w drugim operator++().

GCC

Wyniki dla GCC są dużo ciekawsze. Po pierwsze rzuca się w oczy, że dla optymalizacji -O3 jedna para funkcji się różni - bliższe spojrzenie na kod i wniosek jest taki, że kompilator zamienił kolejność rejestrów w instrukcji: cmp %rbp,%r13 zamiast cmp %r13,%rbp. W innych przypadkach, dla tego poziomu optymalizacji gcc wygenerował ten sam kod.

Dla -O2 wygenerowany kod jest różny dla 3 par funkcji. Bliższe spojrzenie na to jest zaskakujące:

Dump of assembler code for function test_non_const_preinc_endoutsidefor(std::vector<int, std::allocator<int> >&):
   0x0000000000400ea0 <+0>: jmpq   0x400e00 <test_non_const_postinc_endoutsidefor(std::vector<int, std::allocator<int> >&)>
End of assembler dump.

Dla wszystkich czterech pary funkcji są takie same: skok do innej funkcji, która robi to samo. Zatem GCC zoptymalizował kod pod względem rozmiaru. Potrafił uznać, że funkcja, która zamiast post inkrementacji używa pre inkrementacji robi to samo i wygenerował kod dla jednej, a dla drugiej wstawił tylko skok do pierwszej. M A G I A.

Dla optymalizacji -O1 gcc wygenerował taki sam kod dla wszystkich par funkcji. Dla -O0, podobnie jak clang, kod różni się wywołaniem funkcji operatora inkrementacji.

Wnioski

Główny wniosek jest krótki: dla nowoczesnych kompilatorów nie ma znaczenia czy używamy pre czy post inkrementacji.

Oczywiście ma znaczenie jakiego kompilatora używamy i z jakim poziomem optymalizacji był kompilowany kod. GCC potrafi już to zrobić dla -O1, Clang dla -O2.

Oczywiście badam tylko niewielki obszar. Aby dokładniej zbadać temat powinienem sprawdzić to na innych systemach operacyjnych, większej ilości kompilatorów, wziąć pod uwagę chociażby Visual Studio. Nie mam też pojęcia jaki kod zostanie wygenerowany dla innych procesorów.

Największym zaskoczeniem było dla mnie to, że GCC potrafi uznać, że funkcja używająca pre inkrementacji robi to samo co funkcja używająca post inkrementacji i wygenerować kod dla pierwszej, a dla drugiej wstawić skok bezwarunkowy do tej pierwszej. Po prostu magia.

Pomimo tego, że testy wypadły pomyślnie uważam że pre inkrementacja powinna być używana zamiast post inkrementacji tam gdzie to tylko możliwe. Przecież nie wszędzie używamy najnowszych kompilatorów...

Pliki do pobrania

Gdyby ktoś chciał sam sprawdzić może pobrać skrypty i kod stąd: iterators.tar.bz2.

W tym pliku znajdują się również wygenerowane pliki wykonywalne, plik results.txt z wynikami porównania oraz wszystkie 128 plików z kodem wynikowym.

Jeżeli ktoś dysponuje wolnym czasem i zasobami może sam zabrać się za badania. Chętnie obejrzę wyniki.


Nie ma jeszcze komentarzy

Zostaw komentarz