folly/test/ConcurrentSkipListBenchmark.cpp

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