diff options
Diffstat (limited to 'util/probing_hash_table_benchmark_main.cc')
| -rw-r--r-- | util/probing_hash_table_benchmark_main.cc | 79 |
1 files changed, 52 insertions, 27 deletions
diff --git a/util/probing_hash_table_benchmark_main.cc b/util/probing_hash_table_benchmark_main.cc index c5129480f..583d21f5e 100644 --- a/util/probing_hash_table_benchmark_main.cc +++ b/util/probing_hash_table_benchmark_main.cc @@ -1,6 +1,6 @@ #include "util/file.hh" #include "util/probing_hash_table.hh" -#include "util/scoped.hh" +#include "util/mmap.hh" #include "util/usage.hh" #include <iostream> @@ -46,11 +46,12 @@ struct PrefetchEntry { const Entry *pointer; }; -const std::size_t kPrefetchSize = 4; -template <class Table> class PrefetchQueue { +template <class TableT, unsigned PrefetchSize> class PrefetchQueue { public: + typedef TableT Table; + explicit PrefetchQueue(Table &table) : table_(table), cur_(0), twiddle_(false) { - for (PrefetchEntry *i = entries_; i != entries_ + kPrefetchSize; ++i) + for (PrefetchEntry *i = entries_; i != entries_ + PrefetchSize; ++i) i->pointer = NULL; } @@ -66,7 +67,7 @@ template <class Table> class PrefetchQueue { bool Drain() { if (Cur().pointer) { - for (PrefetchEntry *i = &Cur(); i < entries_ + kPrefetchSize; ++i) { + for (PrefetchEntry *i = &Cur(); i < entries_ + PrefetchSize; ++i) { twiddle_ ^= table_.FindFromIdeal(i->key, i->pointer); } } @@ -80,11 +81,11 @@ template <class Table> class PrefetchQueue { PrefetchEntry &Cur() { return entries_[cur_]; } void Next() { ++cur_; - cur_ = cur_ % kPrefetchSize; + cur_ = cur_ % PrefetchSize; } Table &table_; - PrefetchEntry entries_[kPrefetchSize]; + PrefetchEntry entries_[PrefetchSize]; std::size_t cur_; bool twiddle_; @@ -93,12 +94,23 @@ template <class Table> class PrefetchQueue { void operator=(const PrefetchQueue&); }; -/*template <class Table> class Immediate { +template <class TableT> class Immediate { public: + typedef TableT Table; + + explicit Immediate(Table &table) : table_(table), twiddle_(false) {} + + void Add(uint64_t key) { + typename Table::ConstIterator it; + twiddle_ ^= table_.Find(key, it); + } + + bool Drain() const { return twiddle_; } private: Table &table_; -};*/ + bool twiddle_; +}; std::size_t Size(uint64_t entries, float multiplier = 1.5) { typedef util::ProbingHashTable<Entry, util::IdentityHash, std::equal_to<Entry::Key>, Power2Mod> Table; @@ -106,39 +118,54 @@ std::size_t Size(uint64_t entries, float multiplier = 1.5) { return Power2Mod::RoundBuckets(Table::Size(entries, multiplier) / sizeof(Entry)) * sizeof(Entry); } -template <class Mod> bool Test(URandom &rn, uint64_t entries, const uint64_t *const queries_begin, const uint64_t *const queries_end, float multiplier = 1.5) { - typedef util::ProbingHashTable<Entry, util::IdentityHash, std::equal_to<Entry::Key>, Mod> Table; +template <class Queue> bool Test(URandom &rn, uint64_t entries, const uint64_t *const queries_begin, const uint64_t *const queries_end, bool ordinary_malloc, float multiplier = 1.5) { std::size_t size = Size(entries, multiplier); - scoped_malloc backing(util::CallocOrThrow(size)); - Table table(backing.get(), size); + scoped_memory backing; + if (ordinary_malloc) { + backing.reset(util::CallocOrThrow(size), size, scoped_memory::MALLOC_ALLOCATED); + } else { + util::HugeMalloc(size, true, backing); + } + typename Queue::Table table(backing.get(), size); - double start = UserTime(); + double start = CPUTime(); for (uint64_t i = 0; i < entries; ++i) { Entry entry; entry.key = rn.Get(); table.Insert(entry); } - double inserted = UserTime() - start; - double before_lookup = UserTime(); - PrefetchQueue<Table> queue(table); + double inserted = CPUTime() - start; + double before_lookup = CPUTime(); + Queue queue(table); for (const uint64_t *i = queries_begin; i != queries_end; ++i) { queue.Add(*i); -/* typename Table::ConstIterator it; - meaningless ^= table.Find(*i, it);*/ } bool meaningless = queue.Drain(); - std::cout << entries << ' ' << size << ' ' << (inserted / static_cast<double>(entries)) << ' ' << (UserTime() - before_lookup) / static_cast<double>(queries_end - queries_begin) << '\n'; + std::cout << ' ' << (inserted / static_cast<double>(entries)) << ' ' << (CPUTime() - before_lookup) / static_cast<double>(queries_end - queries_begin) << std::flush; return meaningless; } -template <class Mod> bool TestRun(uint64_t lookups = 20000000, float multiplier = 1.5) { +bool TestRun(uint64_t lookups = 20000000, float multiplier = 1.5) { URandom rn; - util::scoped_malloc queries(util::CallocOrThrow(lookups * sizeof(uint64_t))); + util::scoped_memory queries; + HugeMalloc(lookups * sizeof(uint64_t), true, queries); rn.Batch(static_cast<uint64_t*>(queries.get()), static_cast<uint64_t*>(queries.get()) + lookups); uint64_t physical_mem_limit = util::GuessPhysicalMemory() / 2; bool meaningless = true; for (uint64_t i = 4; Size(i / multiplier) < physical_mem_limit; i *= 4) { - meaningless ^= util::Test<Mod>(rn, i / multiplier, static_cast<const uint64_t*>(queries.get()), static_cast<const uint64_t*>(queries.get()) + lookups, multiplier); + std::cout << static_cast<std::size_t>(i / multiplier) << ' ' << Size(i / multiplier); + typedef util::ProbingHashTable<Entry, util::IdentityHash, std::equal_to<Entry::Key>, Power2Mod> Table; + typedef util::ProbingHashTable<Entry, util::IdentityHash, std::equal_to<Entry::Key>, DivMod> TableDiv; + const uint64_t *const queries_begin = static_cast<const uint64_t*>(queries.get()); + meaningless ^= util::Test<Immediate<TableDiv> >(rn, i / multiplier, queries_begin, queries_begin + lookups, true, multiplier); + meaningless ^= util::Test<Immediate<Table> >(rn, i / multiplier, queries_begin, queries_begin + lookups, true, multiplier); + meaningless ^= util::Test<PrefetchQueue<Table, 4> >(rn, i / multiplier, queries_begin, queries_begin + lookups, true, multiplier); + meaningless ^= util::Test<Immediate<Table> >(rn, i / multiplier, queries_begin, queries_begin + lookups, false, multiplier); + meaningless ^= util::Test<PrefetchQueue<Table, 2> >(rn, i / multiplier, queries_begin, queries_begin + lookups, false, multiplier); + meaningless ^= util::Test<PrefetchQueue<Table, 4> >(rn, i / multiplier, queries_begin, queries_begin + lookups, false, multiplier); + meaningless ^= util::Test<PrefetchQueue<Table, 8> >(rn, i / multiplier, queries_begin, queries_begin + lookups, false, multiplier); + meaningless ^= util::Test<PrefetchQueue<Table, 16> >(rn, i / multiplier, queries_begin, queries_begin + lookups, false, multiplier); + std::cout << std::endl; } return meaningless; } @@ -148,9 +175,7 @@ template <class Mod> bool TestRun(uint64_t lookups = 20000000, float multiplier int main() { bool meaningless = false; - std::cout << "#Integer division\n"; - meaningless ^= util::TestRun<util::DivMod>(); - std::cout << "#Masking\n"; - meaningless ^= util::TestRun<util::Power2Mod>(); + std::cout << "#CPU time\n"; + meaningless ^= util::TestRun(); std::cerr << "Meaningless: " << meaningless << '\n'; } |