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