Wir entwickeln eine hochleistungskritische Software in C ++. Dort benötigen wir eine gleichzeitige Hash-Map und implementieren eine. Also haben wir einen Benchmark geschrieben, um herauszufinden, mit wie viel langsamer unsere gleichzeitige Hash-Map verglichen wird std::unordered_map.

Aber es std::unordered_mapscheint unglaublich langsam zu sein ... Das ist also unser Mikro-Benchmark (für die gleichzeitige Karte haben wir einen neuen Thread erstellt, um sicherzustellen, dass das Sperren nicht wegoptimiert wird, und beachten Sie, dass ich niemals 0 einfüge, weil ich auch einen Benchmark mit google::dense_hash_map, welches einen Nullwert benötigt):

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;

(BEARBEITEN: Den gesamten Quellcode finden Sie hier: http://pastebin.com/vPqf7eya )

Das Ergebnis für std::unordered_mapist:

inserts: 35126
get    : 2959

Für google::dense_map:

inserts: 3653
get    : 816

Für unsere handgestützte gleichzeitige Karte (die sperrt, obwohl der Benchmark Single-Threaded ist - aber in einem separaten Spawn-Thread):

inserts: 5213
get    : 2594

Wenn ich das Benchmark-Programm ohne Pthread-Unterstützung kompiliere und alles im Hauptthread ausführe, erhalte ich die folgenden Ergebnisse für unsere handgestützte gleichzeitige Karte:

inserts: 4441
get    : 1180

Ich kompiliere mit folgendem Befehl:

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

Daher std::unordered_mapscheinen besonders Einfügungen extrem teuer zu sein - 35 Sekunden gegenüber 3-5 Sekunden für andere Karten. Auch die Suchzeit scheint ziemlich hoch zu sein.

Meine Frage: Warum ist das so? Ich habe eine andere Frage zum Stackoverflow gelesen, in der jemand fragt, warum sie std::tr1::unordered_maplangsamer ist als seine eigene Implementierung. Dort gibt die am höchsten bewertete Antwort an, dass std::tr1::unordered_mapeine kompliziertere Schnittstelle implementiert werden muss. Aber ich kann dieses Argument nicht sehen: Wir verwenden einen Bucket-Ansatz in unserer concurrent_map, std::unordered_mapverwenden auch einen Bucket-Ansatz ( google::dense_hash_mapnicht, aber als std::unordered_mapsollte er mindestens so schnell sein wie unsere handunterstützte, parallelitätssichere Version?). Abgesehen davon kann ich in der Benutzeroberfläche nichts sehen, was eine Funktion erzwingt, die die Leistung der Hash-Map beeinträchtigt ...

Also meine Frage: Stimmt es, dass std::unordered_mapes sehr langsam zu sein scheint? Wenn nein: was ist los? Wenn ja: Was ist der Grund dafür?

Und meine Hauptfrage: Warum ist das Einfügen eines Werts in einen std::unordered_mapso schrecklich teuren Wert (selbst wenn wir zu Beginn genügend Platz reservieren, funktioniert er nicht viel besser - also scheint das Aufwärmen nicht das Problem zu sein)?

BEARBEITEN:

Zuallererst: Ja, der vorgestellte Benchmark ist nicht fehlerfrei - das liegt daran, dass wir viel damit uint64herumgespielt haben und es nur ein Hack ist (zum Beispiel wäre die Verteilung zum Generieren von Ints in der Praxis keine gute Idee, 0 in einer Schleife auszuschließen ist irgendwie dumm etc ...).

Im Moment erklären die meisten Kommentare, dass ich die unordered_map schneller machen kann, indem ich genügend Speicherplatz dafür vorab zuweise. In unserer Anwendung ist dies einfach nicht möglich: Wir entwickeln ein Datenbankverwaltungssystem und benötigen eine Hash-Map, um einige Daten während einer Transaktion zu speichern (z. B. Sperren von Informationen). Diese Karte kann also alles von 1 (Benutzer macht nur eine Einfügung und Festschreibung) bis zu Milliarden von Einträgen (wenn vollständige Tabellenscans stattfinden) sein. Es ist einfach unmöglich, hier genügend Speicherplatz vorzuweisen (und am Anfang nur viel Speicherplatz zuzuweisen, verbraucht zu viel Speicher).

Außerdem entschuldige ich mich, dass ich meine Frage nicht klar genug formuliert habe: Ich bin nicht wirklich daran interessiert, unordered_map schnell zu machen (die Verwendung von Googles Densish Hash Map funktioniert gut für uns), ich verstehe nur nicht wirklich, woher diese enormen Leistungsunterschiede kommen . Es kann nicht nur eine Vorbelegung sein (selbst bei genügend vorbelegtem Speicher ist die dichte Karte eine Größenordnung schneller als unordered_map, unsere handgestützte gleichzeitige Karte beginnt mit einem Array der Größe 64 - also einem kleineren als unordered_map).

Was ist der Grund für diese schlechte Leistung von std::unordered_map? Oder anders gefragt: Könnte man eine Implementierung der std::unordered_mapSchnittstelle schreiben , die standardkonform und (fast) so schnell wie Googles ist? Oder enthält der Standard etwas, das den Implementierer dazu zwingt, einen ineffizienten Weg zur Implementierung zu wählen?

EDIT 2:

Durch die Profilerstellung sehe ich, dass viel Zeit für ganzzahlige Divisionen verwendet wird. std::unordered_mapverwendet Primzahlen für die Arraygröße, während die anderen Implementierungen Zweierpotenzen verwenden. Warum std::unordered_mapwerden Primzahlen verwendet? Um eine bessere Leistung zu erzielen, wenn der Hash schlecht ist? Für gute Hashes macht es imho keinen Unterschied.

EDIT 3:

Dies sind die Zahlen für std::map:

inserts: 16462
get    : 16978

Sooooooo: Warum sind Einfügungen in eine std::mapschneller als Einfügungen in eine std::unordered_map... Ich meine WAT? std::maphat eine schlechtere Lokalität (Baum gegen Array), muss mehr Zuordnungen vornehmen (pro Einfügung gegen pro Wiederaufbereitung + plus ~ 1 für jede Kollision) und, was am wichtigsten ist: hat eine andere algorithmische Komplexität (O (logn) gegen O (1))!

Ich habe den Grund gefunden: Es ist ein Problem von gcc-4.7 !!

Mit gcc-4.7

inserts: 37728
get    : 2985

Mit gcc-4.6

inserts: 2531
get    : 1565

Also std::unordered_mapin gcc-4.7 ist kaputt (oder meine Installation, die eine Installation von gcc-4.7.0 unter Ubuntu ist - und eine andere Installation, die gcc 4.7.1 beim Debian-Testen ist).

Ich werde einen Fehlerbericht einreichen. Bis dahin: NICHT std::unordered_mapmit gcc 4.7 verwenden!

Ich unordered_mapvermute, dass Sie Ihre Größe nicht richtig bemessen haben , wie Ylisar vorgeschlagen hat. Wenn Ketten zu lang werden unordered_map, wird die g ++ - Implementierung automatisch in eine größere Hash-Tabelle umgewandelt, was die Leistung erheblich beeinträchtigt. Wenn ich mich richtig erinnere, ist der unordered_mapStandardwert (kleinste Primzahl größer als) 100.

Ich hatte nicht chronoauf meinem System, also habe ich mit abgestimmt 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;
}

Ich habe ein SIZEvon verwendet 10000000und musste die Dinge für meine Version von ein wenig ändern boost. Beachten Sie auch, dass ich die Hash-Tabelle vorab so angepasst habe SIZE/DEPTH, dass sie DEPTHeine Schätzung der Länge der Bucket-Kette aufgrund von Hash-Kollisionen enthält.

Bearbeiten: Howard weist mich in Kommentaren darauf hin, dass der maximale Auslastungsfaktor für unordered_mapist 1. Die DEPTHSteuerung steuert also, wie oft der Code erneut aufbereitet wird.

#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");
}

Bearbeiten:

Ich habe den Code geändert, damit ich ihn DEPTHleichter ändern kann.

#ifndef DEPTH
#define DEPTH 10000000
#endif

Daher wird standardmäßig die schlechteste Größe für die Hash-Tabelle ausgewählt.

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

Mein Fazit ist, dass es keinen signifikanten Leistungsunterschied für eine anfängliche Hash-Tabellengröße gibt, außer dass sie der gesamten erwarteten Anzahl eindeutiger Einfügungen entspricht. Außerdem sehe ich keinen Leistungsunterschied in der Größenordnung, den Sie beobachten.

Ich habe Ihren Code mit einem 64-Bit / AMD / 4-Kerne-Computer (2,1 GHz) ausgeführt und dabei die folgenden Ergebnisse erzielt:

MinGW-W64 4.9.2:

Verwenden von std :: unordered_map:

inserts: 9280 
get: 3302

Verwenden von std :: map:

inserts: 23946
get: 24824

VC 2015 mit allen mir bekannten Optimierungsflags:

Verwenden von std :: unordered_map:

inserts: 7289
get: 1908

Verwenden von std :: map:

inserts: 19222 
get: 19711

Ich habe den Code nicht mit GCC getestet, aber ich denke, er ist möglicherweise mit der Leistung von VC vergleichbar. Wenn dies zutrifft, ist GCC 4.9 std :: unordered_map immer noch fehlerhaft.

[BEARBEITEN]

Also ja, wie jemand in den Kommentaren sagte, gibt es keinen Grund zu der Annahme, dass die Leistung von GCC 4.9.x mit der VC-Leistung vergleichbar wäre. Wenn ich die Änderung habe, werde ich den Code auf GCC testen.

Meine Antwort ist nur, eine Art Wissensbasis für andere Antworten aufzubauen.