Tworzymy oprogramowanie o wysokiej wydajności w języku C ++. Tam potrzebujemy współbieżnej mapy skrótów i zaimplementowanej. Dlatego napisaliśmy test porównawczy, aby dowiedzieć się, o ile wolniej jest porównywana nasza współbieżna mapa skrótów std::unordered_map.
Ale std::unordered_mapwydaje się być niesamowicie powolny ... Więc to jest nasz mikro-test porównawczy (dla mapy współbieżnej stworzyliśmy nowy wątek, aby upewnić się, że blokowanie nie zostanie zoptymalizowane i zauważ, że nigdy nie wstawiam 0, ponieważ testuję również z google::dense_hash_map, który potrzebuje wartości null):
boost::random::mt19937 rng;
boost::random::uniform_int_distribution<> dist(std::numeric_limits<uint64_t>::min(), std::numeric_limits<uint64_t>::max());
std::vector<uint64_t> vec(SIZE);
for (int i = 0; i < SIZE; ++i) {
uint64_t val = 0;
while (val == 0) {
val = dist(rng);
}
vec[i] = val;
}
std::unordered_map<int, long double> map;
auto begin = std::chrono::high_resolution_clock::now();
for (int i = 0; i < SIZE; ++i) {
map[vec[i]] = 0.0;
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - begin);
std::cout << "inserts: " << elapsed.count() << std::endl;
std::random_shuffle(vec.begin(), vec.end());
begin = std::chrono::high_resolution_clock::now();
long double val;
for (int i = 0; i < SIZE; ++i) {
val = map[vec[i]];
}
end = std::chrono::high_resolution_clock::now();
elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - begin);
std::cout << "get: " << elapsed.count() << std::endl;(EDYCJA: cały kod źródłowy można znaleźć tutaj: http://pastebin.com/vPqf7eya )
Wynik dla std::unordered_mapto:
inserts: 35126
get : 2959Dla google::dense_map:
inserts: 3653
get : 816Dla naszej ręcznie obsługiwanej mapy współbieżnej (która blokuje, chociaż test porównawczy jest jednowątkowy - ale w oddzielnym wątku odradzania):
inserts: 5213
get : 2594Jeśli skompiluję program porównawczy bez obsługi pthread i uruchomię wszystko w głównym wątku, otrzymam następujące wyniki dla naszej ręcznie obsługiwanej mapy współbieżnej:
inserts: 4441
get : 1180Kompiluję za pomocą następującego polecenia:
g++-4.7 -O3 -DNDEBUG -I/tmp/benchmap/sparsehash-2.0.2/src/ -std=c++11 -pthread main.ccWięc szczególnie wkładki std::unordered_map mapach wydają się niezwykle kosztowne - 35 sekund vs 3-5 sekund na innych mapach. Również czas wyszukiwania wydaje się być dość długi.
Moje pytanie: dlaczego tak jest? Czytałem kolejne pytanie na temat stackoverflow, w którym ktoś pyta, dlaczego std::tr1::unordered_mapjest wolniejszy niż jego własna implementacja. Tam najwyżej oceniana odpowiedź stwierdza, że std::tr1::unordered_mapnależy zaimplementować bardziej skomplikowany interfejs. Ale nie widzę tego argumentu: używamy podejścia kubełkowego w naszej concurrent_map, std::unordered_mapużywamy również podejścia kubełkowego (google::dense_hash_map nie, ale niż std::unordered_mappowinno być co najmniej tak szybkie, jak nasza wersja bezpieczna dla współbieżności obsługiwana ręcznie?) Poza tym nie widzę w interfejsie niczego, co wymusza funkcję, która powoduje, że mapa hashowania działa źle ...
Więc moje pytanie: czy to prawda std::unordered_map wydaje się to być bardzo powolne? Jeśli nie: co się stało? Jeśli tak: jaki jest tego powód.
I moje główne pytanie: dlaczego wstawia się wartość do a std::unordered_map tak strasznie drogiego (nawet jeśli na początku zarezerwujemy wystarczająco dużo miejsca, nie działa dużo lepiej - więc ponowne haszowanie wydaje się nie być problemem)?
EDYTOWAĆ:
Po pierwsze: tak, prezentowany benchmark nie jest bezbłędny - to dlatego, że dużo się nim bawiliśmy i to po prostu hack (np. uint64Dystrybucja do generowania intów w praktyce nie byłaby dobrym pomysłem, wyklucz 0 w pętli jest trochę głupi itp ...).
W tej chwili większość komentarzy wyjaśnia, że mogę przyspieszyć unordered_map, przydzielając wcześniej wystarczającą ilość miejsca. W naszej aplikacji jest to po prostu niemożliwe: rozwijamy system zarządzania bazą danych i potrzebujemy mapy hashowej do przechowywania niektórych danych podczas transakcji (na przykład informacje o blokadach). Tak więc ta mapa może obejmować wszystko od 1 (użytkownik wykonuje tylko jedno wstawienie i zatwierdza) do miliardów wpisów (jeśli nastąpi pełne skanowanie tabeli). Po prostu niemożliwe jest wstępne przydzielenie wystarczającej ilości miejsca (a przydzielenie dużej ilości na początku zajmie zbyt dużo pamięci).
Ponadto przepraszam, że nie wyraziłem wystarczająco jasno swojego pytania: nie jestem zbyt zainteresowany szybkim tworzeniem unordered_map (używanie gęstej mapy hash Google działa dobrze dla nas), po prostu nie bardzo rozumiem, skąd biorą się te ogromne różnice w wydajności . Nie może to być tylko wstępna alokacja (nawet przy wystarczającej ilości wstępnie przydzielonej pamięci, gęsta mapa jest o rząd wielkości szybsza niż unordered_map, nasza ręcznie obsługiwana mapa współbieżna zaczyna się od tablicy o rozmiarze 64 - a więc mniejszej niż unordered_map).
Więc jaki jest powód tego złego występu std::unordered_map? Albo inaczej: czy można napisać implementację std::unordered_mapinterfejsu, która jest zgodna ze standardami i (prawie) tak szybka, jak gęsta mapa skrótów Google? A może jest w standardzie coś, co zmusza wdrażającego do wybrania nieefektywnego sposobu jego wdrożenia?
EDYCJA 2:
Dzięki profilowaniu widzę, że dzielenie liczb całkowitych zajmuje dużo czasu. std::unordered_mapużywa liczb pierwszych dla rozmiaru tablicy, podczas gdy inne implementacje używają potęgi dwójki. Dlaczego std::unordered_mapużywa się liczb pierwszych? Aby działać lepiej, jeśli hash jest zły? W przypadku dobrych haszów nie ma znaczenia.
EDYCJA 3:
Oto liczby dla std::map:
inserts: 16462
get : 16978Sooooooo: dlaczego wstawki są std::mapszybsze niż wstawki do std::unordered_map... mam na myśli WAT? std::mapma gorszą lokalizację (drzewo vs tablica), musi dokonać większej liczby alokacji (na wstawkę vs na powtórzenie + plus ~ 1 za każdą kolizję) i, co najważniejsze: ma inną złożoność algorytmiczną (O (logn) vs O (1))!
SIZE.