C performansı çok kritik bir yazılım geliştiriyoruz . Orada eşzamanlı karma bir haritaya ihtiyacımız var ve uygulanıyor. Bir kriter bulmamız yazdım, yavaş eşzamanlı bizim karma harita nasıl std::unordered_map ile karşılaştırılır.

Ama, std::unordered_map sanırım inanılmaz yavaş... Yani bu bizim mikro-gösterge (için eşzamanlı haritası kökenli yeni bir iş emin olmak için kilitleme değil alın optimize ve unutmayın hiç inser 0 çünkü ben de kıyaslama google::dense_hash_map, ihtiyacı olan bir boş değer):

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;

(EDİT: kodu burada bulunabilir tüm kaynak: http://pastebin.com/vPqf7eya)

std::unordered_map sonuç:

inserts: 35126
get    : 2959

google::dense_map:

inserts: 3653
get    : 816

Bizim için eşzamanlı harita destekli kriter tek dişli - ama spawn ayrı bir konu olmasına rağmen kilitleme, yok ():

inserts: 5213
get    : 2594

Ben pthread desteği olmadan kıyaslama programı derlemek ve ana iş parçacığı her şeyi çalıştırın, el destekli eşzamanlı haritası aşağıdaki sonuçlar elde:

inserts: 4441
get    : 1180

Ben aşağıdaki komut ile derleme:

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

Bu yüzden özellikle std::unordered_map ekler son derece pahalı olması - 35 diğer Haritalar için saniye vs 3-5 saniye görünüyor. Ayrıca arama süresi oldukça yüksek gibi görünüyor.

Benim soru: neden bu? std::tr1::unordered_map kendi uygulaması daha yavaştır neden birisi sorar burada stackoverflow üzerinde başka bir soru okudum. std::tr1::unordered_map daha da karmaşık bir arabirim uygulamak için gereken en yüksek oranlı cevap Birleşik Devletleri,. Ama ben hiçbir şey göremiyorum bu argümanı kullanarak bir kova yaklaşım bizim concurrent_map, std::unordered_map kullanan bir kova yaklaşım da (google::dense_hash_map değil, ama daha std::unordered_map olmalı en azından daha hızlı elimizi destekli eşzamanlılık-güvenli sürüm?). Bunun dışında karma haritada kötü bir şekilde gerçekleştirmesi için bir özelliği güç arayüzü bir şey göremiyorum...

Yani benim soru: std::unordered_map çok yavaş gibi görünüyor, doğru mu? Yanlış bir şey mi? hayır ise: Bunun nedeni nedir. cevabınız evet ise:

Ve benim asıl sorum şu: neden takma bir değer haline bir std::unordered_map çok korkunç pahalı (bile saklı tutarız yeterli alan başına değil gerçekleştirmek çok daha iyi - yani ne gibi görünüyor değil sorun)?

DÜZENLEME:

Öncelikle: Evet sunulan kriter değildir kusursuz - bu çaldık çünkü etrafta bir sürü ve sadece bir hack (örneğin uint64 dağıtım oluşturmak için değer vermez ki pratik değil, iyi bir bir fikir, 0 hariç bir döngü, biraz aptalca gibi...).

Bu unordered_map daha hızlı bunun için yeterli alan preallocating olabilirim şu anda en çok yorum açıklar. Bu sadece mümkün değildir bizim uygulama: bir veritabanı yönetim sistemi geliştiriyoruz ve karma harita bir işlem sırasında bazı verileri saklamak için (örneğin bilgi kilitleme) gerekir. Bu harita girişleri ise tam tablo taraması edersek () milyarlarca 1-her kullanıcı sadece bir ekleme yapar ve tamamlar). Sadece imkansız yalnız, (ve sadece başında çok fazla bellek tüketir tahsis) önceden ayır.

Ayrıca, özür dilerim, ben yaptım değil devlet benim soru yeterince açık: benim umurumda değil yapma unordered_map hızlı (kullanarak googles yoğun karma harita sorunsuz çalışıyor bize), ben sadece bilmiyorum nerede bu büyük performans farklılıkları meydana geldi. Olabilir değil sadece preallocation (bile yeterince ön tahsis hafıza, yoğun göster bir sipariş büyüklüğü daha hızlı unordered_map, elimizi destekli eşzamanlı harita ile başlar ve bir dizi boyutu 64 - çok küçük bir daha unordered_map).

std::unordered_map bu kötü performansı nedeni nedir? Ya da farklı bir şekilde sordu: bir standart ve (neredeyse) kadar hızlı googles yoğun karma harita uygulayan std::unordered_map arabirimi uygulaması yazabilir? Ya orada uygulayıcısı verimsiz bir şekilde uygulamak için seçti zorlar standart bir şey mi?

EDİT 2:

Profil ile çok zaman tamsayı divions için kullanılan görüyorum. std::unordered_map diğer uygulamalar iki yetkileri kullanırken dizi boyutu için asal sayıları kullanır. Neden std::unordered_map asal sayıları kullanır? Karma olursa daha iyi gerçekleştirmek için kötü mü? İyi karma için hiçbir şey fark etmez bence.

EDİT 3:

Bu std::map rakamları:

inserts: 16462
get    : 16978

Neden std::unordered_map... ben bir daha ekler std::map daha hızlı bir anlamı ekler WAT? Sooooooo: std::map bir kötü konum (ağaç vs dizi), ihtiyaçları için daha fazla ayırma (başına Ekle vs başına ödeme ve artı ~1 için her çarpışma) ve en önemlisi: başka bir algoritmik karmaşıklık, (O(logn) vs O(1))!

Sebebini buldum: gcc-4.7! bir sorundur!

İlegcc-4.7

inserts: 37728
get    : 2985

İlegcc-4.6

inserts: 2531
get    : 1565

Gcc-4.7 std::unordered_map (veya Ubuntu gcc-4.7.0 bir yükleme - ve gcc debian test 4.7.1 olan başka bir yükleme olan benim yükleme) kırık.

Bir hata raporu o zamana kadar.. sunacağımı: gcc 4.7 ile! std::unordered_map kullanmayın