Wiele lat temu kompilatory C nie były szczególnie inteligentne. Aby obejść ten problem, K&R wymyślił słowo kluczowe register , aby wskazać kompilatorowi, że być może dobrym pomysłem byłoby przechowywanie tej zmiennej w rejestrze wewnętrznym. Zrobili również trzeciorzędny operator, aby pomóc w generowaniu lepszego kodu.

W miarę upływu czasu kompilatory dojrzewały. Stali się bardzo sprytni, ponieważ ich analiza przepływu umożliwiła im podejmowanie lepszych decyzji o tym, jakie wartości przechowywać w rejestrach, niż możesz to zrobić. Słowo kluczowe register stało się nieważne.

FORTRAN może być szybszy niż C dla niektórych rodzajów operacji z powodu problemów z aliasami . Teoretycznie przy starannym kodowaniu można obejść to ograniczenie, aby umożliwić optymalizatorowi generowanie szybszego kodu.

Jakie praktyki kodowania są dostępne, które mogą umożliwić kompilatorowi / optymalizatorowi szybsze generowanie kodu?

• Będziemy wdzięczni za zidentyfikowanie używanej platformy i kompilatora.
• Dlaczego ta technika działa?
• Zachęcamy do przykładowego kodu.

Oto powiązane pytanie

[Edytuj] To pytanie nie dotyczy całego procesu profilowania i optymalizacji. Załóżmy, że program został poprawnie napisany, skompilowany z pełną optymalizacją, przetestowany i wdrożony do produkcji. W kodzie mogą znajdować się konstrukcje, które uniemożliwiają optymalizatorowi wykonanie najlepszej możliwej pracy. Co możesz zrobić, aby dokonać refaktoryzacji, która usunie te zakazy i umożliwi optymalizatorowi generowanie jeszcze szybszego kodu?

[Edytuj] Link powiązany z przesunięciem

Zapisuj do zmiennych lokalnych i nie wyprowadzaj argumentów! Może to być ogromna pomoc w obejściu aliasingu spowolnień. Na przykład, jeśli twój kod wygląda jak

void DoSomething(const Foo& foo1, const Foo* foo2, int numFoo, Foo& barOut)
{
    for (int i=0; i<numFoo, i++)
    {
         barOut.munge(foo1, foo2[i]);
    }
}

kompilator nie wie, że foo1! = barOut i dlatego musi za każdym razem przeładowywać foo1 przez pętlę. Nie może również odczytać foo2 [i], dopóki zapis do barOut nie zostanie zakończony. Możesz zacząć bawić się ograniczonymi wskaźnikami, ale jest to równie skuteczne (i znacznie jaśniejsze), aby zrobić to:

void DoSomethingFaster(const Foo& foo1, const Foo* foo2, int numFoo, Foo& barOut)
{
    Foo barTemp = barOut;
    for (int i=0; i<numFoo, i++)
    {
         barTemp.munge(foo1, foo2[i]);
    }
    barOut = barTemp;
}

Brzmi to głupio, ale kompilator może znacznie sprytniej radzić sobie ze zmienną lokalną, ponieważ nie może ona pokrywać się w pamięci z żadnym z argumentów. Może to pomóc w uniknięciu przerażającego sklepu z ładunkami (o którym wspomniał Francis Boivin w tym wątku).

Oto praktyka kodowania, która pomaga kompilatorowi tworzyć szybki kod - dowolny język, dowolna platforma, dowolny kompilator, każdy problem:

Czy nie stosować żadnych sztuczek, które zmuszają sprytnych, a nawet zachęcać, kompilator położyć zmienne w pamięci podręcznej (w tym i rejestry), jak myślisz najlepiej. Najpierw napisz program, który jest poprawny i możliwy do utrzymania.

Następnie profiluj swój kod.

Wtedy, i tylko wtedy, możesz chcieć rozpocząć badanie skutków mówienia kompilatorowi, jak używać pamięci. Wprowadź jedną zmianę naraz i zmierz jej wpływ.

Spodziewaj się rozczarowania i naprawdę ciężkiej pracy nad niewielkimi poprawkami wydajności. Nowoczesne kompilatory dla dojrzałych języków, takich jak Fortran i C, są bardzo, bardzo dobre. Jeśli czytasz opis „sztuczki” mającej na celu uzyskanie lepszej wydajności z kodu, pamiętaj, że pisarze kompilatorów również o tym czytali i, jeśli warto to zrobić, prawdopodobnie zaimplementowali ją. Prawdopodobnie napisali to, co przeczytałeś w pierwszej kolejności.

Kolejność przemierzania pamięci może mieć głęboki wpływ na wydajność, a kompilatory nie są zbyt dobre w rozwiązywaniu tego i naprawianiu. Pisząc kod, należy być świadomym problemów związanych z lokalizacją pamięci podręcznej, jeśli zależy Ci na wydajności. Na przykład tablice dwuwymiarowe w języku C są alokowane w formacie wiersz-główny. Przechodzenie po tablicach w głównym formacie kolumny spowoduje, że będziesz mieć więcej błędów w pamięci podręcznej i sprawi, że twój program będzie bardziej związany z pamięcią niż z procesorem:

#define N 1000000;
int matrix[N][N] = { ... };

//awesomely fast
long sum = 0;
for(int i = 0; i < N; i++){
  for(int j = 0; j < N; j++){
    sum += matrix[i][j];
  }
}

//painfully slow
long sum = 0;
for(int i = 0; i < N; i++){
  for(int j = 0; j < N; j++){
    sum += matrix[j][i];
  }
}

Optymalizacje ogólne

Oto niektóre z moich ulubionych optymalizacji. W rzeczywistości zwiększyłem czas wykonywania i zmniejszyłem rozmiary programów, używając ich.

Zadeklaruj małe funkcje jako inlinemakra lub

Każde wywołanie funkcji (lub metody) wiąże się z narzutem, takim jak umieszczanie zmiennych na stosie. Niektóre funkcje mogą również wiązać się z kosztami po powrocie. Nieefektywna funkcja lub metoda ma mniej instrukcji w swojej treści niż połączony narzut. Są to dobrzy kandydaci do wstawiania, zarówno jako #definemakra, jak i inlinefunkcje. (Tak, wiem, że inlineto tylko sugestia, ale w tym przypadku traktuję to jako przypomnienie dla kompilatora).

Usuń martwy i zbędny kod

Jeśli kod nie jest używany lub nie ma wpływu na wynik programu, pozbądź się go.

Uprość projektowanie algorytmów

Kiedyś usunąłem dużo kodu asemblera i czasu wykonywania z programu, zapisując równanie algebraiczne, które obliczał, a następnie uprościłem wyrażenie algebraiczne. Realizacja uproszczonego wyrażenia algebraicznego zajęła mniej miejsca i czasu niż pierwotna funkcja.

Rozwijanie pętli

Każda pętla ma narzut związany z zwiększaniem i sprawdzaniem zakończenia. Aby uzyskać oszacowanie współczynnika wydajności, policz liczbę instrukcji w narzutu (minimum 3: zwiększ, sprawdź, przejdź do początku pętli) i podziel przez liczbę instrukcji wewnątrz pętli. Im niższa liczba, tym lepiej.

Edycja: podaj przykład rozwijania pętli Przed:

unsigned int sum = 0;
for (size_t i; i < BYTES_TO_CHECKSUM; ++i)
{
    sum += *buffer++;
}

Po rozwinięciu:

unsigned int sum = 0;
size_t i = 0;
**const size_t STATEMENTS_PER_LOOP = 8;**
for (i = 0; i < BYTES_TO_CHECKSUM; **i = i / STATEMENTS_PER_LOOP**)
{
    sum += *buffer++; // 1
    sum += *buffer++; // 2
    sum += *buffer++; // 3
    sum += *buffer++; // 4
    sum += *buffer++; // 5
    sum += *buffer++; // 6
    sum += *buffer++; // 7
    sum += *buffer++; // 8
}
// Handle the remainder:
for (; i < BYTES_TO_CHECKSUM; ++i)
{
    sum += *buffer++;
}

Zaletą tej korzyści jest dodatkowa korzyść: wykonywanych jest więcej instrukcji, zanim procesor będzie musiał ponownie załadować pamięć podręczną instrukcji.

Osiągnąłem niesamowite rezultaty, kiedy rozwinąłem pętlę do 32 instrukcji. Było to jednym z wąskich gardeł, ponieważ program musiał obliczyć sumę kontrolną pliku o wielkości 2 GB. Ta optymalizacja w połączeniu z odczytem bloków poprawiła wydajność od 1 godziny do 5 minut. Rozwijanie pętli zapewniało doskonałą wydajność również w języku asemblera, mój memcpybył dużo szybszy niż kompilator memcpy. - TM

Redukcja ifinstrukcji

Procesory nienawidzą rozgałęzień lub skoków, ponieważ zmusza procesor do ponownego załadowania kolejki instrukcji.

Boolean Arithmetic ( Edytowano: zastosowany format kodu do fragmentu kodu, dodany przykład)

Konwertuj ifinstrukcje na przypisania logiczne. Niektóre procesory mogą warunkowo wykonywać instrukcje bez rozgałęziania:

bool status = true;
status = status && /* first test */;
status = status && /* second test */;

Krótki spięciom z logicznego I operatora ( &&) uniemożliwia wykonywanie testów jeżeli statusjest false.

Przykład:

struct Reader_Interface
{
  virtual bool  write(unsigned int value) = 0;
};

struct Rectangle
{
  unsigned int origin_x;
  unsigned int origin_y;
  unsigned int height;
  unsigned int width;

  bool  write(Reader_Interface * p_reader)
  {
    bool status = false;
    if (p_reader)
    {
       status = p_reader->write(origin_x);
       status = status && p_reader->write(origin_y);
       status = status && p_reader->write(height);
       status = status && p_reader->write(width);
    }
    return status;
};

Alokacja zmiennej czynnika poza pętlami

Jeśli zmienna jest tworzona w locie wewnątrz pętli, przenieś tworzenie / alokację na miejsce przed pętlą. W większości przypadków zmienna nie musi być przydzielana podczas każdej iteracji.

Czynnikowe wyrażenia stałe poza pętlami

Jeśli wartość obliczenia lub zmiennej nie zależy od indeksu pętli, przenieś ją poza pętlę (przed).

I / O w blokach

Odczyt i zapis danych w dużych porcjach (blokach). Im większy tym lepszy. Na przykład czytanie jednego oktektu na raz jest mniej wydajne niż czytanie 1024 oktetów przy jednym odczycie.
Przykład:

static const char  Menu_Text[] = "\n"
    "1) Print\n"
    "2) Insert new customer\n"
    "3) Destroy\n"
    "4) Launch Nasal Demons\n"
    "Enter selection:  ";
static const size_t Menu_Text_Length = sizeof(Menu_Text) - sizeof('\0');
//...
std::cout.write(Menu_Text, Menu_Text_Length);

Skuteczność tej techniki można wykazać wizualnie. :-)

Nie używaj printf rodziny do stałych danych

Stałe dane można wyprowadzać za pomocą zapisu blokowego. Sformatowany zapis marnuje czas na skanowanie tekstu pod kątem formatowania znaków lub przetwarzania poleceń formatujących. Zobacz powyższy przykład kodu.

Sformatuj do pamięci, a następnie napisz

Sformatuj do chartablicy przy użyciu wielu sprintf, a następnie użyj fwrite. Umożliwia to również podział układu danych na „sekcje stałe” i sekcje zmienne. Pomyśl o korespondencji seryjnej .

Zadeklaruj stały tekst (literały ciągów) jako static const

Gdy zmienne są deklarowane bez static, niektóre kompilatory mogą przydzielić miejsce na stosie i skopiować dane z pamięci ROM. To są dwie niepotrzebne operacje. Można to naprawić za pomocą staticprefiksu.

Wreszcie, kod taki jak kompilator

Czasami kompilator może lepiej zoptymalizować kilka małych instrukcji niż jedną skomplikowaną wersję. Pomocne jest również pisanie kodu, który pomoże kompilatorowi w optymalizacji. Jeśli chcę, aby kompilator korzystał ze specjalnych instrukcji transferu bloków, napiszę kod, który wygląda tak, że powinien korzystać ze specjalnych instrukcji.

Optymalizator tak naprawdę nie kontroluje wydajności twojego programu, ty tak. Stosuj odpowiednie algorytmy i struktury oraz profil, profil, profil.

To powiedziawszy, nie powinieneś wykonywać pętli wewnętrznej na małej funkcji z jednego pliku w innym pliku, ponieważ powstrzymuje to przed wstawieniem.

Jeśli to możliwe, unikaj przyjmowania adresu zmiennej. Pytanie o wskaźnik nie jest „wolne”, ponieważ oznacza, że ​​zmienna musi być przechowywana w pamięci. Nawet tablica może być przechowywana w rejestrach, jeśli unikniesz wskaźników - jest to niezbędne do wektoryzacji.

Co prowadzi do następnego punktu, przeczytaj instrukcję ^ # $ @ ! GCC może wektoryzować zwykły kod C, jeśli posypiesz __restrict__tu i __attribute__( __aligned__ )tam. Jeśli potrzebujesz czegoś bardzo konkretnego od optymalizatora, być może będziesz musiał być dokładny.

W większości nowoczesnych procesorów największym wąskim gardłem jest pamięć.

Aliasing: Load-Hit-Store może być niszczycielski w ciasnej pętli. Jeśli czytasz jedną lokalizację pamięci i piszesz do innej i wiesz, że są one rozłączne, ostrożne umieszczenie słowa kluczowego alias na parametrach funkcji może naprawdę pomóc kompilatorowi w wygenerowaniu szybszego kodu. Jeśli jednak regiony pamięci nakładają się i użyłeś „aliasu”, czeka Cię dobra sesja debugowania niezdefiniowanych zachowań!

Brak pamięci podręcznej: Nie jestem pewien, jak możesz pomóc kompilatorowi, ponieważ jest to głównie algorytmiczne, ale są nieodłączne elementy pamięci wstępnego pobierania.

Nie próbuj też zbytnio konwertować wartości zmiennoprzecinkowych na int i odwrotnie, ponieważ używają różnych rejestrów, a konwersja z jednego typu na inny oznacza wywołanie właściwej instrukcji konwersji, zapisanie wartości do pamięci i odczytanie jej z powrotem w odpowiednim zestawie rejestrów .

Zdecydowana większość kodu, który ludzie piszą, będzie związana z I / O (wierzę, że cały kod, który napisałem dla pieniędzy w ciągu ostatnich 30 lat, był tak ograniczony), więc działania optymalizatora dla większości ludzi będą miały charakter akademicki.

Chciałbym jednak przypomnieć ludziom, że aby zoptymalizować kod, musisz powiedzieć kompilatorowi, aby go zoptymalizował - wiele osób (w tym ja, gdy zapomnę) publikuje tutaj testy porównawcze C ++, które są bez znaczenia bez włączonego optymalizatora.

używaj stałej poprawności tak często, jak to możliwe w swoim kodzie. Pozwala kompilatorowi na znacznie lepszą optymalizację.

W tym dokumencie znajduje się wiele innych wskazówek dotyczących optymalizacji: Optymalizacje CPP (choć trochę stary)

najważniejsze:

• użyj list inicjalizacyjnych konstruktorów
• użyj operatorów przedrostków
• użyj jawnych konstruktorów
• funkcje inline
• unikaj tymczasowych obiektów
• zdawać sobie sprawę z kosztu funkcji wirtualnych
• zwracać obiekty za pomocą parametrów referencyjnych
• rozważ dla przydziału klas
• rozważ alokatory kontenerów STL
• optymalizacja „pustego członka”
• itp

W miarę możliwości próbuj programować przy użyciu statycznego pojedynczego przypisania. SSA jest dokładnie tym samym, co otrzymujesz w większości funkcjonalnych języków programowania, i właśnie na to większość kompilatorów konwertuje Twój kod, aby dokonać optymalizacji, ponieważ jest łatwiejszy w obsłudze. W ten sposób ujawniają się miejsca, w których kompilator może się pomylić. Sprawia również, że wszystkie oprócz najgorszych alokatorów rejestrów działają tak dobrze, jak najlepsze alokatory rejestrów i pozwala na łatwiejsze debugowanie, ponieważ prawie nigdy nie musisz się zastanawiać, skąd zmienna wzięła swoją wartość, ponieważ było tylko jedno miejsce, do którego została przypisana.
Unikaj zmiennych globalnych.

Podczas pracy z danymi przez odniesienie lub wskaźnik przeciągnij je do zmiennych lokalnych, wykonaj swoją pracę, a następnie skopiuj ją z powrotem. (chyba że masz dobry powód, aby tego nie robić)

Skorzystaj z prawie darmowego porównania z 0, które oferuje większość procesorów podczas wykonywania operacji matematycznych lub logicznych. Prawie zawsze otrzymujesz flagę dla == 0 i <0, z której możesz łatwo uzyskać 3 warunki:

x= f();
if(!x){
   a();
} else if (x<0){
   b();
} else {
   c();
}

jest prawie zawsze tańsze niż testowanie innych stałych.

Inną sztuczką jest użycie odejmowania, aby wyeliminować jedno porównanie w testowaniu zakresu.

#define FOO_MIN 8
#define FOO_MAX 199
int good_foo(int foo) {
    unsigned int bar = foo-FOO_MIN;
    int rc = ((FOO_MAX-FOO_MIN) < bar) ? 1 : 0;
    return rc;
} 

Pozwala to bardzo często uniknąć przeskoku w językach, w których występują zwarcia w wyrażeniach boolowskich i pozwala kompilatorowi uniknąć konieczności zastanowienia się, jak poradzić sobie z nadążaniem za wynikiem pierwszego porównania, wykonując drugie, a następnie łącząc je. Może to wyglądać na możliwość wykorzystania dodatkowego rejestru, ale prawie nigdy tak się nie dzieje. Często i tak nie potrzebujesz już foo, a jeśli to zrobisz, rc nie jest jeszcze używany, więc może tam iść.

Używając funkcji łańcuchowych w c (strcpy, memcpy, ...) pamiętaj, co zwracają - przeznaczenie! Często można uzyskać lepszy kod, „zapominając” o swojej kopii wskaźnika do miejsca docelowego i po prostu odzyskując ją z powrotu tych funkcji.

Nigdy nie zapomnij o możliwości zwrócenia dokładnie tego samego, co zwróciła ostatnia funkcja, którą wywołałeś. Kompilatory nie są tak dobre w wychwytywaniu, że:

foo_t * make_foo(int a, int b, int c) {
        foo_t * x = malloc(sizeof(foo));
        if (!x) {
             // return NULL;
             return x; // x is NULL, already in the register used for returns, so duh
        }
        x->a= a;
        x->b = b;
        x->c = c;
        return x;
}

Oczywiście możesz odwrócić logikę, jeśli masz tylko jeden punkt powrotu.

(sztuczki, które przypomniałem sobie później)

Deklarowanie funkcji jako statycznych zawsze jest dobrym pomysłem. Jeśli kompilator może udowodnić sobie, że uwzględnił każdego wywołującego określoną funkcję, może złamać konwencje wywoływania tej funkcji w imię optymalizacji. Kompilatory często mogą uniknąć przenoszenia parametrów do rejestrów lub pozycji na stosie, które wywoływane funkcje zwykle oczekują, że ich parametry się znajdą (aby to zrobić, musi się różnić zarówno w wywołanej funkcji, jak i lokalizacji wszystkich wywołujących). Kompilator może również często skorzystać ze znajomości pamięci i rejestrów, których będzie potrzebować wywoływana funkcja i uniknąć generowania kodu w celu zachowania wartości zmiennych znajdujących się w rejestrach lub miejscach pamięci, których wywoływana funkcja nie zakłóca. Działa to szczególnie dobrze, gdy jest niewiele wywołań funkcji.

Napisałem optymalizujący kompilator C i oto kilka bardzo przydatnych rzeczy do rozważenia:

1. Uczyń większość funkcji statyczną. Umożliwia to stałą propagację międzyprocedurową i analizę aliasów, w przeciwnym razie kompilator musi założyć, że funkcję można wywołać spoza jednostki tłumaczącej z całkowicie nieznanymi wartościami parametrów. Jeśli spojrzysz na dobrze znane biblioteki open source, wszystkie one oznaczają funkcje statyczne, z wyjątkiem tych, które naprawdę muszą być zewnętrzne.

2. Jeśli używane są zmienne globalne, oznacz je jako statyczne i stałe, jeśli to możliwe. Jeśli są inicjalizowane raz (tylko do odczytu), lepiej jest użyć listy inicjalizującej, takiej jak static const int VAL [] = {1,2,3,4}, w przeciwnym razie kompilator może nie wykryć, że zmienne są faktycznie zainicjowanymi stałymi i nie zastąpi obciążeń ze zmiennej stałymi.

3. NIGDY nie używaj goto do wnętrza pętli, pętla nie będzie już rozpoznawana przez większość kompilatorów i żadna z najważniejszych optymalizacji nie zostanie zastosowana.

4. Używaj parametrów wskaźnika tylko wtedy, gdy jest to konieczne, i oznacz je jako ograniczające, jeśli to możliwe. To bardzo pomaga w analizie aliasów, ponieważ programista gwarantuje, że alias nie istnieje (międzyproceduralna analiza aliasów jest zwykle bardzo prymitywna). Bardzo małe obiekty strukturalne powinny być przekazywane przez wartość, a nie przez odwołanie.

5. Jeśli to możliwe, używaj tablic zamiast wskaźników, zwłaszcza wewnątrz pętli (a [i]). Tablica zwykle oferuje więcej informacji do analizy aliasów, a po kilku optymalizacjach ten sam kod zostanie wygenerowany i tak (jeśli jesteś ciekawy, poszukaj zmniejszenia siły pętli). Zwiększa to również szansę zastosowania ruchu kodu niezmiennego w pętli.

6. Spróbuj wyciągnąć poza pętle wywołania dużych funkcji lub funkcji zewnętrznych, które nie mają skutków ubocznych (nie zależą od bieżącej iteracji pętli). Małe funkcje są w wielu przypadkach wstawiane lub konwertowane na wewnętrzne, które są łatwe do przeniesienia, ale duże funkcje mogą wydawać się kompilatorowi mieć skutki uboczne, podczas gdy w rzeczywistości ich nie ma. Skutki uboczne funkcji zewnętrznych są całkowicie nieznane, z wyjątkiem niektórych funkcji z biblioteki standardowej, które są czasami modelowane przez niektóre kompilatory, co umożliwia ruch kodu niezmiennego w pętli.

7. Pisząc testy z wieloma warunkami, najpierw umieść ten najbardziej prawdopodobny. if (a || b || c) powinno być if (b || a || c) jeśli b jest bardziej prawdopodobne niż inne. Kompilatory zwykle nie wiedzą nic o możliwych wartościach warunków ani o tym, które gałęzie są pobierane częściej (można je poznać, używając informacji o profilu, ale niewielu programistów z nich korzysta).

8. Użycie przełącznika jest szybsze niż wykonanie testu, takiego jak if (a || b || ... || z). Najpierw sprawdź, czy Twój kompilator robi to automatycznie, a niektóre robią, a bardziej czytelne jest ustawienie if .

W przypadku systemów embedded i kodu napisanego w C / C ++ staram się unikać dynamicznej alokacji pamięci jak najbardziej . Głównym powodem, dla którego to robię, niekoniecznie jest wydajność, ale ta praktyczna zasada ma wpływ na wydajność.

Algorytmy używane do zarządzania stertą są notorycznie powolne na niektórych platformach (np. Vxworks). Co gorsza, czas potrzebny na powrót z połączenia do malloc zależy w dużym stopniu od aktualnego stanu sterty. Dlatego każda funkcja, która wywołuje malloc, będzie miała wpływ na wydajność, którego nie można łatwo uwzględnić. Ten spadek wydajności może być minimalny, jeśli sterta jest nadal czysta, ale po pewnym czasie działania tego urządzenia sterta może ulec fragmentacji. Połączenia będą trwać dłużej i nie można łatwo obliczyć, jak wydajność spadnie z czasem. Tak naprawdę nie można oszacować gorszego przypadku. W tym przypadku również optymalizator nie może Ci pomóc. Co gorsza, jeśli sterta zostanie zbyt mocno podzielona, ​​wywołania zaczną całkowicie kończyć się niepowodzeniem. Rozwiązaniem jest użycie pul pamięci (np.glib slices ) zamiast stosu. Wezwania do alokacji będą znacznie szybsze i deterministyczne, jeśli zrobisz to dobrze.

Głupia mała wskazówka, ale taka, która pozwoli Ci zaoszczędzić mikroskopijne ilości szybkości i kodu.

Zawsze przekazuj argumenty funkcji w tej samej kolejności.

Jeśli masz f_1 (x, y, z), które wywołuje f_2, zadeklaruj f_2 jako f_2 (x, y, z). Nie deklaruj go jako f_2 (x, z, y).

Powodem tego jest fakt, że platforma C / C ++ ABI (konwencja wywoływania AKA) obiecuje przekazywać argumenty w określonych rejestrach i lokalizacjach stosu. Kiedy argumenty znajdują się już w odpowiednich rejestrach, nie trzeba ich przesuwać.

Czytając zdemontowany kod, widziałem śmieszne tasowanie rejestrów, ponieważ ludzie nie przestrzegali tej zasady.

Dwie techniki kodowania, których nie widziałem na powyższej liście:

Omiń konsolidator, pisząc kod jako unikalne źródło

Chociaż oddzielna kompilacja jest naprawdę dobra do czasu kompilacji, jest bardzo zła, gdy mówisz o optymalizacji. Zasadniczo kompilator nie może optymalizować poza jednostką kompilacji, czyli domeną zarezerwowaną dla konsolidatora.

Ale jeśli dobrze zaprojektujesz swój program, możesz go również skompilować za pomocą unikalnego wspólnego źródła. Oznacza to, że zamiast kompilowania jednostek unit1.c i unit2.c, połącz oba obiekty, skompiluj all.c, które po prostu # zawierają jednostki1.c i jednostka2.c. W ten sposób skorzystasz ze wszystkich optymalizacji kompilatora.

To bardzo przypomina pisanie tylko nagłówków programów w C ++ (a nawet łatwiejsze w C).

Ta technika jest dość łatwa, jeśli napiszesz swój program, aby włączyć go od samego początku, ale musisz także mieć świadomość, że zmienia on część semantyki C i możesz napotkać pewne problemy, takie jak zmienne statyczne lub kolizje makr. W przypadku większości programów dość łatwo jest pokonać pojawiające się drobne problemy. Należy również pamiętać, że kompilacja jako unikalnego źródła jest znacznie wolniejsza i może wymagać dużej ilości pamięci (zwykle nie jest to problem w przypadku nowoczesnych systemów).

Używając tej prostej techniki zdarzyło mi się zrobić kilka programów, które napisałem dziesięć razy szybciej!

Podobnie jak słowo kluczowe register, ta sztuczka może wkrótce stać się przestarzała. Optymalizacja przez linker zaczyna być obsługiwana przez kompilatory gcc: Optymalizacja czasu łącza .

Oddzielne zadania atomowe w pętlach

Ten jest trudniejszy. Chodzi o interakcję między projektem algorytmu a sposobem zarządzania pamięcią podręczną i alokacją rejestrów przez optymalizator. Dość często programy muszą zapętlić jakąś strukturę danych i dla każdego elementu wykonać pewne czynności. Dość często wykonywane czynności można podzielić na dwa logicznie niezależne zadania. W takim przypadku możesz napisać dokładnie ten sam program z dwiema pętlami na tej samej granicy, wykonując dokładnie jedno zadanie. W niektórych przypadkach zapisanie tego w ten sposób może być szybsze niż w przypadku pętli unikatowej (szczegóły są bardziej złożone, ale wyjaśnienie może być takie, że w przypadku prostego zadania wszystkie zmienne mogą być przechowywane w rejestrach procesora, a przy bardziej złożonym nie jest to możliwe, a niektóre rejestry muszą być zapisane w pamięci i później odczytane, a koszt jest wyższy niż dodatkowa kontrola przepływu).

Bądź ostrożny z tym (profilowe wyniki używające tej sztuczki lub nie), ponieważ podobnie jak użycie rejestru może równie dobrze dawać gorsze wyniki niż ulepszone.

Rzeczywiście widziałem to zrobione w SQLite i twierdzą, że powoduje to wzrost wydajności o ~ 5%: Umieść cały kod w jednym pliku lub użyj preprocesora, aby zrobić to samo. W ten sposób optymalizator będzie miał dostęp do całego programu i będzie mógł wykonać więcej optymalizacji międzyproceduralnych.

Większość nowoczesnych kompilatorów powinna wykonać dobrą robotę, przyspieszając rekurencję ogonową , ponieważ wywołania funkcji można zoptymalizować.

Przykład:

int fac2(int x, int cur) {
  if (x == 1) return cur;
  return fac2(x - 1, cur * x); 
}
int fac(int x) {
  return fac2(x, 1);
}

Oczywiście ten przykład nie ma żadnego sprawdzania granic.

Późna edycja

Chociaż nie mam bezpośredniej znajomości kodu; wydaje się jasne, że wymagania używania CTE na SQL Server zostały specjalnie zaprojektowane tak, aby można było je optymalizować za pomocą rekurencji końca.

Nie wykonuj w kółko tej samej pracy!

Typowy antywzor, który widzę, przebiega w ten sposób:

void Function()
{
   MySingleton::GetInstance()->GetAggregatedObject()->DoSomething();
   MySingleton::GetInstance()->GetAggregatedObject()->DoSomethingElse();
   MySingleton::GetInstance()->GetAggregatedObject()->DoSomethingCool();
   MySingleton::GetInstance()->GetAggregatedObject()->DoSomethingReallyNeat();
   MySingleton::GetInstance()->GetAggregatedObject()->DoSomethingYetAgain();
}

Kompilator musi w rzeczywistości wywoływać wszystkie te funkcje przez cały czas. Zakładając, że programista wie, że zagregowany obiekt nie zmienia się w trakcie tych wezwań, z miłości do wszystkiego, co święte ...

void Function()
{
   MySingleton* s = MySingleton::GetInstance();
   AggregatedObject* ao = s->GetAggregatedObject();
   ao->DoSomething();
   ao->DoSomethingElse();
   ao->DoSomethingCool();
   ao->DoSomethingReallyNeat();
   ao->DoSomethingYetAgain();
}

W przypadku pojedynczego gettera wywołania mogą nie być zbyt kosztowne, ale z pewnością jest to koszt (zazwyczaj „sprawdź, czy obiekt został utworzony, jeśli nie, utwórz go, a następnie zwróć). tym bardziej skomplikowany staje się ten łańcuch pochłaniaczy, tym więcej będziemy tracić czasu.

1. Użyj możliwie największego zakresu lokalnego dla wszystkich deklaracji zmiennych.

2. Używaj w constmiarę możliwości

3. Nie używaj register, chyba że planujesz profilować zarówno z, jak i bez niego

Pierwsze 2 z nich, zwłaszcza numer 1, pomagają optymalizatorowi w analizie kodu. Szczególnie pomoże mu to w dokonywaniu dobrych wyborów dotyczących tego, jakie zmienne należy przechowywać w rejestrach.

Ślepe użycie słowa kluczowego register może równie dobrze pomóc, co zaszkodzić optymalizacji. Po prostu zbyt trudno jest wiedzieć, co będzie miało znaczenie, dopóki nie spojrzysz na wyjście zespołu lub profil.

Są inne rzeczy, które mają znaczenie dla uzyskania dobrej wydajności z kodu; na przykład projektowanie struktur danych w celu maksymalizacji spójności pamięci podręcznej. Ale pytanie dotyczyło optymalizatora.

Dopasuj dane do rodzimych / naturalnych granic.

Przypomniało mi się coś, co kiedyś napotkałem, gdzie objawem było po prostu to, że kończyła się nam pamięć, ale rezultatem był znaczny wzrost wydajności (jak również ogromne zmniejszenie zużycia pamięci).

Problem w tym przypadku polegał na tym, że oprogramowanie, którego używaliśmy, generowało mnóstwo niewielkich przydziałów. Na przykład przydzielanie czterech bajtów tutaj, sześciu bajtów tam itd. Wiele małych obiektów również działa w zakresie 8-12 bajtów. Problem nie polegał na tym, że program potrzebował wielu drobiazgów, ale na tym, że przydzielał wiele drobiazgów indywidualnie, co powodowało rozdęcie każdego przydziału do (na tej konkretnej platformie) 32 bajtów.

Częścią rozwiązania było złożenie małej puli obiektów w stylu Alexandrescu, ale rozszerzenie jej, aby móc przydzielać zarówno tablice małych obiektów, jak i pojedyncze elementy. Pomogło to również ogromnie w wydajności, ponieważ więcej elementów mieści się w pamięci podręcznej w dowolnym momencie.

Drugą częścią rozwiązania było zastąpienie szalejącego używania ręcznie zarządzanych elementów char * ciągiem SSO (optymalizacji małych ciągów). Minimalna alokacja to 32 bajty, zbudowałem klasę ciągów, która miała osadzony 28-znakowy bufor za char *, więc 95% naszych ciągów nie musiało wykonywać dodatkowej alokacji (a następnie ręcznie zastąpiłem prawie każdy wygląd char * w tej bibliotece z tą nową klasą, było fajnie, czy nie). Pomogło to również tonowi w fragmentacji pamięci, co następnie zwiększyło lokalność odniesienia dla innych wskazanych obiektów i podobnie nastąpił wzrost wydajności.

Zgrabna technika, której nauczyłem się z komentarza @MSalters do tej odpowiedzi, pozwala kompilatorom kopiować elision nawet wtedy, gdy zwracają różne obiekty zgodnie z pewnym warunkiem:

// before
BigObject a, b;
if(condition)
  return a;
else
  return b;

// after
BigObject a, b;
if(condition)
  swap(a,b);
return a;

Jeśli masz małe funkcje, które wywołujesz wielokrotnie, miałem w przeszłości duże korzyści, umieszczając je w nagłówkach jako „statyczne wbudowane”. Wywołania funkcji w ix86 są zaskakująco drogie.

Reimplementacja funkcji rekurencyjnych w sposób nierekurencyjny przy użyciu jawnego stosu również może wiele zyskać, ale tak naprawdę jesteś w sferze czasu programowania w porównaniu do zysku.

Oto moja druga rada dotycząca optymalizacji. Podobnie jak w przypadku mojej pierwszej rady, jest to cel ogólny, a nie specyficzny dla języka lub procesora.

Przeczytaj dokładnie instrukcję kompilatora i zrozum, o czym ona mówi. Użyj kompilatora do maksimum.

Zgadzam się z jednym lub dwoma innymi respondentami, którzy wskazali, że wybór odpowiedniego algorytmu ma kluczowe znaczenie dla wyciśnięcia wydajności z programu. Poza tym stopa zwrotu (mierzona poprawą wykonywania kodu) w czasie inwestowania w użycie kompilatora jest znacznie wyższa niż stopa zwrotu w ulepszaniu kodu.

Tak, twórcy kompilatorów nie są z rasy gigantów kodowania, a kompilatory zawierają błędy, a to, co powinno, zgodnie z instrukcją i zgodnie z teorią kompilatora, przyspieszyć, czasami spowalnia. Dlatego musisz robić krok po kroku i mierzyć wydajność przed i po poprawieniu.

I tak, ostatecznie możesz stanąć w obliczu kombinatorycznej eksplozji flag kompilatora, więc musisz mieć skrypt lub dwa, aby uruchomić make z różnymi flagami kompilatora, ustawić w kolejce zadania w dużym klastrze i zebrać statystyki czasu wykonywania. Jeśli jesteś tylko ty i Visual Studio na komputerze PC, stracisz zainteresowanie na długo przed wypróbowaniem wystarczającej liczby kombinacji wystarczającej liczby flag kompilatora.

pozdrowienia

znak

Kiedy po raz pierwszy odbieram fragment kodu, zwykle mogę uzyskać współczynnik 1,4 - 2,0 razy większą wydajność (tj. Nowa wersja kodu działa w 1 / 1,4 lub 1/2 czasu starej wersji) w ciągu dzień lub dwa, bawiąc się flagami kompilatora. To prawda, że ​​może to być raczej komentarz dotyczący braku umiejętności kompilatora wśród naukowców, którzy są twórcami większości kodu, nad którym pracuję, a nie symptom mojej doskonałości. Po ustawieniu flag kompilatora na max (i rzadko jest to tylko -O3) może zająć miesiące ciężkiej pracy, aby uzyskać kolejny współczynnik 1,05 lub 1,1

Kiedy DEC pojawił się ze swoimi procesorami alfa, było zalecenie, aby utrzymywać liczbę argumentów funkcji poniżej 7, ponieważ kompilator zawsze próbowałby automatycznie umieścić do 6 argumentów w rejestrach.

Aby uzyskać wydajność, skoncentruj się najpierw na pisaniu kodu, który można konserwować - skomponowany, luźno powiązany itp., Więc jeśli musisz wyodrębnić część w celu przepisania, optymalizacji lub po prostu profilowania, możesz to zrobić bez większego wysiłku.

Optymalizator nieznacznie zwiększy wydajność programu.

Otrzymujesz tutaj dobre odpowiedzi, ale zakładają, że Twój program jest na początku dość bliski optymalnego, i mówisz

Załóżmy, że program został poprawnie napisany, skompilowany z pełną optymalizacją, przetestowany i wdrożony do produkcji.

Z mojego doświadczenia wynika, że ​​program może być napisany poprawnie, ale to nie znaczy, że jest bliski optymalnego. Dojście do tego punktu wymaga dodatkowej pracy.

Jeśli mogę podać przykład, ta odpowiedź pokazuje, jak doskonale wyglądający program został wykonany ponad 40 razy szybciej dzięki optymalizacji makro . Duże przyspieszenia nie mogą być wykonane w każdym programie, tak jak napisano na początku, ale w wielu (z wyjątkiem bardzo małych programów) jest to możliwe, z mojego doświadczenia.

Po wykonaniu tej czynności mikro-optymalizacja (hot-spotów) może przynieść niezłe korzyści.

używam kompilatora Intel. zarówno w systemie Windows, jak i Linux.

kiedy mniej więcej skończyłem, profiluję kod. następnie zawieszaj się na hotspotach i próbuj zmienić kod, aby umożliwić kompilatorowi lepszą pracę.

jeśli kod jest kodem obliczeniowym i zawiera dużo pętli - bardzo pomocny jest raport wektoryzacji w kompilatorze Intel - poszukaj w pomocy 'vec-report'.

więc główna idea - dopracuj kod krytyczny dla wydajności. co do reszty - pierwszeństwo poprawności i utrzymania - krótkie funkcje, czytelny kod, który można było zrozumieć 1 rok później.

Jedną z optymalizacji, której użyłem w C ++, jest utworzenie konstruktora, który nic nie robi. Należy ręcznie wywołać init () w celu wprowadzenia obiektu w stan roboczy.

Jest to korzystne w przypadku, gdy potrzebuję dużego wektora tych klas.

Wywołuję Reserve (), aby przydzielić miejsce na wektor, ale konstruktor w rzeczywistości nie dotyka strony pamięci, na której znajduje się obiekt. Więc spędziłem trochę przestrzeni adresowej, ale tak naprawdę nie zużyłem dużo pamięci fizycznej. Unikam błędów stron związanych z kosztami budowy.

Kiedy generuję obiekty do wypełnienia wektora, ustawiam je za pomocą init (). Ogranicza to całkowitą liczbę błędów stron i pozwala uniknąć konieczności zmiany rozmiaru () wektora podczas wypełniania go.

Jedną z rzeczy, które zrobiłem, jest próba zatrzymania kosztownych działań w miejscach, w których użytkownik może oczekiwać, że program trochę się opóźni. Ogólna wydajność jest związana z responsywnością, ale nie jest taka sama, a pod wieloma względami czas reakcji jest ważniejszą częścią wydajności.

Ostatnim razem, gdy naprawdę musiałem poprawić ogólną wydajność, zwracałem uwagę na nieoptymalne algorytmy i szukałem miejsc, w których prawdopodobnie wystąpiły problemy z pamięcią podręczną. Najpierw profilowałem i mierzyłem wydajność, a potem ponownie po każdej zmianie. Potem firma upadła, ale i tak była to ciekawa i pouczająca praca.

Od dawna podejrzewałem, ale nigdy nie udowodniłem, że zadeklarowanie tablic tak, aby miały potęgę 2, jako liczbę elementów, umożliwia optymalizatorowi zmniejszenie siły poprzez zastąpienie mnożenia przez przesunięcie o liczbę bitów, patrząc w górę poszczególne elementy.

Umieść małe i / lub często wywoływane funkcje na górze pliku źródłowego. Ułatwia to kompilatorowi znalezienie możliwości wbudowania.