00001 #include "util/file.hh"
00002 #include "util/probing_hash_table.hh"
00003 #include "util/mmap.hh"
00004 #include "util/usage.hh"
00005
00006 #include <iostream>
00007
00008 namespace util {
00009 namespace {
00010
00011 struct Entry {
00012 typedef uint64_t Key;
00013 Key key;
00014 Key GetKey() const { return key; }
00015 };
00016
00017
00018 class URandom {
00019 public:
00020 URandom() :
00021 it_(buf_ + 1024), end_(buf_ + 1024),
00022 file_(util::OpenReadOrThrow("/dev/urandom")) {}
00023
00024 uint64_t Get() {
00025 if (it_ == end_) {
00026 it_ = buf_;
00027 util::ReadOrThrow(file_.get(), buf_, sizeof(buf_));
00028 it_ = buf_;
00029 }
00030 return *it_++;
00031 }
00032
00033 void Batch(uint64_t *begin, uint64_t *end) {
00034 util::ReadOrThrow(file_.get(), begin, (end - begin) * sizeof(uint64_t));
00035 }
00036
00037 private:
00038 uint64_t buf_[1024];
00039 uint64_t *it_, *end_;
00040
00041 util::scoped_fd file_;
00042 };
00043
00044 struct PrefetchEntry {
00045 uint64_t key;
00046 const Entry *pointer;
00047 };
00048
00049 template <class TableT, unsigned PrefetchSize> class PrefetchQueue {
00050 public:
00051 typedef TableT Table;
00052
00053 explicit PrefetchQueue(Table &table) : table_(table), cur_(0), twiddle_(false) {
00054 for (PrefetchEntry *i = entries_; i != entries_ + PrefetchSize; ++i)
00055 i->pointer = NULL;
00056 }
00057
00058 void Add(uint64_t key) {
00059 if (Cur().pointer) {
00060 twiddle_ ^= table_.FindFromIdeal(Cur().key, Cur().pointer);
00061 }
00062 Cur().key = key;
00063 Cur().pointer = table_.Ideal(key);
00064 __builtin_prefetch(Cur().pointer, 0, 0);
00065 Next();
00066 }
00067
00068 bool Drain() {
00069 if (Cur().pointer) {
00070 for (PrefetchEntry *i = &Cur(); i < entries_ + PrefetchSize; ++i) {
00071 twiddle_ ^= table_.FindFromIdeal(i->key, i->pointer);
00072 }
00073 }
00074 for (PrefetchEntry *i = entries_; i < &Cur(); ++i) {
00075 twiddle_ ^= table_.FindFromIdeal(i->key, i->pointer);
00076 }
00077 return twiddle_;
00078 }
00079
00080 private:
00081 PrefetchEntry &Cur() { return entries_[cur_]; }
00082 void Next() {
00083 ++cur_;
00084 cur_ = cur_ % PrefetchSize;
00085 }
00086
00087 Table &table_;
00088 PrefetchEntry entries_[PrefetchSize];
00089 std::size_t cur_;
00090
00091 bool twiddle_;
00092
00093 PrefetchQueue(const PrefetchQueue&);
00094 void operator=(const PrefetchQueue&);
00095 };
00096
00097 template <class TableT> class Immediate {
00098 public:
00099 typedef TableT Table;
00100
00101 explicit Immediate(Table &table) : table_(table), twiddle_(false) {}
00102
00103 void Add(uint64_t key) {
00104 typename Table::ConstIterator it;
00105 twiddle_ ^= table_.Find(key, it);
00106 }
00107
00108 bool Drain() const { return twiddle_; }
00109
00110 private:
00111 Table &table_;
00112 bool twiddle_;
00113 };
00114
00115 std::size_t Size(uint64_t entries, float multiplier = 1.5) {
00116 typedef util::ProbingHashTable<Entry, util::IdentityHash, std::equal_to<Entry::Key>, Power2Mod> Table;
00117
00118 return Power2Mod::RoundBuckets(Table::Size(entries, multiplier) / sizeof(Entry)) * sizeof(Entry);
00119 }
00120
00121 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) {
00122 std::size_t size = Size(entries, multiplier);
00123 scoped_memory backing;
00124 if (ordinary_malloc) {
00125 backing.reset(util::CallocOrThrow(size), size, scoped_memory::MALLOC_ALLOCATED);
00126 } else {
00127 util::HugeMalloc(size, true, backing);
00128 }
00129 typename Queue::Table table(backing.get(), size);
00130
00131 double start = CPUTime();
00132 for (uint64_t i = 0; i < entries; ++i) {
00133 Entry entry;
00134 entry.key = rn.Get();
00135 table.Insert(entry);
00136 }
00137 double inserted = CPUTime() - start;
00138 double before_lookup = CPUTime();
00139 Queue queue(table);
00140 for (const uint64_t *i = queries_begin; i != queries_end; ++i) {
00141 queue.Add(*i);
00142 }
00143 bool meaningless = queue.Drain();
00144 std::cout << ' ' << (inserted / static_cast<double>(entries)) << ' ' << (CPUTime() - before_lookup) / static_cast<double>(queries_end - queries_begin) << std::flush;
00145 return meaningless;
00146 }
00147
00148 bool TestRun(uint64_t lookups = 20000000, float multiplier = 1.5) {
00149 URandom rn;
00150 util::scoped_memory queries;
00151 HugeMalloc(lookups * sizeof(uint64_t), true, queries);
00152 rn.Batch(static_cast<uint64_t*>(queries.get()), static_cast<uint64_t*>(queries.get()) + lookups);
00153 uint64_t physical_mem_limit = util::GuessPhysicalMemory() / 2;
00154 bool meaningless = true;
00155 for (uint64_t i = 4; Size(i / multiplier) < physical_mem_limit; i *= 4) {
00156 std::cout << static_cast<std::size_t>(i / multiplier) << ' ' << Size(i / multiplier);
00157 typedef util::ProbingHashTable<Entry, util::IdentityHash, std::equal_to<Entry::Key>, Power2Mod> Table;
00158 typedef util::ProbingHashTable<Entry, util::IdentityHash, std::equal_to<Entry::Key>, DivMod> TableDiv;
00159 const uint64_t *const queries_begin = static_cast<const uint64_t*>(queries.get());
00160 meaningless ^= util::Test<Immediate<TableDiv> >(rn, i / multiplier, queries_begin, queries_begin + lookups, true, multiplier);
00161 meaningless ^= util::Test<Immediate<Table> >(rn, i / multiplier, queries_begin, queries_begin + lookups, true, multiplier);
00162 meaningless ^= util::Test<PrefetchQueue<Table, 4> >(rn, i / multiplier, queries_begin, queries_begin + lookups, true, multiplier);
00163 meaningless ^= util::Test<Immediate<Table> >(rn, i / multiplier, queries_begin, queries_begin + lookups, false, multiplier);
00164 meaningless ^= util::Test<PrefetchQueue<Table, 2> >(rn, i / multiplier, queries_begin, queries_begin + lookups, false, multiplier);
00165 meaningless ^= util::Test<PrefetchQueue<Table, 4> >(rn, i / multiplier, queries_begin, queries_begin + lookups, false, multiplier);
00166 meaningless ^= util::Test<PrefetchQueue<Table, 8> >(rn, i / multiplier, queries_begin, queries_begin + lookups, false, multiplier);
00167 meaningless ^= util::Test<PrefetchQueue<Table, 16> >(rn, i / multiplier, queries_begin, queries_begin + lookups, false, multiplier);
00168 std::cout << std::endl;
00169 }
00170 return meaningless;
00171 }
00172
00173 }
00174 }
00175
00176 int main() {
00177 bool meaningless = false;
00178 std::cout << "#CPU time\n";
00179 meaningless ^= util::TestRun();
00180 std::cerr << "Meaningless: " << meaningless << '\n';
00181 }