folly/test/ConcurrentSkipListBenchmark.cpp

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 // @author: Xin Liu <xliux@fb.com>
  18
  19 #include <map>
  20 #include <memory>
  21 #include <random>
  22 #include <set>
  23 #include <thread>
  24
  25 #include <folly/Benchmark.h>
  26 #include <folly/ConcurrentSkipList.h>
  27 #include <folly/RWSpinLock.h>
  28 #include <folly/hash/Hash.h>
  29 #include <folly/portability/GFlags.h>
  30 #include <glog/logging.h>
  31
  32 DEFINE_int32(num_threads, 12, "num concurrent threads to test");
  33
  34 // In some case, we may want to test worker threads operating on multiple
  35 // lists. For example in search, not all threads are visiting the same posting
  36 // list, but for the ones with some popular terms, they do get multiple
  37 // visitors at the same time.
  38 DEFINE_int32(num_sets, 1, "num of set to operate on");
  39
  40 static const int kInitHeadHeight = 10;
  41 static const int kMaxValue = 0x1000000;
  42
  43 namespace {
  44
  45 using namespace folly;
  46
  47 typedef int ValueType;
  48 typedef ConcurrentSkipList<ValueType> SkipListType;
  49 typedef SkipListType::Accessor SkipListAccessor;
  50 typedef std::set<ValueType> SetType;
  51
  52 static std::vector<ValueType> gData;
  53 static void initData() {
  54   gData.resize(kMaxValue);
  55   for (int i = 0; i < kMaxValue; ++i) {
  56     gData[i] = i;
  57   }
  58   std::shuffle(gData.begin(), gData.end(), std::mt19937{});
  59 }
  60
  61 // single thread benchmarks
  62 void BM_IterateOverSet(int iters, int size) {
  63   SetType a_set;
  64
  65   BENCHMARK_SUSPEND {
  66     CHECK_GT(size, 0);
  67     for (int i = 0; i < size; ++i) {
  68       a_set.insert(gData[rand() % kMaxValue]);
  69     }
  70   }
  71
  72   int64_t sum = 0;
  73   auto iter = a_set.begin();
  74   for (int i = 0; i < iters; ++i) {
  75     sum += *iter++;
  76     if (iter == a_set.end()) {
  77       iter = a_set.begin();
  78     }
  79   }
  80   BENCHMARK_SUSPEND {
  81     // VLOG(20) << "sum = " << sum;
  82   }
  83 }
  84
  85 void BM_IterateSkipList(int iters, int size) {
  86   BenchmarkSuspender susp;
  87   CHECK_GT(size, 0);
  88   auto skipList = SkipListType::create(kInitHeadHeight);
  89   for (int i = 0; i < size; ++i) {
  90     skipList.add(rand() % kMaxValue);
  91   }
  92   int64_t sum = 0;
  93   susp.dismiss();
  94
  95   auto iter = skipList.begin();
  96   for (int i = 0; i < iters; ++i) {
  97     sum += *iter++;
  98     if (iter == skipList.end()) {
  99       iter = skipList.begin();
 100     }
 101   }
 102
 103   BENCHMARK_SUSPEND {
 104     // VLOG(20) << "sum = " << sum;
 105   }
 106 }
 107
 108 void BM_SetMerge(int iters, int size) {
 109   BenchmarkSuspender susp;
 110   SetType a_set;
 111   SetType b_set;
 112   for (int i = 0; i < iters; ++i) {
 113     a_set.insert(rand() % kMaxValue);
 114   }
 115   for (int i = 0; i < size; ++i) {
 116     b_set.insert(rand() % kMaxValue);
 117   }
 118   susp.dismiss();
 119
 120   int64_t mergedSum = 0;
 121   FOR_EACH(it, a_set) {
 122     if (b_set.find(*it) != b_set.end()) {
 123       mergedSum += *it;
 124     }
 125   }
 126   BENCHMARK_SUSPEND {
 127     // VLOG(20) << mergedSum;
 128   }
 129 }
 130
 131 void BM_CSLMergeLookup(int iters, int size) {
 132   BenchmarkSuspender susp;
 133   auto skipList = SkipListType::create(kInitHeadHeight);
 134   auto skipList2 = SkipListType::create(kInitHeadHeight);
 135
 136   for (int i = 0; i < iters; ++i) {
 137     skipList.add(rand() % kMaxValue);
 138   }
 139   for (int i = 0; i < size; ++i) {
 140     skipList2.add(rand() % kMaxValue);
 141   }
 142   int64_t mergedSum = 0;
 143   susp.dismiss();
 144
 145   SkipListType::Skipper skipper(skipList2);
 146   FOR_EACH(it, skipList) {
 147     if (skipper.to(*it)) {
 148       mergedSum += *it;
 149     }
 150   }
 151
 152   BENCHMARK_SUSPEND {
 153     // VLOG(20) << mergedSum;
 154   }
 155 }
 156
 157 // merge by two skippers
 158 void BM_CSLMergeIntersection(int iters, int size) {
 159   BenchmarkSuspender susp;
 160   auto skipList = SkipListType::create(kInitHeadHeight);
 161   auto skipList2 = SkipListType::create(kInitHeadHeight);
 162   for (int i = 0; i < iters; ++i) {
 163     skipList.add(rand() % kMaxValue);
 164   }
 165   for (int i = 0; i < size; ++i) {
 166     skipList2.add(rand() % kMaxValue);
 167   }
 168   susp.dismiss();
 169
 170   SkipListType::Skipper s1(skipList);
 171   SkipListType::Skipper s2(skipList2);
 172
 173   int64_t mergedSum = 0;
 174
 175   while (s1.good() && s2.good()) {
 176     int v1 = s1.data();
 177     int v2 = s2.data();
 178     if (v1 < v2) {
 179       s1.to(v2);
 180     } else if (v1 > v2) {
 181       s2.to(v1);
 182     } else {
 183       mergedSum += v1;
 184       ++s1;
 185       ++s2;
 186     }
 187   }
 188
 189   BENCHMARK_SUSPEND {
 190     // VLOG(20) << mergedSum;
 191   }
 192 }
 193
 194 void BM_SetContainsNotFound(int iters, int size) {
 195   BenchmarkSuspender susp;
 196   SetType aset;
 197   CHECK_LT(size, kMaxValue);
 198   for (int i = 0; i < size; ++i) {
 199     aset.insert(2 * i);
 200   }
 201   int64_t sum = 0;
 202   susp.dismiss();
 203
 204   for (int i = 0; i < iters; ++i) {
 205     sum += (aset.end() == aset.find(2 * i + 1));
 206   }
 207
 208   BENCHMARK_SUSPEND {
 209     // VLOG(20) << sum;
 210   }
 211 }
 212
 213 void BM_SetContainsFound(int iters, int size) {
 214   BenchmarkSuspender susp;
 215   SetType aset;
 216   CHECK_LT(size, kMaxValue);
 217
 218   for (int i = 0; i < size; ++i) {
 219     aset.insert(i);
 220   }
 221
 222   std::vector<int> values;
 223   for (int i = 0; i < iters; ++i) {
 224     values.push_back(rand() % size);
 225   }
 226   int64_t sum = 0;
 227   susp.dismiss();
 228
 229   for (int i = 0; i < iters; ++i) {
 230     sum += (aset.end() == aset.find(values[i]));
 231   }
 232
 233   BENCHMARK_SUSPEND {
 234     // VLOG(20) << sum;
 235   }
 236 }
 237
 238 void BM_CSLContainsFound(int iters, int size) {
 239   BenchmarkSuspender susp;
 240   auto skipList = SkipListType::create(kInitHeadHeight);
 241   CHECK_LT(size, kMaxValue);
 242
 243   for (int i = 0; i < size; ++i) {
 244     skipList.add(i);
 245   }
 246   std::vector<int> values;
 247   for (int i = 0; i < iters; ++i) {
 248     values.push_back(rand() % size);
 249   }
 250   int64_t sum = 0;
 251   susp.dismiss();
 252
 253   for (int i = 0; i < iters; ++i) {
 254     sum += skipList.contains(values[i]);
 255   }
 256
 257   BENCHMARK_SUSPEND {
 258     // VLOG(20) << sum;
 259   }
 260 }
 261
 262 void BM_CSLContainsNotFound(int iters, int size) {
 263   BenchmarkSuspender susp;
 264   auto skipList = SkipListType::create(kInitHeadHeight);
 265   CHECK_LT(size, kMaxValue);
 266
 267   for (int i = 0; i < size; ++i) {
 268     skipList.add(2 * i);
 269   }
 270   int64_t sum = 0;
 271   susp.dismiss();
 272
 273   for (int i = 0; i < iters; ++i) {
 274     sum += skipList.contains(2 * i + 1);
 275   }
 276
 277   BENCHMARK_SUSPEND {
 278     // VLOG(20) << sum;
 279   }
 280 }
 281
 282 void BM_AddSet(int iters, int size) {
 283   BenchmarkSuspender susp;
 284   SetType aset;
 285   for (int i = 0; i < size; ++i) {
 286     aset.insert(gData[i]);
 287   }
 288   susp.dismiss();
 289
 290   for (int i = size; i < size + iters; ++i) {
 291     aset.insert(gData[i]);
 292   }
 293 }
 294
 295 void BM_AddSkipList(int iters, int size) {
 296   BenchmarkSuspender susp;
 297   auto skipList = SkipListType::create(kInitHeadHeight);
 298   for (int i = 0; i < size; ++i) {
 299     skipList.add(gData[i]);
 300   }
 301   susp.dismiss();
 302
 303   for (int i = size; i < size + iters; ++i) {
 304     skipList.add(gData[i]);
 305   }
 306 }
 307
 308 BENCHMARK(Accessor, iters) {
 309   BenchmarkSuspender susp;
 310   auto skiplist = SkipListType::createInstance(kInitHeadHeight);
 311   auto sl = skiplist.get();
 312
 313   susp.dismiss();
 314   for (size_t i = 0; i < iters; ++i) {
 315     SkipListAccessor accessor(sl);
 316   }
 317 }
 318
 319 // a benchmark to estimate the
 320 // low bound of doing a ref counting for an Accessor
 321 BENCHMARK(accessorBasicRefcounting, iters) {
 322   BenchmarkSuspender susp;
 323   auto* value = new std::atomic<int32_t>();
 324   auto* dirty = new std::atomic<int32_t>();
 325   *value = *dirty = 0;
 326   folly::MicroSpinLock l;
 327   l.init();
 328
 329   susp.dismiss();
 330   for (size_t i = 0; i < iters; ++i) {
 331     value->fetch_add(1, std::memory_order_relaxed);
 332     if (dirty->load(std::memory_order_acquire) != 0) {
 333       folly::MSLGuard g(l);
 334     }
 335     value->fetch_sub(1, std::memory_order_relaxed);
 336   }
 337
 338   BENCHMARK_SUSPEND {
 339     delete dirty;
 340     delete value;
 341   }
 342 }
 343
 344
 345 // Data For testing contention benchmark
 346 class ConcurrentAccessData {
 347  public:
 348   explicit ConcurrentAccessData(int size) :
 349     skipList_(SkipListType::create(10)),
 350     sets_(FLAGS_num_sets), locks_(FLAGS_num_sets) {
 351
 352     for (int i = 0; i < size; ++i) {
 353       sets_[0].insert(i);
 354       skipList_.add(i);
 355     }
 356
 357     for (int i = 0; i < FLAGS_num_sets; ++i) {
 358       locks_[i] = new RWSpinLock();
 359       if (i > 0) {
 360         sets_[i] = sets_[0];
 361       }
 362     }
 363
 364 // This requires knowledge of the C++ library internals. Only use it if we're
 365 // using the GNU C++ library.
 366 #ifdef _GLIBCXX_SYMVER
 367     // memory usage
 368     int64_t setMemorySize = sets_[0].size() * sizeof(*sets_[0].begin()._M_node);
 369     int64_t cslMemorySize = 0;
 370     for (auto it = skipList_.begin(); it != skipList_.end(); ++it) {
 371       cslMemorySize += it.nodeSize();
 372     }
 373
 374     LOG(INFO) << "size=" << sets_[0].size()
 375       << "; std::set memory size=" << setMemorySize
 376       << "; csl memory size=" << cslMemorySize;
 377 #endif
 378
 379     readValues_.reserve(size);
 380     deleteValues_.reserve(size);
 381     writeValues_.reserve(size);
 382     for (int i = size; i < 2 * size; ++i) {
 383       readValues_.push_back(2 * i);
 384       deleteValues_.push_back(2 * i);
 385
 386       // half new values and half already in the list
 387       writeValues_.push_back((rand() % 2) + 2 * i);
 388     }
 389     std::shuffle(readValues_.begin(), readValues_.end(), std::mt19937{});
 390     std::shuffle(deleteValues_.begin(), deleteValues_.end(), std::mt19937{});
 391     std::shuffle(writeValues_.begin(), writeValues_.end(), std::mt19937{});
 392   }
 393
 394   ~ConcurrentAccessData() {
 395     FOR_EACH(lock, locks_) delete *lock;
 396   }
 397
 398   inline bool skipListFind(int /* idx */, ValueType val) {
 399     return skipList_.contains(val);
 400   }
 401   inline void skipListInsert(int /* idx */, ValueType val) {
 402     skipList_.add(val);
 403   }
 404   inline void skipListErase(int /* idx */, ValueType val) {
 405     skipList_.remove(val);
 406   }
 407
 408   inline bool setFind(int idx, ValueType val) {
 409     RWSpinLock::ReadHolder g(locks_[idx]);
 410     return sets_[idx].find(val) == sets_[idx].end();
 411   }
 412   inline void setInsert(int idx, ValueType val) {
 413     RWSpinLock::WriteHolder g(locks_[idx]);
 414     sets_[idx].insert(val);
 415   }
 416   inline void setErase(int idx, ValueType val) {
 417     RWSpinLock::WriteHolder g(locks_[idx]);
 418     sets_[idx].erase(val);
 419   }
 420
 421   void runSkipList(int id, size_t iters) {
 422     int sum = 0;
 423     for (size_t i = 0; i < iters; ++i) {
 424       sum += accessSkipList(id, i);
 425     }
 426     // VLOG(20) << sum;
 427   }
 428
 429   void runSet(size_t id, size_t iters) {
 430     int sum = 0;
 431     for (size_t i = 0; i < iters; ++i) {
 432       sum += accessSet(id, i);
 433     }
 434     // VLOG(20) << sum;
 435   }
 436
 437   bool accessSkipList(int64_t id, size_t t) {
 438     if (t > readValues_.size()) {
 439       t = t % readValues_.size();
 440     }
 441     uint32_t h = folly::hash::twang_32from64(t * id);
 442     switch (h % 8) {
 443       case 7:   // write
 444         if ((h & 0x31) == 0) { // 1/4 chance to delete
 445           skipListErase(0, deleteValues_[t]);
 446         } else {
 447           skipListInsert(0, writeValues_[t]);
 448         }
 449         return false;
 450       default:
 451         return skipListFind(0, readValues_[t]);
 452     }
 453   }
 454
 455   bool accessSet(int64_t id, size_t t) {
 456     if (t > readValues_.size()) {
 457       t = t % readValues_.size();
 458     }
 459     uint32_t h = folly::hash::twang_32from64(t * id);
 460     int idx = (h % FLAGS_num_sets);
 461     switch (h % 8) {  // 1/8 chance to write
 462       case 7:   // write
 463         if ((h & 0x31) == 0) { // 1/32 chance to delete
 464           setErase(idx, deleteValues_[t]);
 465         } else {
 466           setInsert(idx, writeValues_[t]);
 467         }
 468         return false;
 469       default:
 470         return setFind(idx, readValues_[t]);
 471     }
 472   }
 473
 474  private:
 475   SkipListType::Accessor skipList_;
 476   std::vector<SetType> sets_;
 477   std::vector<RWSpinLock*> locks_;
 478
 479   std::vector<ValueType> readValues_;
 480   std::vector<ValueType> writeValues_;
 481   std::vector<ValueType> deleteValues_;
 482 };
 483
 484 static std::map<int, std::shared_ptr<ConcurrentAccessData> > g_data;
 485
 486 static ConcurrentAccessData *mayInitTestData(int size) {
 487   auto it = g_data.find(size);
 488   if (it == g_data.end()) {
 489     auto ptr = std::make_shared<ConcurrentAccessData>(size);
 490     g_data[size] = ptr;
 491     return ptr.get();
 492   }
 493   return it->second.get();
 494 }
 495
 496 void BM_ContentionCSL(int iters, int size) {
 497   BenchmarkSuspender susp;
 498   auto data = mayInitTestData(size);
 499   std::vector<std::thread> threads;
 500   susp.dismiss();
 501
 502   for (int i = 0; i < FLAGS_num_threads; ++i) {
 503     threads.push_back(std::thread(
 504           &ConcurrentAccessData::runSkipList, data, i, iters));
 505   }
 506   FOR_EACH(t, threads) {
 507     (*t).join();
 508   }
 509 }
 510
 511 void BM_ContentionStdSet(int iters, int size) {
 512   BenchmarkSuspender susp;
 513   auto data = mayInitTestData(size);
 514   std::vector<std::thread> threads;
 515   susp.dismiss();
 516
 517   for (int i = 0; i < FLAGS_num_threads; ++i) {
 518     threads.push_back(std::thread(
 519           &ConcurrentAccessData::runSet, data, i, iters));
 520   }
 521   FOR_EACH(t, threads) {
 522     (*t).join();
 523   }
 524   susp.rehire();
 525 }
 526
 527
 528 // Single-thread benchmarking
 529
 530 BENCHMARK_DRAW_LINE();
 531
 532 BENCHMARK_PARAM(BM_IterateOverSet,  1000);
 533 BENCHMARK_PARAM(BM_IterateSkipList, 1000);
 534 BENCHMARK_DRAW_LINE();
 535 BENCHMARK_PARAM(BM_IterateOverSet,  1000000);
 536 BENCHMARK_PARAM(BM_IterateSkipList, 1000000);
 537 BENCHMARK_DRAW_LINE();
 538
 539 // find with keys in the set
 540 BENCHMARK_PARAM(BM_SetContainsFound, 1000);
 541 BENCHMARK_PARAM(BM_CSLContainsFound, 1000);
 542 BENCHMARK_DRAW_LINE();
 543 BENCHMARK_PARAM(BM_SetContainsFound, 100000);
 544 BENCHMARK_PARAM(BM_CSLContainsFound, 100000);
 545 BENCHMARK_DRAW_LINE();
 546 BENCHMARK_PARAM(BM_SetContainsFound, 1000000);
 547 BENCHMARK_PARAM(BM_CSLContainsFound, 1000000);
 548 BENCHMARK_DRAW_LINE();
 549 BENCHMARK_PARAM(BM_SetContainsFound, 10000000);
 550 BENCHMARK_PARAM(BM_CSLContainsFound, 10000000);
 551 BENCHMARK_DRAW_LINE();
 552
 553
 554 // find with keys not in the set
 555 BENCHMARK_PARAM(BM_SetContainsNotFound, 1000);
 556 BENCHMARK_PARAM(BM_CSLContainsNotFound, 1000);
 557 BENCHMARK_DRAW_LINE();
 558 BENCHMARK_PARAM(BM_SetContainsNotFound, 100000);
 559 BENCHMARK_PARAM(BM_CSLContainsNotFound, 100000);
 560 BENCHMARK_DRAW_LINE();
 561 BENCHMARK_PARAM(BM_SetContainsNotFound, 1000000);
 562 BENCHMARK_PARAM(BM_CSLContainsNotFound, 1000000);
 563 BENCHMARK_DRAW_LINE();
 564
 565
 566 BENCHMARK_PARAM(BM_AddSet,      1000);
 567 BENCHMARK_PARAM(BM_AddSkipList, 1000);
 568 BENCHMARK_DRAW_LINE();
 569
 570 BENCHMARK_PARAM(BM_AddSet,      65536);
 571 BENCHMARK_PARAM(BM_AddSkipList, 65536);
 572 BENCHMARK_DRAW_LINE();
 573
 574 BENCHMARK_PARAM(BM_AddSet,      1000000);
 575 BENCHMARK_PARAM(BM_AddSkipList, 1000000);
 576 BENCHMARK_DRAW_LINE();
 577
 578 BENCHMARK_PARAM(BM_SetMerge,             1000);
 579 BENCHMARK_PARAM(BM_CSLMergeIntersection, 1000);
 580 BENCHMARK_PARAM(BM_CSLMergeLookup,       1000);
 581 BENCHMARK_DRAW_LINE();
 582
 583 BENCHMARK_PARAM(BM_SetMerge,             65536);
 584 BENCHMARK_PARAM(BM_CSLMergeIntersection, 65536);
 585 BENCHMARK_PARAM(BM_CSLMergeLookup,       65536);
 586 BENCHMARK_DRAW_LINE();
 587
 588 BENCHMARK_PARAM(BM_SetMerge,             1000000);
 589 BENCHMARK_PARAM(BM_CSLMergeIntersection, 1000000);
 590 BENCHMARK_PARAM(BM_CSLMergeLookup,       1000000);
 591 BENCHMARK_DRAW_LINE();
 592
 593
 594 // multithreaded benchmarking
 595
 596 BENCHMARK_PARAM(BM_ContentionStdSet, 1024);
 597 BENCHMARK_PARAM(BM_ContentionCSL,    1024);
 598 BENCHMARK_DRAW_LINE();
 599
 600 BENCHMARK_PARAM(BM_ContentionStdSet, 65536);
 601 BENCHMARK_PARAM(BM_ContentionCSL,    65536);
 602 BENCHMARK_DRAW_LINE();
 603
 604 BENCHMARK_PARAM(BM_ContentionStdSet, 1048576);
 605 BENCHMARK_PARAM(BM_ContentionCSL,    1048576);
 606 BENCHMARK_DRAW_LINE();
 607
 608 } // namespace
 609
 610 int main(int argc, char** argv) {
 611   google::InitGoogleLogging(argv[0]);
 612   gflags::ParseCommandLineFlags(&argc, &argv, true);
 613
 614   initData();
 615   runBenchmarks();
 616   return 0;
 617 }
 618
 619 #if 0
 620 /*
 621 Benchmark on Intel(R) Xeon(R) CPU X5650 @2.67GHz
 622
 623 ==============================================================================
 624 1 thread Benchmark                     Iters   Total t    t/iter iter/sec
 625 ------------------------------------------------------------------------------
 626  +37.0% BM_Accessor                    100000  1.958 ms  19.58 ns  48.71 M
 627 *       BM_AccessorBasicRefcounting    100000  1.429 ms  14.29 ns  66.74 M
 628 ------------------------------------------------------------------------------
 629  + 603% BM_IterateOverSet/1000         100000  1.589 ms  15.89 ns  60.02 M
 630 *       BM_IterateSkipList/1000        100000    226 us   2.26 ns    422 M
 631 ------------------------------------------------------------------------------
 632  + 107% BM_IterateOverSet/976.6k       100000  8.324 ms  83.24 ns  11.46 M
 633 *       BM_IterateSkipList/976.6k      100000  4.016 ms  40.16 ns  23.75 M
 634 ------------------------------------------------------------------------------
 635 *       BM_SetContainsFound/1000       100000  7.082 ms  70.82 ns  13.47 M
 636  +39.9% BM_CSLContainsFound/1000       100000  9.908 ms  99.08 ns  9.625 M
 637 ------------------------------------------------------------------------------
 638 *       BM_SetContainsFound/97.66k     100000   23.8 ms    238 ns  4.006 M
 639  +5.97% BM_CSLContainsFound/97.66k     100000  25.23 ms  252.3 ns  3.781 M
 640 ------------------------------------------------------------------------------
 641  +33.6% BM_SetContainsFound/976.6k     100000   64.3 ms    643 ns  1.483 M
 642 *       BM_CSLContainsFound/976.6k     100000  48.13 ms  481.3 ns  1.981 M
 643 ------------------------------------------------------------------------------
 644  +30.3% BM_SetContainsFound/9.537M     100000  115.1 ms  1.151 us  848.6 k
 645 *       BM_CSLContainsFound/9.537M     100000  88.33 ms  883.3 ns   1.08 M
 646 ------------------------------------------------------------------------------
 647 *       BM_SetContainsNotFound/1000    100000  2.081 ms  20.81 ns  45.83 M
 648  +76.2% BM_CSLContainsNotFound/1000    100000  3.667 ms  36.67 ns  26.01 M
 649 ------------------------------------------------------------------------------
 650 *       BM_SetContainsNotFound/97.66k  100000  6.049 ms  60.49 ns  15.77 M
 651  +32.7% BM_CSLContainsNotFound/97.66k  100000  8.025 ms  80.25 ns  11.88 M
 652 ------------------------------------------------------------------------------
 653 *       BM_SetContainsNotFound/976.6k  100000  7.464 ms  74.64 ns  12.78 M
 654  +12.8% BM_CSLContainsNotFound/976.6k  100000  8.417 ms  84.17 ns  11.33 M
 655 ------------------------------------------------------------------------------
 656 *       BM_AddSet/1000                 100000  29.26 ms  292.6 ns  3.259 M
 657  +70.0% BM_AddSkipList/1000            100000  49.75 ms  497.5 ns  1.917 M
 658 ------------------------------------------------------------------------------
 659 *       BM_AddSet/64k                  100000  38.73 ms  387.3 ns  2.462 M
 660  +55.7% BM_AddSkipList/64k             100000   60.3 ms    603 ns  1.581 M
 661 ------------------------------------------------------------------------------
 662 *       BM_AddSet/976.6k               100000  75.71 ms  757.1 ns   1.26 M
 663  +33.6% BM_AddSkipList/976.6k          100000  101.2 ms  1.012 us  965.3 k
 664 ------------------------------------------------------------------------------
 665  + 716% BM_SetMerge/1000               100000  6.872 ms  68.72 ns  13.88 M
 666 *       BM_CSLMergeIntersection/1000   100000    842 us   8.42 ns  113.3 M
 667  + 268% BM_CSLMergeLookup/1000         100000    3.1 ms     31 ns  30.76 M
 668 ------------------------------------------------------------------------------
 669  +36.3% BM_SetMerge/64k                100000  14.03 ms  140.3 ns  6.798 M
 670  +39.4% BM_CSLMergeIntersection/64k    100000  14.35 ms  143.5 ns  6.645 M
 671 *       BM_CSLMergeLookup/64k          100000  10.29 ms  102.9 ns  9.266 M
 672 ------------------------------------------------------------------------------
 673  +10.3% BM_SetMerge/976.6k             100000  46.24 ms  462.4 ns  2.062 M
 674  +25.1% BM_CSLMergeIntersection/976.6k 100000  52.47 ms  524.7 ns  1.818 M
 675 *       BM_CSLMergeLookup/976.6k       100000  41.94 ms  419.3 ns  2.274 M
 676 ------------------------------------------------------------------------------
 677
 678
 679 ==============================================================================
 680 Contention benchmark 7/8 find, 3/32 insert, 1/32 erase
 681
 682  4 threads Benchmark                   Iters   Total t    t/iter iter/sec
 683 ------------------------------------------------------------------------------
 684  + 269% BM_ContentionStdSet/1k         100000  75.66 ms  756.6 ns   1.26 M
 685 *       BM_ContentionCSL/1k            100000  20.47 ms  204.7 ns  4.658 M
 686 ------------------------------------------------------------------------------
 687  + 228% BM_ContentionStdSet/64k        100000  105.6 ms  1.056 us  924.9 k
 688 *       BM_ContentionCSL/64k           100000  32.18 ms  321.8 ns  2.963 M
 689 ------------------------------------------------------------------------------
 690  + 224% BM_ContentionStdSet/1M         100000  117.4 ms  1.174 us  832.2 k
 691 *       BM_ContentionCSL/1M            100000  36.18 ms  361.8 ns  2.636 M
 692 ------------------------------------------------------------------------------
 693
 694
 695 12 threads Benchmark                   Iters   Total t    t/iter iter/sec
 696 ------------------------------------------------------------------------------
 697  + 697% BM_ContentionStdSet/1k         100000  455.3 ms  4.553 us  214.5 k
 698 *       BM_ContentionCSL/1k            100000  57.12 ms  571.2 ns   1.67 M
 699 ------------------------------------------------------------------------------
 700  +1257% BM_ContentionStdSet/64k        100000  654.9 ms  6.549 us  149.1 k
 701 *       BM_ContentionCSL/64k           100000  48.24 ms  482.4 ns  1.977 M
 702 ------------------------------------------------------------------------------
 703  +1262% BM_ContentionStdSet/1M         100000  657.3 ms  6.573 us  148.6 k
 704 *       BM_ContentionCSL/1M            100000  48.25 ms  482.5 ns  1.977 M
 705 ------------------------------------------------------------------------------
 706
 707 */
 708 #endif