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

Question

Полагаю, что некоторые предыдущие вопросы 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 )?).

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

Answer 1

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

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

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

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

Answer 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, и из-за того, что версия test-and-jump может быть быстрее, если нет большого количества присутствующих меток регистра.

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

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

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

Answer 3

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

Answer 4

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