MalDevBlog

Haszowanie stringów z wykorzystaniem prostego algorytmu Roberta Sedgwicks 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ć ze właśnie RS jest prostym i małokolizyjnym algorytmem.

Dlatego właśnie go wybrałem do użycia w swoim projekcie, do haszowania nazw funkcji serwisowych eventów, hooków.

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 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, ale założyłem ze str jest różny od NULL, aby nieco ułatwić sprawę i pozbyć się kilku „nadmiarowych” poleceń i skoków.

G++ się postarał z optymalizacją, 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

Przy okazji poruszając temat STLa, standard zaleca w make_pair przekazywać elementy przez referencje, a kochane gcc wspomina o tym, ale „robi” przez wartość ;)

Przez co proste dodanie elementu do mapa z wykorzystaniem make_pair w postaci:

std::pair<my_map_type::iterator, bool> ret = my_map.insert(std::make_pair(key, value));

doprowadziło do 4-krotnego kopiowania obiektu.

Zmiana na:

std::pair<my_map_type::iterator, bool> ret = my_map.insert(my_map_type::value_type(key, value));

zredukowała kopiowanie do 2.

Jak to ładnie ktoś rozwinął na pl.comp.lang.c skrót STL do Slow Template Library ;)

Dodano @ 20:49:34

Poprawiłem jeszcze swój kod, porównując go do zoptymalizowanej wersji z gcc. Powinien teraz być wydajniejszy i formalnie poprawniejszy ;)

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
jnz	L

; porownywanie
test	rej, rej
; jest szybsze od
cmp	rej, 0

W porównaniu do wersji gcc, w pętli mamy 1 instrukcje mniej, oraz wrzuciliśmy do rejestru wartość stałej b, co powinno przyśpieszyć działanie, bo w pętli procesor operuje na samych rejestrach ;)