Czy implementacja gcc std :: unordered_map jest powolna? Jeśli tak - dlaczego?

100

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    : 2959

Dla google::dense_map:

inserts: 3653
get    : 816

Dla 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    : 2594

Jeś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    : 1180

Kompiluję za pomocą następującego polecenia:

g++-4.7 -O3 -DNDEBUG -I/tmp/benchmap/sparsehash-2.0.2/src/ -std=c++11 -pthread main.cc

Wię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    : 16978

Sooooooo: 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))!

Markus Pilman
źródło
1
Większość kontenerów w standardowym stanie jest BARDZO konserwatywna w swoich szacunkach. Spojrzałbym na liczbę segmentów, których używasz (określoną w konstruktorze) i zwiększyłem ją, aby uzyskać lepsze oszacowanie dla twojego SIZE.
Ylisar
Czy próbowałeś (aś) concurrent_hash_map z Intel TBB? threadingbuildingblocks.org/docs/help/reference/…
MadScientist
1
@MadScientist Rozważaliśmy TBB. Problem w licencjonowaniu: to projekt badawczy i nie jesteśmy jeszcze pewni, jak go opublikujemy (zdecydowanie open source - ale jeśli chcemy pozwolić na użycie w produkcie komercyjnym, to GPLv2 jest zbyt restrykcyjne). Jest to również inna zależność. Ale być może użyjemy go w późniejszym czasie, na razie możemy bez niego dobrze żyć.
Markus Pilman
1
Uruchomienie go pod profilerem, np. Valgrind, może być wnikliwe.
Maxim Egorushkin
1
Lokalność w tablicy mieszającej jest w najlepszym razie nieco lepsza niż lokalność w drzewie, przynajmniej jeśli funkcja skrótu jest „losowa”. Ta funkcja skrótu zapewnia rzadki dostęp do pobliskich przedmiotów w pobliżu. Jedyną zaletą, jaką masz, jest to, że tablica haszująca jest jednym ciągłym blokiem. To i tak może być prawdą w przypadku drzewa, jeśli sterta nie jest podzielona i tworzysz drzewo naraz. Gdy rozmiar będzie większy niż pamięć podręczna, różnice w lokalizacji będą miały niewielki lub żaden wpływ na wydajność.
Steve314

Odpowiedzi:

87

Znalazłem powód: jest to problem z gcc-4.7 !!

Dzięki gcc-4.7

inserts: 37728
get    : 2985

Dzięki gcc-4.6

inserts: 2531
get    : 1565

Tak więc std::unordered_mapw gcc-4.7 jest zepsuta (lub moja instalacja, która jest instalacją gcc-4.7.0 na Ubuntu - i inna instalacja, która jest gcc 4.7.1 na testach Debiana).

Prześlę raport o błędzie ... do tego czasu: NIE używaj std::unordered_mapz gcc 4.7!

Markus Pilman
źródło
Czy jest coś w delcie z 4.6, co mogłoby to spowodować?
Mark Canlas
30
Na liście mailingowej jest już raport. Dyskusja wydaje się wskazywać na „poprawki” w max_load_factorobsłudze, które doprowadziły do ​​różnicy w wydajności.
jxh
Zły czas na ten błąd! Otrzymałem bardzo słabe wyniki z unordered_map, ale cieszę się, że zostało to zgłoszone i "naprawione".
Bo Lu
+1 - Co za ssanie BBBBBUG .. Zastanawiam się, co się stanie z gcc-4.8.2
ikh
2
Jakieś aktualizacje tego błędu? Czy nadal istnieje dla późniejszych wersji GCC (5+)?
rph
21

Domyślam się, że nie masz odpowiedniego rozmiaru unordered_map, jak zasugerował Ylisar. Gdy łańcuchy rosną zbyt długo unordered_map, implementacja g ++ automatycznie przerzuci się na większą tablicę haszującą, co byłoby dużym spadkiem wydajności. Jeśli dobrze pamiętam, unordered_mapdomyślnie (najmniejsza liczba pierwsza większa niż) 100.

Nie miałem chronow swoim systemie, więc ustawiłem czas z times().

template <typename TEST>
void time_test (TEST t, const char *m) {
    struct tms start;
    struct tms finish;
    long ticks_per_second;

    times(&start);
    t();
    times(&finish);
    ticks_per_second = sysconf(_SC_CLK_TCK);
    std::cout << "elapsed: "
              << ((finish.tms_utime - start.tms_utime
                   + finish.tms_stime - start.tms_stime)
                  / (1.0 * ticks_per_second))
              << " " << m << std::endl;
}

Użyłem SIZEof 10000000i musiałem trochę zmienić rzeczy w mojej wersji boost. Zwróć również uwagę, że wstępnie dopasowałem rozmiar tabeli skrótów, aby dopasować SIZE/DEPTH, gdzie DEPTHjest oszacowana długość łańcucha wiader z powodu kolizji z skrótami.

Edycja: Howard zwraca mi uwagę w komentarzach, że maksymalny współczynnik obciążenia unordered_mapwynosi 1. Zatem DEPTHkontroluje, ile razy kod zostanie ponownie zhasowany.

#define SIZE 10000000
#define DEPTH 3
std::vector<uint64_t> vec(SIZE);
boost::mt19937 rng;
boost::uniform_int<uint64_t> dist(std::numeric_limits<uint64_t>::min(),
                                  std::numeric_limits<uint64_t>::max());
std::unordered_map<int, long double> map(SIZE/DEPTH);

void
test_insert () {
    for (int i = 0; i < SIZE; ++i) {
        map[vec[i]] = 0.0;
    }
}

void
test_get () {
    long double val;
    for (int i = 0; i < SIZE; ++i) {
        val = map[vec[i]];
    }
}

int main () {
    for (int i = 0; i < SIZE; ++i) {
        uint64_t val = 0;
        while (val == 0) {
            val = dist(rng);
        }
        vec[i] = val;
    }
    time_test(test_insert, "inserts");
    std::random_shuffle(vec.begin(), vec.end());
    time_test(test_insert, "get");
}

Edytować:

Zmodyfikowałem kod, aby móc DEPTHłatwiej zmieniać .

#ifndef DEPTH
#define DEPTH 10000000
#endif

Dlatego domyślnie wybierany jest najgorszy rozmiar tabeli skrótów.

elapsed: 7.12 inserts, elapsed: 2.32 get, -DDEPTH=10000000
elapsed: 6.99 inserts, elapsed: 2.58 get, -DDEPTH=1000000
elapsed: 8.94 inserts, elapsed: 2.18 get, -DDEPTH=100000
elapsed: 5.23 inserts, elapsed: 2.41 get, -DDEPTH=10000
elapsed: 5.35 inserts, elapsed: 2.55 get, -DDEPTH=1000
elapsed: 6.29 inserts, elapsed: 2.05 get, -DDEPTH=100
elapsed: 6.76 inserts, elapsed: 2.03 get, -DDEPTH=10
elapsed: 2.86 inserts, elapsed: 2.29 get, -DDEPTH=1

Mój wniosek jest taki, że nie ma zbyt dużej różnicy w wydajności dla jakiejkolwiek początkowej tabeli mieszania, poza wyrównaniem jej całkowitej oczekiwanej liczby unikalnych wstawień. Poza tym nie widzę różnicy w wydajności rzędu wielkości, którą obserwujesz.

jxh
źródło
6
std::unordered_mapma domyślny współczynnik maksymalnego obciążenia równy 1. Tak więc, z wyjątkiem początkowej liczby kubełków, GŁĘBOKOŚĆ jest ignorowana. Jeśli chcesz, możesz map.max_load_factor(DEPTH).
Howard Hinnant
@HowardHinnant: Dzięki za te informacje. Jest więc DEPTHignorowane, ale nadal kontroluje, jak często mapa będzie przekształcana w większą mapę. Odpowiedź została zaktualizowana i jeszcze raz dziękuję
jxh
@ user315052 Tak, wiem, że mogę to ulepszyć, nadając mu rozsądny rozmiar na początku - ale nie mogę tego zrobić w naszym oprogramowaniu (to projekt badawczy - DBMS - a tam nie wiem, ile wstawię) - może wynosić od 0 do 1 miliarda ...). Ale nawet z prealikacją jest wolniejszy niż nasza mapa i znacznie wolniejszy niż google dense_map - wciąż się zastanawiam, co powoduje dużą różnicę.
Markus Pilman
@MarkusPilman: Nie wiem, jak moje wyniki wypadają w porównaniu z twoimi, ponieważ nigdy nie podałeś, z jakim rozmiarem SIZEpracujesz. Mogę powiedzieć, że unordered_mapjest dwa razy szybszy przy DEPTHustawieniu na 1i odpowiednio wstępnie przydzielonym.
jxh
1
@MarkusPilman: Moje czasy są już w sekundach. Myślałem, że twoje czasy były w milisekundach. Jeśli wstawienia z DEPTHustawieniem na 1trwają mniej niż 3sekundy, w jaki sposób jest to o rząd wielkości wolniejsze?
jxh
3

Uruchomiłem twój kod na komputerze 64-bitowym / AMD / 4-rdzeniowym (2,1 GHz) i dało mi to następujące wyniki:

MinGW-W64 4.9.2:

Używanie std :: unordered_map:

inserts: 9280 
get: 3302

Używanie std :: map:

inserts: 23946
get: 24824

VC 2015 ze wszystkimi flagami optymalizacji, które znam:

Używanie std :: unordered_map:

inserts: 7289
get: 1908

Używanie std :: map:

inserts: 19222 
get: 19711

Nie testowałem kodu przy użyciu GCC, ale myślę, że może być porównywalny z wydajnością VC, więc jeśli to prawda, to GCC 4.9 std :: unordered_map nadal jest uszkodzony.

[EDYTOWAĆ]

A więc tak, jak ktoś powiedział w komentarzach, nie ma powodu, aby sądzić, że wydajność GCC 4.9.x byłaby porównywalna z wydajnością VC. Kiedy będę miał zmianę, będę testował kod na GCC.

Moja odpowiedź to po prostu stworzenie jakiejś bazy wiedzy dla innych odpowiedzi.

Christian Leon
źródło
„Nie testowałem kodu przy użyciu GCC, ale myślę, że może być porównywalny z wydajnością VC”. Całkowicie bezzasadne roszczenie, bez żadnej analizy porównawczej, porównywalnej z tą, którą można znaleźć w oryginalnym poście. Ta „odpowiedź” w żaden sposób nie odpowiada na pytanie, nie mówiąc już o odpowiedzi na pytanie „dlaczego”.
4ae1e1
2
„Nie testowałem kodu za pomocą GCC”… jak to się stało, że udało ci się zdobyć i używać MinGW, wiedząc o nim tak mało? MinGW jest zasadniczo ściśle śledzącym portem GCC.
underscore_d