Czy w C ++ powinienem zawracać sobie głowę buforowaniem zmiennych, czy pozwolić kompilatorowi na optymalizację? (Aliasing)


114

Rozważmy następujący kod ( pjest typu unsigned char*i bitmap->widthjest typu całkowitego, który jest dokładnie nieznany i zależy od wersji jakiejś zewnętrznej biblioteki, której używamy):

for (unsigned x = 0;  x < static_cast<unsigned>(bitmap->width);  ++x)
{
    *p++ = 0xAA;
    *p++ = 0xBB;
    *p++ = 0xCC;
}

Czy warto to zoptymalizować [..]

Czy może zaistnieć przypadek, w którym przyniosłoby to bardziej wydajne wyniki, pisząc:

unsigned width(static_cast<unsigned>(bitmap->width));
for (unsigned x = 0;  x < width;  ++x)
{
    *p++ = 0xAA;
    *p++ = 0xBB;
    *p++ = 0xCC;
}

... czy jest to trywialne dla kompilatora, aby zoptymalizować?

Jaki kod uważasz za „lepszy”?

Uwaga od redaktora (Ike): dla tych, którzy zastanawiali się nad tekstem przekreślonym, pierwotne pytanie, tak jak zostało sformułowane, było niebezpiecznie bliskie terytorium poza tematem i było bardzo bliskie zamknięcia pomimo pozytywnych opinii. Te zostały usunięte. Jednak proszę nie karać tych, którzy odpowiedzieli na te dotknięte części pytania.


19
Jeśli *pjest tego samego typu, co widthwtedy, optymalizacja nie jest trywialna, ponieważ pmoże wskazywać widthi modyfikować ją wewnątrz pętli.
emlai

31
Pytanie o to, czy kompilator optymalizuje określoną operację, jest zwykle błędnym pytaniem. Ostatecznie interesuje Cię (zazwyczaj), która wersja działa szybciej, co należy po prostu zmierzyć.
SirGuy,

4
@GuyGreer Zgadzam się, chociaż powiedziałbym, że pytanie jest dobre lub przynajmniej interesujące, pomyślałem, że niestety odpowiedź brzmi: „musisz to zmierzyć dla każdego przypadku użycia”. Powodem jest to, że funkcjonalność jest przenośna, ale wydajność nie. Zależy to więc od każdej części procesu kompilacji, począwszy od kompilatora, a skończywszy na docelowej witrynie (kombinacja systemu operacyjnego i sprzętu). I oczywiście najlepiej przypuszczać, że kompilator jest w tym mądrzejszy od człowieka.
luk32

19
Gdybym był kompilatorem, zobaczyłbym, że twoje dwa przykłady nie są takie same. Możliwe, że pwskazuje na tę samą pamięć, co bitmap->width. Dlatego nie mogę prawnie zoptymalizować pierwszego przykładu do drugiego.
Mysticial

4
Gdzie jest przechowywane „p”? Sugerowałbym, że możesz uzyskać naprawdę dużą wygraną w wydajności, robiąc coś w rodzaju "char * ogranicz p2 = p;" a następnie używając „p2” zamiast „p” w pętli. Następnie, jeśli chcesz, aby zmiany w „p2” zostały zastosowane z powrotem do p, użyj „p + = (p2-p);”. Zauważ, że żaden wskaźnik zapisany w okresie życia p2 przez wskaźnik nie skopiowany z p2 nie może być odczytywany przy użyciu wskaźnika skopiowanego z p2 ani odwrotnie, a żadna kopia p2 nie może być używana w jakimkolwiek celu po okresie życia p2, ale kompilator może ich użyć fakty umożliwiające optymalizacje, których nie można osiągnąć w żaden inny sposób.
supercat

Odpowiedzi:


81

Na pierwszy rzut oka pomyślałem, że kompilator może wygenerować równoważny zestaw dla obu wersji z aktywowanymi flagami optymalizacji. Kiedy to sprawdziłem, zdziwiłem się, widząc wynik:

Źródło unoptimized.cpp

uwaga: ten kod nie jest przeznaczony do wykonania.

struct bitmap_t
{
    long long width;
} bitmap;

int main(int argc, char** argv)
{
    for (unsigned x = 0 ; x < static_cast<unsigned>(bitmap.width) ; ++x)
    {
        argv[x][0] = '\0';
    }
    return 0;
}

Źródło optimized.cpp

uwaga: ten kod nie jest przeznaczony do wykonania.

struct bitmap_t
{
    long long width;
} bitmap;

int main(int argc, char** argv)
{
    const unsigned width = static_cast<unsigned>(bitmap.width);
    for (unsigned x = 0 ; x < width ; ++x)
    {
        argv[x][0] = '\0';
    }
    return 0;
}

Kompilacja

  • $ g++ -s -O3 unoptimized.cpp
  • $ g++ -s -O3 optimized.cpp

Montaż (unoptimized.s)

    .file   "unoptimized.cpp"
    .text
    .p2align 4,,15
.globl main
    .type   main, @function
main:
.LFB0:
    .cfi_startproc
    .cfi_personality 0x3,__gxx_personality_v0
    movl    bitmap(%rip), %eax
    testl   %eax, %eax
    je  .L2
    xorl    %eax, %eax
    .p2align 4,,10
    .p2align 3
.L3:
    mov %eax, %edx
    addl    $1, %eax
    movq    (%rsi,%rdx,8), %rdx
    movb    $0, (%rdx)
    cmpl    bitmap(%rip), %eax
    jb  .L3
.L2:
    xorl    %eax, %eax
    ret
    .cfi_endproc
.LFE0:
    .size   main, .-main
.globl bitmap
    .bss
    .align 8
    .type   bitmap, @object
    .size   bitmap, 8
bitmap:
    .zero   8
    .ident  "GCC: (GNU) 4.4.7 20120313 (Red Hat 4.4.7-16)"
    .section    .note.GNU-stack,"",@progbits

Montaż (zoptymalizowany.s)

    .file   "optimized.cpp"
    .text
    .p2align 4,,15
.globl main
    .type   main, @function
main:
.LFB0:
    .cfi_startproc
    .cfi_personality 0x3,__gxx_personality_v0
    movl    bitmap(%rip), %eax
    testl   %eax, %eax
    je  .L2
    subl    $1, %eax
    leaq    8(,%rax,8), %rcx
    xorl    %eax, %eax
    .p2align 4,,10
    .p2align 3
.L3:
    movq    (%rsi,%rax), %rdx
    addq    $8, %rax
    cmpq    %rcx, %rax
    movb    $0, (%rdx)
    jne .L3
.L2:
    xorl    %eax, %eax
    ret
    .cfi_endproc
.LFE0:
    .size   main, .-main
.globl bitmap
    .bss
    .align 8
    .type   bitmap, @object
    .size   bitmap, 8
bitmap:
    .zero   8
    .ident  "GCC: (GNU) 4.4.7 20120313 (Red Hat 4.4.7-16)"
    .section    .note.GNU-stack,"",@progbits

różn

$ diff -uN unoptimized.s optimized.s
--- unoptimized.s   2015-11-24 16:11:55.837922223 +0000
+++ optimized.s 2015-11-24 16:12:02.628922941 +0000
@@ -1,4 +1,4 @@
-   .file   "unoptimized.cpp"
+   .file   "optimized.cpp"
    .text
    .p2align 4,,15
 .globl main
@@ -10,16 +10,17 @@
    movl    bitmap(%rip), %eax
    testl   %eax, %eax
    je  .L2
+   subl    $1, %eax
+   leaq    8(,%rax,8), %rcx
    xorl    %eax, %eax
    .p2align 4,,10
    .p2align 3
 .L3:
-   mov %eax, %edx
-   addl    $1, %eax
-   movq    (%rsi,%rdx,8), %rdx
+   movq    (%rsi,%rax), %rdx
+   addq    $8, %rax
+   cmpq    %rcx, %rax
    movb    $0, (%rdx)
-   cmpl    bitmap(%rip), %eax
-   jb  .L3
+   jne .L3
 .L2:
    xorl    %eax, %eax
    ret

Wygenerowany zestaw dla wersji zoptymalizowanej faktycznie ładuje ( lea) widthstałą, w przeciwieństwie do niezoptymalizowanej wersji, która oblicza widthprzesunięcie przy każdej iteracji ( movq).

Kiedy będę miał czas, w końcu opublikuję jakiś punkt odniesienia na ten temat. Dobre pytanie.


3
Byłoby interesujące zobaczyć, czy kod zostałby wygenerowany inaczej, gdybyś rzutował do const unsignedzamiast tylko unsignedw niezoptymalizowanym przypadku.
Mark Ransom

2
@MarkRansom Myślę, że to nie powinno mieć znaczenia: „Obietnica” bycia stałym jest tylko podczas pojedynczego porównania, a nie całej pętli
Hagen von Eitzen

13
Proszę nigdy nie korzystać z funkcji maindo testu dla optymalizacji. Gcc celowo oznacza go jako zimny i tym samym wyłącza niektóre jego optymalizacje. Nie wiem, czy tak jest w tym przypadku, ale to ważny nawyk.
Marc Glisse

3
@MarcGlisse Masz 100% racji. Napisałem to w pośpiechu, poprawię to.
YSC

3
Oto link do obu funkcji w jednej jednostce kompilacji na godbolt , przy założeniu, że bitmapjest globalny. Wersja inna niż CSEd używa operandu pamięci to cmp, co nie stanowi problemu dla perf w tym przypadku. Gdyby była lokalna, kompilator mógłby założyć, że inne wskaźniki nie mogą o niej „wiedzieć” i wskazywać na nią. Przechowywanie wyrażeń obejmujących wartości globalne w zmiennych temp nie jest złym pomysłem, o ile poprawia (lub nie szkodzi) czytelność lub jeśli wydajność jest krytyczna. O ile dużo się nie dzieje, tacy miejscowi mogą zwykle żyć w rejestrach i nigdy się nie rozlać.
Peter Cordes

38

W rzeczywistości nie ma wystarczających informacji z twojego fragmentu kodu, aby być w stanie to stwierdzić, a jedyną rzeczą, o której mogę pomyśleć, jest aliasowanie. Z naszego punktu widzenia jest całkiem jasne, że nie chcesz pi nie chcesz bitmapwskazywać tego samego miejsca w pamięci, ale kompilator o tym nie wie i (ponieważ pjest tego typu char*) kompilator musi sprawić, by ten kod działał, nawet jeśli pi bitmapnakładają się.

Oznacza to w tym przypadku, że jeśli pętla zmienia się bitmap->widthprzez wskaźnik p, to trzeba to zobaczyć przy ponownym czytaniu bitmap->widthpóźniej, co z kolei oznacza, że ​​przechowywanie jej w zmiennej lokalnej byłoby nielegalne.

Biorąc to pod uwagę, uważam, że niektóre kompilatory czasami generują dwie wersje tego samego kodu (widziałem poszlaki na to, ale nigdy bezpośrednio nie szukałem informacji o tym, co kompilator robi w tym przypadku) i szybko sprawdzą, czy wskaźniki alias i uruchom szybszy kod, jeśli uzna, że ​​jest to w porządku.

Biorąc to pod uwagę, podtrzymuję swój komentarz dotyczący prostego pomiaru wydajności obu wersji, moje pieniądze polegają na tym, że nie widzę żadnej stałej różnicy wydajności między dwiema wersjami kodu.

Moim zdaniem takie pytania są w porządku, jeśli celem jest poznanie teorii i technik optymalizacji kompilatorów, ale jest to strata czasu (bezużyteczna mikro-optymalizacja), jeśli Twoim końcowym celem jest przyspieszenie działania programu.


1
@GuyGreer: Jest to główny bloker optymalizacji; Uważam za niefortunne, że reguły językowe koncentrują się na regułach dotyczących typów skutecznych, zamiast identyfikować sytuacje, w których zapisy i odczyty różnych elementów są lub nie są bez kolejności. Reguły napisane w takim terminie mogłyby znacznie lepiej sprostać potrzebom kompilatora i programisty niż obecne.
supercat

3
@GuyGreer - czy restrictkwalifikator nie byłby odpowiedzią na problem aliasingu w tym przypadku?
LThode

4
Z mojego doświadczenia restrictwynika , że jest w dużej mierze chybiony. MSVC jest jedynym kompilatorem, jaki widziałem, który wydaje się robić to poprawnie. ICC traci informacje o aliasowaniu przez wywołania funkcji, nawet jeśli są one wbudowane. A GCC zwykle nie uzyskuje żadnej korzyści, chyba że zadeklarujesz każdy parametr wejściowy jako restrict(w tym thisdla funkcji składowych).
Mysticial

1
@Mystical: Jedną rzeczą do zapamiętania jest to, że charaliasy wszystkich typów, więc jeśli masz znak *, musisz go użyć restrictna wszystkim. Lub jeśli wymusiłeś ścisłe reguły aliasingu GCC, -fno-strict-aliasingwtedy wszystko jest uważane za możliwy alias.
Zan Lynx,

1
@Ray Najnowszą propozycją restrictsemantyki podobnej do typu w C ++ jest N4150 .
TC

24

Ok, więc zmierzyłem GCC -O3(używając GCC 4.9 na Linux x64).

Okazuje się, że druga wersja działa 54% szybciej!

Więc myślę, że aliasing jest rzeczą, nie myślałem o tym.

[Edytować]

Próbowałem ponownie pierwszej wersji ze wszystkimi wskaźnikami zdefiniowanymi za pomocą __restrict__i wyniki są takie same. Dziwne ... Albo aliasing nie jest problemem, albo z jakiegoś powodu kompilator nie optymalizuje go dobrze, nawet z __restrict__.

[Edytuj 2]

Ok, myślę, że byłem w stanie udowodnić, że problemem jest aliasing. Powtórzyłem mój pierwotny test, tym razem używając tablicy zamiast wskaźnika:

const std::size_t n = 0x80000000ull;
bitmap->width = n;
static unsigned char d[n*3];
std::size_t i=0;
for (unsigned x = 0;  x < static_cast<unsigned>(bitmap->width);  ++x)
{
    d[i++] = 0xAA;
    d[i++] = 0xBB;
    d[i++] = 0xCC;
}

I zmierzone (trzeba było użyć „-mcmodel = large”, aby to połączyć). Potem spróbowałem:

const std::size_t n = 0x80000000ull;
bitmap->width = n;
static unsigned char d[n*3];
std::size_t i=0;
unsigned width(static_cast<unsigned>(bitmap->width));
for (unsigned x = 0;  x < width;  ++x)
{
    d[i++] = 0xAA;
    d[i++] = 0xBB;
    d[i++] = 0xCC;
}

Wyniki pomiarów były takie same - wydaje się, że kompilator był w stanie sam go zoptymalizować.

Następnie wypróbowałem oryginalne kody (ze wskazówką p), tym razem kiedy pjest typu std::uint16_t*. Znowu wyniki były takie same - z powodu ścisłego aliasingu. Potem spróbowałem budować z „-fno-strict-aliasing” i ponownie zauważyłem różnicę w czasie.


4
Wydaje się, że powinien to być komentarz, chociaż technicznie odpowiada na pytanie. Zauważ też, że niestety nie wykazałeś, że chodziło o aliasing. Wydaje się to prawdopodobne, z pewnością wiarygodne, ale to coś innego niż wniosek, że to było to.
SirGuy

@GuyGreer: Zobacz moje [edytuj 2] - teraz myślę, że jest to całkiem sprawdzone.
Yaron Cohen-Tal

2
Zastanawiam się tylko, dlaczego zacząłeś używać zmiennej "i" kiedy masz "x" w pętli?
Jesper Madsen

1
Czy to tylko ja uważam, że wyrażenie 54% szybciej jest trudne do zrozumienia? Czy masz na myśli to, że jest 1,54 razy większa niż ta niezoptymalizowana, czy coś innego?
Roddy

3
@ YaronCohen-Tal czyli ponad dwa razy szybciej? Imponujące, ale nie to, co bym zrozumiał „54% szybciej” na myśli!
Roddy

24

Inne odpowiedzi wskazywały, że wyciągnięcie operacji wskaźnika poza pętlę może zmienić zdefiniowane zachowanie z powodu reguł aliasingu, które pozwalają char na aliasowanie czegokolwiek, a zatem nie jest dopuszczalną optymalizacją dla kompilatora, mimo że w większości przypadków jest to oczywiście poprawne dla człowieka programista.

Zwrócili również uwagę, że wyprowadzenie operacji z pętli jest zwykle, ale nie zawsze, poprawą z punktu widzenia wydajności i często jest niekorzystne z punktu widzenia czytelności.

Chciałbym podkreślić, że często istnieje „trzecia droga”. Zamiast liczyć do żądanej liczby iteracji, możesz odliczyć do zera. Oznacza to, że liczba iteracji jest potrzebna tylko raz na początku pętli, nie musi być później zapisywana. Jeszcze lepiej na poziomie asemblera często eliminuje potrzebę jawnego porównania, ponieważ operacja dekrementacji zwykle ustawia flagi wskazujące, czy licznik był zerowy zarówno przed (flaga przeniesienia), jak i po (flaga zero) dekrementacji.

for (unsigned x = static_cast<unsigned>(bitmap->width);x > 0;  x--)
{
    *p++ = 0xAA;
    *p++ = 0xBB;
    *p++ = 0xCC;
}

Zauważ, że ta wersja pętli podaje wartości x z zakresu 1..szerokość zamiast zakresu 0 .. (szerokość-1). To nie ma znaczenia w twoim przypadku, ponieważ tak naprawdę nie używasz x do niczego, ale jest to coś, o czym należy pamiętać. Jeśli chcesz pętlę odliczającą z wartościami x w zakresie 0 .. (szerokość-1), możesz to zrobić.

for (unsigned x = static_cast<unsigned>(bitmap->width); x-- > 0;)
{
    *p++ = 0xAA;
    *p++ = 0xBB;
    *p++ = 0xCC;
}

Możesz również pozbyć się rzutów w powyższych przykładach, jeśli chcesz, nie martwiąc się o ich wpływ na reguły porównania, ponieważ wszystko, co robisz z bitmap-> width, to przypisywanie go bezpośrednio do zmiennej.


2
Widziałem ten drugi przypadek sformatowany jako x --> 0, co skutkowało operatorem „downto”. Całkiem zabawne. PS Nie uważam, aby zmienna warunku końcowego była ujemna dla czytelności, w rzeczywistości może być odwrotnie.
Mark Ransom

To naprawdę zależy, czasami stwierdzenie staje się tak okropne, że podzielenie go na wiele zdań poprawia czytelność, ale nie wierzę, że tak jest w tym przypadku.
plugwash

1
+1 Dobra obserwacja, chociaż argumentowałbym, że podnoszenie static_cast<unsigned>(bitmap->width)i używanie widthzamiast tego w pętli jest w rzeczywistości poprawą czytelności, ponieważ teraz jest mniej rzeczy do przeanalizowania przez czytelnika na wiersz. Jednak opinie innych mogą się różnić.
SirGuy

1
Istnieje wiele innych sytuacji, w których liczenie w dół jest lepsze (np. Przy usuwaniu pozycji z listy). Nie wiem, dlaczego nie robi się tego częściej.
Ian Goldby

3
Jeśli chcesz pisać pętle, które wyglądają bardziej jak optymalny asm, użyj do { } while(), ponieważ w ASM tworzysz pętle z gałęzią warunkową na końcu. Zwykłe pętle for(){}i while(){}wymagają dodatkowych instrukcji, aby przetestować warunek pętli raz przed pętlą, jeśli kompilator nie może udowodnić, że zawsze działa co najmniej raz. Jak najbardziej, użyj for()lub while()kiedy warto sprawdzić, czy pętla powinna choćby uruchomić się raz, czy też jest bardziej czytelna.
Peter Cordes

11

Jedyną rzeczą, która może uniemożliwić optymalizację, jest ścisła reguła aliasingu . W skrócie :

„Ścisłe aliasy to założenie, poczynione przez kompilator C (lub C ++), że wyłuskiwanie wskaźników do obiektów różnych typów nigdy nie będzie odnosić się do tej samej lokalizacji w pamięci (tj. Aliasów)”.

[…]

Wyjątkiem od reguły jest a char*, który może wskazywać na dowolny typ.

Wyjątek dotyczy również wskaźników unsignedi signed char.

Tak jest w przypadku twojego kodu: modyfikujesz, *pza pomocą pktórego jest an unsigned char*, więc kompilator musi założyć, że może wskazywać bitmap->width. Dlatego buforowanie bitmap->widthjest nieprawidłową optymalizacją. To zachowanie zapobiegające optymalizacji jest pokazane w odpowiedzi YSC .

Gdyby i tylko wtedy, gdyby pwskazano na inny niż chari inny decltype(bitmap->width)typ, buforowanie byłoby możliwą optymalizacją.


10

Pytanie pierwotnie zadane:

Czy warto to zoptymalizować?

I moja odpowiedź na to pytanie (zebranie dobrej mieszanki głosów w górę i w dół ..)

Niech kompilator się tym martwi.

Kompilator prawie na pewno wykona lepszą robotę niż ty. I nie ma gwarancji, że Twoja „optymalizacja” jest lepsza niż „oczywisty” kod - zmierzyłeś go?

Co ważniejsze, czy masz jakikolwiek dowód na to, że optymalizowany kod ma jakikolwiek wpływ na wydajność Twojego programu?

Pomimo głosów przeciw (i teraz widzę problem z aliasami), nadal jestem zadowolony z tego jako ważnej odpowiedzi. Jeśli nie wiesz, czy warto coś zoptymalizować, prawdopodobnie tak nie jest.

Oczywiście inne pytanie brzmiałoby:

Po czym mogę sprawdzić, czy warto zoptymalizować fragment kodu?

Po pierwsze, czy Twoja aplikacja lub biblioteka musi działać szybciej niż obecnie? Czy użytkownik czekał zbyt długo? Czy Twoje oprogramowanie prognozuje wczorajszą pogodę zamiast jutrzejszej?

Tylko Ty możesz to naprawdę powiedzieć na podstawie tego, do czego służy Twoje oprogramowanie i czego oczekują Twoi użytkownicy.

Zakładając, że oprogramowanie wymaga optymalizacji, następną rzeczą do zrobienia jest rozpoczęcie pomiaru. Profilerowie powiedzą Ci, gdzie Twój kod spędza czas. Jeśli Twój fragment nie wyświetla się jako wąskie gardło, najlepiej zostaw go w spokoju. Profilerowie i inne narzędzia pomiarowe również powiedzą Ci, czy Twoje zmiany miały znaczenie. Można spędzić godziny na optymalizacji kodu, ale okazuje się, że nie dokonałeś żadnej zauważalnej różnicy.

Co właściwie masz na myśli mówiąc o „optymalizacji”?

Jeśli nie piszesz kodu „zoptymalizowanego”, powinien on być tak przejrzysty, czysty i zwięzły, jak tylko możesz. Argument „Przedwczesna optymalizacja jest zła” nie jest usprawiedliwieniem dla niechlujnego lub nieefektywnego kodu.

Zoptymalizowany kod zwykle poświęca niektóre z powyższych atrybutów na rzecz wydajności. Może to obejmować wprowadzenie dodatkowych zmiennych lokalnych, posiadanie obiektów o szerszym niż oczekiwany zakresie, a nawet odwrócenie kolejności normalnej pętli. Wszystko to może być mniej jasne lub zwięzłe, więc udokumentuj kod (pokrótce!), Dlaczego to robisz.

Ale często przy „wolnym” kodzie te mikro-optymalizacje są ostatnią deską ratunku. W pierwszej kolejności należy przyjrzeć się algorytmom i strukturom danych. Czy istnieje sposób, aby w ogóle uniknąć wykonywania pracy? Czy wyszukiwania liniowe można zastąpić wyszukiwaniami binarnymi? Czy lista połączona byłaby tutaj szybsza niż wektor? Albo tablica haszująca? Czy mogę zapisać wyniki w pamięci podręcznej? Podejmowanie dobrych „efektywnych” decyzji w tym miejscu często może wpłynąć na wydajność o rząd wielkości lub więcej!


12
Podczas iteracji po szerokości obrazu bitmapowego, logika zapętlenia może stanowić znaczną część czasu spędzonego w pętli. Zamiast martwić się o przedwczesną optymalizację, w takim przypadku lepiej jest opracować najlepsze praktyki, które są wydajne od samego początku.
Mark Ransom

4
@MarkRansom częściowo zgodził się z tym: ale „najlepsze praktyki” to albo: użyj istniejącej biblioteki lub wywołania API do wypełniania obrazów, albo b: poproś GPU, aby zrobił to za Ciebie. Nigdy nie powinien to być rodzaj niezmierzonej mikrooptymalizacji, jaką sugeruje PO. A skąd wiesz, że ten kod jest kiedykolwiek wykonywany więcej niż jeden raz lub z bitmapami o szerokości większej niż 16 pikseli ...?
Roddy,

@Veedrac. Doceń uzasadnienie dla -1. Odkąd udzieliłem odpowiedzi, siła pytania uległa subtelnej i znaczącej zmianie. Jeśli uważasz, że (rozszerzona) odpowiedź jest nadal nieprzydatna, czas, żebym ją usunął… „Czy warto…” i tak zawsze opiera się głównie na opiniach.
Roddy,

@Roddy Doceniam zmiany, pomagają (a mój komentarz prawdopodobnie i tak brzmiał zbyt ostro). Jednak nadal jestem na płocie, ponieważ tak naprawdę jest to odpowiedź na pytanie, które nie nadaje się do przepełnienia stosu. Wydaje się, że właściwa odpowiedź byłaby specyficzna dla fragmentu, tak jak odpowiedzi, które zostały tutaj wysoko ocenione.
Veedrac,

6

W takiej sytuacji używam następującego schematu. Jest prawie tak krótki, jak twój pierwszy przypadek i jest lepszy niż drugi, ponieważ utrzymuje tymczasową zmienną lokalną dla pętli.

for (unsigned int x = 0, n = static_cast<unsigned>(bitmap->width); x < n; ++x)
{
  *p++ = 0xAA;
  *p++ = 0xBB;
  *p++ = 0xCC;
}

Będzie to szybsze z mniej niż inteligentnym kompilatorem, kompilacją do debugowania lub niektórymi flagami kompilacji.

Edycja1 : Umieszczenie stałej operacji poza pętlą jest dobrym wzorcem programowania. Pokazuje zrozumienie podstaw obsługi maszyn, szczególnie w C / C ++. Twierdzę, że wysiłek, aby udowodnić swoją wartość, powinien spoczywać na osobach, które nie przestrzegają tej praktyki. Jeśli kompilator karze za dobry wzorzec, jest to błąd w kompilatorze.

Edit2:: Zmierzyłem moją sugestię z oryginalnym kodem w vs2013, uzyskałem% 1 poprawę. Czy możemy zrobić lepiej? Prosta ręczna optymalizacja daje 3-krotną poprawę w stosunku do oryginalnej pętli na komputerze x64 bez uciekania się do egzotycznych instrukcji. Poniższy kod zakłada system little endian i odpowiednio wyrównaną mapę bitową. TEST 0 jest oryginalny (9 sekund), TEST 1 jest szybszy (3 sekundy). Założę się, że ktoś mógłby to zrobić jeszcze szybciej, a wynik testu zależałby od rozmiaru mapy bitowej. Zdecydowanie niedługo w przyszłości kompilator będzie w stanie generować konsekwentnie najszybszy kod. Obawiam się, że to będzie przyszłość, kiedy kompilator będzie również programistą AI, więc nie mielibyśmy pracy. Ale na razie po prostu napisz kod, który pokaże, że wiesz, że dodatkowa operacja w pętli nie jest potrzebna.

#include <memory>
#include <time.h>

struct Bitmap_line
{
  int blah;
  unsigned int width;
  Bitmap_line(unsigned int w)
  {
    blah = 0;
    width = w;
  }
};

#define TEST 0 //define 1 for faster test

int main(int argc, char* argv[])
{
  unsigned int size = (4 * 1024 * 1024) / 3 * 3; //makes it divisible by 3
  unsigned char* pointer = (unsigned char*)malloc(size);
  memset(pointer, 0, size);
  std::unique_ptr<Bitmap_line> bitmap(new Bitmap_line(size / 3));
  clock_t told = clock();
#if TEST == 0
  for (int iter = 0; iter < 10000; iter++)
  {
    unsigned char* p = pointer;
    for (unsigned x = 0; x < static_cast<unsigned>(bitmap->width); ++x)
    //for (unsigned x = 0, n = static_cast<unsigned>(bitmap->width); x < n; ++x)
    {
      *p++ = 0xAA;
      *p++ = 0xBB;
      *p++ = 0xCC;
    }
  }
#else
  for (int iter = 0; iter < 10000; iter++)
  {
    unsigned char* p = pointer;
    unsigned x = 0;
    for (const unsigned n = static_cast<unsigned>(bitmap->width) - 4; x < n; x += 4)
    {
      *(int64_t*)p = 0xBBAACCBBAACCBBAALL;
      p += 8;
      *(int32_t*)p = 0xCCBBAACC;
      p += 4;
    }

    for (const unsigned n = static_cast<unsigned>(bitmap->width); x < n; ++x)
    {
      *p++ = 0xAA;
      *p++ = 0xBB;
      *p++ = 0xCC;
    }
  }
#endif
  double ms = 1000.0 * double(clock() - told) / CLOCKS_PER_SEC;
  printf("time %0.3f\n", ms);

  {
    //verify
    unsigned char* p = pointer;
    for (unsigned x = 0, n = static_cast<unsigned>(bitmap->width); x < n; ++x)
    {
      if ((*p++ != 0xAA) || (*p++ != 0xBB) || (*p++ != 0xCC))
      {
        printf("EEEEEEEEEEEEERRRRORRRR!!!\n");
        abort();
      }
    }
  }

  return 0;
}

Możesz zaoszczędzić kolejne 25% na 64-bitowym, jeśli używasz trzech int64_t zamiast int64_t i int32_t.
Antonín Lejsek

5

Należy wziąć pod uwagę dwie kwestie.

A) Jak często będzie przebiegać optymalizacja?

Jeśli odpowiedź nie pojawia się zbyt często, na przykład tylko wtedy, gdy użytkownik kliknie przycisk, nie przejmuj się, jeśli spowoduje to, że Twój kod będzie nieczytelny. Jeśli odpowiedź brzmi 1000 razy na sekundę, prawdopodobnie będziesz chciał przejść do optymalizacji. Jeśli jest to choćby trochę skomplikowane, umieść komentarz, aby wyjaśnić, co się dzieje, aby pomóc następnemu facetowi, który się pojawi.

B) Czy spowoduje to, że kod będzie trudniejszy do utrzymania / rozwiązywania problemów?

Jeśli nie widzisz dużego wzrostu wydajności, uczynienie kodu tajemniczym po prostu po to, aby zaoszczędzić kilka tyknięć zegara, nie jest dobrym pomysłem. Wiele osób powie Ci, że każdy dobry programista powinien być w stanie spojrzeć na kod i dowiedzieć się, co się dzieje. To prawda. Problem polega na tym, że w świecie biznesu dodatkowy czas na zastanowienie się nad tym kosztuje. Więc jeśli możesz sprawić, że czytanie będzie ładniejsze, zrób to. Twoi przyjaciele będą Ci za to wdzięczni.

To powiedziawszy, że osobiście użyję przykładu B.


4

Kompilator jest w stanie zoptymalizować wiele rzeczy. Na przykład powinieneś postawić na czytelność, łatwość obsługi i to, co jest zgodne ze standardem Twojego kodu. Aby uzyskać więcej informacji o tym, co można zoptymalizować (za pomocą GCC), zobacz ten wpis na blogu .


4

Z reguły pozwól kompilatorowi przeprowadzić optymalizację za Ciebie, dopóki nie zdecydujesz, że powinieneś przejąć kontrolę. Logika tego nie ma nic wspólnego z wydajnością, ale raczej z czytelnością dla człowieka. W zdecydowanej większości przypadków czytelność programu jest ważniejsza niż jego wydajność. Powinieneś dążyć do pisania kodu, który jest łatwiejszy do odczytania dla człowieka, a następnie martwić się o optymalizację tylko wtedy, gdy jesteś przekonany, że wydajność jest ważniejsza niż łatwość utrzymania kodu.

Gdy zobaczysz, że wydajność ma znaczenie, należy uruchomić profiler w kodzie, aby określić, które pętle są nieefektywne, i zoptymalizować je indywidualnie. Rzeczywiście mogą istnieć przypadki, w których chcesz przeprowadzić tę optymalizację (zwłaszcza jeśli migrujesz do C ++, gdzie zaangażowane są kontenery STL), ale koszt w zakresie czytelności jest duży.

Ponadto przychodzą mi do głowy sytuacje patologiczne, w których mogłoby to faktycznie spowolnić kod. Na przykład rozważmy przypadek, w którym kompilator nie mógł udowodnić, że bitmap->widthbył on stały w trakcie procesu. Dodając widthzmienną, wymuszasz na kompilatorze utrzymywanie zmiennej lokalnej w tym zakresie. Jeśli z jakiegoś powodu, specyficznego dla platformy, ta dodatkowa zmienna uniemożliwiła pewną optymalizację miejsca na stosie, może być konieczna reorganizacja sposobu, w jaki emituje kody bajtowe, i wyprodukowanie czegoś mniej wydajnego.

Na przykład w systemie Windows x64 należy wywołać specjalne wywołanie API __chkstkw preambule funkcji, jeśli funkcja będzie wykorzystywać więcej niż 1 stronę zmiennych lokalnych. Ta funkcja daje systemowi Windows możliwość zarządzania stronami ochronnymi, których używają do rozszerzania stosu w razie potrzeby. Jeśli twoja dodatkowa zmienna przesuwa użycie stosu z poziomu poniżej 1 strony na 1 stronę lub powyżej, twoja funkcja jest teraz zobowiązana do wywoływania za __chkstkkażdym razem, gdy jest wprowadzana. Gdybyś miał zoptymalizować tę pętlę na wolnej ścieżce, możesz w rzeczywistości spowolnić szybką ścieżkę bardziej niż zaoszczędziłeś na wolnej ścieżce!

Jasne, jest to trochę patologiczne, ale celem tego przykładu jest to, że możesz faktycznie spowolnić kompilator. Pokazuje tylko, że musisz profilować swoją pracę, aby określić, gdzie idą optymalizacje. W międzyczasie prosimy nie poświęcać w żaden sposób czytelności na rzecz optymalizacji, która może mieć znaczenie lub nie.


4
Chciałbym, żeby C i C ++ zapewniały więcej sposobów jawnego identyfikowania rzeczy, na których programista nie dba. Nie tylko zapewniłyby kompilatorom większe szanse na optymalizację rzeczy, ale także zaoszczędziłyby innym programistom, którzy czytają kod, konieczności zgadywania, czy np. Może ponownie sprawdzać bitmapę-> szerokość za każdym razem, aby upewnić się, że zmiany w niej wpływają na pętlę, lub czy może buforować bitmapę-> szerokość, aby zapewnić, że zmiany w niej nie wpłyną na pętlę. Mając sposób na powiedzenie „Buforuj to lub nie - nie obchodzi mnie to”, byłby jasny powód wyboru programisty.
supercat

@supercat Zgadzam się z całego serca, ponieważ można zobaczyć, jeśli spojrzy się na stosy wytatuowanych nieudanych języków, które próbowałem napisać, aby rozwiązać ten problem. Zauważyłem, że niezwykle trudno jest zdefiniować „czego” komuś nie obchodzi bez tak wielkiej bezbożnej składni, że po prostu nie jest to tego warte. Na próżno kontynuuję poszukiwania.
Cort Ammon

Nie jest możliwe zdefiniowanie tego we wszystkich przypadkach, ale myślę, że jest wiele przypadków, w których system typów mógłby pomóc. Również C zdecydował się uczynić typy znaków „uniwersalnymi akcesoriami” zamiast mieć kwalifikator typu, który byłby nieco luźniejszy niż „niestabilny”, który można by zastosować do dowolnego typu, z semantyką, że dostęp do takich typów byłby przetwarzany sekwencyjnie z dostępy niekwalifikowanego równoważnego typu, a także dostęp do wszystkich typów zmiennych z tym samym kwalifikatorem. To pomogłoby wyjaśnić, czy ktoś używał typów postaci, ponieważ potrzebował ...
supercat

... zachowanie aliasingu lub czy ktoś ich używał, ponieważ był odpowiedni dla potrzeb. Byłoby również pomocne, gdyby istniały wyraźne bariery aliasingu, które w wielu przypadkach można by umieścić poza pętlami, w przeciwieństwie do niejawnych barier związanych z dostępami znakowymi.
supercat

1
To mądra rozmowa, ale generalnie, jeśli już wybrałeś C do swojego zadania, prawdopodobnie wykonanie jest bardzo ważne i powinny obowiązywać inne zasady. W przeciwnym razie lepiej będzie użyć Rubiego, Javy, Pythona lub czegoś podobnego.
Audrius Meskauskas

4

Porównanie jest błędne , ponieważ dwóch fragmentów kodu

for (unsigned x = 0;  x < static_cast<unsigned>(bitmap->width);  ++x)

i

unsigned width(static_cast<unsigned>(bitmap->width));
for (unsigned x = 0;  x<width ;  ++x)

nie są równoważne

W pierwszym przypadku widthjest zależna, a nie stała, i nie można zakładać, że może się ona nie zmieniać między kolejnymi iteracjami. Dlatego nie można go zoptymalizować, ale należy go sprawdzić w każdej pętli .

W zoptymalizowanym przypadku zmiennej lokalnej przypisywana jest wartość bitmap->widthw pewnym momencie podczas wykonywania programu. Kompilator może sprawdzić, czy to się nie zmienia.

Czy myślałeś o wielowątkowości, czy może wartość może być zewnętrznie zależna, tak że jej wartość jest zmienna. Jak można by oczekiwać, że kompilator rozwiąże wszystkie te kwestie, jeśli nie powiesz?

Kompilator może działać tylko na tyle dobrze, na ile pozwala na to Twój kod.


2

O ile nie wiesz, jak dokładnie kompilator optymalizuje kod, lepiej jest przeprowadzić własne optymalizacje, zachowując czytelność kodu i projekt. Praktycznie trudno jest sprawdzić kod asemblera dla każdej funkcji, którą piszemy dla nowych wersji kompilatora.


1

Kompilator nie może zoptymalizować, bitmap->widthponieważ widthmożna zmienić wartość między iteracjami. Istnieje kilka najczęstszych powodów:

  1. Wielowątkowość. Kompilator nie może przewidzieć, czy inny wątek ma zmienić wartość.
  2. Modyfikacja wewnątrz pętli, czasami nie jest łatwo stwierdzić, czy zmienna zostanie zmieniona w pętli.
  3. Jest to wywołanie funkcji, na przykład iterator::end()czy container::size()tak trudno jest przewidzieć, czy będzie on zawsze zwraca ten sam wynik.

Reasumując (moja osobista opinia) dla miejsc wymagających wysokiego poziomu optymalizacji trzeba to zrobić samemu, w innych miejscach po prostu to zostaw, kompilator może to zoptymalizować lub nie, jeśli nie ma dużej różnicy czytelność kodu jest głównym celem.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.