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

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

4 894 539 казней:

в то время как не CharInSet (P^, [' ', #10,#13, #0]) do inc(P);

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

Но столько же казней:

в то время как правда делать
случай P ^ of
'', # 10, # 13, # 0: перерыв;
еще inc (P);
конец;

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

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

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

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

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

Мне кажется, что регистр использует очень эффективный ассемблер, в то время как оператор 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 ответов

Решение

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
Источник

Барри, я хотел бы отметить, что ваш тест не отражает фактическую производительность различных методов, потому что структура реализаций отличается. Вместо этого все методы должны использовать конструкцию "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 не очень помогает. Прости, Марко!

Источник

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

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

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

Источник

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

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

Источник

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

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

Источник
Другие вопросы по тегам