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 <random>
  21 #include <set>
  22 #include <thread>
  23
  24 #include <folly/Benchmark.h>
  25 #include <folly/ConcurrentSkipList.h>
  26 #include <folly/Hash.h>
  27 #include <folly/RWSpinLock.h>
  28 #include <folly/portability/GFlags.h>
  29 #include <glog/logging.h>
  30
  31 DEFINE_int32(num_threads, 12, "num concurrent threads to test");
  32
  33 // In some case, we may want to test worker threads operating on multiple
  34 // lists. For example in search, not all threads are visiting the same posting
  35 // list, but for the ones with some popular terms, they do get multiple
  36 // visitors at the same time.
  37 DEFINE_int32(num_sets, 1, "num of set to operate on");
  38
  39 static const int kInitHeadHeight = 10;
  40 static const int kMaxValue = 0x1000000;
  41
  42 namespace {
  43
  44 using namespace folly;
  45
  46 typedef int ValueType;
  47 typedef ConcurrentSkipList<ValueType> SkipListType;
  48 typedef SkipListType::Accessor SkipListAccessor;
  49 typedef std::set<ValueType> SetType;
  50
  51 static std::vector<ValueType> gData;
  52 static void initData() {
  53   gData.resize(kMaxValue);
  54   for (int i = 0; i < kMaxValue; ++i) {
  55     gData[i] = i;
  56   }
  57   std::shuffle(gData.begin(), gData.end(), std::mt19937{});
  58 }
  59
  60 // single thread benchmarks
  61 void BM_IterateOverSet(int iters, int size) {
  62   SetType a_set;
  63
  64   BENCHMARK_SUSPEND {
  65     CHECK_GT(size, 0);
  66     for (int i = 0; i < size; ++i) {
  67       a_set.insert(gData[rand() % kMaxValue]);
  68     }
  69   }
  70
  71   int64_t sum = 0;
  72   auto iter = a_set.begin();
  73   for (int i = 0; i < iters; ++i) {
  74     sum += *iter++;
  75     if (iter == a_set.end()) {
  76       iter = a_set.begin();
  77     }
  78   }
  79   BENCHMARK_SUSPEND {
  80     // VLOG(20) << "sum = " << sum;
  81   }
  82 }
  83
  84 void BM_IterateSkipList(int iters, int size) {
  85   BenchmarkSuspender susp;
  86   CHECK_GT(size, 0);
  87   auto skipList = SkipListType::create(kInitHeadHeight);
  88   for (int i = 0; i < size; ++i) {
  89     skipList.add(rand() % kMaxValue);
  90   }
  91   int64_t sum = 0;
  92   susp.dismiss();
  93
  94   auto iter = skipList.begin();
  95   for (int i = 0; i < iters; ++i) {
  96     sum += *iter++;
  97     if (iter == skipList.end()) {
  98       iter = skipList.begin();
  99     }
 100   }
 101
 102   BENCHMARK_SUSPEND {
 103     // VLOG(20) << "sum = " << sum;
 104   }
 105 }
 106
 107 void BM_SetMerge(int iters, int size) {
 108   BenchmarkSuspender susp;
 109   SetType a_set;
 110   SetType b_set;
 111   for (int i = 0; i < iters; ++i) {
 112     a_set.insert(rand() % kMaxValue);
 113   }
 114   for (int i = 0; i < size; ++i) {
 115     b_set.insert(rand() % kMaxValue);
 116   }
 117   susp.dismiss();
 118
 119   int64_t mergedSum = 0;
 120   FOR_EACH(it, a_set) {
 121     if (b_set.find(*it) != b_set.end()) {
 122       mergedSum += *it;
 123     }
 124   }
 125   BENCHMARK_SUSPEND {
 126     // VLOG(20) << mergedSum;
 127   }
 128 }
 129
 130 void BM_CSLMergeLookup(int iters, int size) {
 131   BenchmarkSuspender susp;
 132   auto skipList = SkipListType::create(kInitHeadHeight);
 133   auto skipList2 = SkipListType::create(kInitHeadHeight);
 134
 135   for (int i = 0; i < iters; ++i) {
 136     skipList.add(rand() % kMaxValue);
 137   }
 138   for (int i = 0; i < size; ++i) {
 139     skipList2.add(rand() % kMaxValue);
 140   }
 141   int64_t mergedSum = 0;
 142   susp.dismiss();
 143
 144   SkipListType::Skipper skipper(skipList2);
 145   FOR_EACH(it, skipList) {
 146     if (skipper.to(*it)) {
 147       mergedSum += *it;
 148     }
 149   }
 150
 151   BENCHMARK_SUSPEND {
 152     // VLOG(20) << mergedSum;
 153   }
 154 }
 155
 156 // merge by two skippers
 157 void BM_CSLMergeIntersection(int iters, int size) {
 158   BenchmarkSuspender susp;
 159   auto skipList = SkipListType::create(kInitHeadHeight);
 160   auto skipList2 = SkipListType::create(kInitHeadHeight);
 161   for (int i = 0; i < iters; ++i) {
 162     skipList.add(rand() % kMaxValue);
 163   }
 164   for (int i = 0; i < size; ++i) {
 165     skipList2.add(rand() % kMaxValue);
 166   }
 167   susp.dismiss();
 168
 169   SkipListType::Skipper s1(skipList);
 170   SkipListType::Skipper s2(skipList2);
 171
 172   int64_t mergedSum = 0;
 173
 174   while (s1.good() && s2.good()) {
 175     int v1 = s1.data();
 176     int v2 = s2.data();
 177     if (v1 < v2) {
 178       s1.to(v2);
 179     } else if (v1 > v2) {
 180       s2.to(v1);
 181     } else {
 182       mergedSum += v1;
 183       ++s1;
 184       ++s2;
 185     }
 186   }
 187
 188   BENCHMARK_SUSPEND {
 189     // VLOG(20) << mergedSum;
 190   }
 191 }
 192
 193 void BM_SetContainsNotFound(int iters, int size) {
 194   BenchmarkSuspender susp;
 195   SetType aset;
 196   CHECK_LT(size, kMaxValue);
 197   for (int i = 0; i < size; ++i) {
 198     aset.insert(2 * i);
 199   }
 200   int64_t sum = 0;
 201   susp.dismiss();
 202
 203   for (int i = 0; i < iters; ++i) {
 204     sum += (aset.end() == aset.find(2 * i + 1));
 205   }
 206
 207   BENCHMARK_SUSPEND {
 208     // VLOG(20) << sum;
 209   }
 210 }
 211
 212 void BM_SetContainsFound(int iters, int size) {
 213   BenchmarkSuspender susp;
 214   SetType aset;
 215   CHECK_LT(size, kMaxValue);
 216
 217   for (int i = 0; i < size; ++i) {
 218     aset.insert(i);
 219   }
 220
 221   std::vector<int> values;
 222   for (int i = 0; i < iters; ++i) {
 223     values.push_back(rand() % size);
 224   }
 225   int64_t sum = 0;
 226   susp.dismiss();
 227
 228   for (int i = 0; i < iters; ++i) {
 229     sum += (aset.end() == aset.find(values[i]));
 230   }
 231
 232   BENCHMARK_SUSPEND {
 233     // VLOG(20) << sum;
 234   }
 235 }
 236
 237 void BM_CSLContainsFound(int iters, int size) {
 238   BenchmarkSuspender susp;
 239   auto skipList = SkipListType::create(kInitHeadHeight);
 240   CHECK_LT(size, kMaxValue);
 241
 242   for (int i = 0; i < size; ++i) {
 243     skipList.add(i);
 244   }
 245   std::vector<int> values;
 246   for (int i = 0; i < iters; ++i) {
 247     values.push_back(rand() % size);
 248   }
 249   int64_t sum = 0;
 250   susp.dismiss();
 251
 252   for (int i = 0; i < iters; ++i) {
 253     sum += skipList.contains(values[i]);
 254   }
 255
 256   BENCHMARK_SUSPEND {
 257     // VLOG(20) << sum;
 258   }
 259 }
 260
 261 void BM_CSLContainsNotFound(int iters, int size) {
 262   BenchmarkSuspender susp;
 263   auto skipList = SkipListType::create(kInitHeadHeight);
 264   CHECK_LT(size, kMaxValue);
 265
 266   for (int i = 0; i < size; ++i) {
 267     skipList.add(2 * i);
 268   }
 269   int64_t sum = 0;
 270   susp.dismiss();
 271
 272   for (int i = 0; i < iters; ++i) {
 273     sum += skipList.contains(2 * i + 1);
 274   }
 275
 276   BENCHMARK_SUSPEND {
 277     // VLOG(20) << sum;
 278   }
 279 }
 280
 281 void BM_AddSet(int iters, int size) {
 282   BenchmarkSuspender susp;
 283   SetType aset;
 284   for (int i = 0; i < size; ++i) {
 285     aset.insert(gData[i]);
 286   }
 287   susp.dismiss();
 288
 289   for (int i = size; i < size + iters; ++i) {
 290     aset.insert(gData[i]);
 291   }
 292 }
 293
 294 void BM_AddSkipList(int iters, int size) {
 295   BenchmarkSuspender susp;
 296   auto skipList = SkipListType::create(kInitHeadHeight);
 297   for (int i = 0; i < size; ++i) {
 298     skipList.add(gData[i]);
 299   }
 300   susp.dismiss();
 301
 302   for (int i = size; i < size + iters; ++i) {
 303     skipList.add(gData[i]);
 304   }
 305 }
 306
 307 BENCHMARK(Accessor, iters) {
 308   BenchmarkSuspender susp;
 309   auto skiplist = SkipListType::createInstance(kInitHeadHeight);
 310   auto sl = skiplist.get();
 311
 312   susp.dismiss();
 313   for (size_t i = 0; i < iters; ++i) {
 314     SkipListAccessor accessor(sl);
 315   }
 316 }
 317
 318 // a benchmark to estimate the
 319 // low bound of doing a ref counting for an Accessor
 320 BENCHMARK(accessorBasicRefcounting, iters) {
 321   BenchmarkSuspender susp;
 322   auto* value = new std::atomic<int32_t>();
 323   auto* dirty = new std::atomic<int32_t>();
 324   *value = *dirty = 0;
 325   folly::MicroSpinLock l;
 326   l.init();
 327
 328   susp.dismiss();
 329   for (size_t i = 0; i < iters; ++i) {
 330     value->fetch_add(1, std::memory_order_relaxed);
 331     if (dirty->load(std::memory_order_acquire) != 0) {
 332       folly::MSLGuard g(l);
 333     }
 334     value->fetch_sub(1, std::memory_order_relaxed);
 335   }
 336
 337   BENCHMARK_SUSPEND {
 338     delete dirty;
 339     delete value;
 340   }
 341 }
 342
 343
 344 // Data For testing contention benchmark
 345 class ConcurrentAccessData {
 346  public:
 347   explicit ConcurrentAccessData(int size) :
 348     skipList_(SkipListType::create(10)),
 349     sets_(FLAGS_num_sets), locks_(FLAGS_num_sets) {
 350
 351     for (int i = 0; i < size; ++i) {
 352       sets_[0].insert(i);
 353       skipList_.add(i);
 354     }
 355
 356     for (int i = 0; i < FLAGS_num_sets; ++i) {
 357       locks_[i] = new RWSpinLock();
 358       if (i > 0) {
 359         sets_[i] = sets_[0];
 360       }
 361     }
 362
 363 // This requires knowledge of the C++ library internals. Only use it if we're
 364 // using the GNU C++ library.
 365 #ifdef _GLIBCXX_SYMVER
 366     // memory usage
 367     int64_t setMemorySize = sets_[0].size() * sizeof(*sets_[0].begin()._M_node);
 368     int64_t cslMemorySize = 0;
 369     for (auto it = skipList_.begin(); it != skipList_.end(); ++it) {
 370       cslMemorySize += it.nodeSize();
 371     }
 372
 373     LOG(INFO) << "size=" << sets_[0].size()
 374       << "; std::set memory size=" << setMemorySize
 375       << "; csl memory size=" << cslMemorySize;
 376 #endif
 377
 378     readValues_.reserve(size);
 379     deleteValues_.reserve(size);
 380     writeValues_.reserve(size);
 381     for (int i = size; i < 2 * size; ++i) {
 382       readValues_.push_back(2 * i);
 383       deleteValues_.push_back(2 * i);
 384
 385       // half new values and half already in the list
 386       writeValues_.push_back((rand() % 2) + 2 * i);
 387     }
 388     std::shuffle(readValues_.begin(), readValues_.end(), std::mt19937{});
 389     std::shuffle(deleteValues_.begin(), deleteValues_.end(), std::mt19937{});
 390     std::shuffle(writeValues_.begin(), writeValues_.end(), std::mt19937{});
 391   }
 392
 393   ~ConcurrentAccessData() {
 394     FOR_EACH(lock, locks_) delete *lock;
 395   }
 396
 397   inline bool skipListFind(int /* idx */, ValueType val) {
 398     return skipList_.contains(val);
 399   }
 400   inline void skipListInsert(int /* idx */, ValueType val) {
 401     skipList_.add(val);
 402   }
 403   inline void skipListErase(int /* idx */, ValueType val) {
 404     skipList_.remove(val);
 405   }
 406
 407   inline bool setFind(int idx, ValueType val) {
 408     RWSpinLock::ReadHolder g(locks_[idx]);
 409     return sets_[idx].find(val) == sets_[idx].end();
 410   }
 411   inline void setInsert(int idx, ValueType val) {
 412     RWSpinLock::WriteHolder g(locks_[idx]);
 413     sets_[idx].insert(val);
 414   }
 415   inline void setErase(int idx, ValueType val) {
 416     RWSpinLock::WriteHolder g(locks_[idx]);
 417     sets_[idx].erase(val);
 418   }
 419
 420   void runSkipList(int id, size_t iters) {
 421     int sum = 0;
 422     for (size_t i = 0; i < iters; ++i) {
 423       sum += accessSkipList(id, i);
 424     }
 425     // VLOG(20) << sum;
 426   }
 427
 428   void runSet(size_t id, size_t iters) {
 429     int sum = 0;
 430     for (size_t i = 0; i < iters; ++i) {
 431       sum += accessSet(id, i);
 432     }
 433     // VLOG(20) << sum;
 434   }
 435
 436   bool accessSkipList(int64_t id, size_t t) {
 437     if (t > readValues_.size()) {
 438       t = t % readValues_.size();
 439     }
 440     uint32_t h = folly::hash::twang_32from64(t * id);
 441     switch (h % 8) {
 442       case 7:   // write
 443         if ((h & 0x31) == 0) { // 1/4 chance to delete
 444           skipListErase(0, deleteValues_[t]);
 445         } else {
 446           skipListInsert(0, writeValues_[t]);
 447         }
 448         return 0;
 449       default:
 450         return skipListFind(0, readValues_[t]);
 451     }
 452   }
 453
 454   bool accessSet(int64_t id, size_t t) {
 455     if (t > readValues_.size()) {
 456       t = t % readValues_.size();
 457     }
 458     uint32_t h = folly::hash::twang_32from64(t * id);
 459     int idx = (h % FLAGS_num_sets);
 460     switch (h % 8) {  // 1/8 chance to write
 461       case 7:   // write
 462         if ((h & 0x31) == 0) { // 1/32 chance to delete
 463           setErase(idx, deleteValues_[t]);
 464         } else {
 465           setInsert(idx, writeValues_[t]);
 466         }
 467         return 0;
 468       default:
 469         return setFind(idx, readValues_[t]);
 470     }
 471   }
 472
 473  private:
 474   SkipListType::Accessor skipList_;
 475   std::vector<SetType> sets_;
 476   std::vector<RWSpinLock*> locks_;
 477
 478   std::vector<ValueType> readValues_;
 479   std::vector<ValueType> writeValues_;
 480   std::vector<ValueType> deleteValues_;
 481 };
 482
 483 static std::map<int, std::shared_ptr<ConcurrentAccessData> > g_data;
 484
 485 static ConcurrentAccessData *mayInitTestData(int size) {
 486   auto it = g_data.find(size);
 487   if (it == g_data.end()) {
 488     auto ptr = std::shared_ptr<ConcurrentAccessData>(
 489         new 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 }
 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