Proste haszowanie stringa

Haszowanie stringów z wykorzystaniem prostego algorytmu Roberta Sedgwicksa z książki “Algorithms in C”.

Według testów różnych prostych algorytmów opublikowanych na stronie Hash Function Efficiency, można zauważyć, że to właśnie RS jest prostym i mało kolizyjnym algorytmem. Dlatego wybrałem go do użycia w swoim projekcie, do haszowania nazw funkcji serwisowych, eventów, hooków.

Jego najprostsza implementacja w C++:

unsigned int RSHash(char* str) {
	unsigned int a = 63689;
	unsigned int b = 378551;
	unsigned int hash = 0;

	while (*str) {
		hash = hash * a + static_cast<unsigned char>(*str);
		a = a * b;
		str++;
	}

	return hash;
}

W źródłach mirandy, użyty przez nią algorytm znalazłem w wersji C i Asemblera, więc naszła mnie mała ochota, aby mój algorytm również nieco zoptymalizować i przy okazji przypomnieć sobie bebechy asemblera ;)

Tak też zrobiłem i wygenerowany asm przez g++ bez flag optymalizacyjnych doprowadziłem do takiej postaci:

xor		eax, eax
mov		ebx, 63689
mov		esi, [ebp+8]
hL:
imul	eax, ebx
movzx	edx, BYTE PTR [esi]
add		eax, edx
imul	ebx, 378551
inc		esi
cmp		BYTE PTR [esi], 0
jg		hL

Efekt ciekawy. Dla ułatwienia założyłem, że str jest różny od NULL, co pozwoliło pozbyć się kilku “nadmiarowych” poleceń i skoków.

Z włączonymi optymalizacjami kompilator g++ się postarał, do porównania wersja z flagą O2:

push	ebx
mov		ecx, DWORD PTR [ebp+8]
mov		ebx, 63689
jmp		L7
.p2align 4,,7
L9:
imul	edx, ebx
movzx	eax, al
imul	ebx, ebx, 378551
inc		ecx
add		edx, eax
L7:
movzx	eax, BYTE PTR [ecx]
test	al, al
jne		L9
pop		ebx
mov		eax, edx

[dodano 20:50]

Poprawiłem jeszcze trochę swój kod, porównując go do zoptymalizowanej wersji z gcc. Teraz powinien być lepszy i formalnie bardziej poprawny ;)

xor		eax, eax
mov		ebx, 63689
mov		ecx, 378551
mov		esi, DWORD PTR [ebp+8]
jmp		C
L:
imul	eax, ebx
add		eax, edx
imul	ebx, ecx
inc		esi
C:
movzx	edx, BYTE PTR [esi]
test	edx, edx	; szybsze niz cmp edx, 0
jnz		L

W porównaniu do kodu “wyplutego” przez gcc, w pętli mam 1 instrukcję mniej, no i wrzuciłem do rejestru wartość stałej b. To powinno przyśpieszyć działanie, bo w pętli procesor będzie operował na samych rejestrach ;)