Kiedy ma sens przepisywanie hasza?

Question

Od perldata:

You can preallocate space for a hash by assigning to the keys() function. 
This rounds up the allocated buckets to the next power of two: 

    keys(%users) = 1000;  # allocate 1024 buckets 

Czy istnieje zasada, gdy presizing hash poprawi wydajność?

Answer 1

Zasada jest taka, że ​​im większy wiesz, że Hash będzie, tym bardziej prawdopodobne, że uzyskasz wartość z jego wcześniejszego rozmiaru. Zastanów się, czy twój hash ma 10 slotów i zaczniesz dodawać jeden po drugim, liczba rozszerzeń będzie a) nieliczne (jeśli w ogóle) i b) małe (ponieważ jest mało danych).

Ale jeśli wiesz, że będziesz potrzebować co najmniej 1 mln przedmiotów, nie ma powodu do rozszerzania i kopiowania podstawowych i wciąż rozwijających się struktur danych podczas gdy stół rośnie.

Czy powiadomisz o tym rozszerzeniu? Eh, może. Nowoczesne maszyny są bardzo cholernie szybkie, może się nie pojawić. Ale jest to wielka szansa na rozszerzenie sterty, powodując w ten sposób GC i kaskadę wszelkiego rodzaju rzeczy. Tak więc, jeśli wiesz, że zamierzasz z niego korzystać, jest to "tania" poprawka pozwalająca ulepszyć jeszcze kilka miligramów wydajności.

Answer 2

Zasadniczo jest to drzwi do optymalizacji wydajności hash. Wydajność skrótu zależy w dużej mierze od zastosowanego algorytmu mieszania i od danych, którymi się posługujesz, więc prawie niemożliwe jest wymyślenie zasady kciuka. W każdym razie można coś powiedzieć.

Wiesz, że każda struktura danych oferuje określoną równowagę między wydajnością czasu i przestrzeni. Tabele skrótu są szczególnie dobre pod względem wydajności czasowej, oferując atrakcyjny czas stały (0 (1)).

To prawda, o ile nie ma kolizji. Kiedy dochodzi do kolizji, czas dostępu jest liniowy wraz z rozmiarem wiadra odpowiadającego wartości kolizji. (Zajrzyj do this po więcej szczegółów). Zderzenia, oprócz bycia "wolniejszymi", są głównie zakłóceniem gwarancji czasu dostępu, która jest najważniejszym aspektem, który często prowadzi do wyboru tabeli mieszającej w pierwszej kolejności.

Idealnie, tabele mieszania mogą mieć na celu tzw. "Doskonałe mieszanie" (co jest w rzeczywistości możliwe tylko wtedy, gdy można dostroić algorytm do rodzaju danych, które zechcesz obsłużyć), ale nie jest to takie łatwe osiągnąć w przypadku ogólnym (faktycznie jest to eufemizm). W każdym razie, jest faktem, że większe tabele mieszania (wraz z dobrym algorytmem mieszającym) mogą zmniejszyć częstotliwość kolizji, a tym samym poprawić wydajność, kosztem pamięci. Mniejsze tablice skrótów będą powodowały więcej kolizji (stąd będą mieć mniejszą wydajność i mniejszą gwarancję czasu dostępu), ale zajmują mniej pamięci.

Tak więc, jeśli profilujesz swój program i widzisz, że dostęp do tablicy hash jest wąskim gardłem (z jakichkolwiek powodów), masz szansę rozwiązać ten problem, rezerwując więcej pamięci na spację (jeśli masz pamięć do nadania).

W każdym razie nie zwiększałbym tej wartości losowo, ale tylko po dokładnym profilowaniu, ponieważ prawdą jest również, że algorytm używa perl (AFAIK), co ma również duży wpływ na wydajność skrótu (innymi słowy, możesz mieć wiele kolizji, nawet jeśli zwiększysz obszar mieszania).

Jak zwykle w przypadku rzeczy związanych z wydajnością, może być przydatny lub nie, zależy to od konkretnego przypadku.

Answer 3

Próbowałem porównawczego kosztów ekspansji na hash winorośli:

use Benchmark qw(cmpthese); 

# few values 
cmpthese(-4, { 
    prealloc => sub { 
     my %hash; 
     keys(%hash) = 17576; 
     $hash{$_} = $_ for 'aaa' .. 'zzz'; 
    }, 
    normal => sub { 
     my %hash; 
     $hash{$_} = $_ for 'aaa' .. 'zzz'; 
    }, 
}); 

# more values 
cmpthese(-8, { 
    prealloc => sub { 
     my %hash; 
     keys(%hash) = 456976; 
     $hash{$_} = $_ for 'aaaa' .. 'zzzz'; 
    }, 
    normal => sub { 
     my %hash; 
     $hash{$_} = $_ for 'aaaa' .. 'zzzz'; 
    }, 
}); 

Wyniki nie brzmi jak wielki optymalizacji, jednak zmniejszenie fragmentacji sterty wspomniany przez Will Hartung może być zaletą. Uruchomienie perla 5.12 na maszynie WinXP.

 Rate normal prealloc 
normal 48.3/s  --  -2% 
prealloc 49.4/s  2%  -- 
     (warning: too few iterations for a reliable count) 
    s/iter normal prealloc 
normal  3.62  --  -1% 
prealloc 3.57  1%  --