Kami sedang mengembangkan perangkat lunak kritis berkinerja tinggi dalam C ++. Di sana kita membutuhkan peta hash bersamaan dan menerapkannya. Jadi kami menulis patokan untuk mencari tahu, seberapa lambat peta hash serentak kami dibandingkan std::unordered_map.

Tapi, std::unordered_mapsepertinya sangat lambat ... Jadi ini adalah tolok ukur mikro kami (untuk peta bersamaan kami menghasilkan utas baru untuk memastikan bahwa penguncian tidak dioptimalkan dan perhatikan bahwa saya tidak pernah memasukkan 0 karena saya juga melakukan tolok ukur dengan google::dense_hash_map, yang membutuhkan nilai nol):

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;

(EDIT: seluruh kode sumber dapat ditemukan di sini: http://pastebin.com/vPqf7eya )

Hasil untuk std::unordered_mapadalah:

inserts: 35126
get    : 2959

Untuk google::dense_map:

inserts: 3653
get    : 816

Untuk peta serentak yang didukung tangan kami (yang mengunci, meskipun tolok ukurnya adalah utas tunggal - tetapi dalam utas pemijahan terpisah):

inserts: 5213
get    : 2594

Jika saya mengkompilasi program benchmark tanpa dukungan pthread dan menjalankan semuanya di utas utama, saya mendapatkan hasil berikut untuk peta konkuren yang didukung tangan kami:

inserts: 4441
get    : 1180

Saya mengkompilasi dengan perintah berikut:

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

Jadi khususnya sisipan std::unordered_maptampaknya sangat mahal - 35 detik vs 3-5 detik untuk peta lain. Juga waktu pencarian tampaknya cukup tinggi.

Pertanyaan saya: mengapa demikian? Saya membaca pertanyaan lain tentang stackoverflow di mana seseorang bertanya, mengapa std::tr1::unordered_maplebih lambat dari implementasinya sendiri. Di sana nilai jawaban tertinggi menyatakan, bahwa std::tr1::unordered_mapkebutuhan untuk mengimplementasikan antarmuka yang lebih rumit. Tapi saya tidak bisa melihat argumen ini: kami menggunakan pendekatan ember di concurrent_map kami, std::unordered_mapmenggunakan pendekatan ember juga ( google::dense_hash_maptidak, tetapi std::unordered_mapsetidaknya harus secepatnya daripada versi aman konkurensi yang didukung tangan?). Selain itu, saya tidak dapat melihat apa pun di antarmuka yang memaksa fitur yang membuat peta hash berkinerja buruk ...

Jadi pertanyaan saya: apakah benar itu std::unordered_mapterlihat sangat lambat? Jika tidak: apa yang salah? Jika ya: apa alasannya.

Dan pertanyaan utama saya: mengapa memasukkan nilai menjadi std::unordered_mapsangat mahal (bahkan jika kita memesan cukup ruang di awal, itu tidak bekerja jauh lebih baik - jadi mengulangi tampaknya tidak menjadi masalah)?

EDIT:

Pertama-tama: ya, tolok ukur yang disajikan tidak sempurna - ini karena kami sering bermain-main dengannya dan itu hanya peretasan (misalnya uint64distribusi untuk menghasilkan int pada praktiknya bukan ide yang baik, kecualikan 0 dalam satu lingkaran agak bodoh dll ...).

Saat ini sebagian besar komentar menjelaskan, bahwa saya dapat membuat unordered_map lebih cepat dengan mengalokasikan ruang yang cukup untuk itu. Dalam aplikasi kami ini tidak mungkin: kami sedang mengembangkan sistem manajemen database dan membutuhkan peta hash untuk menyimpan beberapa data selama transaksi (misalnya mengunci informasi). Jadi peta ini dapat terdiri dari 1 (pengguna hanya membuat satu penyisipan dan melakukan) hingga miliaran entri (jika pemindaian tabel lengkap terjadi). Tidak mungkin mengalokasikan cukup ruang di sini (dan mengalokasikan banyak di awal akan menghabiskan terlalu banyak memori).

Selain itu, saya minta maaf, karena saya tidak menyatakan pertanyaan saya dengan cukup jelas: Saya tidak terlalu tertarik untuk membuat unordered_map dengan cepat (menggunakan peta hash padat googles bekerja dengan baik untuk kami), saya hanya tidak begitu mengerti dari mana perbedaan kinerja yang besar ini berasal . Ini tidak bisa hanya pra-alokasi (bahkan dengan memori yang cukup dialokasikan, peta padat adalah urutan besarnya lebih cepat daripada unordered_map, peta konkuren yang didukung tangan dimulai dengan larik berukuran 64 - jadi lebih kecil dari unordered_map).

Jadi apa alasan dari kinerja buruk ini std::unordered_map? Atau ditanyakan secara berbeda: Bisakah seseorang menulis implementasi std::unordered_mapantarmuka yang sesuai standar dan (hampir) secepat peta hash padat Google? Atau adakah sesuatu dalam standar yang memaksa pelaksana untuk memilih cara yang tidak efisien untuk mengimplementasikannya?

EDIT 2:

Dengan membuat profil saya melihat bahwa banyak waktu digunakan untuk divions integer. std::unordered_mapmenggunakan bilangan prima untuk ukuran larik, sedangkan implementasi lainnya menggunakan pangkat dua. Mengapa std::unordered_mapmenggunakan bilangan prima? Untuk tampil lebih baik jika hashnya buruk? Untuk hash yang bagus, tidak ada bedanya.

EDIT 3:

Ini adalah angka-angka untuk std::map:

inserts: 16462
get    : 16978

Sooooooo: mengapa menyisipkan menjadi std::maplebih cepat daripada menyisipkan ke std::unordered_map... maksud saya WAT? std::mapmemiliki lokalitas yang lebih buruk (pohon vs larik), perlu membuat lebih banyak alokasi (per penyisipan vs per rehash + plus ~ 1 untuk setiap tabrakan) dan, yang paling penting: memiliki kompleksitas algoritme lain (O (logn) vs O (1))!

Saya menemukan alasannya: ini adalah Masalah gcc-4.7 !!

Dengan gcc-4.7

inserts: 37728
get    : 2985

Dengan gcc-4.6

inserts: 2531
get    : 1565

Jadi std::unordered_mapdi gcc-4.7 rusak (atau instalasi saya, yang merupakan instalasi gcc-4.7.0 di Ubuntu - dan instalasi lain yaitu gcc 4.7.1 pada pengujian debian).

Saya akan mengirimkan laporan bug .. sampai saat itu: JANGAN gunakan std::unordered_mapdengan gcc 4.7!

Saya menduga Anda belum unordered_mapmengukur Anda dengan benar , seperti yang disarankan Ylisar. Jika rantai tumbuh terlalu lama unordered_map, implementasi g ++ akan otomatis diulang ke tabel hash yang lebih besar, dan ini akan menjadi hambatan besar pada kinerja. Jika saya ingat dengan benar, unordered_mapdefaultnya adalah (bilangan prima terkecil lebih besar dari) 100.

Saya tidak punya chronodi sistem saya, jadi saya mengatur waktunya 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;
}

Saya menggunakan SIZEdari 10000000, dan harus mengubah sedikit untuk versi saya boost. Perhatikan juga, saya melakukan pra-ukuran tabel hash agar sesuai SIZE/DEPTH, di mana DEPTHperkiraan panjang rantai ember karena tabrakan hash.

Sunting: Howard menunjukkan kepada saya dalam komentar bahwa faktor beban maksimum unordered_mapadalah 1. Jadi, DEPTHkontrol berapa kali kode akan diulang.

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

Edit:

Saya memodifikasi kodenya sehingga saya bisa mengganti DEPTHdengan lebih mudah.

#ifndef DEPTH
#define DEPTH 10000000
#endif

Jadi, secara default, ukuran terburuk untuk tabel hash dipilih.

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

Kesimpulan saya adalah bahwa tidak ada banyak perbedaan kinerja yang signifikan untuk setiap ukuran tabel hash awal selain membuatnya sama dengan seluruh jumlah penyisipan unik yang diharapkan. Selain itu, saya tidak melihat urutan perbedaan kinerja besarnya yang Anda amati.

Saya telah menjalankan kode Anda menggunakan komputer 64 bit / AMD / 4 core (2.1GHz) dan itu memberi saya hasil sebagai berikut:

MinGW-W64 4.9.2:

Menggunakan std :: unordered_map:

inserts: 9280 
get: 3302

Menggunakan std :: map:

inserts: 23946
get: 24824

VC 2015 dengan semua tanda pengoptimalan yang saya tahu:

Menggunakan std :: unordered_map:

inserts: 7289
get: 1908

Menggunakan std :: map:

inserts: 19222 
get: 19711

Saya belum menguji kodenya menggunakan GCC tetapi menurut saya mungkin sebanding dengan kinerja VC, jadi jika itu benar, maka GCC 4.9 std :: unordered_map masih rusak.

[EDIT]

Jadi ya, seperti yang dikatakan seseorang di komentar, tidak ada alasan untuk berpikir bahwa kinerja GCC 4.9.x akan sebanding dengan kinerja VC. Ketika saya memiliki perubahan, saya akan menguji kode di GCC.

Jawaban saya hanya untuk membangun semacam basis pengetahuan untuk jawaban lain.