Почему CharInSet быстрее, чем оператор Case? - PullRequest
Новая
       15

Почему CharInSet быстрее, чем оператор Case?

18 голосов
/ 02 декабря 2008

Я в недоумении. Сегодня в CodeRage Марко Канту сказал, что CharInSet работает медленно, и я должен вместо этого попробовать оператор Case. Я сделал это в своем парсере, а затем проверил с помощью AQTime, каково было ускорение. Я обнаружил, что заявление Case намного медленнее.

4 894 539 казней:

пока не CharInSet (P ^, ['', # 10, # 13, # 0]) do inc (P);

было приурочено к 0,25 секундам.

Но такое же количество казней:

в то время как True делают
дело P ^ of
'', # 10, # 13, # 0: перерыв;
остальное вкл. (P);
конец;

занимает 0,16 секунды для «while True», 0,80 секунды для первого случая и 0,13 секунды для остального случая, всего 1,09 секунды или более чем в 4 раза дольше.

Код ассемблера для оператора CharInSet:

добавить edi, $ 02
MOV EDX, $ 0064b290
movzx eax, [edi]
позвоните CharInSet
тест а1, а1
jz $ 00649f18 (вернуться к оператору добавления)

тогда как логика кейса просто так:

movzx eax, [edi]
дополнительный топор, $ 01
jb $ 00649ef0
дополнительный топор, $ 09
jz $ 00649ef0
дополнительный топор, $ 03
jz $ 00649ef0
добавить edi, $ 02
jmp $ 00649ed6 (назад к выражению movzx)

Мне кажется, что логика case использует очень эффективный ассемблер, в то время как оператор CharInSet фактически должен вызвать функцию CharInSet, которая находится в SysUtils и также проста:

функция CharInSet (C: AnsiChar; const CharSet: TSysCharSet): Boolean;
начать
Результат: = C в CharSet;
конец;

Я думаю, что единственная причина, по которой это делается, заключается в том, что P ^ in ['', # 10, # 13, # 0] больше не разрешены в Delphi 2009, поэтому вызов выполняет преобразование типов, чтобы разрешить это.

Тем не менее я очень удивлен этим и все еще не доверяю своему результату.

AQTime измеряет что-то не так, я что-то упускаю в этом сравнении или CharInSet действительно эффективная функция, которую стоит использовать?

Вывод:

Я думаю, ты понял, Барри. Спасибо, что нашли время и сделали подробный пример. Я проверил ваш код на своей машине и получил 0,117, 0,066 и 0,052 секунды (думаю, мой рабочий стол немного быстрее вашего ноутбука).

Тестируя этот код в AQTime, он дает: 0,79, 1,57 и 1,46 секунды для трех тестов. Там вы можете увидеть большие накладные расходы от приборов. Но что меня действительно удивляет, так это то, что эти издержки изменяют видимый «лучший» результат на функцию CharInSet, которая на самом деле является худшей.

Значит, Марку прав, а CharInSet медленнее. Но вы случайно (или, может быть, нарочно) дали мне лучший способ, вытянув то, что CharInSet делает с методом AnsiChar (P ^) в методе Set. Помимо незначительного преимущества в скорости по сравнению с методом case, он также меньше кода и более понятен, чем использование case.

Вы также уведомили меня о возможности некорректной оптимизации с использованием AQTime (и других профилировщиков инструментов). Знание этого поможет моему решению о инструментах профилирования и анализа памяти для Delphi , а также является еще одним ответом на мой вопрос Как это делает AQTime? . Конечно, AQTime не меняет код, когда использует инструменты, поэтому он должен использовать для этого какую-то другую магию.

Таким образом, ответ таков: AQTime показывает результаты, которые приводят к неверному выводу.

Продолжение: я оставил этот вопрос с «обвинением» в том, что результаты AQTime могут вводить в заблуждение. Но, честно говоря, я должен попросить вас прочитать этот вопрос: Есть ли быстрая процедура GetToken для Delphi? , которая начала думать, что AQTime дал ошибочные результаты, и пришла к выводу, что это не так.

Ответы [ 5 ]

25 голосов
/ 02 декабря 2008

AQTime - инструментальный профилировщик. Профилировщики инструментов часто не подходят для измерения времени кода, особенно в таких микробенчмарках, как ваша, потому что стоимость инструментов часто перевешивает стоимость измеряемой вещи. Инструментальные профилировщики, с другой стороны, преуспевают в профилировании памяти и использовании других ресурсов.

Профилировщики выборки, которые периодически проверяют местоположение ЦП, обычно лучше измеряют время кода.

В любом случае, вот еще один микробенчмарк, который действительно показывает, что оператор case быстрее, чем CharInSet. Тем не менее, обратите внимание, что проверка набора все еще может использоваться с типом, чтобы устранить предупреждение об усечении (фактически это единственная причина, по которой существует CharInSet): 

{$apptype console}

uses Windows, SysUtils;

const
  SampleString = 'foo bar baz blah de;blah de blah.';

procedure P1;
var
  cp: PChar;
begin
  cp := PChar(SampleString);
  while not CharInSet(cp^, [#0, ';', '.']) do
    Inc(cp);
end;

procedure P2;
var
  cp: PChar;
begin
  cp := PChar(SampleString);
  while True do
    case cp^ of
      '.', #0, ';':
        Break;
    else
      Inc(cp);
    end;
end;

procedure P3;
var
  cp: PChar;
begin
  cp := PChar(SampleString);
  while not (AnsiChar(cp^) in [#0, ';', '.']) do
    Inc(cp);
end;

procedure Time(const Title: string; Proc: TProc);
var
  i: Integer;
  start, finish, freq: Int64;
begin
  QueryPerformanceCounter(start);
  for i := 1 to 1000000 do
    Proc;
  QueryPerformanceCounter(finish);
  QueryPerformanceFrequency(freq);
  Writeln(Format('%20s: %.3f seconds', [Title, (finish - start) / freq]));
end;

begin
  Time('CharInSet', P1);
  Time('case stmt', P2);
  Time('set test', P3);
end.

Его вывод на моем ноутбуке здесь: 

CharInSet: 0.261 seconds
case stmt: 0.077 seconds
 set test: 0.060 seconds
7 голосов
/ 02 декабря 2008

Барри, я хотел бы отметить, что ваш тест не отражает фактическую производительность различных методов, потому что структура реализаций отличается. Вместо этого все методы должны использовать конструкцию «while True do», чтобы лучше отражать влияние различных способов выполнения проверки набора символов.

Здесь замена для тестовых методов (P2 неизменен, P1 и P3 теперь используют конструкцию «while True do»): 

procedure P1;
var
  cp: PChar;
begin
  cp := PChar(SampleString);
  while True do
    if CharInSet(cp^, [#0, ';', '.']) then
      Break
    else
      Inc(cp);
end;

procedure P2;
var
  cp: PChar;
begin
  cp := PChar(SampleString);
  while True do
    case cp^ of
      '.', #0, ';':
        Break;
    else
      Inc(cp);
    end;
end;

procedure P3;
var
  cp: PChar;
begin
  cp := PChar(SampleString);
  while True do
    if AnsiChar(cp^) in [#0, ';', '.'] then
      Break
    else
      Inc(cp);
end;

Моя рабочая станция дает: 

CharInSet: 0.099 seconds
case stmt: 0.043 seconds
 set test: 0.043 seconds

Что лучше соответствует ожидаемым результатам. Мне кажется, использование конструкции case in не очень помогает. Прости, Марко!

3 голосов
/ 11 декабря 2008

Бесплатный профилировщик выборки для Delphi можно найти здесь:

https://forums.codegear.com/thread.jspa?messageID=18506

Помимо вопроса о неправильном измерении времени профилировщиков инструментов, следует отметить, что то, что быстрее, будет также зависеть от того, насколько предсказуемы ветви "случая". Если тесты в «случае» имеют одинаковую вероятность того, что они встретятся, производительность «дела» может оказаться ниже, чем у CharInSet.

2 голосов
/ 05 января 2009

Код в функции «CharInSet» быстрее, чем «case», время тратится на «call» использование пока нет (cp ^ in [..]) тогда

вы увидите, что это пост.

1 голос
/ 02 декабря 2008

Как я знаю, вызов занимает столько же операций с процессором, что и переход, если они оба используют короткие указатели. С длинными указателями могут быть разные. Вызов в ассемблере не использует стек по умолчанию. Если свободных регистров достаточно, используйте регистрацию. Так что операции со стеком тоже занимают нулевое время. Это просто регистры, которые очень быстрые.

В отличие от этого варианта, как я вижу, используются операции add и sub, которые довольно медленные и, вероятно, добавляют большую часть дополнительного времени.

...