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

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!

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.

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.