From 02d4f862b3111d9b715bdb4b8ebe536ab5880887 Mon Sep 17 00:00:00 2001 From: Henning Baldersheim Date: Wed, 28 Nov 2018 18:01:27 +0100 Subject: Randomize keys --- vespalib/src/tests/stllike/lookup_benchmark.cpp | 14 +++++++++----- 1 file changed, 9 insertions(+), 5 deletions(-) diff --git a/vespalib/src/tests/stllike/lookup_benchmark.cpp b/vespalib/src/tests/stllike/lookup_benchmark.cpp index 1145a110fa2..98aff9cd4ce 100644 --- a/vespalib/src/tests/stllike/lookup_benchmark.cpp +++ b/vespalib/src/tests/stllike/lookup_benchmark.cpp @@ -1,7 +1,7 @@ // Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. -#include -#include -#include +#include +#include +#include #include #include #include @@ -20,6 +20,10 @@ void fill(S & s, size_t count) template size_t lookup_bench(S & s, size_t count, size_t rep) { + std::vector keys(count); + for (uint32_t & key : keys) { + key = rand()%count; + } size_t sum(0); typename S::const_iterator e(s.end()); for (size_t j(0); j < rep; j++) { @@ -72,10 +76,10 @@ int main(int argc, char *argv[]) type = argv[1][0]; } if (argc >= 3) { - count = strtoul(argv[2], NULL, 0); + count = strtoul(argv[2], nullptr, 0); } if (argc >= 4) { - rep = strtoul(argv[3], NULL, 0); + rep = strtoul(argv[3], nullptr, 0); } std::vector description(256); description['m'] = "std::set"; -- cgit v1.2.3 From 190fa93b41aaca71a9f7fc84a3856a79fc40444d Mon Sep 17 00:00:00 2001 From: Henning Baldersheim Date: Wed, 28 Nov 2018 17:52:49 +0000 Subject: Also test with hash_map --- vespalib/src/tests/stllike/lookup_benchmark.cpp | 36 +++++++++++++++++++++++-- 1 file changed, 34 insertions(+), 2 deletions(-) diff --git a/vespalib/src/tests/stllike/lookup_benchmark.cpp b/vespalib/src/tests/stllike/lookup_benchmark.cpp index 98aff9cd4ce..4f65bebe560 100644 --- a/vespalib/src/tests/stllike/lookup_benchmark.cpp +++ b/vespalib/src/tests/stllike/lookup_benchmark.cpp @@ -8,6 +8,7 @@ #include #include #include +#include template void fill(S & s, size_t count) @@ -17,6 +18,14 @@ void fill(S & s, size_t count) } } +template +void fillM(M & m, size_t count) +{ + for(size_t i(0); i < count; i++) { + m[i] = i; + } +} + template size_t lookup_bench(S & s, size_t count, size_t rep) { @@ -43,6 +52,13 @@ size_t bench(S & set, size_t sz, size_t numLookups) return lookup_bench(set, sz, numLookups/sz); } +template +size_t benchM(M & map, size_t sz, size_t numLookups) +{ + fillM(map, sz); + return lookup_bench(map, sz, numLookups/sz); +} + size_t benchMap(size_t sz, size_t numLookups) { std::set set; @@ -57,16 +73,28 @@ size_t benchHashStl(size_t sz, size_t numLookups) size_t benchHashVespaLib(size_t sz, size_t numLookups) { - vespalib::hash_set set; + vespalib::hash_set set(3*sz); return bench(set, sz, numLookups); } size_t benchHashVespaLib2(size_t sz, size_t numLookups) { - vespalib::hash_set, std::equal_to, vespalib::hashtable_base::and_modulator > set; + vespalib::hash_set, std::equal_to, vespalib::hashtable_base::and_modulator > set(3*sz); return bench(set, sz, numLookups); } +size_t benchHashMapVespaLib(size_t sz, size_t numLookups) +{ + vespalib::hash_map set(3*sz); + return benchM(set, sz, numLookups); +} + +size_t benchHashMapVespaLib2(size_t sz, size_t numLookups) +{ + vespalib::hash_map, std::equal_to, vespalib::hashtable_base::and_modulator > set(3*sz); + return benchM(set, sz, numLookups); +} + int main(int argc, char *argv[]) { size_t count(1000); @@ -86,12 +114,16 @@ int main(int argc, char *argv[]) description['h'] = "std::hash_set"; description['g'] = "vespalib::hash_set"; description['G'] = "vespalib::hash_set with simple and modulator."; + description['k'] = "vespalib::hash_map"; + description['K'] = "vespalib::hash_map with simple and modulator."; size_t found(0); switch (type) { case 'm': found = benchMap(count, rep); break; case 'h': found = benchHashStl(count, rep); break; case 'g': found = benchHashVespaLib(count, rep); break; case 'G': found = benchHashVespaLib2(count, rep); break; + case 'k': found = benchHashMapVespaLib(count, rep); break; + case 'K': found = benchHashMapVespaLib2(count, rep); break; default: printf("'m' = %s\n", description[type]); printf("'h' = %s\n", description[type]); -- cgit v1.2.3 From d88040df6fece52b15a5fe27a3777016069de97d Mon Sep 17 00:00:00 2001 From: Henning Baldersheim Date: Wed, 28 Nov 2018 18:59:53 +0100 Subject: Reserve a large hashmap to reduce number of collisions. --- searchlib/src/vespa/searchlib/attribute/enumattribute.hpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/searchlib/src/vespa/searchlib/attribute/enumattribute.hpp b/searchlib/src/vespa/searchlib/attribute/enumattribute.hpp index 6a5777b5696..527b869431d 100644 --- a/searchlib/src/vespa/searchlib/attribute/enumattribute.hpp +++ b/searchlib/src/vespa/searchlib/attribute/enumattribute.hpp @@ -104,7 +104,7 @@ EnumAttribute::insertNewUniqueValues(EnumStoreBase::IndexVector & newIndexes) this->_enumStore.getPendingCompact()) { this->removeAllOldGenerations(); this->_enumStore.clearPendingCompact(); - EnumIndexMap old2New(this->_enumStore.getNumUniques()); + EnumIndexMap old2New(this->_enumStore.getNumUniques()*3); if (!this->_enumStore.performCompaction(extraBytesNeeded, old2New)) { // fallback to resize strategy this->_enumStore.fallbackResize(extraBytesNeeded); -- cgit v1.2.3 From 01a55c11e32198bad0f18921b1b9943735c00fcd Mon Sep 17 00:00:00 2001 From: Henning Baldersheim Date: Wed, 28 Nov 2018 19:01:05 +0100 Subject: Use a simple and instead of div for modulo operation. --- searchlib/src/vespa/searchlib/attribute/enumstorebase.h | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/searchlib/src/vespa/searchlib/attribute/enumstorebase.h b/searchlib/src/vespa/searchlib/attribute/enumstorebase.h index 70cb6abc0ea..6b5ba3eca56 100644 --- a/searchlib/src/vespa/searchlib/attribute/enumstorebase.h +++ b/searchlib/src/vespa/searchlib/attribute/enumstorebase.h @@ -166,7 +166,8 @@ public: typedef EnumStoreIndex Index; typedef EnumStoreIndexVector IndexVector; typedef EnumStoreEnumVector EnumVector; - using EnumIndexMap = vespalib::hash_map; + using EnumIndexMap = vespalib::hash_map, std::equal_to, + vespalib::hashtable_base::and_modulator>; class EntryBase { protected: -- cgit v1.2.3 From 13b0ebdd56a3c875ed3a9abd0f3abd8d574db61c Mon Sep 17 00:00:00 2001 From: Henning Baldersheim Date: Wed, 28 Nov 2018 19:04:12 +0100 Subject: Follow template instantiation. --- searchlib/src/vespa/searchlib/attribute/enumstorebase.cpp | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/searchlib/src/vespa/searchlib/attribute/enumstorebase.cpp b/searchlib/src/vespa/searchlib/attribute/enumstorebase.cpp index f829016fd30..20c66993486 100644 --- a/searchlib/src/vespa/searchlib/attribute/enumstorebase.cpp +++ b/searchlib/src/vespa/searchlib/attribute/enumstorebase.cpp @@ -636,4 +636,6 @@ namespace attribute { } -template class vespalib::hash_map; +template class vespalib::hash_map, std::equal_to, + vespalib::hashtable_base::and_modulator>; -- cgit v1.2.3