folly/test/ConcurrentSkipListBenchmark.cpp

   1 /*
   2  * Copyright 2013 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 <set>
  21 #include <thread>
  22
  23 #include <gflags/gflags.h>
  24 #include <glog/logging.h>
  25 #include "folly/Benchmark.h"
  26 #include "folly/ConcurrentSkipList.h"
  27 #include "folly/Hash.h"
  28 #include "folly/RWSpinLock.h"
  29
  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::random_shuffle(gData.begin(), gData.end());
  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 (int 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 (int 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     // memory usage
 354     int64_t setMemorySize = sets_[0].size() * sizeof(*sets_[0].begin()._M_node);
 355     int64_t cslMemorySize = 0;
 356     for (auto it = skipList_.begin(); it != skipList_.end(); ++it) {
 357       cslMemorySize += it.nodeSize();
 358     }
 359
 360     LOG(INFO) << "size=" << sets_[0].size()
 361       << "; std::set memory size=" << setMemorySize
 362       << "; csl memory size=" << cslMemorySize;
 363
 364     readValues_.reserve(size);
 365     deleteValues_.reserve(size);
 366     writeValues_.reserve(size);
 367     for (int i = size; i < 2 * size; ++i) {
 368       readValues_.push_back(2 * i);
 369       deleteValues_.push_back(2 * i);
 370
 371       // half new values and half already in the list
 372       writeValues_.push_back((rand() % 2) + 2 * i);
 373     }
 374     std::random_shuffle(readValues_.begin(), readValues_.end());
 375     std::random_shuffle(deleteValues_.begin(), deleteValues_.end());
 376     std::random_shuffle(writeValues_.begin(), writeValues_.end());
 377   }
 378
 379   ~ConcurrentAccessData() {
 380     FOR_EACH(lock, locks_) delete *lock;
 381   }
 382
 383   inline bool skipListFind(int idx, ValueType val) {
 384     return skipList_.contains(val);
 385   }
 386   inline void skipListInsert(int idx, ValueType val) {
 387     skipList_.add(val);
 388   }
 389   inline void skipListErase(int idx, ValueType val) {
 390     skipList_.remove(val);
 391   }
 392
 393   inline bool setFind(int idx, ValueType val) {
 394     RWSpinLock::ReadHolder g(locks_[idx]);
 395     return sets_[idx].find(val) == sets_[idx].end();
 396   }
 397   inline void setInsert(int idx, ValueType val) {
 398     RWSpinLock::WriteHolder g(locks_[idx]);
 399     sets_[idx].insert(val);
 400   }
 401   inline void setErase(int idx, ValueType val) {
 402     RWSpinLock::WriteHolder g(locks_[idx]);
 403     sets_[idx].erase(val);
 404   }
 405
 406   void runSkipList(int id, int iters) {
 407     int sum = 0;
 408     for (int i = 0; i < iters; ++i) {
 409       sum += accessSkipList(id, i);
 410     }
 411     // VLOG(20) << sum;
 412   }
 413
 414   void runSet(int id, int iters) {
 415     int sum = 0;
 416     for (int i = 0; i < iters; ++i) {
 417       sum += accessSet(id, i);
 418     }
 419     // VLOG(20) << sum;
 420   }
 421
 422   bool accessSkipList(int64_t id, int t) {
 423     if (t > readValues_.size()) {
 424       t = t % readValues_.size();
 425     }
 426     uint32_t h = folly::hash::twang_32from64(t * id);
 427     switch (h % 8) {
 428       case 7:   // write
 429         if ((h & 0x31) == 0) { // 1/4 chance to delete
 430           skipListErase(0, deleteValues_[t]);
 431         } else {
 432           skipListInsert(0, writeValues_[t]);
 433         }
 434         return 0;
 435       default:
 436         return skipListFind(0, readValues_[t]);
 437     }
 438   }
 439
 440   bool accessSet(int64_t id, int t) {
 441     if (t > readValues_.size()) {
 442       t = t % readValues_.size();
 443     }
 444     uint32_t h = folly::hash::twang_32from64(t * id);
 445     int idx = (h % FLAGS_num_sets);
 446     switch (h % 8) {  // 1/8 chance to write
 447       case 7:   // write
 448         if ((h & 0x31) == 0) { // 1/32 chance to delete
 449           setErase(idx, deleteValues_[t]);
 450         } else {
 451           setInsert(idx, writeValues_[t]);
 452         }
 453         return 0;
 454       default:
 455         return setFind(idx, readValues_[t]);
 456     }
 457   }
 458
 459  private:
 460   SkipListType::Accessor skipList_;
 461   std::vector<SetType> sets_;
 462   std::vector<RWSpinLock*> locks_;
 463
 464   std::vector<ValueType> readValues_;
 465   std::vector<ValueType> writeValues_;
 466   std::vector<ValueType> deleteValues_;
 467 };
 468
 469 static std::map<int, std::shared_ptr<ConcurrentAccessData> > g_data;
 470
 471 static ConcurrentAccessData *mayInitTestData(int size) {
 472   auto it = g_data.find(size);
 473   if (it == g_data.end()) {
 474     auto ptr = std::shared_ptr<ConcurrentAccessData>(
 475         new ConcurrentAccessData(size));
 476     g_data[size] = ptr;
 477     return ptr.get();
 478   }
 479   return it->second.get();
 480 }
 481
 482 void BM_ContentionCSL(int iters, int size) {
 483   BenchmarkSuspender susp;
 484   auto data = mayInitTestData(size);
 485   std::vector<std::thread> threads;
 486   susp.dismiss();
 487
 488   for (int i = 0; i < FLAGS_num_threads; ++i) {
 489     threads.push_back(std::thread(
 490           &ConcurrentAccessData::runSkipList, data, i, iters));
 491   }
 492   FOR_EACH(t, threads) {
 493     (*t).join();
 494   }
 495 }
 496
 497 void BM_ContentionStdSet(int iters, int size) {
 498   BenchmarkSuspender susp;
 499   auto data = mayInitTestData(size);
 500   std::vector<std::thread> threads;
 501   susp.dismiss();
 502
 503   for (int i = 0; i < FLAGS_num_threads; ++i) {
 504     threads.push_back(std::thread(
 505           &ConcurrentAccessData::runSet, data, i, iters));
 506   }
 507   FOR_EACH(t, threads) {
 508     (*t).join();
 509   }
 510   susp.rehire();
 511 }
 512
 513
 514 // Single-thread benchmarking
 515
 516 BENCHMARK_DRAW_LINE();
 517
 518 BENCHMARK_PARAM(BM_IterateOverSet,  1000);
 519 BENCHMARK_PARAM(BM_IterateSkipList, 1000);
 520 BENCHMARK_DRAW_LINE();
 521 BENCHMARK_PARAM(BM_IterateOverSet,  1000000);
 522 BENCHMARK_PARAM(BM_IterateSkipList, 1000000);
 523 BENCHMARK_DRAW_LINE();
 524
 525 // find with keys in the set
 526 BENCHMARK_PARAM(BM_SetContainsFound, 1000);
 527 BENCHMARK_PARAM(BM_CSLContainsFound, 1000);
 528 BENCHMARK_DRAW_LINE();
 529 BENCHMARK_PARAM(BM_SetContainsFound, 100000);
 530 BENCHMARK_PARAM(BM_CSLContainsFound, 100000);
 531 BENCHMARK_DRAW_LINE();
 532 BENCHMARK_PARAM(BM_SetContainsFound, 1000000);
 533 BENCHMARK_PARAM(BM_CSLContainsFound, 1000000);
 534 BENCHMARK_DRAW_LINE();
 535 BENCHMARK_PARAM(BM_SetContainsFound, 10000000);
 536 BENCHMARK_PARAM(BM_CSLContainsFound, 10000000);
 537 BENCHMARK_DRAW_LINE();
 538
 539
 540 // find with keys not in the set
 541 BENCHMARK_PARAM(BM_SetContainsNotFound, 1000);
 542 BENCHMARK_PARAM(BM_CSLContainsNotFound, 1000);
 543 BENCHMARK_DRAW_LINE();
 544 BENCHMARK_PARAM(BM_SetContainsNotFound, 100000);
 545 BENCHMARK_PARAM(BM_CSLContainsNotFound, 100000);
 546 BENCHMARK_DRAW_LINE();
 547 BENCHMARK_PARAM(BM_SetContainsNotFound, 1000000);
 548 BENCHMARK_PARAM(BM_CSLContainsNotFound, 1000000);
 549 BENCHMARK_DRAW_LINE();
 550
 551
 552 BENCHMARK_PARAM(BM_AddSet,      1000);
 553 BENCHMARK_PARAM(BM_AddSkipList, 1000);
 554 BENCHMARK_DRAW_LINE();
 555
 556 BENCHMARK_PARAM(BM_AddSet,      65536);
 557 BENCHMARK_PARAM(BM_AddSkipList, 65536);
 558 BENCHMARK_DRAW_LINE();
 559
 560 BENCHMARK_PARAM(BM_AddSet,      1000000);
 561 BENCHMARK_PARAM(BM_AddSkipList, 1000000);
 562 BENCHMARK_DRAW_LINE();
 563
 564 BENCHMARK_PARAM(BM_SetMerge,             1000);
 565 BENCHMARK_PARAM(BM_CSLMergeIntersection, 1000);
 566 BENCHMARK_PARAM(BM_CSLMergeLookup,       1000);
 567 BENCHMARK_DRAW_LINE();
 568
 569 BENCHMARK_PARAM(BM_SetMerge,             65536);
 570 BENCHMARK_PARAM(BM_CSLMergeIntersection, 65536);
 571 BENCHMARK_PARAM(BM_CSLMergeLookup,       65536);
 572 BENCHMARK_DRAW_LINE();
 573
 574 BENCHMARK_PARAM(BM_SetMerge,             1000000);
 575 BENCHMARK_PARAM(BM_CSLMergeIntersection, 1000000);
 576 BENCHMARK_PARAM(BM_CSLMergeLookup,       1000000);
 577 BENCHMARK_DRAW_LINE();
 578
 579
 580 // multithreaded benchmarking
 581
 582 BENCHMARK_PARAM(BM_ContentionStdSet, 1024);
 583 BENCHMARK_PARAM(BM_ContentionCSL,    1024);
 584 BENCHMARK_DRAW_LINE();
 585
 586 BENCHMARK_PARAM(BM_ContentionStdSet, 65536);
 587 BENCHMARK_PARAM(BM_ContentionCSL,    65536);
 588 BENCHMARK_DRAW_LINE();
 589
 590 BENCHMARK_PARAM(BM_ContentionStdSet, 1048576);
 591 BENCHMARK_PARAM(BM_ContentionCSL,    1048576);
 592 BENCHMARK_DRAW_LINE();
 593
 594 }
 595
 596 int main(int argc, char** argv) {
 597   google::InitGoogleLogging(argv[0]);
 598   google::ParseCommandLineFlags(&argc, &argv, true);
 599
 600   initData();
 601   runBenchmarks();
 602   return 0;
 603 }
 604
 605 #if 0
 606 /*
 607 Benchmark on Intel(R) Xeon(R) CPU X5650 @2.67GHz
 608
 609 ==============================================================================
 610 1 thread Benchmark                     Iters   Total t    t/iter iter/sec
 611 ------------------------------------------------------------------------------
 612  +37.0% BM_Accessor                    100000  1.958 ms  19.58 ns  48.71 M
 613 *       BM_AccessorBasicRefcounting    100000  1.429 ms  14.29 ns  66.74 M
 614 ------------------------------------------------------------------------------
 615  + 603% BM_IterateOverSet/1000         100000  1.589 ms  15.89 ns  60.02 M
 616 *       BM_IterateSkipList/1000        100000    226 us   2.26 ns    422 M
 617 ------------------------------------------------------------------------------
 618  + 107% BM_IterateOverSet/976.6k       100000  8.324 ms  83.24 ns  11.46 M
 619 *       BM_IterateSkipList/976.6k      100000  4.016 ms  40.16 ns  23.75 M
 620 ------------------------------------------------------------------------------
 621 *       BM_SetContainsFound/1000       100000  7.082 ms  70.82 ns  13.47 M
 622  +39.9% BM_CSLContainsFound/1000       100000  9.908 ms  99.08 ns  9.625 M
 623 ------------------------------------------------------------------------------
 624 *       BM_SetContainsFound/97.66k     100000   23.8 ms    238 ns  4.006 M
 625  +5.97% BM_CSLContainsFound/97.66k     100000  25.23 ms  252.3 ns  3.781 M
 626 ------------------------------------------------------------------------------
 627  +33.6% BM_SetContainsFound/976.6k     100000   64.3 ms    643 ns  1.483 M
 628 *       BM_CSLContainsFound/976.6k     100000  48.13 ms  481.3 ns  1.981 M
 629 ------------------------------------------------------------------------------
 630  +30.3% BM_SetContainsFound/9.537M     100000  115.1 ms  1.151 us  848.6 k
 631 *       BM_CSLContainsFound/9.537M     100000  88.33 ms  883.3 ns   1.08 M
 632 ------------------------------------------------------------------------------
 633 *       BM_SetContainsNotFound/1000    100000  2.081 ms  20.81 ns  45.83 M
 634  +76.2% BM_CSLContainsNotFound/1000    100000  3.667 ms  36.67 ns  26.01 M
 635 ------------------------------------------------------------------------------
 636 *       BM_SetContainsNotFound/97.66k  100000  6.049 ms  60.49 ns  15.77 M
 637  +32.7% BM_CSLContainsNotFound/97.66k  100000  8.025 ms  80.25 ns  11.88 M
 638 ------------------------------------------------------------------------------
 639 *       BM_SetContainsNotFound/976.6k  100000  7.464 ms  74.64 ns  12.78 M
 640  +12.8% BM_CSLContainsNotFound/976.6k  100000  8.417 ms  84.17 ns  11.33 M
 641 ------------------------------------------------------------------------------
 642 *       BM_AddSet/1000                 100000  29.26 ms  292.6 ns  3.259 M
 643  +70.0% BM_AddSkipList/1000            100000  49.75 ms  497.5 ns  1.917 M
 644 ------------------------------------------------------------------------------
 645 *       BM_AddSet/64k                  100000  38.73 ms  387.3 ns  2.462 M
 646  +55.7% BM_AddSkipList/64k             100000   60.3 ms    603 ns  1.581 M
 647 ------------------------------------------------------------------------------
 648 *       BM_AddSet/976.6k               100000  75.71 ms  757.1 ns   1.26 M
 649  +33.6% BM_AddSkipList/976.6k          100000  101.2 ms  1.012 us  965.3 k
 650 ------------------------------------------------------------------------------
 651  + 716% BM_SetMerge/1000               100000  6.872 ms  68.72 ns  13.88 M
 652 *       BM_CSLMergeIntersection/1000   100000    842 us   8.42 ns  113.3 M
 653  + 268% BM_CSLMergeLookup/1000         100000    3.1 ms     31 ns  30.76 M
 654 ------------------------------------------------------------------------------
 655  +36.3% BM_SetMerge/64k                100000  14.03 ms  140.3 ns  6.798 M
 656  +39.4% BM_CSLMergeIntersection/64k    100000  14.35 ms  143.5 ns  6.645 M
 657 *       BM_CSLMergeLookup/64k          100000  10.29 ms  102.9 ns  9.266 M
 658 ------------------------------------------------------------------------------
 659  +10.3% BM_SetMerge/976.6k             100000  46.24 ms  462.4 ns  2.062 M
 660  +25.1% BM_CSLMergeIntersection/976.6k 100000  52.47 ms  524.7 ns  1.818 M
 661 *       BM_CSLMergeLookup/976.6k       100000  41.94 ms  419.3 ns  2.274 M
 662 ------------------------------------------------------------------------------
 663
 664
 665 ==============================================================================
 666 Contention benchmark 7/8 find, 3/32 insert, 1/32 erase
 667
 668  4 threads Benchmark                   Iters   Total t    t/iter iter/sec
 669 ------------------------------------------------------------------------------
 670  + 269% BM_ContentionStdSet/1k         100000  75.66 ms  756.6 ns   1.26 M
 671 *       BM_ContentionCSL/1k            100000  20.47 ms  204.7 ns  4.658 M
 672 ------------------------------------------------------------------------------
 673  + 228% BM_ContentionStdSet/64k        100000  105.6 ms  1.056 us  924.9 k
 674 *       BM_ContentionCSL/64k           100000  32.18 ms  321.8 ns  2.963 M
 675 ------------------------------------------------------------------------------
 676  + 224% BM_ContentionStdSet/1M         100000  117.4 ms  1.174 us  832.2 k
 677 *       BM_ContentionCSL/1M            100000  36.18 ms  361.8 ns  2.636 M
 678 ------------------------------------------------------------------------------
 679
 680
 681 12 threads Benchmark                   Iters   Total t    t/iter iter/sec
 682 ------------------------------------------------------------------------------
 683  + 697% BM_ContentionStdSet/1k         100000  455.3 ms  4.553 us  214.5 k
 684 *       BM_ContentionCSL/1k            100000  57.12 ms  571.2 ns   1.67 M
 685 ------------------------------------------------------------------------------
 686  +1257% BM_ContentionStdSet/64k        100000  654.9 ms  6.549 us  149.1 k
 687 *       BM_ContentionCSL/64k           100000  48.24 ms  482.4 ns  1.977 M
 688 ------------------------------------------------------------------------------
 689  +1262% BM_ContentionStdSet/1M         100000  657.3 ms  6.573 us  148.6 k
 690 *       BM_ContentionCSL/1M            100000  48.25 ms  482.5 ns  1.977 M
 691 ------------------------------------------------------------------------------
 692
 693 */
 694 #endif