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