ceph/src/rocksdb/utilities/persistent_cache/hash_table_bench.cc

   1 //  Copyright (c) 2013, Facebook, Inc.  All rights reserved.
   2 //  This source code is licensed under the BSD-style license found in the
   3 //  LICENSE file in the root directory of this source tree. An additional grant
   4 //  of patent rights can be found in the PATENTS file in the same directory.
   5 //
   6
   7 #if !defined(OS_WIN) && !defined(ROCKSDB_LITE)
   8
   9 #ifndef GFLAGS
  10 #include <cstdio>
  11 int main() { fprintf(stderr, "Please install gflags to run tools\n"); }
  12 #else
  13 #include <gflags/gflags.h>
  14
  15 #include <atomic>
  16 #include <functional>
  17 #include <string>
  18 #include <unordered_map>
  19
  20 #include "port/port_posix.h"
  21 #include "rocksdb/env.h"
  22 #include "util/mutexlock.h"
  23 #include "utilities/persistent_cache/hash_table.h"
  24
  25 using std::string;
  26
  27 DEFINE_int32(nsec, 10, "nsec");
  28 DEFINE_int32(nthread_write, 1, "insert %");
  29 DEFINE_int32(nthread_read, 1, "lookup %");
  30 DEFINE_int32(nthread_erase, 1, "erase %");
  31
  32 namespace rocksdb {
  33
  34 //
  35 // HashTableImpl interface
  36 //
  37 // Abstraction of a hash table implementation
  38 template <class Key, class Value>
  39 class HashTableImpl {
  40  public:
  41   virtual ~HashTableImpl() {}
  42
  43   virtual bool Insert(const Key& key, const Value& val) = 0;
  44   virtual bool Erase(const Key& key) = 0;
  45   virtual bool Lookup(const Key& key, Value* val) = 0;
  46 };
  47
  48 // HashTableBenchmark
  49 //
  50 // Abstraction to test a given hash table implementation. The test mostly
  51 // focus on insert, lookup and erase. The test can operate in test mode and
  52 // benchmark mode.
  53 class HashTableBenchmark {
  54  public:
  55   explicit HashTableBenchmark(HashTableImpl<size_t, std::string>* impl,
  56                               const size_t sec = 10,
  57                               const size_t nthread_write = 1,
  58                               const size_t nthread_read = 1,
  59                               const size_t nthread_erase = 1)
  60       : impl_(impl),
  61         sec_(sec),
  62         ninserts_(0),
  63         nreads_(0),
  64         nerases_(0),
  65         nerases_failed_(0),
  66         quit_(false) {
  67     Prepop();
  68
  69     StartThreads(nthread_write, WriteMain);
  70     StartThreads(nthread_read, ReadMain);
  71     StartThreads(nthread_erase, EraseMain);
  72
  73     uint64_t start = NowInMillSec();
  74     while (!quit_) {
  75       quit_ = NowInMillSec() - start > sec_ * 1000;
  76       /* sleep override */ sleep(1);
  77     }
  78
  79     Env* env = Env::Default();
  80     env->WaitForJoin();
  81
  82     if (sec_) {
  83       printf("Result \n");
  84       printf("====== \n");
  85       printf("insert/sec = %f \n", ninserts_ / static_cast<double>(sec_));
  86       printf("read/sec = %f \n", nreads_ / static_cast<double>(sec_));
  87       printf("erases/sec = %f \n", nerases_ / static_cast<double>(sec_));
  88       const uint64_t ops = ninserts_ + nreads_ + nerases_;
  89       printf("ops/sec = %f \n", ops / static_cast<double>(sec_));
  90       printf("erase fail = %d (%f%%)\n", static_cast<int>(nerases_failed_),
  91              static_cast<float>(nerases_failed_ / nerases_ * 100));
  92       printf("====== \n");
  93     }
  94   }
  95
  96   void RunWrite() {
  97     while (!quit_) {
  98       size_t k = insert_key_++;
  99       std::string tmp(1000, k % 255);
 100       bool status = impl_->Insert(k, tmp);
 101       assert(status);
 102       ninserts_++;
 103     }
 104   }
 105
 106   void RunRead() {
 107     Random64 rgen(time(nullptr));
 108     while (!quit_) {
 109       std::string s;
 110       size_t k = rgen.Next() % max_prepop_key;
 111       bool status = impl_->Lookup(k, &s);
 112       assert(status);
 113       assert(s == std::string(1000, k % 255));
 114       nreads_++;
 115     }
 116   }
 117
 118   void RunErase() {
 119     while (!quit_) {
 120       size_t k = erase_key_++;
 121       bool status = impl_->Erase(k);
 122       nerases_failed_ += !status;
 123       nerases_++;
 124     }
 125   }
 126
 127  private:
 128   // Start threads for a given function
 129   void StartThreads(const size_t n, void (*fn)(void*)) {
 130     Env* env = Env::Default();
 131     for (size_t i = 0; i < n; ++i) {
 132       env->StartThread(fn, this);
 133     }
 134   }
 135
 136   // Prepop the hash table with 1M keys
 137   void Prepop() {
 138     for (size_t i = 0; i < max_prepop_key; ++i) {
 139       bool status = impl_->Insert(i, std::string(1000, i % 255));
 140       assert(status);
 141     }
 142
 143     erase_key_ = insert_key_ = max_prepop_key;
 144
 145     for (size_t i = 0; i < 10 * max_prepop_key; ++i) {
 146       bool status = impl_->Insert(insert_key_++, std::string(1000, 'x'));
 147       assert(status);
 148     }
 149   }
 150
 151   static uint64_t NowInMillSec() {
 152     timeval tv;
 153     gettimeofday(&tv, /*tz=*/nullptr);
 154     return tv.tv_sec * 1000 + tv.tv_usec / 1000;
 155   }
 156
 157   //
 158   //  Wrapper functions for thread entry
 159   //
 160   static void WriteMain(void* args) {
 161     reinterpret_cast<HashTableBenchmark*>(args)->RunWrite();
 162   }
 163
 164   static void ReadMain(void* args) {
 165     reinterpret_cast<HashTableBenchmark*>(args)->RunRead();
 166   }
 167
 168   static void EraseMain(void* args) {
 169     reinterpret_cast<HashTableBenchmark*>(args)->RunErase();
 170   }
 171
 172   HashTableImpl<size_t, std::string>* impl_;         // Implementation to test
 173   const size_t sec_;                                 // Test time
 174   const size_t max_prepop_key = 1ULL * 1024 * 1024;  // Max prepop key
 175   std::atomic<size_t> insert_key_;                   // Last inserted key
 176   std::atomic<size_t> erase_key_;                    // Erase key
 177   std::atomic<size_t> ninserts_;                     // Number of inserts
 178   std::atomic<size_t> nreads_;                       // Number of reads
 179   std::atomic<size_t> nerases_;                      // Number of erases
 180   std::atomic<size_t> nerases_failed_;               // Number of erases failed
 181   bool quit_;  // Should the threads quit ?
 182 };
 183
 184 //
 185 // SimpleImpl
 186 // Lock safe unordered_map implementation
 187 class SimpleImpl : public HashTableImpl<size_t, string> {
 188  public:
 189   bool Insert(const size_t& key, const string& val) override {
 190     WriteLock _(&rwlock_);
 191     map_.insert(make_pair(key, val));
 192     return true;
 193   }
 194
 195   bool Erase(const size_t& key) override {
 196     WriteLock _(&rwlock_);
 197     auto it = map_.find(key);
 198     if (it == map_.end()) {
 199       return false;
 200     }
 201     map_.erase(it);
 202     return true;
 203   }
 204
 205   bool Lookup(const size_t& key, string* val) override {
 206     ReadLock _(&rwlock_);
 207     auto it = map_.find(key);
 208     if (it != map_.end()) {
 209       *val = it->second;
 210     }
 211     return it != map_.end();
 212   }
 213
 214  private:
 215   port::RWMutex rwlock_;
 216   std::unordered_map<size_t, string> map_;
 217 };
 218
 219 //
 220 // GranularLockImpl
 221 // Thread safe custom RocksDB implementation of hash table with granular
 222 // locking
 223 class GranularLockImpl : public HashTableImpl<size_t, string> {
 224  public:
 225   bool Insert(const size_t& key, const string& val) override {
 226     Node n(key, val);
 227     return impl_.Insert(n);
 228   }
 229
 230   bool Erase(const size_t& key) override {
 231     Node n(key, string());
 232     return impl_.Erase(n, nullptr);
 233   }
 234
 235   bool Lookup(const size_t& key, string* val) override {
 236     Node n(key, string());
 237     port::RWMutex* rlock;
 238     bool status = impl_.Find(n, &n, &rlock);
 239     if (status) {
 240       ReadUnlock _(rlock);
 241       *val = n.val_;
 242     }
 243     return status;
 244   }
 245
 246  private:
 247   struct Node {
 248     explicit Node(const size_t key, const string& val) : key_(key), val_(val) {}
 249
 250     size_t key_ = 0;
 251     string val_;
 252   };
 253
 254   struct Hash {
 255     uint64_t operator()(const Node& node) {
 256       return std::hash<uint64_t>()(node.key_);
 257     }
 258   };
 259
 260   struct Equal {
 261     bool operator()(const Node& lhs, const Node& rhs) {
 262       return lhs.key_ == rhs.key_;
 263     }
 264   };
 265
 266   HashTable<Node, Hash, Equal> impl_;
 267 };
 268
 269 }  // namespace rocksdb
 270
 271 //
 272 // main
 273 //
 274 int main(int argc, char** argv) {
 275   GFLAGS::SetUsageMessage(std::string("\nUSAGE:\n") + std::string(argv[0]) +
 276                           " [OPTIONS]...");
 277   GFLAGS::ParseCommandLineFlags(&argc, &argv, false);
 278
 279   //
 280   // Micro benchmark unordered_map
 281   //
 282   printf("Micro benchmarking std::unordered_map \n");
 283   {
 284     rocksdb::SimpleImpl impl;
 285     rocksdb::HashTableBenchmark _(&impl, FLAGS_nsec, FLAGS_nthread_write,
 286                                   FLAGS_nthread_read, FLAGS_nthread_erase);
 287   }
 288   //
 289   // Micro benchmark scalable hash table
 290   //
 291   printf("Micro benchmarking scalable hash map \n");
 292   {
 293     rocksdb::GranularLockImpl impl;
 294     rocksdb::HashTableBenchmark _(&impl, FLAGS_nsec, FLAGS_nthread_write,
 295                                   FLAGS_nthread_read, FLAGS_nthread_erase);
 296   }
 297
 298   return 0;
 299 }
 300 #endif  // #ifndef GFLAGS
 301 #else
 302 int main(int /*argc*/, char** /*argv*/) { return 0; }
 303 #endif