Kiedy należy zoptymalizować pod kątem pamięci i wydajności wydajność metody?

Niedawno przeprowadziłem wywiad w Amazon. Podczas sesji kodowania ankieter zapytał, dlaczego zadeklarowałem zmienną w metodzie. Wyjaśniłem mój proces, a on wezwał mnie do rozwiązania tego samego problemu przy mniejszej liczbie zmiennych. Na przykład (nie było to z wywiadu), zacząłem od metody A, a następnie ulepszyłem ją do metody B, usuwając ją int s. Był zadowolony i powiedział, że dzięki tej metodzie zmniejszy to zużycie pamięci.

Rozumiem za tym logikę, ale moje pytanie brzmi:

Kiedy należy zastosować metodę A w porównaniu z metodą B i odwrotnie?

Widać, że Metoda A będzie miała większe zużycie pamięci, ponieważ int sjest zadeklarowana, ale musi wykonać tylko jedno obliczenie, tj a + b. Z drugiej strony Metoda B ma mniejsze zużycie pamięci, ale musi wykonać dwa obliczenia, tj a + b. Dwa razy. Kiedy używam jednej techniki na drugiej? Czy może jedna z technik jest zawsze preferowana nad drugą? O czym należy pamiętać przy ocenie tych dwóch metod?

Metoda A:

private bool IsSumInRange(int a, int b)
{
    int s = a + b;

    if (s > 1000 || s < -1000) return false;
    else return true;
}

Metoda B:

private bool IsSumInRange(int a, int b)
{
    if (a + b > 1000 || a + b < -1000) return false;
    else return true;
}

Zamiast spekulować na temat tego, co może się zdarzyć, a co nie, spójrzmy, prawda? Będę musiał użyć C ++, ponieważ nie mam przydatnego kompilatora C # (chociaż zobacz przykład C # z VisualMelon ), ale jestem pewien, że te same zasady obowiązują niezależnie.

Uwzględnimy dwie alternatywy napotkane w wywiadzie. Uwzględnimy również wersję, która używa abszgodnie z sugestiami niektórych odpowiedzi.

#include <cstdlib>

bool IsSumInRangeWithVar(int a, int b)
{
    int s = a + b;

    if (s > 1000 || s < -1000) return false;
    else return true;
}

bool IsSumInRangeWithoutVar(int a, int b)
{
    if (a + b > 1000 || a + b < -1000) return false;
    else return true;
}

bool IsSumInRangeSuperOptimized(int a, int b) {
    return (abs(a + b) < 1000);
}

Teraz skompiluj go bez jakiejkolwiek optymalizacji: g++ -c -o test.o test.cpp

Teraz możemy dokładnie zobaczyć, co to generuje: objdump -d test.o

0000000000000000 <_Z19IsSumInRangeWithVarii>:
   0:   55                      push   %rbp              # begin a call frame
   1:   48 89 e5                mov    %rsp,%rbp
   4:   89 7d ec                mov    %edi,-0x14(%rbp)  # save first argument (a) on stack
   7:   89 75 e8                mov    %esi,-0x18(%rbp)  # save b on stack
   a:   8b 55 ec                mov    -0x14(%rbp),%edx  # load a and b into edx
   d:   8b 45 e8                mov    -0x18(%rbp),%eax  # load b into eax
  10:   01 d0                   add    %edx,%eax         # add a and b
  12:   89 45 fc                mov    %eax,-0x4(%rbp)   # save result as s on stack
  15:   81 7d fc e8 03 00 00    cmpl   $0x3e8,-0x4(%rbp) # compare s to 1000
  1c:   7f 09                   jg     27                # jump to 27 if it's greater
  1e:   81 7d fc 18 fc ff ff    cmpl   $0xfffffc18,-0x4(%rbp) # compare s to -1000
  25:   7d 07                   jge    2e                # jump to 2e if it's greater or equal
  27:   b8 00 00 00 00          mov    $0x0,%eax         # put 0 (false) in eax, which will be the return value
  2c:   eb 05                   jmp    33 <_Z19IsSumInRangeWithVarii+0x33>
  2e:   b8 01 00 00 00          mov    $0x1,%eax         # put 1 (true) in eax
  33:   5d                      pop    %rbp
  34:   c3                      retq

0000000000000035 <_Z22IsSumInRangeWithoutVarii>:
  35:   55                      push   %rbp
  36:   48 89 e5                mov    %rsp,%rbp
  39:   89 7d fc                mov    %edi,-0x4(%rbp)
  3c:   89 75 f8                mov    %esi,-0x8(%rbp)
  3f:   8b 55 fc                mov    -0x4(%rbp),%edx
  42:   8b 45 f8                mov    -0x8(%rbp),%eax  # same as before
  45:   01 d0                   add    %edx,%eax
  # note: unlike other implementation, result is not saved
  47:   3d e8 03 00 00          cmp    $0x3e8,%eax      # compare to 1000
  4c:   7f 0f                   jg     5d <_Z22IsSumInRangeWithoutVarii+0x28>
  4e:   8b 55 fc                mov    -0x4(%rbp),%edx  # since s wasn't saved, load a and b from the stack again
  51:   8b 45 f8                mov    -0x8(%rbp),%eax
  54:   01 d0                   add    %edx,%eax
  56:   3d 18 fc ff ff          cmp    $0xfffffc18,%eax # compare to -1000
  5b:   7d 07                   jge    64 <_Z22IsSumInRangeWithoutVarii+0x2f>
  5d:   b8 00 00 00 00          mov    $0x0,%eax
  62:   eb 05                   jmp    69 <_Z22IsSumInRangeWithoutVarii+0x34>
  64:   b8 01 00 00 00          mov    $0x1,%eax
  69:   5d                      pop    %rbp
  6a:   c3                      retq

000000000000006b <_Z26IsSumInRangeSuperOptimizedii>:
  6b:   55                      push   %rbp
  6c:   48 89 e5                mov    %rsp,%rbp
  6f:   89 7d fc                mov    %edi,-0x4(%rbp)
  72:   89 75 f8                mov    %esi,-0x8(%rbp)
  75:   8b 55 fc                mov    -0x4(%rbp),%edx
  78:   8b 45 f8                mov    -0x8(%rbp),%eax
  7b:   01 d0                   add    %edx,%eax
  7d:   3d 18 fc ff ff          cmp    $0xfffffc18,%eax
  82:   7c 16                   jl     9a <_Z26IsSumInRangeSuperOptimizedii+0x2f>
  84:   8b 55 fc                mov    -0x4(%rbp),%edx
  87:   8b 45 f8                mov    -0x8(%rbp),%eax
  8a:   01 d0                   add    %edx,%eax
  8c:   3d e8 03 00 00          cmp    $0x3e8,%eax
  91:   7f 07                   jg     9a <_Z26IsSumInRangeSuperOptimizedii+0x2f>
  93:   b8 01 00 00 00          mov    $0x1,%eax
  98:   eb 05                   jmp    9f <_Z26IsSumInRangeSuperOptimizedii+0x34>
  9a:   b8 00 00 00 00          mov    $0x0,%eax
  9f:   5d                      pop    %rbp
  a0:   c3                      retq

Widzimy na podstawie adresów stosu (na przykład -0x4in mov %edi,-0x4(%rbp)versus -0x14in mov %edi,-0x14(%rbp)), który IsSumInRangeWithVar()wykorzystuje 16 dodatkowych bajtów na stosie.

Ponieważ IsSumInRangeWithoutVar()nie przydziela miejsca na stosie do przechowywania wartości pośredniej s, musi go ponownie obliczyć, co powoduje, że ta implementacja jest o 2 instrukcje dłuższa.

Zabawne, IsSumInRangeSuperOptimized()wygląda bardzo podobnie IsSumInRangeWithoutVar(), z tym, że najpierw porównuje do -1000 i 1000 sekund.

Teraz skompilować tylko najbardziej podstawowych optymalizacje: g++ -O1 -c -o test.o test.cpp. Wynik:

0000000000000000 <_Z19IsSumInRangeWithVarii>:
   0:   8d 84 37 e8 03 00 00    lea    0x3e8(%rdi,%rsi,1),%eax
   7:   3d d0 07 00 00          cmp    $0x7d0,%eax
   c:   0f 96 c0                setbe  %al
   f:   c3                      retq

0000000000000010 <_Z22IsSumInRangeWithoutVarii>:
  10:   8d 84 37 e8 03 00 00    lea    0x3e8(%rdi,%rsi,1),%eax
  17:   3d d0 07 00 00          cmp    $0x7d0,%eax
  1c:   0f 96 c0                setbe  %al
  1f:   c3                      retq

0000000000000020 <_Z26IsSumInRangeSuperOptimizedii>:
  20:   8d 84 37 e8 03 00 00    lea    0x3e8(%rdi,%rsi,1),%eax
  27:   3d d0 07 00 00          cmp    $0x7d0,%eax
  2c:   0f 96 c0                setbe  %al
  2f:   c3                      retq

Spójrz na to: każdy wariant jest identyczny . Kompilator jest w stanie zrobić coś całkiem sprytnego: abs(a + b) <= 1000jest równoznaczny z a + b + 1000 <= 2000rozważeniem setbewykonania niepodpisanego porównania, więc liczba ujemna staje się bardzo dużą liczbą dodatnią. leaInstrukcja może rzeczywiście wykonać te wszystkie dodatki w jednej instrukcji i wyeliminować wszystkie gałęzie warunkowe.

Aby odpowiedzieć na twoje pytanie, prawie zawsze optymalizacją jest nie pamięć lub szybkość, ale czytelność . Czytanie kodu jest o wiele trudniejsze niż jego pisanie, a czytanie kodu, który został zmodyfikowany w celu „optymalizacji”, jest o wiele trudniejsze niż czytanie kodu, który został napisany dla jasności. Te „optymalizacje” najczęściej są nieistotne lub, jak w tym przypadku, dokładnie zero rzeczywistego wpływu na wydajność.

W odpowiedzi na pytanie, co się zmienia, gdy ten kod jest w języku interpretowanym zamiast kompilowanym? Czy zatem optymalizacja ma znaczenie, czy ma taki sam wynik?

Zmierzmy! Transkrybowałem przykłady do Pythona:

def IsSumInRangeWithVar(a, b):
    s = a + b
    if s > 1000 or s < -1000:
        return False
    else:
        return True

def IsSumInRangeWithoutVar(a, b):
    if a + b > 1000 or a + b < -1000:
        return False
    else:
        return True

def IsSumInRangeSuperOptimized(a, b):
    return abs(a + b) <= 1000

from dis import dis
print('IsSumInRangeWithVar')
dis(IsSumInRangeWithVar)

print('\nIsSumInRangeWithoutVar')
dis(IsSumInRangeWithoutVar)

print('\nIsSumInRangeSuperOptimized')
dis(IsSumInRangeSuperOptimized)

print('\nBenchmarking')
import timeit
print('IsSumInRangeWithVar: %fs' % (min(timeit.repeat(lambda: IsSumInRangeWithVar(42, 42), repeat=50, number=100000)),))
print('IsSumInRangeWithoutVar: %fs' % (min(timeit.repeat(lambda: IsSumInRangeWithoutVar(42, 42), repeat=50, number=100000)),))
print('IsSumInRangeSuperOptimized: %fs' % (min(timeit.repeat(lambda: IsSumInRangeSuperOptimized(42, 42), repeat=50, number=100000)),))

Uruchom z Python 3.5.2, to generuje dane wyjściowe:

IsSumInRangeWithVar
  2           0 LOAD_FAST                0 (a)
              3 LOAD_FAST                1 (b)
              6 BINARY_ADD
              7 STORE_FAST               2 (s)

  3          10 LOAD_FAST                2 (s)
             13 LOAD_CONST               1 (1000)
             16 COMPARE_OP               4 (>)
             19 POP_JUMP_IF_TRUE        34
             22 LOAD_FAST                2 (s)
             25 LOAD_CONST               4 (-1000)
             28 COMPARE_OP               0 (<)
             31 POP_JUMP_IF_FALSE       38

  4     >>   34 LOAD_CONST               2 (False)
             37 RETURN_VALUE

  6     >>   38 LOAD_CONST               3 (True)
             41 RETURN_VALUE
             42 LOAD_CONST               0 (None)
             45 RETURN_VALUE

IsSumInRangeWithoutVar
  9           0 LOAD_FAST                0 (a)
              3 LOAD_FAST                1 (b)
              6 BINARY_ADD
              7 LOAD_CONST               1 (1000)
             10 COMPARE_OP               4 (>)
             13 POP_JUMP_IF_TRUE        32
             16 LOAD_FAST                0 (a)
             19 LOAD_FAST                1 (b)
             22 BINARY_ADD
             23 LOAD_CONST               4 (-1000)
             26 COMPARE_OP               0 (<)
             29 POP_JUMP_IF_FALSE       36

 10     >>   32 LOAD_CONST               2 (False)
             35 RETURN_VALUE

 12     >>   36 LOAD_CONST               3 (True)
             39 RETURN_VALUE
             40 LOAD_CONST               0 (None)
             43 RETURN_VALUE

IsSumInRangeSuperOptimized
 15           0 LOAD_GLOBAL              0 (abs)
              3 LOAD_FAST                0 (a)
              6 LOAD_FAST                1 (b)
              9 BINARY_ADD
             10 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             13 LOAD_CONST               1 (1000)
             16 COMPARE_OP               1 (<=)
             19 RETURN_VALUE

Benchmarking
IsSumInRangeWithVar: 0.019361s
IsSumInRangeWithoutVar: 0.020917s
IsSumInRangeSuperOptimized: 0.020171s

Dezasemblacja w Pythonie nie jest szczególnie interesująca, ponieważ „kompilator” kodu bajtowego nie robi wiele w zakresie optymalizacji.

Wydajność trzech funkcji jest prawie identyczna. Możemy mieć ochotę iść ze IsSumInRangeWithVar()względu na jego krańcowy wzrost prędkości. Chociaż dodam, że próbowałem różnych parametrów timeit, czasem IsSumInRangeSuperOptimized()wychodziło to szybciej, więc podejrzewam, że mogą to być czynniki zewnętrzne odpowiedzialne za różnicę, a nie jakakolwiek istotna zaleta jakiejkolwiek implementacji.

Jeśli jest to naprawdę kod krytyczny pod względem wydajności, interpretowany język jest po prostu bardzo złym wyborem. Uruchamiając ten sam program z pypy, otrzymuję:

IsSumInRangeWithVar: 0.000180s
IsSumInRangeWithoutVar: 0.001175s
IsSumInRangeSuperOptimized: 0.001306s

Samo użycie pypy, które wykorzystuje kompilację JIT w celu wyeliminowania dużej części obciążenia interpretera, przyniosło poprawę wydajności o 1 lub 2 rzędy wielkości. Byłem bardzo zszokowany, widząc, że IsSumInRangeWithVar()jest o rząd wielkości szybszy od innych. Zmieniłem więc kolejność testów porównawczych i uruchomiłem ponownie:

IsSumInRangeSuperOptimized: 0.000191s
IsSumInRangeWithoutVar: 0.001174s
IsSumInRangeWithVar: 0.001265s

Wygląda więc na to, że tak naprawdę to nie implementacja sprawia, że ​​jest szybka, ale kolejność, w jakiej przeprowadzam testy porównawcze!

Chciałbym się w to zagłębić głębiej, bo szczerze mówiąc nie wiem, dlaczego tak się dzieje. Uważam jednak, że o to chodzi: mikrooptymalizacje, takie jak to, czy zadeklarować wartość pośrednią jako zmienną, czy nie, są rzadko istotne. W przypadku interpretowanego języka lub wysoce zoptymalizowanego kompilatora pierwszym celem jest nadal pisanie czystego kodu.

Jeśli konieczna może być dalsza optymalizacja, test porównawczy . Pamiętaj, że najlepsze optymalizacje nie wynikają z drobnych szczegółów, ale z większego obrazu algorytmicznego: pypy będzie o rząd wielkości szybszy do powtarzanej oceny tej samej funkcji niż cpython, ponieważ używa szybszych algorytmów (kompilator JIT vs interpretacja) do oceny program. Jest też kodowany algorytm, który należy wziąć pod uwagę: przeszukiwanie drzewa B będzie szybsze niż połączona lista.

Po upewnieniu się, że używasz odpowiednich narzędzi i algorytmów do pracy, przygotuj się na głębsze zanurzenie się w szczegóły systemu. Wyniki mogą być bardzo zaskakujące, nawet dla doświadczonych programistów, i dlatego musisz mieć wzorzec do oceny zmian.

Aby odpowiedzieć na zadane pytanie:

Kiedy należy zoptymalizować pod kątem pamięci i wydajności wydajność metody?

Musisz ustalić dwie rzeczy:

• Co ogranicza twoją aplikację?
• Gdzie mogę odzyskać większość tego zasobu?

Aby odpowiedzieć na pierwsze pytanie, musisz wiedzieć, jakie są wymagania dotyczące wydajności aplikacji. Jeśli nie ma wymagań dotyczących wydajności, nie ma powodu, aby optymalizować w ten czy inny sposób. Wymagania dotyczące wydajności pomagają dotrzeć do miejsca „wystarczająco dobrego”.

Podana metoda sama w sobie nie spowodowałaby żadnych problemów z wydajnością, ale być może w pętli i przetwarzaniu dużej ilości danych musisz zacząć myśleć nieco inaczej o tym, jak podchodzisz do problemu.

Wykrywanie, co ogranicza aplikację

Zacznij obserwować zachowanie aplikacji za pomocą monitora wydajności. Miej oko na wykorzystanie procesora, dysku, sieci i pamięci podczas pracy. Jeden lub więcej przedmiotów zostanie maksymalnie wykorzystanych, podczas gdy wszystko inne będzie używane w umiarkowanym stopniu - chyba że osiągniesz idealną równowagę, ale to prawie nigdy się nie zdarzy.

Kiedy potrzebujesz głębszego spojrzenia, zwykle używałbyś profilera . Istnieją profilery pamięci i profile procesów , które mierzą różne rzeczy. Akt profilowania ma znaczący wpływ na wydajność, ale instrumentujesz swój kod, aby dowiedzieć się, co jest nie tak.

Załóżmy, że widzisz szczytowe użycie procesora i dysku. Najpierw sprawdziłbyś „hotspoty” lub kod, który jest wywoływany częściej niż reszta lub zajmuje znacznie dłuższy procent przetwarzania.

Jeśli nie możesz znaleźć żadnych gorących punktów, zaczniesz szukać pamięci. Być może tworzysz więcej obiektów, niż jest to konieczne, a twoje operacje usuwania śmieci działają w nadgodzinach.

Odzyskiwanie wydajności

Myśl krytycznie. Poniższa lista zmian jest uporządkowana według wysokości zwrotu z inwestycji:

• Architektura: szukaj dławików komunikacyjnych
• Algorytm: sposób przetwarzania danych może wymagać zmiany
• Hotspoty: zminimalizowanie częstotliwości wywoływania hot spotów może dać duży bonus
• Mikrooptymalizacje: nie jest to powszechne, ale czasami naprawdę musisz pomyśleć o drobnych poprawkach (takich jak podany przez ciebie przykład), szczególnie jeśli jest to punkt krytyczny w kodzie.

W takich sytuacjach musisz zastosować metodę naukową. Wymyśl hipotezę, wprowadź zmiany i przetestuj ją. Jeśli osiągniesz swoje cele wydajnościowe, gotowe. Jeśli nie, przejdź do następnej rzeczy na liście.

Odpowiedzi na pogrubione pytanie:

Kiedy należy zastosować metodę A w porównaniu z metodą B i odwrotnie?

Szczerze mówiąc, jest to ostatni krok w próbie radzenia sobie z problemami z wydajnością lub pamięcią. Wpływ metody A na metodę B będzie naprawdę różny w zależności od języka i platformy (w niektórych przypadkach).

Prawie każdy skompilowany język z optymalizatorem w połowie drogi wygeneruje podobny kod z jedną z tych struktur. Jednak te założenia niekoniecznie pozostają prawdziwe w językach zastrzeżonych i zabawkowych, które nie mają optymalizatora.

Dokładnie to, co będzie miało lepszy wpływ, zależy od tego, czy sumjest to zmienna stosu, czy zmienna stosu. Jest to wybór implementacji języka. Na przykład w C, C ++ i Javie prymitywy liczbowe takie jak an intsą domyślnie zmiennymi stosowymi. Twój kod nie ma większego wpływu na pamięć, przypisując do zmiennej stosu, niż w przypadku kodu w pełni wbudowanego.

Inne optymalizacje, które możesz znaleźć w bibliotekach C (szczególnie starszych), w których możesz zdecydować, czy najpierw skopiować dwuwymiarową tablicę w dół, czy w poprzek, to optymalizacja zależna od platformy. Wymaga to pewnej wiedzy o tym, w jaki sposób chipset, na który celujesz, najlepiej optymalizuje dostęp do pamięci. Istnieją subtelne różnice między architekturami.

Podsumowując, optymalizacja to połączenie sztuki i nauki. Wymaga to krytycznego myślenia, a także pewnej elastyczności w podejściu do problemu. Szukaj wielkich rzeczy, zanim obwinisz małe rzeczy.

„to zmniejszyłoby pamięć” - em, nie. Nawet jeśli byłoby to prawdą (czego nie jest w żadnym przyzwoitym kompilatorze), różnica najprawdopodobniej byłaby nieistotna dla każdej rzeczywistej sytuacji na świecie.

Jednak zaleciłbym użycie metody A * (metoda A z niewielką zmianą):

private bool IsSumInRange(int a, int b)
{
    int sum = a + b;

    if (sum > 1000 || sum < -1000) return false;
    else return true;
    // (yes, the former statement could be cleaned up to
    // return abs(sum)<=1000;
    // but let's ignore this for a moment)
}

ale z dwóch zupełnie różnych powodów:

• poprzez nadanie zmiennej snazwy wyjaśniającej kod staje się wyraźniejszy

• unika podwójnej logiki sumowania w kodzie, więc kod staje się bardziej SUCHY, co oznacza mniej podatności na zmiany.

Możesz zrobić to lepiej niż oba

return (abs(a + b) > 1000);

Większość procesorów (a więc i kompilatorów) może wykonać abs () w jednej operacji. Masz nie tylko mniej sum, ale także mniej porównań, które są generalnie droższe obliczeniowo. Usuwa również rozgałęzienia, co jest znacznie gorsze w większości procesorów, ponieważ uniemożliwia tworzenie potoków.

Ankieter, jak powiedziano w innych odpowiedziach, żyje roślinami i nie prowadzi działalności w celu przeprowadzenia wywiadu technicznego.

To powiedziawszy, jego pytanie jest ważne. Odpowiedzią na optymalizację i sposób jest to, kiedy udowodniłeś, że jest to konieczne, i profilowałeś ją, aby dokładnie udowodnić, które części tego potrzebują . Knuth słynie, że przedwczesna optymalizacja jest źródłem wszelkiego zła, ponieważ zbyt łatwo jest próbować pozłacać nieistotne sekcje lub wprowadzać zmian (jak twój ankieter), które nie przynoszą efektu, a jednocześnie brakuje miejsc, które naprawdę tego potrzebują. Dopóki nie otrzymasz twardego dowodu, jest to naprawdę konieczne, najważniejszym celem jest przejrzystość kodu.

Edytuj FabioTurati poprawnie wskazuje, że jest to logika przeciwna do oryginału (mój błąd!), I że ilustruje to dalszy wpływ cytatu Knutha, w którym ryzykujemy złamanie kodu podczas próby jego optymalizacji.

Kiedy należy zastosować metodę A w porównaniu z metodą B i odwrotnie?

Sprzęt jest tani; programiści są kosztowni . Koszt czasu, jaki wy dwaj zmarnowaliście na to pytanie, jest prawdopodobnie znacznie gorszy niż którakolwiek z odpowiedzi.

Niezależnie od tego większość współczesnych kompilatorów znalazłaby sposób na zoptymalizowanie zmiennej lokalnej w rejestrze (zamiast przydzielania miejsca na stosie), więc metody są prawdopodobnie identyczne pod względem kodu wykonywalnego. Z tego powodu większość programistów wybrałaby opcję, która najlepiej komunikuje zamiar (zobacz Pisanie naprawdę oczywistego kodu (ROC) ). Moim zdaniem byłaby to Metoda A.

Z drugiej strony, jeśli jest to ćwiczenie czysto akademickie, możesz mieć to, co najlepsze z obu światów dzięki Metodzie C:

private bool IsSumInRange(int a, int b)
{
    a += b;
    return (a >= -1000 && a <= 1000);
}

Zoptymalizowałbym czytelność. Metoda X:

private bool IsSumInRange(int number1, int number2)
{
    return IsValueInRange(number1+number2, -1000, 1000);
}

private bool IsValueInRange(int Value, int Lowerbound, int Upperbound)
{
    return  (Value >= Lowerbound && Value <= Upperbound);
}

Małe metody, które robią tylko jedną rzecz, ale są łatwe do uzasadnienia.

(To jest osobista preferencja, lubię pozytywne testy zamiast negatywnych, twój oryginalny kod faktycznie sprawdza, czy wartość NIE jest poza zakresem).

Krótko mówiąc, nie sądzę, aby pytanie miało duże znaczenie w bieżącym przetwarzaniu, ale z historycznego punktu widzenia jest to interesujące ćwiczenie.

Twój ankieter prawdopodobnie jest fanem Miesiąca Mitycznego Człowieka. W książce Fred Brooks twierdzi, że programiści będą na ogół potrzebować dwóch wersji kluczowych funkcji w swoim zestawie narzędzi: wersji zoptymalizowanej pod kątem pamięci i wersji zoptymalizowanej pod kątem procesora. Fred oparł to na swoim doświadczeniu, kierując rozwojem systemu operacyjnego IBM System / 360, w którym maszyny mogą mieć zaledwie 8 kilobajtów pamięci RAM. W takich maszynach pamięć wymagana dla zmiennych lokalnych w funkcjach może być potencjalnie ważna, szczególnie jeśli kompilator nie zoptymalizuje ich skutecznie (lub jeśli kod został napisany bezpośrednio w języku asemblera).

Myślę, że w obecnej erze trudno byłoby znaleźć system, w którym obecność lub brak zmiennej lokalnej w metodzie miałby zauważalną różnicę. Aby zmienna miała znaczenie, metoda musiałaby być rekurencyjna z oczekiwaną głęboką rekurencją. Nawet wtedy prawdopodobne jest, że głębokość stosu zostanie przekroczona, co spowoduje wyjątki przepełnienia stosu, zanim sama zmienna spowoduje problem. Jedynym prawdziwym scenariuszem, w którym może to być problem, są bardzo duże tablice alokowane na stosie metodą rekurencyjną. Jest to jednak mało prawdopodobne, ponieważ myślę, że większość programistów pomyślałaby dwa razy o niepotrzebnych kopiach dużych tablic.

Po przypisaniu s = a + b; zmienne a i b nie są już używane. Dlatego nie używa się pamięci dla s, jeśli nie używasz kompilatora całkowicie uszkodzonego przez mózg; pamięć, która i tak została użyta dla aib, jest ponownie używana.

Ale optymalizacja tej funkcji jest kompletnym nonsensem. Gdybyś mógł zaoszczędzić miejsce, byłoby to może 8 bajtów podczas działania funkcji (która jest odzyskiwana, gdy funkcja powraca), więc absolutnie bez sensu. Gdybyś mógł zaoszczędzić czas, byłaby to pojedyncza liczba nanosekund. Optymalizacja tego to całkowita strata czasu.

Zmienne typu wartości lokalnych są przydzielane na stosie lub (bardziej prawdopodobne dla takich małych fragmentów kodu) używają rejestrów w procesorze i nigdy nie widzą żadnej pamięci RAM. Tak czy inaczej, są krótkotrwałe i nie mają się czym martwić. Zaczynasz rozważać użycie pamięci, gdy potrzebujesz buforować lub umieszczać w kolejce elementy danych w kolekcjach, które są potencjalnie duże i długo żyją.

To zależy od tego, co najbardziej zależy Ci na aplikacji. Szybkość przetwarzania? Czas odpowiedzi? Ślad pamięci? Konserwowalność? Spójność w projektowaniu? Wszystko zależy od Ciebie.

Jak już powiedzieli inne odpowiedzi, musisz pomyśleć o tym, co optymalizujesz.

W tym przykładzie podejrzewam, że każdy przyzwoity kompilator wygenerowałby równoważny kod dla obu metod, więc decyzja nie miałaby wpływu na czas działania ani pamięć!

Co to ma wpłynąć na to czytelność kodu. (Kod jest przeznaczony do czytania przez ludzi, nie tylko komputery). Nie ma zbyt dużej różnicy między tymi dwoma przykładami; kiedy wszystkie inne rzeczy są równe, uważam zwięzłość za cnotę, więc prawdopodobnie wybrałbym Metodę B. Ale wszystkie inne rzeczy rzadko są równe, aw bardziej złożonym przypadku w świecie rzeczywistym może to mieć duży efekt.

Rzeczy do rozważenia:

• Czy wyrażenie pośrednie ma jakieś skutki uboczne? Jeśli wywoła jakieś nieczyste funkcje lub zaktualizuje dowolne zmienne, to oczywiście powielenie tego byłoby kwestią poprawności, a nie tylko stylu.
• Jak złożone jest wyrażenie pośrednie? Jeśli wykonuje wiele obliczeń i / lub wywołuje funkcje, kompilator może nie być w stanie go zoptymalizować, a to wpłynęłoby na wydajność. (Chociaż, jak powiedział Knuth , „Powinniśmy zapomnieć o małej wydajności, powiedzmy, że w około 97% przypadków”).
• Czy zmienna pośrednia ma jakieś znaczenie ? Czy można mu nadać nazwę, która pomoże wyjaśnić, co się dzieje? Krótka, ale pouczająca nazwa mogłaby lepiej wyjaśnić kod, podczas gdy bez znaczenia jest jedynie wizualny szum.
• Jak długie jest wyrażenie pośrednie? Jeśli jest długi, to powielenie go może spowodować, że kod będzie dłuższy i trudniejszy do odczytania (zwłaszcza jeśli wymusza podział linii); jeśli nie, duplikacja może być krótsza.

Jak wskazało wiele odpowiedzi, próba dostrojenia tej funkcji za pomocą nowoczesnych kompilatorów nie zrobi żadnej różnicy. Optymalizator najprawdopodobniej może znaleźć najlepsze rozwiązanie (głosuj na odpowiedź, która pokazała kod asemblera, aby to udowodnić!). Stwierdziłeś, że kod w wywiadzie nie był dokładnie kodem, o który poproszono cię do porównania, więc być może faktyczny przykład ma trochę więcej sensu.

Ale spójrzmy jeszcze raz na to pytanie: jest to pytanie do wywiadu. Prawdziwy problem polega na tym, jak odpowiedzieć na to pytanie, zakładając, że chcesz spróbować znaleźć pracę?

Załóżmy również, że osoba przeprowadzająca wywiad wie, o czym mówi, i po prostu próbuje zobaczyć, co wiesz.

Wspomnę, że ignorując optymalizator, pierwszy może utworzyć tymczasową zmienną na stosie, podczas gdy drugi nie, ale wykona obliczenia dwukrotnie. Dlatego pierwszy zużywa więcej pamięci, ale jest szybszy.

Można wspomnieć, że tak czy inaczej, obliczenia mogą wymagać zmiennej tymczasowej do przechowywania wyniku (w celu porównania), więc niezależnie od tego, czy nazwiesz tę zmienną, czy nie, nie będzie to miało znaczenia.

Wspomniałbym wtedy, że w rzeczywistości kod zostałby zoptymalizowany i najprawdopodobniej wygenerowany zostałby równoważny kod maszynowy, ponieważ wszystkie zmienne są lokalne. Zależy to jednak od używanego kompilatora (nie tak dawno temu mogłem uzyskać użyteczną poprawę wydajności, deklarując zmienną lokalną jako „końcową” w Javie).

Można wspomnieć, że stos w każdym przypadku znajduje się na swojej własnej stronie pamięci, więc jeśli twoja dodatkowa zmienna nie spowodowała przepełnienia strony, w rzeczywistości nie przydzieli więcej pamięci. Jeśli jednak się przepełni, będzie potrzebować zupełnie nowej strony.

Chciałbym wspomnieć, że bardziej realistycznym przykładem może być wybór, czy użyć pamięci podręcznej do przechowywania wyników wielu obliczeń, czy nie, i to spowodowałoby pytanie o wydajność procesora kontra pamięć.

Wszystko to pokazuje, że wiesz o czym mówisz.

Pozostawiłbym do końca stwierdzenie, że zamiast tego lepiej skupić się na czytelności. Chociaż w tym przypadku jest to prawda, w kontekście wywiadu może być interpretowane jako „Nie wiem o wydajności, ale mój kod brzmi jak historia Janet i John ”.

To, czego nie powinieneś robić, to wypróbować zwykłe nijakie stwierdzenia o tym, jak optymalizacja kodu nie jest konieczna, nie optymalizuj, dopóki nie wyprofilujesz kodu (to tylko oznacza, że ​​nie widzisz złego kodu dla siebie), sprzęt kosztuje mniej niż programiści i proszę, proszę, nie cytuj Knutha „przedwczesnego bla bla ...”.

Wydajność kodu jest prawdziwym problemem w wielu organizacjach i wiele organizacji potrzebuje programistów, którzy to rozumieją.

W szczególności w przypadku organizacji takich jak Amazon część kodu ma ogromny wpływ. Fragment kodu może zostać wdrożony na tysiącach serwerów lub milionach urządzeń i może być nazywany miliardami razy dziennie każdego dnia w roku. Mogą istnieć tysiące podobnych fragmentów. Różnica między złym a dobrym algorytmem może łatwo być równa tysiącowi. Zrób liczby i pomnóż to wszystko: to robi różnicę. Potencjalny koszt organizacji kodu niedziałającego może być bardzo znaczący, a nawet śmiertelny, jeśli w systemie zabraknie pojemności.

Ponadto wiele z tych organizacji działa w środowisku konkurencyjnym. Nie możesz więc po prostu powiedzieć swoim klientom, aby kupili większy komputer, jeśli oprogramowanie konkurencji działa już dobrze na posiadanym sprzęcie lub jeśli oprogramowanie działa na telefonie komórkowym i nie można go zaktualizować. Niektóre aplikacje mają szczególne znaczenie dla wydajności (przychodzą mi na myśl gry i aplikacje mobilne) i mogą żyć lub umrzeć w zależności od ich szybkości reakcji lub szybkości.

Przez ponad dwie dekady osobiście pracowałem nad wieloma projektami, w których systemy uległy awarii lub były niezdatne do użytku z powodu problemów z wydajnością. Zostałem wezwany do optymalizacji tych systemów i we wszystkich przypadkach było to spowodowane złym kodem napisanym przez programistów, którzy nie rozumieli wpływ tego, co pisali. Co więcej, nigdy nie jest to jeden fragment kodu, zawsze jest wszędzie. Kiedy się pojawię, jest już za późno, aby zacząć myśleć o wydajności: szkody zostały wyrządzone.

Zrozumienie wydajności kodu jest dobrą umiejętnością, podobnie jak rozumienie poprawności i stylu kodu. To wychodzi z praktyki. Awarie wydajności mogą być równie złe, co awarie funkcjonalne. Jeśli system nie działa, to nie działa. Nie ważne dlaczego. Podobnie, wydajność i funkcje, które nigdy nie są używane, są złe.

Tak więc, jeśli ankieter zapyta cię o wyniki, zaleciłbym spróbowanie wykazania jak największej wiedzy. Jeśli pytanie wydaje się złe, uprzejmie zwróć uwagę, dlaczego Twoim zdaniem nie byłoby problemu w takim przypadku. Nie cytuj Knutha.

Najpierw powinieneś zoptymalizować poprawność.

Funkcja nie działa dla wartości wejściowych zbliżonych do Int.MaxValue:

int a = int.MaxValue - 200;
int b = int.MaxValue - 200;
bool inRange = test.IsSumInRangeA(a, b);

Zwraca wartość true, ponieważ suma przepełnia się do -400. Ta funkcja również nie działa dla a = int.MinValue + 200. (niepoprawnie sumuje się do „400”)

Nie będziemy wiedzieć, czego szukał ankieter, chyba że on lub ona wejdzie, ale „przepełnienie jest prawdziwe” .

W trakcie rozmowy zadawaj pytania, aby wyjaśnić zakres problemu: Jakie są dozwolone maksymalne i minimalne wartości wejściowe? Gdy już je masz, możesz zgłosić wyjątek, jeśli osoba dzwoniąca prześle wartości spoza zakresu. Lub (w języku C #) możesz użyć zaznaczonej sekcji {}, która wygenerowałaby wyjątek przy przepełnieniu. Tak, jest to więcej pracy i skomplikowane, ale czasem to wystarczy.

Twoje pytanie powinno brzmieć: „Czy w ogóle muszę to optymalizować?”.

Wersja A i B różnią się jednym ważnym szczegółem, który sprawia, że ​​A jest preferowane, ale nie ma to związku z optymalizacją: Nie powtarzasz kodu.

Rzeczywista „optymalizacja” nazywa się wspólną eliminacją podwyrażeń, co robi właściwie każdy kompilator. Niektórzy dokonują tej podstawowej optymalizacji, nawet gdy optymalizacje są wyłączone. To nie jest tak naprawdę optymalizacja (wygenerowany kod prawie na pewno będzie dokładnie taki sam w każdym przypadku).

Ale jeśli nie jest to optymalizacja, to dlaczego jest lepsza? W porządku, nie powtarzasz kodu, kogo to obchodzi!

Po pierwsze, nie ma ryzyka, że ​​przypadkowo pomylisz się z połową klauzuli warunkowej. Ale co ważniejsze, ktoś czytający ten kod może od razu sprawdzić, co próbujesz zrobić, zamiast if((((wtf||is||this||longexpression))))doświadczenia. To, co czytelnik zobaczy if(one || theother), to dobra rzecz. Nierzadko zdarza mi się, że jesteś tą inną osobą, która trzy lata później czyta twój kod i myśli „WTF to znaczy?”. W takim przypadku zawsze pomocne jest, jeśli Twój kod natychmiast komunikuje zamiar. Tak jest w przypadku wspólnego nazwania podwyrażeń.
Ponadto, jeśli w dowolnym momencie w przyszłości, na przykład zdecydować, że trzeba zmienić a+bsię a-b, trzeba zmienić jednąlokalizacja, nie dwa. I nie ma ryzyka (ponownego) popełnienia błędu przez przypadek drugiego.

Jeśli chodzi o twoje aktualne pytanie, co powinieneś zoptymalizować, przede wszystkim kod powinien być poprawny . To jest absolutnie najważniejsza rzecz. Kod, który nie jest poprawny, jest złym kodem, nawet więcej, nawet jeśli jest niepoprawny, „działa dobrze” lub przynajmniej wygląda na to, że działa dobrze. Następnie kod powinien być czytelny (czytelny dla kogoś, kto go nie zna).
Jeśli chodzi o optymalizację ... z pewnością nie należy celowo pisać kodu antyoptymalizowanego, a na pewno nie mówię, że nie powinieneś zastanawiać się nad projektem przed rozpoczęciem (np. Wybierając odpowiedni algorytm dla problemu, nie najmniej wydajny).

Ale w większości aplikacji wydajność uzyskiwana po uruchomieniu poprawnego, czytelnego kodu przy użyciu rozsądnego algorytmu za pomocą optymalizującego kompilatora jest w porządku, nie trzeba się martwić.

Jeśli tak nie jest, tj. Jeśli wydajność aplikacji rzeczywiście nie spełnia wymagań, i tylko wtedy powinieneś się martwić robieniem takich lokalnych optymalizacji, jak te, które próbowałeś. Najlepiej byłoby jednak ponownie rozważyć algorytm najwyższego poziomu. Jeśli wywołujesz funkcję 500 razy zamiast 50 000 razy z powodu lepszego algorytmu, ma to większy wpływ niż oszczędzanie trzech cykli zegara na mikrooptymalizacji. Jeśli nie utkniesz w martwym punkcie przez kilkaset cykli przez cały czas, ma to większy wpływ niż wykonanie kilku dodatkowych tanich obliczeń itp.

Optymalizacja jest trudną sprawą (możesz napisać o tym całe książki i nie mieć końca), a spędzanie czasu na ślepej optymalizacji jakiegoś konkretnego miejsca (nawet nie wiedząc, czy to w ogóle jest wąskie gardło!) To zwykle zmarnowany czas. Bez profilowania bardzo trudno jest uzyskać optymalizację.

Ale jako ogólną zasadę, gdy latasz w ciemno i po prostu potrzebujesz / chcesz coś zrobić , lub jako ogólną domyślną strategię, sugerowałbym optymalizację pod kątem „pamięci”.
Optymalizacja pod kątem „pamięci” (w szczególności lokalizacji przestrzennej i wzorców dostępu) zwykle przynosi korzyść, ponieważ w przeciwieństwie do dawnych czasów, kiedy wszystko było „trochę takie samo”, obecnie dostęp do pamięci RAM należy do najdroższych (brak odczytu z dysku!) co w zasadzie możesz zrobić. Natomiast ALU jest tanie i z każdym tygodniem robi się coraz szybsze. Przepustowość pamięci i opóźnienie nie poprawiają się tak szybko. Dobra lokalizacja i dobre wzorce dostępu mogą z łatwością zrobić 5-krotną różnicę (20-krotnie w skrajnych, sprzecznych przykładach) w środowisku wykonawczym w porównaniu ze złymi wzorcami dostępu w aplikacjach wymagających dużej ilości danych. Bądź miły dla swoich skrzynek, a będziesz szczęśliwym człowiekiem.

Aby umieścić poprzedni akapit w perspektywie, zastanów się, ile kosztują różne rzeczy, które możesz zrobić. Wykonanie czegoś takiego jak a+bzajmuje (jeśli nie jest zoptymalizowane) jeden lub dwa cykle, ale procesor zwykle może uruchomić kilka instrukcji na cykl i może przetwarzać instrukcje niezależne, więc bardziej realistycznie kosztuje tylko około pół cyklu lub mniej. Idealnie, jeśli kompilator jest dobry w planowaniu, a w zależności od sytuacji może kosztować zero.
Pobieranie danych („pamięci”) kosztuje albo 4-5 cykli, jeśli masz szczęście i jest w L1, i około 15 cykli, jeśli nie masz szczęścia (trafienie L2). Jeśli danych w ogóle nie ma w pamięci podręcznej, zajmuje to kilkaset cykli. Jeśli przypadkowy wzorzec dostępu przekracza możliwości TLB (łatwe do zrobienia tylko ~ 50 wpisów), dodaj kolejne kilkaset cykli. Jeśli przypadkowy wzorzec dostępu faktycznie powoduje błąd strony, w najlepszym przypadku kosztuje Cię kilka tysięcy cykli, a najgorszy kilka milionów.
Zastanów się teraz, czego pilnie chcesz uniknąć?

Kiedy należy zoptymalizować pod kątem pamięci i wydajności wydajność metody?

Po uzyskaniu funkcjonalności prawo pierwszy . Następnie selektywność dotyczą siebie z mikro optymalizacje.

Jako pytanie wywiadu dotyczące optymalizacji, kod wywołuje zwykłą dyskusję, ale nie spełnia celu wyższego poziomu Czy kod jest funkcjonalnie poprawny?

Zarówno C ++, C i inni uważają intprzepełnienie za problem z a + b. Nie jest dobrze zdefiniowane, a C nazywa to zachowaniem niezdefiniowanym . Nie jest określane jako „zawijanie” - nawet jeśli jest to powszechne zachowanie.

bool IsSumInRange(int a, int b) {
    int s = a + b;  // Overflow possible
    if (s > 1000 || s < -1000) return false;
    else return true;
}

IsSumInRange()Oczekuje się, że taka wywołana funkcja będzie dobrze zdefiniowana i działać poprawnie dla wszystkich intwartości a,b. Surowiec a + bnie jest. Rozwiązanie AC może wykorzystywać:

#define N 1000
bool IsSumInRange_FullRange(int a, int b) {
  if (a >= 0) {
    if (b > INT_MAX - a) return false;
  } else {
    if (b < INT_MIN - a) return false;
  }
  int sum = a + b;
  if (sum > N || sum < -N) return false;
  else return true;
}

Powyższy kod może być optymalizowane przy użyciu większej niż całkowita typu int, o ile są dostępne, tak jak poniżej lub dystrybucją sum > N, sum < -Ntesty w if (a >= 0)logice. Jednak takie optymalizacje mogą nie prowadzić do „szybszego” emitowanego kodu, biorąc pod uwagę inteligentny kompilator, ani nie powinny być warte dodatkowej konserwacji, ponieważ są sprytne.

  long long sum a;
  sum += b;

Nawet używanie abs(sum)jest podatne na problemy, kiedy sum == INT_MIN.

O jakich kompilatorach mówimy i jakiego rodzaju „pamięci”? Ponieważ w twoim przykładzie, zakładając rozsądny optymalizator, wyrażenie a+bmusi być ogólnie przechowywane w rejestrze (formie pamięci) przed wykonaniem takiej arytmetyki.

Więc jeśli mówimy o głupim kompilatorze, który napotyka a+bdwa razy, przydzieli więcej rejestrów (pamięci) w drugim przykładzie, ponieważ twój pierwszy przykład może po prostu zapisać to wyrażenie raz w jednym rejestrze odwzorowanym na zmienną lokalną, ale my mówimy o bardzo głupich kompilatorach w tym momencie ... chyba że pracujesz z innym typem głupich kompilatorów, które stosy rozlewają każdą zmienną w każdym miejscu, w takim przypadku być może pierwszy z nich spowodowałby więcej żalu do optymalizacji niż drugi*.

Nadal chcę to podrapać i sądzę, że drugi prawdopodobnie zużyje więcej pamięci z głupim kompilatorem, nawet jeśli jest podatny na gromadzenie wycieków, ponieważ może to skończyć przydzieleniem trzech rejestrów dla a+bi rozlewania ai bwięcej. Jeśli mówimy o najbardziej prymitywnym optymalizatorze, wówczas przechwycenie a+bgo sprawdopodobnie „pomoże” zużywać mniej rejestrów / stosów.

Wszystko to jest wyjątkowo spekulacyjne w dość głupiutki sposób przy braku pomiarów / dezasemblacji, a nawet w najgorszych przypadkach nie jest to przypadek „pamięć kontra wydajność” (ponieważ nawet wśród najgorszych optymalizatorów, o których myślę, nie rozmawiamy o czymkolwiek innym niż pamięć tymczasowa, taka jak stos / rejestr), jest to co najwyżej przypadek „wydajnościowy”, a wśród każdego rozsądnego optymalizatora oba są równoważne, a jeśli ktoś nie używa rozsądnego optymalizatora, dlaczego obsesja na punkcie optymalizacji o tak mikroskopijnym charakterze i szczególnie nieobecne pomiary? To jak selekcja instrukcji / alokacja rejestru, skupienie się na poziomie zespołu, którego nigdy nie spodziewałbym się, że ktokolwiek chce pozostać produktywny, gdy używa się, powiedzmy, interpretera, który gromadzi wszystko.

Kiedy należy zoptymalizować pod kątem pamięci i wydajności wydajność metody?

Jeśli chodzi o to pytanie, jeśli mogę poradzić sobie z nim szerzej, często nie uważam, że oba diametralnie się przeciwstawiają. Zwłaszcza jeśli wzorce dostępu są sekwencyjne, a biorąc pod uwagę szybkość pamięci podręcznej procesora, często zmniejszenie liczby bajtów przetwarzanych sekwencyjnie dla niebanalnych danych wejściowych przekłada się (nawet o jeden punkt) na szybsze przeszukiwanie tych danych. Oczywiście istnieją punkty krytyczne, w których jeśli dane są znacznie, znacznie mniejsze w zamian za sposób, znacznie więcej instrukcji, szybsze przetwarzanie może być sekwencyjne w większej formie w zamian za mniej instrukcji.

Ale zauważyłem, że wielu deweloperów ma tendencję do niedoceniania, jak bardzo zmniejszenie zużycia pamięci w tego typu przypadkach może przełożyć się na proporcjonalne skrócenie czasu przetwarzania. Bardzo ludzko intuicyjnie jest przekładanie kosztów wydajności na instrukcje zamiast dostępu do pamięci do punktu sięgania po duże LUT w jakiejś próżnej próbie przyspieszenia niektórych małych obliczeń, tylko po to, aby stwierdzić obniżenie wydajności przy dodatkowym dostępie do pamięci.

W przypadku przypadków sekwencyjnego dostępu przez jakąś ogromną tablicę (nie mówiąc o lokalnych zmiennych skalarnych, jak w twoim przykładzie), stosuję zasadę, że mniej pamięci do sekwencyjnego przeszukiwania przekłada się na większą wydajność, szczególnie gdy wynikowy kod jest prostszy niż w innym przypadku, dopóki nie dopóki moje pomiary i profiler nie powiedzą mi inaczej, i to ma znaczenie, w ten sam sposób zakładam, że sekwencyjny odczyt mniejszego pliku binarnego na dysku byłby szybszy do przeszukania niż większy (nawet jeśli mniejszy wymaga więcej instrukcji ), dopóki nie zostanie wykazane, że założenie to nie ma zastosowania w moich pomiarach.