ceph/src/rocksdb/util/autovector_test.cc

   1 //  Copyright (c) 2011-present, 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 #include <atomic>
   7 #include <iostream>
   8 #include <string>
   9 #include <utility>
  10
  11 #include "rocksdb/env.h"
  12 #include "test_util/testharness.h"
  13 #include "test_util/testutil.h"
  14 #include "util/autovector.h"
  15 #include "util/string_util.h"
  16
  17 using std::cout;
  18 using std::endl;
  19
  20 namespace ROCKSDB_NAMESPACE {
  21
  22 class AutoVectorTest : public testing::Test {};
  23 const unsigned long kSize = 8;
  24
  25 namespace {
  26 template <class T>
  27 void AssertAutoVectorOnlyInStack(autovector<T, kSize>* vec, bool result) {
  28 #ifndef ROCKSDB_LITE
  29   ASSERT_EQ(vec->only_in_stack(), result);
  30 #else
  31   (void) vec;
  32   (void) result;
  33 #endif  // !ROCKSDB_LITE
  34 }
  35 }  // namespace
  36
  37 TEST_F(AutoVectorTest, PushBackAndPopBack) {
  38   autovector<size_t, kSize> vec;
  39   ASSERT_TRUE(vec.empty());
  40   ASSERT_EQ(0ul, vec.size());
  41
  42   for (size_t i = 0; i < 1000 * kSize; ++i) {
  43     vec.push_back(i);
  44     ASSERT_TRUE(!vec.empty());
  45     if (i < kSize) {
  46       AssertAutoVectorOnlyInStack(&vec, true);
  47     } else {
  48       AssertAutoVectorOnlyInStack(&vec, false);
  49     }
  50     ASSERT_EQ(i + 1, vec.size());
  51     ASSERT_EQ(i, vec[i]);
  52     ASSERT_EQ(i, vec.at(i));
  53   }
  54
  55   size_t size = vec.size();
  56   while (size != 0) {
  57     vec.pop_back();
  58     // will always be in heap
  59     AssertAutoVectorOnlyInStack(&vec, false);
  60     ASSERT_EQ(--size, vec.size());
  61   }
  62
  63   ASSERT_TRUE(vec.empty());
  64 }
  65
  66 TEST_F(AutoVectorTest, EmplaceBack) {
  67   typedef std::pair<size_t, std::string> ValType;
  68   autovector<ValType, kSize> vec;
  69
  70   for (size_t i = 0; i < 1000 * kSize; ++i) {
  71     vec.emplace_back(i, ToString(i + 123));
  72     ASSERT_TRUE(!vec.empty());
  73     if (i < kSize) {
  74       AssertAutoVectorOnlyInStack(&vec, true);
  75     } else {
  76       AssertAutoVectorOnlyInStack(&vec, false);
  77     }
  78
  79     ASSERT_EQ(i + 1, vec.size());
  80     ASSERT_EQ(i, vec[i].first);
  81     ASSERT_EQ(ToString(i + 123), vec[i].second);
  82   }
  83
  84   vec.clear();
  85   ASSERT_TRUE(vec.empty());
  86   AssertAutoVectorOnlyInStack(&vec, false);
  87 }
  88
  89 TEST_F(AutoVectorTest, Resize) {
  90   autovector<size_t, kSize> vec;
  91
  92   vec.resize(kSize);
  93   AssertAutoVectorOnlyInStack(&vec, true);
  94   for (size_t i = 0; i < kSize; ++i) {
  95     vec[i] = i;
  96   }
  97
  98   vec.resize(kSize * 2);
  99   AssertAutoVectorOnlyInStack(&vec, false);
 100   for (size_t i = 0; i < kSize; ++i) {
 101     ASSERT_EQ(vec[i], i);
 102   }
 103   for (size_t i = 0; i < kSize; ++i) {
 104     vec[i + kSize] = i;
 105   }
 106
 107   vec.resize(1);
 108   ASSERT_EQ(1U, vec.size());
 109 }
 110
 111 namespace {
 112 void AssertEqual(
 113     const autovector<size_t, kSize>& a, const autovector<size_t, kSize>& b) {
 114   ASSERT_EQ(a.size(), b.size());
 115   ASSERT_EQ(a.empty(), b.empty());
 116 #ifndef ROCKSDB_LITE
 117   ASSERT_EQ(a.only_in_stack(), b.only_in_stack());
 118 #endif  // !ROCKSDB_LITE
 119   for (size_t i = 0; i < a.size(); ++i) {
 120     ASSERT_EQ(a[i], b[i]);
 121   }
 122 }
 123 }  // namespace
 124
 125 TEST_F(AutoVectorTest, CopyAndAssignment) {
 126   // Test both heap-allocated and stack-allocated cases.
 127   for (auto size : { kSize / 2, kSize * 1000 }) {
 128     autovector<size_t, kSize> vec;
 129     for (size_t i = 0; i < size; ++i) {
 130       vec.push_back(i);
 131     }
 132
 133     {
 134       autovector<size_t, kSize> other;
 135       other = vec;
 136       AssertEqual(other, vec);
 137     }
 138
 139     {
 140       autovector<size_t, kSize> other(vec);
 141       AssertEqual(other, vec);
 142     }
 143   }
 144 }
 145
 146 TEST_F(AutoVectorTest, Iterators) {
 147   autovector<std::string, kSize> vec;
 148   for (size_t i = 0; i < kSize * 1000; ++i) {
 149     vec.push_back(ToString(i));
 150   }
 151
 152   // basic operator test
 153   ASSERT_EQ(vec.front(), *vec.begin());
 154   ASSERT_EQ(vec.back(), *(vec.end() - 1));
 155   ASSERT_TRUE(vec.begin() < vec.end());
 156
 157   // non-const iterator
 158   size_t index = 0;
 159   for (const auto& item : vec) {
 160     ASSERT_EQ(vec[index++], item);
 161   }
 162
 163   index = vec.size() - 1;
 164   for (auto pos = vec.rbegin(); pos != vec.rend(); ++pos) {
 165     ASSERT_EQ(vec[index--], *pos);
 166   }
 167
 168   // const iterator
 169   const auto& cvec = vec;
 170   index = 0;
 171   for (const auto& item : cvec) {
 172     ASSERT_EQ(cvec[index++], item);
 173   }
 174
 175   index = vec.size() - 1;
 176   for (auto pos = cvec.rbegin(); pos != cvec.rend(); ++pos) {
 177     ASSERT_EQ(cvec[index--], *pos);
 178   }
 179
 180   // forward and backward
 181   auto pos = vec.begin();
 182   while (pos != vec.end()) {
 183     auto old_val = *pos;
 184     auto old = pos++;
 185     // HACK: make sure -> works
 186     ASSERT_TRUE(!old->empty());
 187     ASSERT_EQ(old_val, *old);
 188     ASSERT_TRUE(pos == vec.end() || old_val != *pos);
 189   }
 190
 191   pos = vec.begin();
 192   for (size_t i = 0; i < vec.size(); i += 2) {
 193     // Cannot use ASSERT_EQ since that macro depends on iostream serialization
 194     ASSERT_TRUE(pos + 2 - 2 == pos);
 195     pos += 2;
 196     ASSERT_TRUE(pos >= vec.begin());
 197     ASSERT_TRUE(pos <= vec.end());
 198
 199     size_t diff = static_cast<size_t>(pos - vec.begin());
 200     ASSERT_EQ(i + 2, diff);
 201   }
 202 }
 203
 204 namespace {
 205 std::vector<std::string> GetTestKeys(size_t size) {
 206   std::vector<std::string> keys;
 207   keys.resize(size);
 208
 209   int index = 0;
 210   for (auto& key : keys) {
 211     key = "item-" + ROCKSDB_NAMESPACE::ToString(index++);
 212   }
 213   return keys;
 214 }
 215 }  // namespace
 216
 217 template <class TVector>
 218 void BenchmarkVectorCreationAndInsertion(
 219     std::string name, size_t ops, size_t item_size,
 220     const std::vector<typename TVector::value_type>& items) {
 221   auto env = Env::Default();
 222
 223   int index = 0;
 224   auto start_time = env->NowNanos();
 225   auto ops_remaining = ops;
 226   while(ops_remaining--) {
 227     TVector v;
 228     for (size_t i = 0; i < item_size; ++i) {
 229       v.push_back(items[index++]);
 230     }
 231   }
 232   auto elapsed = env->NowNanos() - start_time;
 233   cout << "created " << ops << " " << name << " instances:\n\t"
 234        << "each was inserted with " << item_size << " elements\n\t"
 235        << "total time elapsed: " << elapsed << " (ns)" << endl;
 236 }
 237
 238 template <class TVector>
 239 size_t BenchmarkSequenceAccess(std::string name, size_t ops, size_t elem_size) {
 240   TVector v;
 241   for (const auto& item : GetTestKeys(elem_size)) {
 242     v.push_back(item);
 243   }
 244   auto env = Env::Default();
 245
 246   auto ops_remaining = ops;
 247   auto start_time = env->NowNanos();
 248   size_t total = 0;
 249   while (ops_remaining--) {
 250     auto end = v.end();
 251     for (auto pos = v.begin(); pos != end; ++pos) {
 252       total += pos->size();
 253     }
 254   }
 255   auto elapsed = env->NowNanos() - start_time;
 256   cout << "performed " << ops << " sequence access against " << name << "\n\t"
 257        << "size: " << elem_size << "\n\t"
 258        << "total time elapsed: " << elapsed << " (ns)" << endl;
 259   // HACK avoid compiler's optimization to ignore total
 260   return total;
 261 }
 262
 263 // This test case only reports the performance between std::vector<std::string>
 264 // and autovector<std::string>. We chose string for comparison because in most
 265 // of our use cases we used std::vector<std::string>.
 266 TEST_F(AutoVectorTest, PerfBench) {
 267   // We run same operations for kOps times in order to get a more fair result.
 268   size_t kOps = 100000;
 269
 270   // Creation and insertion test
 271   // Test the case when there is:
 272   //  * no element inserted: internal array of std::vector may not really get
 273   //    initialize.
 274   //  * one element inserted: internal array of std::vector must have
 275   //    initialized.
 276   //  * kSize elements inserted. This shows the most time we'll spend if we
 277   //    keep everything in stack.
 278   //  * 2 * kSize elements inserted. The internal vector of
 279   //    autovector must have been initialized.
 280   cout << "=====================================================" << endl;
 281   cout << "Creation and Insertion Test (value type: std::string)" << endl;
 282   cout << "=====================================================" << endl;
 283
 284   // pre-generated unique keys
 285   auto string_keys = GetTestKeys(kOps * 2 * kSize);
 286   for (auto insertions : { 0ul, 1ul, kSize / 2, kSize, 2 * kSize }) {
 287     BenchmarkVectorCreationAndInsertion<std::vector<std::string>>(
 288         "std::vector<std::string>", kOps, insertions, string_keys);
 289     BenchmarkVectorCreationAndInsertion<autovector<std::string, kSize>>(
 290         "autovector<std::string>", kOps, insertions, string_keys);
 291     cout << "-----------------------------------" << endl;
 292   }
 293
 294   cout << "=====================================================" << endl;
 295   cout << "Creation and Insertion Test (value type: uint64_t)" << endl;
 296   cout << "=====================================================" << endl;
 297
 298   // pre-generated unique keys
 299   std::vector<uint64_t> int_keys(kOps * 2 * kSize);
 300   for (size_t i = 0; i < kOps * 2 * kSize; ++i) {
 301     int_keys[i] = i;
 302   }
 303   for (auto insertions : { 0ul, 1ul, kSize / 2, kSize, 2 * kSize }) {
 304     BenchmarkVectorCreationAndInsertion<std::vector<uint64_t>>(
 305         "std::vector<uint64_t>", kOps, insertions, int_keys);
 306     BenchmarkVectorCreationAndInsertion<autovector<uint64_t, kSize>>(
 307       "autovector<uint64_t>", kOps, insertions, int_keys
 308     );
 309     cout << "-----------------------------------" << endl;
 310   }
 311
 312   // Sequence Access Test
 313   cout << "=====================================================" << endl;
 314   cout << "Sequence Access Test" << endl;
 315   cout << "=====================================================" << endl;
 316   for (auto elem_size : { kSize / 2, kSize, 2 * kSize }) {
 317     BenchmarkSequenceAccess<std::vector<std::string>>("std::vector", kOps,
 318                                                       elem_size);
 319     BenchmarkSequenceAccess<autovector<std::string, kSize>>("autovector", kOps,
 320                                                             elem_size);
 321     cout << "-----------------------------------" << endl;
 322   }
 323 }
 324
 325 }  // namespace ROCKSDB_NAMESPACE
 326
 327 int main(int argc, char** argv) {
 328   ::testing::InitGoogleTest(&argc, argv);
 329   return RUN_ALL_TESTS();
 330 }