Hiệu suất Delphi: Case Versus Nếu

Question

Tôi đoán có thể có một số chồng chéo với các câu hỏi SO trước đó, nhưng tôi không thể tìm thấy câu hỏi cụ thể về Delphi về chủ đề này.

Giả sử bạn muốn kiểm tra xem biến số nguyên 32 bit không dấu "MyAction" có bằng bất kỳ hằng số ACTION1, ACTION2, ..., ACTIONn, trong đó n là - giả sử 1000. Tôi đoán rằng, ngoài ra là tao nhã hơn,

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

là nhanh hơn nhiều so

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

tôi đoán rằng nếu biến thể mất nhiều thời gian O (n) để hoàn thành (ví dụ: để tìm ra hành động đúng) nếu hành động đúng ACTIONi có một giá trị cao của i, trong khi trường hợp biến thể mất rất nhiều thời gian (O (1)?).

1. Tôi có sửa công tắc đó nhanh hơn không?
2. Tôi có đúng thời gian cần thiết để tìm đúng hành động trong trường hợp chuyển đổi thực sự độc lập với n không? I E. đúng là nó không thực sự mất nhiều thời gian hơn để kiểm tra một triệu trường hợp hơn là kiểm tra 10 trường hợp?
3. Làm thế nào, chính xác, tính năng này có hoạt động không?

Answer 1

1. Có công tắc là O (1) trong khi các tầng nếu nhân là O (n)
2. Vâng, nhìn thấy (1)
3. Với branch table

Answer 2

Lưu ý rằng nếu giá trị của MyAction là trọng số, hiệu suất tốt có thể thu được với các tầng nếu..xem, nơi bạn đặt các trường hợp có khả năng nhất gần đầu trang. Tôi không nói rằng nó sẽ cạnh tranh với trường hợp/chuyển đổi tuyên bố về hiệu suất khi bạn đang đối phó với số nguyên. Nhưng nếu một trường hợp không phù hợp (giả sử bạn đã có chuỗi, ví dụ), hãy kiểm tra tỷ lệ phần trăm cao của bạn ở trên cùng.

Answer 3

Luôn kiểm tra thực tế trước tiên ...

Trình biên dịch Delphi 2010 có vẻ như rất nhiều thử nghiệm và chi nhánh. Ví dụ, mã đơn giản sau đây không được biên dịch thành một bảng chi nhánh.

var 
    c: (aaa, bbb, ccc); 

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

trình biên dịch sẽ tạo ra đoạn mã sau:

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 

Thậm chí phức tạp hơn trường hợp sẽ được biên dịch vào một loạt thử nghiệm-và-nhảy. Ví dụ ...

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. 

... được biên dịch vào ...

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 

Các lẽ hầu hết gây ra nguyên nhân cho mã như vậy là bảng nhảy không chơi rất tốt với bộ nhớ đệm L1 và vì phiên bản thử nghiệm và nhảy đó có thể nhanh hơn nếu không có nhiều nhãn trường hợp hiện diện.

Một "bằng chứng" cho lý do đó là chương trình sau đây không được dịch sang bảng nhảy.

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 có thể cho chúng tôi câu trả lời rõ ràng cho câu hỏi đó. Tôi chỉ đang thử nghiệm và đánh bạc.

Answer 4

Trình biên dịch sẽ dịch một tuyên bố trường hợp vào một trong số:

1. bảng Hai cấp, sử dụng một bảng để lập bản đồ giá trị cho một chỉ số, và sử dụng các chỉ số để chọn một địa chỉ từ một bảng nhảy
2. nhảy gián tiếp thông qua bảng
3. tuần tự nhảy
4. tìm kiếm nhị phân - đây là đệ quy, vì vậy lá của việc tìm kiếm nhị phân có thể sử dụng bất kỳ 2, 3 hoặc 4.

Nó sử dụng chẩn đoán như số lượng trường hợp, phạm vi trường hợp, số lượng lựa chọn thay thế khác nhau (mỗi thay thế có thể thực hiện một loạt các giá trị khác nhau), v.v.

Trực giác cho trường hợp là hoạt động O(1).