La función Hash Unicode más eficiente para Delphi 2009
https://stackoverflow.com/questions/1005010
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Necesito la función hash más rápida posible en Delphi 2009 que creará valores hash de una cadena Unicode que se distribuirá de manera bastante aleatoria en grupos.
Originalmente comencé con la función HashOf de Gabr de 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 }
Pero encontré que esto no produjo buenos números de las cadenas Unicode. Noté que las rutinas de Gabr no se han actualizado a Delphi 2009.
Luego descubrí HashNameMBCS en SysUtils of Delphi 2009 y lo traduje a esta simple función (donde " cadena " es una cadena de Delphi 2009 Unicode):
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 }
Pensé que esto era bastante bueno hasta que miré la ventana de la CPU y vi el código del ensamblador que generó:
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
Esto parece contener un poco más de código ensamblador que el código de Gabr.
La velocidad es esencial. ¿Hay algo que pueda hacer para mejorar el código pascal que escribí o el ensamblador que generó mi código?
Seguimiento.
Finalmente fui con la función HashOf basada en SysUtils.HashNameMBCS. Parece dar una buena distribución de hash para cadenas Unicode, y parece ser bastante rápido.
Sí, se genera una gran cantidad de código de ensamblador, pero el código de Delphi que lo genera es muy simple y utiliza solo operaciones de cambio de bits, por lo que es difícil creer que no sea rápido.
Solución
La salida ASM no es una buena indicación de la velocidad del algoritmo. Además, por lo que puedo ver, las dos piezas de código están haciendo casi el mismo trabajo. La mayor diferencia parece ser la estrategia de acceso a la memoria y la primera es usar roll-left en lugar del conjunto de instrucciones equivalente (shl | shr - la mayoría de los lenguajes de programación de nivel superior dejan de lado a los operadores "roll"). El último puede canalizarse mejor que el primero.
La optimización de ASM es magia negra y, a veces, más instrucciones se ejecutan más rápido que menos.
Para estar seguro, haga una evaluación comparativa de ambas y elija al ganador . Si te gusta la salida del segundo pero el primero es más rápido, conecta los valores del segundo al primero.
rol edx,5 { edx := (edx shl 5) or (edx shr 27)... }
Tenga en cuenta que las diferentes máquinas ejecutarán el código de diferentes maneras, por lo que si la velocidad es REALMENTE esencial, entonces evalúe el hardware en el que planea ejecutar la aplicación final. Estoy dispuesto a apostar a que, a lo largo de megabytes de datos, la diferencia será en cuestión de milisegundos, que es mucho menos de lo que el sistema operativo le está quitando.
PS. No estoy convencido de que este algoritmo cree una distribución uniforme, algo que mencionaste explícitamente (¿has ejecutado los histogramas?). Puede mirar portar esta función hash a Delphi. Puede que no sea tan rápido como el algoritmo anterior, pero parece ser bastante rápido y también ofrece una buena distribución. Una vez más, probablemente estamos hablando del orden de milisegundos de diferencia sobre megabytes de datos.
Otros consejos
Hace poco tuvimos un pequeño concurso, mejorando un hash llamado " MurmurHash " ;; Citando Wikipedia:
Se destaca por ser excepcionalmente. Rápido, a menudo dos a cuatro veces más rápido. que los algoritmos comparables, tales como FNV, lookup3 de Jenkins y Hsieh's SuperFastHash, con excelente Distribución, comportamiento de avalanchas y resistencia general a la colisión.
Puede descargar las presentaciones para ese concurso aquí .
Una cosa que aprendimos fue que, a veces, las optimizaciones no mejoran los resultados en todas las CPU. Mi contribución fue modificada para funcionar bien en AMD, pero no tan bien en Intel. También sucedió lo contrario (las optimizaciones de Intel se están ejecutando por debajo del nivel óptimo en AMD).
Entonces, como dijo Talljoe: ¡mida sus optimizaciones, ya que podrían ser perjudiciales para su rendimiento!
Como nota al margen: no estoy de acuerdo con Lee; Delphi es un buen compilador y todo, pero a veces lo veo generando un código que no es óptimo (incluso cuando se compila con todas las optimizaciones activadas). Por ejemplo, regularmente lo veo borrando registros que ya habían sido borrados solo dos o tres declaraciones antes. O EAX se pone en EBX, solo para cambiarlo y volver a ponerlo en EAX. Esa clase de cosas. Solo estoy adivinando aquí, pero la optimización manual de ese tipo de código seguramente ayudará en situaciones difíciles.
Pero sobre todo; Primero analice su cuello de botella, luego vea si se puede utilizar un mejor algoritmo o estructura de datos, luego intente optimizar el código pascal (como: reducir las asignaciones de memoria, evitar el conteo de referencias, la finalización, probar / finalmente, probar / excepto los bloques, etc.), y luego, solo como último recurso, optimice el código de ensamblaje.
He escrito dos conjuntos "optimizados" funciones en Delphi, o más algoritmos hash rápidos conocidos implementados tanto en pascal afinado como en Borland Assembler. La primera fue una implementación de SuperFastHash , y la segunda fue una implementación MurmurHash2 activada por una solicitud de Tommi Prami en mi blog para traducir mi versión c # a una implementación de pascal. Esto generó un debate sobre continuado en los foros BASC de discusión de Embarcadero , que en el final dio como resultado unas 20 implementaciones (consulte el último conjunto de pruebas ) lo que en última instancia mostró que sería difícil seleccionar la mejor implementación debido a las grandes diferencias en los tiempos de ciclo por instrucción entre Intel y AMD.
Entonces, intente uno de esos, pero recuerde, obtener el más rápido cada vez probablemente significaría cambiar el algoritmo a uno más simple, lo que perjudicaría su distribución. La optimización de una implementación lleva mucho tiempo y es mejor crear un buen conjunto de validación y evaluación comparativa para verificar sus implementaciones.
Ha habido un poco de discusión en el foro Delphi / BASM que puede ser de su interés. Echa un vistazo a lo siguiente:
http://forums.embarcadero.com/thread.jspa?threadID = 13902 & amp; tstart = 0
