Wydajność Delphi: Case Versus If If

Question

Domyślam się, że mogą wystąpić pewne nakładanie się z poprzednimi pytaniami SO, ale nie mogłem znaleźć pytania specyficznego dla Delphi na ten temat.

Załóżmy, że chcesz sprawdzić, czy niepodpisana 32-bitowa zmienna całkowita "MojaAkcja" jest równa którejkolwiek ze stałych ACTION1, ACTION2, ..., ACTIONn, gdzie n to - powiedzmy 1000. Zgaduję, że oprócz jest bardziej elegancki,

case MyAction of 
    ACTION1: {code}; 
    ACTION2: {code}; 
    ... 
    ACTIONn: {code}; 
end; 

jest znacznie szybsze niż

if MyAction = ACTION1 then 
    // code 
else if MyAction = ACTION2 then 
    // code 
... 
else if MyAction = ACTIONn then 
    // code; 

myślę, że jeśli wariant wymaga czasu o (n), aby zakończyć (tj znaleźć odpowiednią akcję), jeżeli właściwe działanie ACTIONi ma wysoka wartość i, podczas gdy wariant przypadku zajmuje dużo mniej czasu (O (1)?).

1. Czy mam rację, że przełącznik jest znacznie szybszy?
2. Czy mam rację, że czas wymagany do znalezienia właściwego działania w obudowie przełącznika rzeczywiście jest niezależny od n? To znaczy. Czy to prawda, że ​​nie trzeba już dłużej sprawdzać miliona przypadków, niż sprawdzać 10 przypadków?
3. Jak dokładnie to działa?

Answer 1

1. Tak przełącznik O (1), podczas gdy w kaskadzie, gdy są wy (n)
2. tak, patrz (1)
3. Z branch table

Answer 2

zauważyć, że jeżeli wartość MyAction jest ważona, dobrą wydajność można uzyskać przy kaskadowaniu, jeśli ... else, gdzie umieszczasz najbardziej prawdopodobne przypadki w pobliżu góry. Nie twierdzę, że będzie konkurować z instrukcją case/switch pod względem wydajności, gdy mamy do czynienia z liczbami całkowitymi. Ale jeśli przypadek nie jest odpowiedni (załóżmy, że masz na przykład łańcuchy), umieść wysokie testy procentowe u góry.

Answer 3

Zawsze dobrze jest najpierw sprawdzić rzeczywistość ...

kompilator Delphi 2010 wydaje się jak test i-oddział partii. Na przykład poniższy prosty kod nie jest wkompilowany w tabelę oddziału.

var 
    c: (aaa, bbb, ccc); 

begin 
    case c of 
    aaa: sleep(0); 
    bbb: sleep(0); 
    ccc: sleep(0); 
    end; 
end. 

kompilator wygeneruje następujący kod:

Project56.dpr.24: case c of 
0040A1C4 0FB6053C0E4100 movzx eax,[$00410e3c] 
0040A1CB 2C01    sub al,$01 
0040A1CD 7208    jb $0040a1d7 
0040A1CF 740F    jz $0040a1e0 
0040A1D1 FEC8    dec al 
0040A1D3 7414    jz $0040a1e9 
0040A1D5 EB19    jmp $0040a1f0 
Project56.dpr.25: aaa: sleep(0); 
0040A1D7 6A00    push $00 
0040A1D9 E86EDAFFFF  call Sleep 
0040A1DE EB10    jmp $0040a1f0 
Project56.dpr.26: bbb: sleep(0); 
0040A1E0 6A00    push $00 
0040A1E2 E865DAFFFF  call Sleep 
0040A1E7 EB07    jmp $0040a1f0 
Project56.dpr.27: ccc: sleep(0); 
0040A1E9 6A00    push $00 
0040A1EB E85CDAFFFF  call Sleep 

jeszcze bardziej skomplikowane przypadki będą się zebrane w serii prób i skakać. Na przykład ...

var 
    c: (aaa, bbb, ccc, eee, fff, ggg, hhh); 

begin 
    case c of 
    aaa: sleep(0); 
    bbb: sleep(0); 
    ccc: sleep(0); 
    hhh: sleep(0); 
    end; 
end. 

... jest kompilowany do ...

Project56.dpr.24: case c of 
0040A1C4 0FB6053C0E4100 movzx eax,[$00410e3c] 
0040A1CB 2C01    sub al,$01 
0040A1CD 720C    jb $0040a1db 
0040A1CF 7413    jz $0040a1e4 
0040A1D1 FEC8    dec al 
0040A1D3 7418    jz $0040a1ed 
0040A1D5 2C04    sub al,$04 
0040A1D7 741D    jz $0040a1f6 
0040A1D9 EB22    jmp $0040a1fd 
Project56.dpr.25: aaa: sleep(0); 
0040A1DB 6A00    push $00 
0040A1DD E86ADAFFFF  call Sleep 
0040A1E2 EB19    jmp $0040a1fd 
Project56.dpr.26: bbb: sleep(0); 
0040A1E4 6A00    push $00 
0040A1E6 E861DAFFFF  call Sleep 
0040A1EB EB10    jmp $0040a1fd 
Project56.dpr.27: ccc: sleep(0); 
0040A1ED 6A00    push $00 
0040A1EF E858DAFFFF  call Sleep 
0040A1F4 EB07    jmp $0040a1fd 
Project56.dpr.28: hhh: sleep(0); 
0040A1F6 6A00    push $00 
0040A1F8 E84FDAFFFF  call Sleep 

Przyczyną najprawdopodobniej powodem do takiego kodu jest to, że stoły jump nie gramy bardzo dobrze z pamięci podręcznej L1 i ze względu na to, że wersja test-and-jump może być szybsza, jeśli nie ma dużej liczby etykiet przypadków.

"Dowodem" tego rozumowania jest następujący program, który ma przekształcić w tabelę skoku.

var 
    b: byte; 

begin 
    case b of 
    0: sleep(0); 
    1: sleep(0); 
    2: sleep(0); 
    3: sleep(0); 
    4: sleep(0); 
    5: sleep(0); 
    6: sleep(0); 
    7: sleep(0); 
    8: sleep(0); 
    9: sleep(0); 
    10: sleep(0); 
    11: sleep(0); 
    12: sleep(0); 
    13: sleep(0); 
    14: sleep(0); 
    15: sleep(0); 
    16: sleep(0); 
    17: sleep(0); 
    18: sleep(0); 
    19: sleep(0); 
    20: sleep(0); 
    end; 
end. 

Project56.dpr.12: case b of 
0040A178 0FB6C0   movzx eax,al 
0040A17B 83F814   cmp eax,$14 
0040A17E 0F8728010000  jnbe $0040a2ac 
0040A184 FF24858BA14000 jmp dword ptr [eax*4+$40a18b] 
... 
Project56.dpr.14: 1: sleep(0); 
0040A1EB 6A00    push $00 
0040A1ED E85ADAFFFF  call Sleep 
0040A1F2 E9B5000000  jmp $0040a2ac 
Project56.dpr.15: 2: sleep(0); 
0040A1F7 6A00    push $00 
0040A1F9 E84EDAFFFF  call Sleep 
0040A1FE E9A9000000  jmp $0040a2ac 
Project56.dpr.16: 3: sleep(0); 
0040A203 6A00    push $00 
0040A205 E842DAFFFF  call Sleep 
0040A20A E99D000000  jmp $0040a2ac 
... 

Barry mógł udzielić nam jednoznacznej odpowiedzi na to pytanie. Po prostu testuję i włóczę się.

Answer 4

Kompilator przetłumaczyć instrukcję case w jednym:

1. stół dwupoziomowy, stosując jedną tabelę, aby odwzorować wartość indeksu, a przy użyciu indeksu, aby wybrać adres z tabeli skoku
2. pośrednie skoku przez stół
3. Sequential skacze
4. Binary wyszukiwanie - to jest rekurencyjna, więc liście wyszukiwania binarnego może korzystać każdy z 2, 3 lub 4.

Wykorzystuje heurystykę, taką jak liczba przypadków, zakres przypadków, liczbę różnych alternatyw (każda alternatywa może implementować zakres różnych wartości), itp.

Intuicją dla stwierdzenia przypadku jest to, że jest operacja O(1).