[C][C++] Dywagacje o i++ a ++i i optymalizacjach

Santiago A · Post autor: **Santiago A** » 28 sie 2016, o 11:20

W którym współczesnym kompilatorze można odczuć różnicę między ++i oraz i++?

kalwi · Post autor: **kalwi** » 28 sie 2016, o 12:06

Co do samego ++i oraz i++ to w sumie w żadnym (chyba, że będzie takich działań baaardzo dużo i będzie wyłączona optymalizacja - wtedy w każdym). Natomiast co do reszty przypadków:

Dopiero jak przejdzie ci zastąpić to iteratorem lub większą liczbą lub obiektem np streampos ... eam/tellg/ wtedy kompilator nawet nie ma prawa nic optymalizować i będziesz mieć bezsensowne "wycieki czasu".

athame · Post autor: **athame** » 28 sie 2016, o 14:35

Daj przykład kodu do sprawdzenia, bo inaczej uznaję to za prowokację. Stwierdzenie "kompilator nawet nie ma prawa nic optymalizować" jest niezgodne z używanymi przeze mnie kompilatorami, a przynajmniej nie można łatwo całkowicie zablokować optymalizacji. Mam wrażenie, że ten cytowany tekst zdezaktualizował się kilka lat temu.

Santiago A · Post autor: **Santiago A** » 28 sie 2016, o 14:58

Pozwolę sobie zacytować komentarz z pewnej strony poświęconej takim zagadnieniom.

Mark Harrison pisze:I used to be a compiler writer, and had the opportunity to test this code on many CPUs, operating systems, and compilers. The only compiler I found that didn't optimize the i++ case (in fact, the compiler that brought this to my attention professionally) was the Software Toolworks C80 compiler by Walt Bilofsky. That compiler was for Intel 8080 CP/M systems. It's safe to say that any compiler which does not include this optimization is not one meant for general use.

kalwi · Post autor: **kalwi** » 28 sie 2016, o 18:07

Kod: Zaznacz cały

#include <iostream>
#include <vector>
#include <ctime>

int main()
{
    clock_t t1, t2, t3, t4;

    t1 = clock();
    std::vector<long long int> vec1;
    for (long long int i = 0; i < 999999999L; ++i)
        vec1.push_back(i);
    t2 = clock();
    float diff1 ((float)t2-(float)t1);
    float seconds1 = diff1 / CLOCKS_PER_SEC;
    std::cout << "++i: " << seconds1 << " s" << std::endl;

    t3 = clock();
    std::vector<long long int> vec2;
    for (long long int i = 0; i < 999999999L; i++)
        vec2.push_back(i);
    t4 = clock();
    float diff2 ((float)t4-(float)t3);
    float seconds2 = diff2 / CLOCKS_PER_SEC;
    std::cout << "i++: " << seconds2 << " s" << std::endl;
    return 0;
}

Na moim Macbooku:

Kod: Zaznacz cały

++i: 38.7001 s
i++: 42.5566 s

-- 28 sie 2016, o 17:08 --

athame pisze:Daj przykład kodu do sprawdzenia, bo inaczej uznaję to za prowokację. Stwierdzenie "kompilator nawet nie ma prawa nic optymalizować" jest niezgodne z używanymi przeze mnie kompilatorami, a przynajmniej nie można łatwo całkowicie zablokować optymalizacji. Mam wrażenie, że ten cytowany tekst zdezaktualizował się kilka lat temu.

Słyszałeś o typie zmiennych volatile?

athame · Post autor: **athame** » 28 sie 2016, o 20:58

U mnie (Arch Linux 64-bit, GCC 6.1.1) taki wynik programu:

Kod: Zaznacz cały

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
Przerwane (zrzut pamięci)

Po zmniejszeniu iteracji do \(\displaystyle{ 199999999L}\) taki wynik:

Kod: Zaznacz cały

++i: 3.53009 s
i++: 3.47582 s

O volatile słyszałem, ale nie zajmuję się na co dzień programowaniem, więc nie mam z tym styczności.

kalwi · Post autor: **kalwi** » 29 sie 2016, o 00:54

Hmm rzeczywiście, dla mniejszej ilości iteracji też mi czasem tak pokazuje.
Ale jak wyłączy się optymalizacje w GCC (czyli -O0):

Kod: Zaznacz cały

Bez optymalizacji:
MBP-Dominik:desktop user$ g++ Untitled.cpp -O0 -o test
MBP-Dominik:desktop user$ ./test
++i: 8.84344 s
i++: 9.26068 s

Z optymalizacją: 

MBP-Dominik:desktop user$ g++ Untitled.cpp -o test1
MBP-Dominik:desktop user$ ./test1
++i: 9.35894 s
i++: 9.05727 s

Aczkolwiek to było na gcc 4.2.1 i w tym momencie kompiluje mi się 6.2.0 (no i tu jest wykorzystanie procka 95%, także wynik jeszcze się wstrzymam chwilę jeśli chodzi o pewność)

volatile to jest taki typ, którego kompilator nie ma prawa optymalizować (to oczywiście nie jest jego główna cecha, ale to nieistotne).

athame · Post autor: **athame** » 29 sie 2016, o 01:34

volatile ma sens tylko jeśli wymagana jest ściśle określona kontrola zachowania pamięci. W praktyce mikrokontrolery, a nie komputery uniwersalne. Jeśli już chcemy znaleźć odpowiednik javowego volatile w c++ dla procesora Intel x86 (także 64 bit) lub ARM, to będzie std::atomic.

Po wyłączeniu optymalizacji:

Kod: Zaznacz cały

++i: 3.56654 s
i++: 3.51086 s

kalwi · Post autor: **kalwi** » 29 sie 2016, o 01:52

Naprawdę ciekawe, że takie wyniki otrzymujesz przy tylu iteracjach. Po zaktualizowaniu gcc do 6.2.0 takie wartości dostałem:

Dla \(\displaystyle{ 999999999L}\):

Ukryta treść:

Dla \(\displaystyle{ 199999999L}\):

Ukryta treść:

Dla \(\displaystyle{ 55999999L}\):

Ukryta treść:

Dla \(\displaystyle{ 999999L}\):

Ukryta treść:

Wniosek: jestem mocno przekonany, że jakbyś zwiększył rozmiar iteracji (bo, zakładając, że u Ciebie LLI waży 8 bajtów, to wtedy \(\displaystyle{ 999999999L}\) LLI zajmie koło 7,4GB RAMu - więc rzeczywiście może wywalić błąd o przepełnieniu stosu) to wtedy byś dostał wynik podobny do mojego (tj. coraz widoczniejsza będzie przewaga preinkrementacji nad postinkrementacją)

I jeszcze tak dla porównania GCC 4.2.1 (\(\displaystyle{ 999999999L}\)):

Ukryta treść:

Fajnie widać efekty pracy nad optymalizacją na poziomie kompilatora

athame · Post autor: **athame** » 29 sie 2016, o 01:57

No niestety nie zwiększę dostępnego RAM-u. Takie wyniki mam dla procesora i7-3612QM (laptop Clevo).

kalwi · Post autor: **kalwi** » 29 sie 2016, o 02:12

No niestety W każdym razie mam nadzieję, że pokazałem, że jednak jest różnica pomiędzy ++i oraz i++

athame · Post autor: **athame** » 29 sie 2016, o 06:33

Różnica jest, ale u mnie przy wszystkich dopuszczalnych wartościach (ograniczenia rozmiaru pamięci) jest dokładnie odwrotnie niż postulowałeś od początku:

Kod: Zaznacz cały

tmp : cat speed.cpp | grep for
    for (long long int i = 0; i < 199999999L; ++i)
    for (long long int i = 0; i < 199999999L; i++)
tmp : g++ -O0 speed.cpp -o speed
tmp : g++ speed.cpp -o speedO
tmp : ./speed
++i: 3.46913 s
i++: 3.39606 s
tmp : ./speedO
++i: 3.46237 s
i++: 3.39336 s

i jeszcze w ramach uzupełnienia:

Kod: Zaznacz cały

tmp : g++ -O3 speed.cpp -o speed
tmp : ./speed 
++i: 1.09391 s
i++: 1.00993 s

Sprzęt:

Kod: Zaznacz cały

tmp : cat /proc/cpuinfo | grep name | uniq && free -h
model name      : Intel(R) Core(TM) i7-3612QM CPU @ 2.10GHz
              razem       użyte       wolne    dzielone   buf/cache    dostępne
Pamięć:        7,7G        951M        5,5G        446M        1,3G        6,1G
Wymiana:        511M          0B        511M

Post autor: **Afish** » 29 sie 2016, o 10:18

kalwi pisze:

Kod: Zaznacz cały

#include <iostream>
#include <vector>
#include <ctime>

int main()
{
    clock_t t1, t2, t3, t4;

    t1 = clock();
    std::vector<long long int> vec1;
    for (long long int i = 0; i < 999999999L; ++i)
        vec1.push_back(i);
    t2 = clock();
    float diff1 ((float)t2-(float)t1);
    float seconds1 = diff1 / CLOCKS_PER_SEC;
    std::cout << "++i: " << seconds1 << " s" << std::endl;

    t3 = clock();
    std::vector<long long int> vec2;
    for (long long int i = 0; i < 999999999L; i++)
        vec2.push_back(i);
    t4 = clock();
    float diff2 ((float)t4-(float)t3);
    float seconds2 = diff2 / CLOCKS_PER_SEC;
    std::cout << "i++: " << seconds2 << " s" << std::endl;
    return 0;
}

Przecież ten kod nawet nie bada tego, o co się spieracie. Jak chcecie wnioskować o szybkości pojedynczej instrukcji, skoro większość pracy program wykona w alokacji pamięci? O takich „szczegółach”, jak niejednakowe środowisko, wykonanie testów tysiące razy, porównanie kodu maszynowego, czy optymalizacje na poziomie procesora już nie wspomnę.

athame pisze:Stwierdzenie "kompilator nawet nie ma prawa nic optymalizować" jest niezgodne z używanymi przeze mnie kompilatorami, a przynajmniej nie można łatwo całkowicie zablokować optymalizacji. Mam wrażenie, że ten cytowany tekst zdezaktualizował się kilka lat temu.

Jest jak najbardziej zgodne, bo i++ i ++i są semantycznie różnymi operacjami i ich optymalizowanie nie może zmienić zachowania. Jeżeli i++ ma jakiekolwiek efekty zewnętrzne (a w cytowanym poście chodziło o obiekty, dla których te operatory są jawnie przeciążone, więc takie efekty jak najbardziej mogą występować), to nie można ot tak zamienić tych operacji, bo zmieniłoby to logikę programu.

kalwi pisze:Słyszałeś o typie zmiennych volatile?

volatile nie zablokuje wszystkich optymalizacji, zmieni jedynie sposób ich przeprowadzenia, najczęściej przez wstawienie barier w pamięci, co nie oznacza, że i++ nie zostanie zamienione na ++i lub na odwrót. W szczególności jakiekolwiek teoretyzowanie o optymalizacjach jest niewiarygodne bez solidnych testów, bo poza optymalizacjami w trakcie kompilacji jest masa przyspieszeń, które wykonuje procesor. Nawet fakt, że kompilator wygeneruje kod wykonujący fizycznie i++ nie oznacza, że taki kod zostanie wykonany przez jednostkę obliczeniową.

Polecam poczytać o modelach pamięci i dlaczego double-checked lock działa w Javie, ale już niekoniecznie w C++. Tutaj krótka prezentacja pokazująca, co właściwie różne procesory mogą zrobić nawet z najprostszymi kodami:

Kod: Zaznacz cały

https://vimeo.com/171942746

Matematyka.pl

[C][C++] Dywagacje o i++ a ++i i optymalizacjach

[C][C++] Dywagacje o i++ a ++i i optymalizacjach

[error] - runge kutty felberg C++

[error] - runge kutty felberg C++

[error] - runge kutty felberg C++

[error] - runge kutty felberg C++

[error] - runge kutty felberg C++

[error] - runge kutty felberg C++

[error] - runge kutty felberg C++

[error] - runge kutty felberg C++

[error] - runge kutty felberg C++

[error] - runge kutty felberg C++

[error] - runge kutty felberg C++

[error] - runge kutty felberg C++