Самая эффективная функция хеширования Unicode для Delphi 2009

Question

Самая эффективная функция хеширования Unicode для Delphi 2009

Мне нужна самая быстрая хеш-функция, возможная в Delphi 2009, которая создаст хешированные значения из строки Unicode, которая будет распределяться довольно случайным образом в ведра.

Сначала я начал с функции Gabr 's HashOf из GpStringHash:

function HashOf(const key: string): cardinal;
asm
  xor edx,edx     { result := 0 }
  and eax,eax     { test if 0 }
  jz @End         { skip if nil }
  mov ecx,[eax-4] { ecx := string length }
  jecxz @End      { skip if length = 0 }
@loop:            { repeat }
  rol edx,2       { edx := (edx shl 2) or (edx shr 30)... }
  xor dl,[eax]    { ... xor Ord(key[eax]) }
  inc eax         { inc(eax) }
  loop @loop      { until ecx = 0 }
@End:
  mov eax,edx     { result := eax }
end; { HashOf }

Но я обнаружил, что это не привело к хорошим номерам из строк Unicode. Я отметил, что подпрограммы Gabr не были обновлены до Delphi 2009.

Затем я обнаружил HashNameMBCS в SysUtils Delphi 2009 и перевел его на эту простую функцию (где «строка» - это строка Unicode Delphi 2009):

function HashOf(const key: string): cardinal;
var
  I: integer;
begin
  Result := 0;
  for I := 1 to length(key) do
  begin
    Result := (Result shl 5) or (Result shr 27);
    Result := Result xor Cardinal(key[I]);
  end;
end; { HashOf }

Я думал, что это было очень хорошо, пока я не посмотрел на окно CPU и не увидел, что он создал код ассемблера:

Process.pas.1649: Result := 0;
0048DEA8 33DB             xor ebx,ebx
Process.pas.1650: for I := 1 to length(key) do begin
0048DEAA 8BC6             mov eax,esi
0048DEAC E89734F7FF       call $00401348
0048DEB1 85C0             test eax,eax
0048DEB3 7E1C             jle $0048ded1
0048DEB5 BA01000000       mov edx,$00000001
Process.pas.1651: Result := (Result shl 5) or (Result shr 27);
0048DEBA 8BCB             mov ecx,ebx
0048DEBC C1E105           shl ecx,$05
0048DEBF C1EB1B           shr ebx,$1b
0048DEC2 0BCB             or ecx,ebx
0048DEC4 8BD9             mov ebx,ecx
Process.pas.1652: Result := Result xor Cardinal(key[I]);
0048DEC6 0FB74C56FE       movzx ecx,[esi+edx*2-$02]
0048DECB 33D9             xor ebx,ecx
Process.pas.1653: end;
0048DECD 42               inc edx
Process.pas.1650: for I := 1 to length(key) do begin
0048DECE 48               dec eax
0048DECF 75E9             jnz $0048deba
Process.pas.1654: end; { HashOf }
0048DED1 8BC3             mov eax,ebx

Похоже, что этот код содержит скорее код ассемблера, чем код Gabr.

Скорость - это сущность. Есть ли что-нибудь, что я могу сделать, чтобы улучшить либо код паскаля, который я написал, либо сборщик, сгенерированный моим кодом?

Следовать за.

Я, наконец, пошел с функцией HashOf на основе SysUtils.HashNameMBCS. Кажется, он дает хорошее распределение хэша для строк Unicode и выглядит довольно быстро.

Да, генерируется много кода ассемблера, но код Delphi, который его генерирует, настолько прост и использует только операции с бит-сдвигом, поэтому трудно поверить, что это не будет быстро.

delphi,unicode,assembly,hash,delphi-2009,

9

Ответов: 4

Следовать за.

Я, наконец, пошел с функцией HashOf на основе SysUtils.HashNameMBCS. Кажется, он дает хорошее распределение хэша для строк Unicode и выглядит довольно быстро.

Да, генерируется много кода ассемблера, но код Delphi, который его генерирует, настолько прост и использует только операции с бит-сдвигом, поэтому трудно поверить, что это не будет быстро.

49

Дельфы, юникод, сборка, хэш, Дельфы-2009,

Похожие вопросы

score 9 · Accepted Answer

9 принят

Выход ASM не является хорошим показателем скорости алгоритма. Кроме того, из того, что я вижу, две части кода выполняют почти идентичную работу. Наибольшее различие, похоже, является стратегией доступа к памяти, а первое использует roll-left вместо эквивалентного набора инструкций (shl | shr - большинство языков программирования более высокого уровня не учитывают операторов «roll»). Последний может быть лучше, чем первый.

Оптимизация ASM - черная магия, а иногда больше команд выполняется быстрее, чем меньше.

Разумеется, сравнивайте и выигрывайте победителей . Если вам нравится вывод второго, но первый быстрее, вставьте значения второго в первый.

rol edx,5 { edx := (edx shl 5) or (edx shr 27)... }

Обратите внимание, что разные машины будут запускать код по-разному, поэтому, если скорость ДЕЙСТВИТЕЛЬНО сущности, тогда сравнивайте его с оборудованием, на котором вы планируете запустить окончательное приложение. Я готов поспорить, что над мегабайтами данных разница будет составлять миллисекунды, что намного меньше, чем операционная система отнимает у вас.

PS. Я не уверен, что этот алгоритм создает равномерное распределение, то, что вы явно вызывали (вы запускаете гистограммы?). Вы можете посмотреть на перенос этой хэш-функции в Delphi. Это может быть не так быстро, как описанный выше алгоритм, но он выглядит довольно быстрым и также дает хорошее распространение. Опять же, мы, вероятно, говорим о порядке миллисекунд разницы по мегабайтам данных.

score 5 · Accepted Answer

5 ов

Некоторое время назад мы провели приятный небольшой конкурс, улучшив хэш, названный « MurmurHash »; Цитата Википедии:

Он отмечается исключительно быстро, часто в два-четыре раза быстрее, чем сопоставимые алгоритмы, такие как FNV, поиск Jenkins3 и SuperFastHash от Hsieh с отличным распределением, лавинным поведением и общим сопротивлением столкновению.

Вы можете скачать материалы для этого конкурса здесь .

Мы узнали, что иногда оптимизация не улучшает результаты на каждом процессоре. Мой вклад был изменен, чтобы хорошо работать на AMD, но на Intel не очень-то хорош. С другой стороны, произошло слишком много (оптимизация Intel работает не оптимально на AMD).

Итак, как сказал Talljoe: измерьте свои оптимизации, так как они могут нанести ущерб вашей работе!

В качестве примечания: я не согласен с Ли; Delphi - хороший компилятор и все, но иногда я вижу, что он генерирует код, который просто не оптимален (даже при компиляции с включенными оптимизациями). Например, я регулярно вижу, что это очищающие регистры, которые уже были очищены только двумя или тремя заявлениями ранее. Или EAX помещается в EBX, только чтобы он переместился и вернулся в EAX. Что-то в этом роде. Я просто угадываю здесь, но ручная оптимизация такого кода наверняка поможет в узких местах.

Прежде всего, хотя; Сначала проанализируйте узкое место, затем посмотрите, можно ли использовать более эффективный алгоритм или структуру данных, затем попытайтесь оптимизировать код паскаля (например: уменьшить выделение памяти, избежать подсчета ссылок, финализации, try / finally, try / except blocks и т. Д.), а затем, только в качестве окончательного варианта, оптимизируйте код сборки.

score 5 · Accepted Answer

5 ов

Я написал две сборные «оптимизированные» функции в Delphi или реализовал известные быстрые алгоритмы хеширования как в тонко настроенном паскале, так и в Borland Assembler. Первой была реализация SuperFastHash , а вторая - реализация MurmurHash2, вызванная запросом Tommi Prami на моем блоге, чтобы перевести мою версию c # в реализацию pascal. Это вызвало дискуссию на дискуссионных форумах Embarcadero Discussion BASM , которые в итоге привели к примерно 20 реализациям (проверьте последний набор тестов ), которые в конечном итоге показали, что будет сложно выбрать лучшую реализацию из-за больших различий в времени цикла в инструкции между Intel и AMD.

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

score 4 · Accepted Answer

4

На форуме Delphi / BASM было немного обсуждения, которое может вас заинтересовать. Посмотрите на следующее:

http://forums.embarcadero.com/thread.jspa?threadID=13902&tstart=0