Jakich prostych technik używasz do poprawy wydajności?

Mówię o tym, w jaki sposób piszemy proste procedury w celu poprawy wydajności bez utrudniania czytania kodu ... na przykład, jest to typowe, czego się nauczyliśmy:

for(int i = 0; i < collection.length(); i++ ){
   // stuff here
}

Ale zwykle robię to, gdy a foreachnie ma zastosowania:

for(int i = 0, j = collection.length(); i < j; i++ ){
   // stuff here
}

Myślę, że jest to lepsze podejście, ponieważ wywoła tę lengthmetodę tylko raz ... moja dziewczyna mówi, że jest to zagadkowe. Czy jest jakaś inna prosta sztuczka, której używasz w swoich projektach?

wstaw wykład przedwczesny-dyskusja-jest-źródłem-złego

To powiedziawszy, oto kilka nawyków, które wdrożyłem, aby uniknąć niepotrzebnej wydajności, aw niektórych przypadkach uczynić mój kod prostszym i bardziej poprawnym.

To nie jest omówienie ogólnych zasad, ale pewnych rzeczy, o których należy pamiętać, aby uniknąć wprowadzania niepotrzebnych nieefektywności do kodu.

Poznaj swoje duże-O

Powinno to prawdopodobnie zostać włączone do długiej dyskusji powyżej. Powszechnie wiadomo, że pętla wewnątrz pętli, w której pętla wewnętrzna powtarza obliczenia, będzie wolniejsza. Na przykład:

for (i = 0; i < strlen(str); i++) {
    ...
}

Zajmie to strasznie dużo czasu, jeśli łańcuch będzie naprawdę długi, ponieważ długość jest ponownie obliczana przy każdej iteracji pętli. Zauważ, że GCC faktycznie optymalizuje ten przypadek, ponieważ strlen()jest oznaczony jako czysta funkcja.

Podczas sortowania miliona 32-bitowych liczb całkowitych sortowanie bąbelkowe byłoby niewłaściwą drogą . Ogólnie rzecz biorąc, sortowanie może odbywać się w czasie O (n * log n) (lub lepiej, w przypadku sortowania Radix), więc jeśli nie wiesz, że twoje dane będą małe, poszukaj algorytmu, który jest co najmniej O (n * log n).

Podobnie, mając do czynienia z bazami danych, należy pamiętać o indeksach. Jeśli SELECT * FROM people WHERE age = 20nie masz indeksu osób (wiek), będzie to wymagać sekwencyjnego skanowania O (n) zamiast znacznie szybszego skanowania indeksu O (log n).

Hierarchia arytmetyczna liczb całkowitych

Podczas programowania w C należy pamiętać, że niektóre operacje arytmetyczne są droższe niż inne. W przypadku liczb całkowitych hierarchia wygląda mniej więcej tak (najpierw najtańsze):

• + - ~ & | ^
• << >>
• *
• /

To prawda, kompilator zwykle Optymalizacja takie rzeczy n / 2się n >> 1automatycznie, jeśli są kierowane do komputera głównego nurtu, ale jeśli jesteś kierowania wbudowanego urządzenia, możesz nie dostać tego luksusu.

Ponadto, % 2i & 1mają inną semantykę. Podział i moduł zwykle zaokrąglają się do zera, ale jego implementacja jest zdefiniowana. Dobry ol ' >>i &zawsze krąży w kierunku ujemnej nieskończoności, co (moim zdaniem) ma znacznie większy sens. Na przykład na moim komputerze:

printf("%d\n", -1 % 2); // -1 (maybe)
printf("%d\n", -1 & 1); // 1

Dlatego używaj tego, co ma sens. Nie myśl, że jesteś dobrym chłopcem, używając, % 2kiedy pierwotnie zamierzałeś pisać & 1.

Drogie operacje zmiennoprzecinkowe

Unikaj ciężkich operacji zmiennoprzecinkowych jak pow()i log()w kodzie, który tak naprawdę nie potrzebują, zwłaszcza gdy mamy do czynienia z liczbami całkowitymi. Weźmy na przykład czytanie numeru:

int parseInt(const char *str)
{
    const char *p;
    int         digits;
    int         number;
    int         position;

    // Count the number of digits
    for (p = str; isdigit(*p); p++)
        {}
    digits = p - str;

    // Sum the digits, multiplying them by their respective power of 10.
    number = 0;
    position = digits - 1;
    for (p = str; isdigit(*p); p++, position--)
        number += (*p - '0') * pow(10, position);

    return number;
}

To użycie pow()(i int<-> doublekonwersje potrzebne do jego użycia) jest nie tylko drogie, ale stwarza szansę na utratę precyzji (nawiasem mówiąc, powyższy kod nie ma problemów z precyzją). Właśnie dlatego wzdrygam się, gdy widzę, że tego typu funkcje są używane w kontekście niematematycznym.

Zauważ też, że poniższy „sprytny” algorytm, który mnoży przez 10 przy każdej iteracji, jest w rzeczywistości bardziej zwięzły niż powyższy kod:

int parseInt(const char *str)
{
    const char *p;
    int         number;

    number = 0;
    for (p = str; isdigit(*p); p++) {
        number *= 10;
        number += *p - '0';
    }

    return number;
}

Z twojego pytania i wątku komentarza wygląda to tak, jakbyś „pomyślał”, że ta zmiana kodu poprawia wydajność, ale tak naprawdę nie wiesz, czy tak się dzieje, czy nie.

Jestem fanem filozofii Kent Beck :

„Spraw, by działało, poprawiło, uczyniło to szybko”.

Moją techniką poprawiania wydajności kodu jest najpierw uzyskanie kodu pomyślnie przechodzącego testy jednostkowe, a następnie dobrze uwzględnione, a następnie (szczególnie w przypadku operacji w pętli) napisanie testu jednostkowego, który sprawdza wydajność, a następnie refaktoryzacja kodu lub wymyślenie innego algorytmu, jeśli ten „ wybrana opcja nie działa zgodnie z oczekiwaniami.

Na przykład, aby przetestować szybkość za pomocą kodu .NET, używam atrybutu Limit czasu NUnit do pisania twierdzeń, że wywołanie określonej metody zostanie wykonane w określonym czasie.

Używając czegoś takiego jak atrybut limitu czasu NUnit w podanym przykładzie kodu (i dużej liczbie iteracji dla pętli), możesz faktycznie udowodnić, czy twoje „ulepszenie” kodu naprawdę pomogło w wykonaniu tej pętli.

Jedno zastrzeżenie: Chociaż jest to skuteczne na poziomie „mikro”, z pewnością nie jest to jedyny sposób testowania wydajności i nie bierze pod uwagę problemów, które mogą wystąpić na poziomie „makro” - ale to dobry początek.

Pamiętaj, że twój kompilator może się obrócić:

for(int i = 0; i < collection.length(); i++ ){
   // stuff here
}

w:

int j = collection.length();
for(int i = 0; i < j; i++ ){
   // stuff here
}

lub coś podobnego, jeśli collectionnie uległo zmianie w pętli.

Jeśli ten kod znajduje się w części krytycznej czasowo Twojej aplikacji, warto dowiedzieć się, czy tak jest, czy nie - a nawet czy możesz zmienić opcje kompilatora, aby to zrobić.

Pozwoli to zachować czytelność kodu (ponieważ jest to pierwsze, czego większość ludzi się spodziewa), a jednocześnie zyska te dodatkowe cykle maszyny. Następnie możesz skoncentrować się na innych obszarach, w których kompilator nie może ci pomóc.

Na marginesie: jeśli zmienisz collectionwewnątrz pętli poprzez dodanie lub usunięcie elementów (tak, wiem, że to zły pomysł, ale tak się dzieje), wtedy twój drugi przykład albo nie zapętli wszystkich elementów, albo spróbuje uzyskać dostęp do przeszłości koniec tablicy.

Tego rodzaju optymalizacja zwykle nie jest zalecana. Kompilacji można łatwo dokonać przy pomocy tej optymalizacji, pracujesz z językiem programowania wyższego poziomu zamiast asemblera, więc myśl na tym samym poziomie.

To może nie dotyczyć tak dużo kodowania ogólnego przeznaczenia, ale obecnie głównie zajmuję się programowaniem wbudowanym. Mamy konkretny procesor docelowy (który nie przyspieszy - do czasu wycofania systemu za ponad 20 lat wyda się dziwnie przestarzały) i bardzo restrykcyjne terminy dla dużej części kodu. Procesor, podobnie jak wszystkie procesory, ma pewne dziwactwa dotyczące tego, które operacje są szybkie lub wolne.

Stosujemy technikę zapewniającą, że generujemy najbardziej wydajny kod, przy jednoczesnym zachowaniu czytelności dla całego zespołu. W miejscach, w których najbardziej naturalna konstrukcja języka nie generuje najbardziej wydajnego kodu, stworzyliśmy makra, które zapewniają stosowanie optymalnego kodu. Jeśli wykonamy kolejny projekt dla innego procesora, możemy zaktualizować makra dla optymalnej metody na tym procesorze.

Jako konkretny przykład dla naszego obecnego procesora, gałęzie opróżniają rurociąg, blokując procesor na 8 cykli. Kompilator pobiera następujący kod:

 bool isReady = (value > TriggerLevel);

i zamienia go w ekwiwalent zestawu

isReady = 0
if (value > TriggerLevel)
{
  isReady = 1;
}

To zajmie albo 3 cykle, albo 10, jeśli przeskoczy isReady=1;. Ale procesor ma maxinstrukcję pojedynczego cyklu , więc znacznie lepiej jest napisać kod, aby wygenerować tę sekwencję, która gwarantuje, że zawsze zajmie 3 cykle:

diff = value-TriggerLevel;
diff = max(diff, 0);
isReady = min(1,diff);

Oczywiście intencja tutaj jest mniej jasna niż oryginał. Stworzyliśmy więc makro, którego używamy, gdy chcemy logiczne porównanie Wielkiego Niż:

#define BOOL_GT(a,b) min(max((a)-(b),0),1)

//isReady = value > TriggerLevel;
isReady = BOOL_GT(value, TriggerLevel);

Możemy zrobić podobne rzeczy dla innych porównań. Dla osoby z zewnątrz kod jest nieco mniej czytelny niż gdybyśmy użyli tylko naturalnej konstrukcji. Jednak szybko staje się to jasne po spędzeniu trochę czasu na pracy z kodem i jest znacznie lepsze niż pozwalanie każdemu programistowi na eksperymentowanie z własnymi technikami optymalizacji.

Cóż, pierwszą radą byłoby uniknięcie takich przedwczesnych optymalizacji, dopóki nie będziesz dokładnie wiedział, co dzieje się z kodem, abyś był pewien, że faktycznie przyspieszasz go, a nie wolniej.

Na przykład w języku C # kompilator zoptymalizuje kod, jeśli zapętlasz długość tablicy, ponieważ wie, że nie musi on zmieniać zakresu, sprawdzaj indeks podczas uzyskiwania dostępu do tablicy. Jeśli spróbujesz go zoptymalizować, umieszczając długość tablicy w zmiennej, przerwiesz połączenie między pętlą a tablicą i faktycznie spowolnisz kod.

Jeśli zamierzasz dokonać mikrooptymalizacji, powinieneś ograniczyć się do rzeczy, o których wiadomo, że wykorzystują wiele zasobów. Jeśli tylko nieznacznie zwiększysz wydajność, powinieneś użyć najbardziej czytelnego i łatwego do utrzymania kodu. Jak praca komputera zmienia się w czasie, więc coś, co odkryłeś, jest teraz nieco szybsze, może nie zostać w ten sposób.

Mam bardzo prostą technikę.

1. Sprawiam, że mój kod działa.
2. Testuję to pod kątem prędkości.
3. Jeśli jest szybki, wrócę do kroku 1, aby uzyskać inną funkcję. Jeśli jest wolny, profiluję go, aby znaleźć wąskie gardło.
4. Naprawiam wąskie gardło. Wróć do kroku 1.

Wiele razy oszczędza się czas na obejście tego procesu, ale ogólnie będziesz wiedział, czy tak jest. W razie wątpliwości trzymam się tego domyślnie.

Skorzystaj ze zwarcia:

if(someVar || SomeMethod())

kodowanie zajmuje tyle samo czasu i jest tak samo czytelne jak:

if(someMethod() || someVar)

ale z czasem będzie szybciej oceniać.

Poczekaj sześć miesięcy, każ szefowi kupić wszystkim nowe komputery. Poważnie. W dłuższej perspektywie czas programisty jest znacznie droższy niż sprzęt. Komputery o wysokiej wydajności pozwalają programistom pisać kod w prosty sposób, nie martwiąc się o szybkość.

Staraj się nie optymalizować zbyt wiele z wyprzedzeniem, a kiedy będziesz optymalizować, mniej martw się o czytelność.

Niewiele nienawidzę bardziej niż niepotrzebnej złożoności, ale kiedy napotykasz złożoną sytuację, często wymagane jest złożone rozwiązanie.

Jeśli piszesz kod w najbardziej oczywisty sposób, zrób komentarz wyjaśniający, dlaczego został zmieniony podczas wprowadzania złożonej zmiany.

Jednak konkretnie w twoim znaczeniu, często okazuje się, że robienie logicznego przeciwieństwa domyślnego podejścia czasami pomaga:

for(int i = 0, j = collection.length(); i < j; i++ ){
// stuff here
}

może zostać

for(int i = collection.length(); i > 0; i-=1 ){
// stuff here
}

W wielu językach, o ile wprowadzisz odpowiednie poprawki do części „rzeczy” i jest ona nadal czytelna. Po prostu nie podchodzi do problemu w taki sposób, w jaki większość ludzi pomyślałaby o zrobieniu go najpierw, ponieważ liczy się on wstecz.

na przykład w c #:

        string[] collection = {"a","b"};

        string result = "";

        for (int i = 0, j = collection.Count() - 1; i < j; i++)
        {
            result += collection[i] + "~";
        }

można również zapisać jako:

        for (int i = collection.Count() - 1; i > 0; i -= 1)
        {
            result = collection[i] + "~" + result;
        }

(i tak, powinieneś to zrobić za pomocą joysticka lub konstruktora ciągów, ale próbuję zrobić prosty przykład)

Istnieje wiele innych sztuczek, których można użyć, które nie są trudne do naśladowania, ale wiele z nich nie ma zastosowania we wszystkich językach, takich jak użycie środkowej części po lewej stronie zadania w starym VB, aby uniknąć kary za ponowne przypisanie łańcucha lub czytanie plików tekstowych w trybie binarnym w .net, aby ominąć karę buforowania, gdy plik jest zbyt duży do odczytu.

Jedynym innym bardzo ogólnym przypadkiem, jaki wymyślę, który miałby zastosowanie wszędzie, byłoby zastosowanie algebry boolowskiej do złożonych warunków warunkowych, aby spróbować przekształcić równanie w coś, co ma większą szansę na skorzystanie z warunku zwarcia lub przekształcenie kompleksu zestaw zagnieżdżonych instrukcji if-then lub case w równaniu w całości. Żadne z nich nie działa we wszystkich przypadkach, ale mogą być znaczną oszczędnością czasu.

1. Profil. Czy w ogóle mamy problem? Gdzie?
2. W 90% przypadków, gdy jest to w jakiś sposób związane z IO, zastosuj buforowanie (a może uzyskaj więcej pamięci)
3. Jeśli jest to związane z procesorem, zastosuj buforowanie
4. Jeśli wydajność nadal stanowi problem, opuściliśmy sferę prostych technik - wykonaj matematykę.

Używaj najlepszych dostępnych narzędzi - dobrego kompilatora, dobrego profilera, dobrych bibliotek. Skorzystaj z algorytmów, a najlepiej - użyj odpowiedniej biblioteki, aby zrobić to za Ciebie. Trywialne optymalizacje pętli to małe ziemniaki, a ponadto nie jesteś tak inteligentny jak kompilator optymalizujący.

Najprostszym dla mnie jest użycie stosu, gdy jest to możliwe, ilekroć wspólny wzorzec użycia przypadku pasuje do zakresu, powiedzmy, [0, 64), ale ma rzadkie przypadki, które nie mają małej górnej granicy.

Prosty przykład C (wcześniej):

void some_hotspot_called_in_big_loops(int n, ...)
{
    // 'n' is, 99% of the time, <= 64.
    int* values = calloc(n, sizeof(int));

    // do stuff with values
    ...
    free(values);
}

Oraz po:

void some_hotspot_called_in_big_loops(int n, ...)
{
    // 'n' is, 99% of the time, <= 64.
    int values_mem[64] = {0}
    int* values = (n <= 64) ? values_mem: calloc(n, sizeof(int));

    // do stuff with values
    ...
    if (values != values_mem)
        free(values);
}

Uogólniłem to w ten sposób, ponieważ tego rodzaju hotspoty często pojawiają się w profilowaniu:

void some_hotspot_called_in_big_loops(int n, ...)
{
    // 'n' is, 99% of the time, <= 64.
    MemFast values_mem;
    int* values = mf_calloc(&values_mem, n, sizeof(int));

    // do stuff with values
    ...

    mf_free(&values_mem);
}

Powyższe używa stosu, gdy przydzielane dane są wystarczająco małe w tych 99,9% przypadkach, a stosu używa inaczej.

W C ++ uogólniłem to za pomocą zgodnej ze standardami małej sekwencji (podobnej do SmallVectorimplementacji tam dostępnych), która obraca się wokół tej samej koncepcji.

Nie jest to epicka optymalizacja (otrzymałem redukcje z, powiedzmy, 3 sekund, aby operacja zakończyła się do 1,8 sekundy), ale wymaga tak trywialnego wysiłku. Kiedy możesz obniżyć wartość z 3 do 1,8 sekundy, po prostu wprowadzając wiersz kodu i zmieniając dwa, to całkiem niezły huk jak na tak małą złotówkę.

Istnieje wiele zmian wydajności, które możesz wprowadzić podczas uzyskiwania dostępu do danych, które będą miały ogromny wpływ na twoją aplikację. Jeśli piszesz zapytania lub używasz ORM, aby uzyskać dostęp do bazy danych, musisz przeczytać kilka książek o optymalizacji wydajności dla używanego zaplecza bazy danych. Możliwe, że używasz znanych słabo działających technik. Nie ma powodu, aby to robić, oprócz ignorancji. To nie jest przedwczesna optymalizacja (przeklinam faceta, który to powiedział, ponieważ jest tak szeroko interpretowana, że ​​nigdy nie martwi się wydajnością), to dobry projekt.

Tylko krótka próbka ulepszeń wydajności dla SQL Server: Używaj odpowiednich indeksów, unikaj kursorów - używaj logiki opartej na zestawie, używaj klauzuli sargable gdzie, nie nakładaj widoków na wierzch widoków, nie zwracaj więcej danych niż potrzebujesz lub więcej kolumn, niż potrzebujesz, nie używaj skorelowanych podkwerend.

Jeśli jest to C ++, powinieneś ++iraczej przyzwyczaić się niż i++. ++inigdy nie będzie gorszy, oznacza to dokładnie to samo, co samodzielne oświadczenie, aw niektórych przypadkach może to być poprawa wydajności.

Nie warto zmieniać istniejącego kodu na wszelki wypadek, że to pomoże, ale dobrym nawykiem jest wchodzenie w to.

Mam trochę inne podejście do tego. Samo podążanie za wskazówkami nie zrobi wielkiej różnicy, ponieważ musisz popełnić kilka błędów, które następnie musisz naprawić, z których następnie musisz się nauczyć.

Błąd, który musisz popełnić, polega na zaprojektowaniu struktury danych tak, jak wszyscy. Oznacza to, że z nadmiarowymi danymi i wieloma warstwami abstrakcji, z właściwościami i powiadomieniami, które rozprzestrzeniają się w całej strukturze, starając się zachować spójność.

Następnie musisz przeprowadzić dostrajanie wydajności (profilowanie) i pokazać, że pod wieloma względami koszta cykli kosztują wiele warstw abstrakcji, a właściwości i powiadomienia rozprzestrzeniają się w całej strukturze, starając się zachować spójność.

Możesz być w stanie rozwiązać te problemy nieco bez większych zmian w kodzie.

Następnie, jeśli masz szczęście, możesz dowiedzieć się, że mniejsza struktura danych jest lepsza i że lepiej jest tolerować przejściową niespójność, niż starać się ściśle trzymać wiele rzeczy w zgodzie z falami wiadomości.

Sposób pisania pętli nie ma z tym nic wspólnego.