Optymalizacja kolejności zmiennych w C++

Czytałem post na blogu przez kodera gry dla introwersji i on jest zajęty próbuje wycisnąć każdy CPU kleszcz może z kodu. Jedna sztuczka, o której wspomina off-hand, to

" ponownie Uporządkuj zmienne członkowskie klasy do najczęściej używanych i najmniej używanych."

Nie jestem zaznajomiony z C++, ani z tym, jak kompiluje, ale zastanawiałem się, czy

  1. to stwierdzenie jest dokładne?
  2. Jak / Dlaczego?
  3. czy dotyczy to inne języki (skompilowane/Skryptowe)?

Zdaję sobie sprawę, że ilość czasu (CPU) zaoszczędzonego przez tę sztuczkę byłaby minimalna, nie jest to łamanie umowy. Ale z drugiej strony, w większości funkcji byłoby dość łatwo zidentyfikować, które zmienne będą najczęściej używane, i po prostu zacząć kodować w ten sposób domyślnie.

Author: jww, 2009-05-21
Source

11 answers

Dwie kwestie tutaj:

  • czy i kiedy utrzymywanie pewnych pól razem jest optymalizacją.
  • Jak właściwie to zrobić.

Powodem, dla którego może to pomóc, jest to, że pamięć jest ładowana do pamięci podręcznej CPU w kawałkach zwanych "liniami pamięci podręcznej". Wymaga to czasu i ogólnie rzecz biorąc, im więcej linii pamięci podręcznej jest załadowanych dla obiektu, tym dłużej to trwa. Ponadto, im więcej innych rzeczy zostaje wyrzucone z pamięci podręcznej, aby zrobić miejsce, co spowalnia inny kod w nieprzewidywalny sposób.

Wielkość linii pamięci podręcznej zależy od procesora. Jeśli jest on duży w porównaniu z rozmiarem Twoich obiektów, to bardzo niewiele obiektów obejmie granicę linii bufora, więc cała optymalizacja jest dość nieistotna. W przeciwnym razie, może ujdzie ci to na sucho, jeśli w pamięci podręcznej znajduje się tylko część obiektu, a reszta w pamięci głównej (lub L2 cache, być może). Dobrze, że najczęstsze operacje (te, które mają dostęp do powszechnie używanych pól) używają tak małej ilości pamięci podręcznej, jak możliwe dla obiektu, więc grupowanie tych pól razem daje większą szansę na to.

Ogólna zasada nazywa się "miejscem odniesienia". Im bliżej różnych adresów pamięci jest dostęp do programu, tym większe są szanse na uzyskanie dobrego zachowania pamięci podręcznej. Często trudno jest przewidzieć wydajność z góry: różne modele procesorów o tej samej architekturze mogą zachowywać się inaczej, wielowątkowość oznacza, że często nie wiesz, co to jest będzie w pamięci podręcznej itp. Ale można mówić o tym, co prawdopodobnie się wydarzy, przez większość czasu. Jeśli chcesz wiedzieć cokolwiek, zazwyczaj musisz to zmierzyć.

Proszę zauważyć, że są tu jakieś gotchy. Jeśli używasz operacji atomowych opartych na CPU (co zazwyczaj robią typy atomowe w C++0x), może się okazać, że procesor blokuje całą linię pamięci podręcznej w celu zablokowania pola. Następnie, jeśli masz kilka pól atomowych blisko siebie, z różne wątki działające na różnych rdzeniach i działające na różnych polach w tym samym czasie, przekonasz się, że wszystkie te operacje atomowe są serializowane, ponieważ wszystkie blokują tę samą lokalizację pamięci, mimo że działają na różnych polach. Gdyby działały na różnych liniach pamięci podręcznej, pracowałyby równolegle i działały szybciej. W rzeczywistości, jak wskazuje Glen (za pośrednictwem Herb Sutter) w swojej odpowiedzi, na architekturze koherentnej dzieje się to nawet bez atomów operacji i może całkowicie zrujnować twój dzień. Tak więc lokalizacja odniesienia nie jest koniecznie dobrą rzeczą, w której zaangażowanych jest wiele rdzeni, nawet jeśli dzielą one pamięć podręczną. Możesz się tego spodziewać, ponieważ chybione pamięci podręczne zwykle są źródłem utraconej prędkości, ale w konkretnym przypadku bardzo się mylisz.

Teraz, pomijając rozróżnianie między polami powszechnie używanymi i mniej używanymi, im mniejszy obiekt, tym mniej zajmuje pamięć (a co za tym idzie mniej pamięci podręcznej). To jest piękne. wiele dobrych wiadomości dookoła, przynajmniej tam, gdzie nie masz ciężkich sporów. Rozmiar obiektu zależy od znajdujących się w nim pól oraz od dowolnego wypełnienia, które musi zostać wstawione między polami w celu zapewnienia ich prawidłowego wyrównania dla architektury. C++ (czasami) nakłada ograniczenia na kolejność, jakie pola muszą pojawić się w obiekcie, w zależności od kolejności, w jakiej są zadeklarowane. Ma to ułatwić programowanie niskopoziomowe. Tak więc, jeśli twój obiekt zawiera:

  • an int (4 bajty, 4-wyrównane)
  • po którym następuje znak (1 bajt, dowolne wyrównanie)
  • po którym następuje int (4 bajty, 4-wyrównane)
  • po którym następuje znak (1 bajt, dowolne wyrównanie)

Wtedy są szanse, że zajmie to 16 bajtów w pamięci. Rozmiar i wyrównanie int nie jest taki sam na każdej platformie, nawiasem mówiąc, ale 4 jest bardzo powszechne i to jest tylko przykład.

W tym przypadku kompilator wstawia 3 bajty padding przed drugą int, aby ją poprawnie wyrównać, oraz 3 bajty of wyściółka na końcu. Rozmiar obiektu musi być wielokrotnością jego wyrównania, aby obiekty tego samego typu mogły być umieszczone obok siebie w pamięci. To wszystko tablica jest w C / C++, sąsiednie obiekty w pamięci. Gdyby struct był int, int, char, char, to ten sam obiekt mógłby mieć 12 bajtów, ponieważ char nie ma wymogu wyrównania.

Powiedziałem, że to, czy int jest wyrównany do 4, zależy od platformy: na ARM absolutnie musi być, ponieważ unaligned access rzuca wyjątek sprzętowy. Na x86 możesz uzyskać dostęp do int bez zmian, ale ogólnie jest wolniejszy i IIRC nie-atomowy. Więc Kompilatory zazwyczaj(zawsze?/ 4-align = "center" bgcolor = "# e0ffe0"

Regułą podczas pisania kodu, jeśli zależy ci na pakowaniu, jest przyjrzenie się wymaganiom wyrównania każdego elementu struktury. Następnie najpierw porządkuj pola z typami najbardziej wyrównanymi, a następnie najmniejszymi, i tak dalej, aż do członków bez wymogu aligacji. Na przykład, jeśli próbuję napisać przenośny Kod, mogę wymyślić to: 

struct some_stuff {
    double d;   // I expect double is 64bit IEEE, it might not be
    uint64_t l; // 8 bytes, could be 8-aligned or 4-aligned, I don't know
    uint32_t i; // 4 bytes, usually 4-aligned
    int32_t j;  // same
    short s;    // usually 2 bytes, could be 2-aligned or unaligned, I don't know
    char c[4];  // array 4 chars, 4 bytes big but "never" needs 4-alignment
    char d;     // 1 byte, any alignment
};

Jeśli nie znasz wyrównania pola lub piszesz przenośny Kod, ale chcesz zrobić wszystko, co w twojej mocy, bez większych sztuczek, to zakładasz, że wymaganie wyrównania jest największym wymaganiem każdego fundamentalnego typu w strukturze i że wymaganiem wyrównania podstawowych typów jest ich rozmiar. Tak więc, jeśli twoja struktura zawiera uint64_t lub long long, to najlepiej zgadywać, że jest wyrównana do 8. Czasami będziesz się mylić, ale będziesz miał rację. czas.

Zauważ, że programiści gier tacy jak Twój bloger często wiedzą wszystko o swoim procesorze i sprzęcie, a tym samym nie muszą zgadywać. Znają rozmiar linii bufora, rozmiar i wyrównanie każdego typu oraz reguły układu struct używane przez ich kompilator (dla typów POD i nie-POD). Jeśli obsługują wiele platform, w razie potrzeby mogą w specjalnym przypadku dla każdej z nich. Spędzają również dużo czasu na myśleniu o tym, które obiekty w ich grze będą skorzystaj z poprawy wydajności i skorzystaj z profilerów, aby dowiedzieć się, gdzie są prawdziwe wąskie gardła. Ale mimo to, to nie jest taki zły pomysł, aby mieć kilka zasad, które można zastosować, czy obiekt tego potrzebuje, czy nie. Dopóki kod nie będzie niejasny, "umieść powszechnie używane pola na początku obiektu" i "sortuj według wymogu wyrównania" to dwie dobre zasady.

 56
Author: Steve Jessop,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-07-29 06:52:21

W zależności od typu programu, który uruchamiasz, ta porada może spowodować zwiększenie wydajności lub może drastycznie spowolnić działanie.

Robienie tego w programie wielowątkowym oznacza, że zwiększysz szanse na "fałszywe dzielenie się".

Zobacz artykuły na ten temat tutaj

Już to mówiłem i będę to powtarzał. Jedynym realnym sposobem, aby uzyskać rzeczywisty wzrost wydajności, jest zmierzenie kodu i użycie narzędzi do identyfikacji rzeczywistego szyjka butelki zamiast dowolnie zmieniać rzeczy w bazie kodu.

 10
Author: Glen,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-05-21 13:00:16

Jest to jeden ze sposobów optymalizacji rozmiaru zestawu roboczego . Istnieje dobry Artykuł autorstwa Johna Robbinsa o tym, jak można przyspieszyć wydajność aplikacji poprzez optymalizację rozmiaru zestawu roboczego. Oczywiście wiąże się to ze starannym wyborem najczęstszych przypadków użycia, które użytkownik końcowy może wykonać z aplikacją.

 6
Author: Canopus,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-10-24 21:22:28

Mamy tutaj nieco inne wytyczne dla członków (ARM architecture target, głównie THUMB 16-bit codegen z różnych powodów):

  • group by alignment requirements (lub, dla początkujących, "group by size" zwykle robi sztuczkę)
  • najmniejszy pierwszy

"Grupowanie według wyrównania" jest dość oczywiste i poza zakresem tego pytania; unika wypełniania, zużywa mniej pamięci itp.

Drugi pocisk wywodzi się jednak z małego, 5-bitowego pola" natychmiastowego" rozmiar na kciuku instrukcji LDRB (Load Register Byte), LDRH (Load Register Halfword) i LDR (Load Register).

5 bitów oznacza, że można zakodować offsety o wartości 0-31. W praktyce, zakładając, że" to " jest przydatne w rejestrze (którym zazwyczaj jest):

  • 8-bitowe bajty mogą być ładowane w jednej instrukcji, jeśli istnieją w tym+0 przez to + 31
  • 16-bitowe halfwords jeśli istnieją przy tym + 0 do tego + 62;
  • 32-bitowe słowa maszynowe, jeśli istnieją w tym+0 przez ten+124.

Jeśli znajdują się poza tym zakresem, należy wygenerować wiele instrukcji: albo sekwencję ADDs z natychmiastami, aby zgromadzić odpowiedni adres w rejestrze, albo, co gorsza, obciążenie z puli dosłownej na końcu funkcji.

Jeśli trafimy w pulę dosłowną, to boli: Pula dosłowna przechodzi przez D-cache, a nie i-cache; oznacza to co najmniej wartość cacheline ładowań z pamięci głównej dla pierwszego dosłownego dostępu do puli, a następnie wiele potencjalne problemy z eksmisją i unieważnieniem pomiędzy D-cache I i-cache, jeśli pula literałów nie zaczyna się na własnej linii pamięci podręcznej (tzn. jeśli rzeczywisty kod nie kończy się na końcu linii pamięci podręcznej).

(gdybym miał kilka życzeń dla kompilatora, z którym pracujemy, jednym z nich byłby sposób na zmuszenie dosłownych basenów do rozpoczęcia na granicach cacheline.)

(niezmiennie, jedną z rzeczy, które robimy, aby uniknąć dosłownego użycia puli, jest utrzymywanie wszystkich naszych "globali" w jednej tabeli. Oznacza to, że jeden dosłowne wyszukiwanie puli dla "GlobalTable", a nie wielokrotne wyszukiwanie dla każdego globalnego. Jeśli jesteś naprawdę mądry, możesz być w stanie utrzymać GlobalTable w jakiejś pamięci, do której można uzyskać dostęp bez ładowania dosłownego wpisu puli-prawda .sbss?)

 3
Author: leander,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-05-21 17:44:58

Chociaż lokalizacja odniesienia w celu poprawy zachowania pamięci podręcznej dostępu do danych jest często istotnym czynnikiem, istnieje kilka innych powodów do kontrolowania układu, gdy wymagana jest optymalizacja - szczególnie w systemach wbudowanych, nawet jeśli Procesory używane w wielu systemach wbudowanych nie mają nawet pamięci podręcznej.

- wyrównanie pamięci pól w strukturach

Względy wyrównania są dość dobrze rozumiane przez wielu programistów, więc nie będę się zbytnio angażował szczegóły tutaj.

Na większości architektur CPU, pola w strukturze muszą być dostępne z natywnym wyrównaniem dla wydajności. Oznacza to, że jeśli mieszasz pola o różnych rozmiarach, kompilator musi dodać wypełnienie między polami, aby wymagania wyrównania były poprawne. Tak więc, aby zoptymalizować pamięć używaną przez strukturę, ważne jest, aby mieć to na uwadze i rozłożyć pola tak, aby po największych polach następowały mniejsze pola, aby ograniczyć wymagane wypełnienie do minimum. Jeśli struktura dostęp do niepodpisanych pól ma być "zapakowany", aby zapobiec wypełnieniu, ponieważ kompilator musi uzyskać dostęp do niepodpisanych pól przy użyciu serii dostępu do mniejszych części pola wraz z przesunięciami i maskami, aby zmontować wartość pola w rejestrze.

- przesunięcie często używanych pól w strukturze

Inną kwestią, która może być ważna w wielu systemach wbudowanych, jest posiadanie często dostępnych pól na początku struktury.

Niektóre architektury mają ograniczoną liczbę bitów dostępnych w instrukcji kodowania offsetu do dostępu do wskaźnika, więc jeśli uzyskasz dostęp do pola, którego offset przekracza tę liczbę bitów, kompilator będzie musiał użyć wielu instrukcji, aby utworzyć wskaźnik do pola. Na przykład, Architektura kciuka ramienia ma 5 bitów do kodowania offsetu, więc może uzyskać dostęp do pola o rozmiarze słowa w pojedynczej instrukcji tylko wtedy, gdy pole znajduje się w odległości 124 bajtów od początku. Więc jeśli masz duży struktura optymalizacja, o której inżynier Wbudowany może chcieć pamiętać, polega na umieszczeniu często używanych pól na początku układu struktury.

 3
Author: Michael Burr,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-05-23 03:26:51

Well the first member doesn ' t need a offset added to the pointer to access it.

 2
Author: Lou Franco,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-05-21 12:52:06

W C# kolejność elementów jest określona przez kompilator, chyba że umieścisz atrybut [LayoutKind.Sequential/ Explicit], która zmusza kompilator do ułożenia struktury / klasy w sposób, w jaki ją podpowiadasz.

Z tego co wiem, kompilator wydaje się minimalizować pakowanie, wyrównując typy danych w ich naturalnym porządku (np. 4 bajty int rozpoczynają się na 4 bajtowych adresach).

 1
Author: Remi Lemarchand,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-05-21 14:28:42

Teoretycznie może to zmniejszyć liczbę braków w pamięci podręcznej, jeśli masz duże obiekty. Ale zazwyczaj lepiej jest grupować członków tej samej wielkości razem, więc masz mocniejsze zapakowanie pamięci.

 0
Author: Johan Kotlinski,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-05-21 12:52:53

Skupiam się na wydajności, szybkości wykonania, a nie wykorzystaniu pamięci. Kompilator, bez żadnego przełącznika optymalizującego, mapuje obszar przechowywania zmiennych używając tej samej kolejności deklaracji w kodzie. Imagine 

 unsigned char a;
 unsigned char b;
 long c;
Wielki bałagan? bez przełączników wyrównujących, operacje o niskiej pamięci. et al, będziemy mieć unsigned char za pomocą 64-bitowego słowa na Twoim dimm DDR3, a kolejne 64-bitowe słowo dla drugiego, a jednak nieuniknione jeden na długo.

Więc, to aport dla każdego zmienna.

Jednak pakowanie go lub ponowne zamówienie spowoduje, że one fetch i one and masking będą mogły używać znaków niepodpisanych.

Więc pod względem szybkości, na obecnej 64-bitowej maszynie word-memory, wyrównania, zmiany kolejności itp. są no-nos. zajmuję się mikrokontrolerami i tam różnice w spakowanych / niepakowanych są naprawdę zauważalne (mówiąc o procesorach

Z boku, od dawna wiadomo, że wysiłek inżynieryjny wymagany do poprawienia kodu dla wydajność inna niż to, co nakazuje dobry algorytm i co kompilator jest w stanie zoptymalizować, często skutkuje spalaniem gumy bez rzeczywistych efektów. To i tylko fragment składni kodu dubiusa.

Ostatnim krokiem naprzód w optymalizacji widziałem (w uPs, nie sądzę, że jest to wykonalne dla aplikacji PC) jest skompilowanie programu jako pojedynczy moduł, mieć kompilator zoptymalizować go (znacznie bardziej ogólny widok prędkości / rozdzielczości wskaźnika/pakowania pamięci, itp), i mieć kosz linker Nie wywołane funkcje biblioteczne, metody, itp.

 0
Author: jpinto3912,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-05-21 13:41:57

Hmmm, to brzmi jak bardzo wątpliwa praktyka, dlaczego kompilator nie miałby się tym zająć?

 0
Author: chickeninabiscuit,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-05-22 06:00:18

Bardzo wątpię, aby miało to jakikolwiek wpływ na usprawnienia CPU - może czytelność. Możesz zoptymalizować kod wykonywalny, jeśli najczęściej wykonywane bloki podstawowe, które są wykonywane w danej ramce, znajdują się w tym samym zestawie stron. Jest to ten sam pomysł, ale nie wiedziałby, jak tworzyć podstawowe bloki w kodzie. Domyślam się, że kompilator umieszcza funkcje w kolejności, w jakiej je widzi bez optymalizacji, więc możesz spróbować umieścić wspólną funkcjonalność razem.

Try i uruchom profiler / optymalizator. Najpierw kompilujesz z jakąś opcją profilowania, a następnie uruchamiasz program. Gdy profilowany exe jest kompletny, zrzuci kilka profilowanych informacji. Weź ten zrzut i przeprowadź go przez optymalizator jako dane wejściowe.

Od lat jestem z dala od tej branży, ale niewiele zmieniło to, jak działają.

 0
Author: AndrewB,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-10-24 20:42:23