Производительность Delphi: случай Versus If

Я предполагаю, что могут быть некоторые совпадения с предыдущими вопросами SO, но я не мог найти конкретный вопрос в Delphi по этой теме.

Предположим, что вы хотите проверить, не является ли 32-разрядная целочисленная переменная без знака "MyAction" равным любой из констант ACTION1, ACTION2,..., ACTIONn, где n - 1000. Я предполагаю, что помимо более элегантный,

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

намного быстрее, чем

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

Я предполагаю, что для варианта if требуется время O (n) для завершения (т.е. для нахождения правильного действия), если правильное действие ACTIONi имеет высокое значение i, тогда как вариант варианта занимает намного меньше времени (O (1 )?).

Я исправляю этот переключатель намного быстрее?
Правильно ли, что время, необходимое для нахождения правильного действия в случае коммутатора, фактически не зависит от n? То есть верно ли, что на самом деле не требуется больше времени проверять миллион случаев, чем проверять 10 случаев?
Как именно это работает?

Ответ 1

Да, переключатель O (1), тогда как каскадирование if есть O (n)
Да, см. (1)
С таблицей

Ответ 2

Всегда полезно сначала проверить реальность...

Компилятор Delphi 2010, похоже, много напоминает тестовую ветвь. Например, следующий простой код не скомпилирован в таблицу ветвей.

var
  c: (aaa, bbb, ccc);

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

Компилятор будет генерировать следующий код:

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

Еще более сложные случаи будут скомпилированы в серии тестов и прыжков. Например...

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.

... скомпилирован в...

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

Вероятнее всего, причиной такого кода является то, что таблицы перехода не очень хорошо работают с кэшами L1, и из-за этой версии тестовый и переход может быть более быстрым, если не существует большого количества ярлыков case.

"Доказательство" для этой аргументации - это следующая программа, которая делает переведена в таблицу перехода.

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
...

Барри может дать нам определенный ответ на этот вопрос. Я просто тестирую и бессвязно.

Ответ 3

Компилятор переведет оператор case в один из:

Двухуровневая таблица, использующая одну таблицу для сопоставления значения индексу и используя индекс для выбора адреса из таблицы перехода
Непрямой переход через таблицу
Последовательные прыжки
Двоичный поиск - это рекурсивный, поэтому листья двоичного поиска могут использовать любой из 2, 3 или 4.

Он использует эвристику, такую как количество случаев, диапазон случаев, количество различных альтернатив (каждая альтернатива может реализовывать диапазон различных значений) и т.д.

Интуиция для оператора case заключается в том, что это операция O(1).

Ответ 4

Обратите внимание, что если значение MyAction взвешено, хорошая производительность может быть получена при каскадировании if..else, где вы помещаете наиболее вероятные случаи рядом с вершиной. Я не говорю, что он будет конкурировать с оператором case/switch с точки зрения производительности, когда вы имеете дело с целыми числами. Но если случай не подходит (предположим, у вас есть строки, например), положите свои высокие процентные тесты вверху.