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