folly/test/LifoSemTests.cpp

   1 /*
   2  * Copyright 2016 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 #include <folly/LifoSem.h>
  18
  19 #include <semaphore.h>
  20 #include <thread>
  21
  22 #include <folly/Benchmark.h>
  23 #include <folly/Random.h>
  24 #include <folly/portability/Asm.h>
  25 #include <folly/portability/GFlags.h>
  26 #include <folly/portability/GTest.h>
  27 #include <folly/test/DeterministicSchedule.h>
  28
  29 using namespace folly;
  30 using namespace folly::test;
  31
  32 typedef LifoSemImpl<DeterministicAtomic> DLifoSem;
  33 typedef DeterministicSchedule DSched;
  34
  35 LIFOSEM_DECLARE_POOL(DeterministicAtomic, 100000)
  36
  37 TEST(LifoSem, basic) {
  38   LifoSem sem;
  39   EXPECT_FALSE(sem.tryWait());
  40   sem.post();
  41   EXPECT_TRUE(sem.tryWait());
  42   sem.post();
  43   sem.wait();
  44 }
  45
  46 TEST(LifoSem, multi) {
  47   LifoSem sem;
  48
  49   const int opsPerThread = 10000;
  50   std::thread threads[10];
  51   std::atomic<int> blocks(0);
  52
  53   for (auto& thr : threads) {
  54     thr = std::thread([&]{
  55       int b = 0;
  56       for (int i = 0; i < opsPerThread; ++i) {
  57         if (!sem.tryWait()) {
  58           sem.wait();
  59           ++b;
  60         }
  61         sem.post();
  62       }
  63       blocks += b;
  64     });
  65   }
  66
  67   // start the flood
  68   sem.post();
  69
  70   for (auto& thr : threads) {
  71     thr.join();
  72   }
  73
  74   LOG(INFO) << opsPerThread * sizeof(threads)/sizeof(threads[0])
  75             << " post/wait pairs, " << blocks << " blocked";
  76 }
  77
  78 TEST(LifoSem, pingpong) {
  79   DSched sched(DSched::uniform(0));
  80
  81   const int iters = 100;
  82
  83   for (int pass = 0; pass < 10; ++pass) {
  84     DLifoSem a;
  85     DLifoSem b;
  86
  87     auto thr = DSched::thread([&]{
  88       for (int i = 0; i < iters; ++i) {
  89         a.wait();
  90         // main thread can't be running here
  91         EXPECT_EQ(a.valueGuess(), 0);
  92         EXPECT_EQ(b.valueGuess(), 0);
  93         b.post();
  94       }
  95     });
  96     for (int i = 0; i < iters; ++i) {
  97       a.post();
  98       b.wait();
  99       // child thread can't be running here
 100       EXPECT_EQ(a.valueGuess(), 0);
 101       EXPECT_EQ(b.valueGuess(), 0);
 102     }
 103     DSched::join(thr);
 104   }
 105 }
 106
 107 TEST(LifoSem, mutex) {
 108   DSched sched(DSched::uniform(0));
 109
 110   const int iters = 100;
 111
 112   for (int pass = 0; pass < 10; ++pass) {
 113     DLifoSem a;
 114
 115     auto thr = DSched::thread([&]{
 116       for (int i = 0; i < iters; ++i) {
 117         a.wait();
 118         a.post();
 119       }
 120     });
 121     for (int i = 0; i < iters; ++i) {
 122       a.post();
 123       a.wait();
 124     }
 125     a.post();
 126     DSched::join(thr);
 127     a.wait();
 128   }
 129 }
 130
 131 TEST(LifoSem, no_blocking) {
 132   long seed = folly::randomNumberSeed() % 10000;
 133   LOG(INFO) << "seed=" << seed;
 134   DSched sched(DSched::uniform(seed));
 135
 136   const int iters = 100;
 137   const int numThreads = 2;
 138   const int width = 10;
 139
 140   for (int pass = 0; pass < 10; ++pass) {
 141     DLifoSem a;
 142
 143     std::vector<std::thread> threads;
 144     while (threads.size() < numThreads) {
 145       threads.emplace_back(DSched::thread([&]{
 146         for (int i = 0; i < iters; ++i) {
 147           a.post(width);
 148           for (int w = 0; w < width; ++w) {
 149             a.wait();
 150           }
 151         }
 152       }));
 153     }
 154     for (auto& thr : threads) {
 155       DSched::join(thr);
 156     }
 157   }
 158 }
 159
 160 TEST(LifoSem, one_way) {
 161   long seed = folly::randomNumberSeed() % 10000;
 162   LOG(INFO) << "seed=" << seed;
 163   DSched sched(DSched::uniformSubset(seed, 1, 6));
 164
 165   const int iters = 1000;
 166
 167   for (int pass = 0; pass < 10; ++pass) {
 168     DLifoSem a;
 169
 170     auto thr = DSched::thread([&]{
 171       for (int i = 0; i < iters; ++i) {
 172         a.wait();
 173       }
 174     });
 175     for (int i = 0; i < iters; ++i) {
 176       a.post();
 177     }
 178     DSched::join(thr);
 179   }
 180 }
 181
 182 TEST(LifoSem, shutdown_race) {
 183   long seed = folly::randomNumberSeed() % 10000;
 184   LOG(INFO) << "seed=" << seed;
 185
 186   bool shutdownWon = false;
 187   bool shutdownLost = false;
 188   for (int pass = 0; pass < 1000; ++pass) {
 189     DSched sched(DSched::uniformSubset(seed + pass, 1, 1 + (pass % 50)));
 190
 191     DLifoSem a;
 192     int waitCount = 0;
 193     auto thr = DSched::thread([&]{
 194       try {
 195         while (true) {
 196           a.wait();
 197           ++waitCount;
 198         }
 199       } catch (ShutdownSemError& x) {
 200         // expected
 201         EXPECT_TRUE(a.isShutdown());
 202       }
 203     });
 204     EXPECT_TRUE(!a.isShutdown());
 205     a.shutdown();
 206     EXPECT_TRUE(a.isShutdown());
 207     a.post();
 208     DSched::join(thr);
 209     EXPECT_EQ(1, waitCount + a.valueGuess());
 210     if (waitCount == 0) {
 211       shutdownWon = true;
 212     } else {
 213       shutdownLost = true;
 214     }
 215   }
 216   EXPECT_TRUE(shutdownWon);
 217   EXPECT_TRUE(shutdownLost);
 218 }
 219
 220 TEST(LifoSem, shutdown_multi) {
 221   DSched sched(DSched::uniform(0));
 222
 223   for (int pass = 0; pass < 10; ++pass) {
 224     DLifoSem a;
 225     std::vector<std::thread> threads;
 226     while (threads.size() < 20) {
 227       threads.push_back(DSched::thread([&]{
 228         try {
 229           a.wait();
 230           EXPECT_TRUE(false);
 231         } catch (ShutdownSemError& x) {
 232           // expected
 233           EXPECT_TRUE(a.isShutdown());
 234         }
 235       }));
 236     }
 237     a.shutdown();
 238     for (auto& thr : threads) {
 239       DSched::join(thr);
 240     }
 241   }
 242 }
 243
 244 TEST(LifoSem, multi_try_wait_simple) {
 245   LifoSem sem;
 246   sem.post(5);
 247   auto n = sem.tryWait(10);     // this used to trigger an assert
 248   ASSERT_EQ(5, n);
 249 }
 250
 251 TEST(LifoSem, multi_try_wait) {
 252   long seed = folly::randomNumberSeed() % 10000;
 253   LOG(INFO) << "seed=" << seed;
 254   DSched sched(DSched::uniform(seed));
 255   DLifoSem sem;
 256
 257   const int NPOSTS = 1000;
 258
 259   auto producer = [&]{
 260     for (int i=0; i<NPOSTS; ++i) {
 261       sem.post();
 262     }
 263   };
 264
 265   DeterministicAtomic<bool> consumer_stop(false);
 266   int consumed = 0;
 267
 268   auto consumer = [&]{
 269     bool stop;
 270     do {
 271       stop = consumer_stop.load();
 272       int n;
 273       do {
 274         n = sem.tryWait(10);
 275         consumed += n;
 276       } while (n > 0);
 277     } while (!stop);
 278   };
 279
 280   std::thread producer_thread(DSched::thread(producer));
 281   std::thread consumer_thread(DSched::thread(consumer));
 282   DSched::join(producer_thread);
 283   consumer_stop.store(true);
 284   DSched::join(consumer_thread);
 285
 286   ASSERT_EQ(NPOSTS, consumed);
 287 }
 288
 289 BENCHMARK(lifo_sem_pingpong, iters) {
 290   LifoSem a;
 291   LifoSem b;
 292   auto thr = std::thread([&]{
 293     for (size_t i = 0; i < iters; ++i) {
 294       a.wait();
 295       b.post();
 296     }
 297   });
 298   for (size_t i = 0; i < iters; ++i) {
 299     a.post();
 300     b.wait();
 301   }
 302   thr.join();
 303 }
 304
 305 BENCHMARK(lifo_sem_oneway, iters) {
 306   LifoSem a;
 307   auto thr = std::thread([&]{
 308     for (size_t i = 0; i < iters; ++i) {
 309       a.wait();
 310     }
 311   });
 312   for (size_t i = 0; i < iters; ++i) {
 313     a.post();
 314   }
 315   thr.join();
 316 }
 317
 318 BENCHMARK(single_thread_lifo_post, iters) {
 319   LifoSem sem;
 320   for (size_t n = 0; n < iters; ++n) {
 321     sem.post();
 322     asm_volatile_memory();
 323   }
 324 }
 325
 326 BENCHMARK(single_thread_lifo_wait, iters) {
 327   LifoSem sem(iters);
 328   for (size_t n = 0; n < iters; ++n) {
 329     sem.wait();
 330     asm_volatile_memory();
 331   }
 332 }
 333
 334 BENCHMARK(single_thread_lifo_postwait, iters) {
 335   LifoSem sem;
 336   for (size_t n = 0; n < iters; ++n) {
 337     sem.post();
 338     asm_volatile_memory();
 339     sem.wait();
 340     asm_volatile_memory();
 341   }
 342 }
 343
 344 BENCHMARK(single_thread_lifo_trywait, iters) {
 345   LifoSem sem;
 346   for (size_t n = 0; n < iters; ++n) {
 347     EXPECT_FALSE(sem.tryWait());
 348     asm_volatile_memory();
 349   }
 350 }
 351
 352 BENCHMARK(single_thread_posix_postwait, iters) {
 353   sem_t sem;
 354   EXPECT_EQ(sem_init(&sem, 0, 0), 0);
 355   for (size_t n = 0; n < iters; ++n) {
 356     EXPECT_EQ(sem_post(&sem), 0);
 357     EXPECT_EQ(sem_wait(&sem), 0);
 358   }
 359   EXPECT_EQ(sem_destroy(&sem), 0);
 360 }
 361
 362 BENCHMARK(single_thread_posix_trywait, iters) {
 363   sem_t sem;
 364   EXPECT_EQ(sem_init(&sem, 0, 0), 0);
 365   for (size_t n = 0; n < iters; ++n) {
 366     EXPECT_EQ(sem_trywait(&sem), -1);
 367   }
 368   EXPECT_EQ(sem_destroy(&sem), 0);
 369 }
 370
 371 static void contendedUse(uint32_t n, int posters, int waiters) {
 372   LifoSemImpl<std::atomic> sem;
 373
 374   std::vector<std::thread> threads;
 375   std::atomic<bool> go(false);
 376
 377   BENCHMARK_SUSPEND {
 378     for (int t = 0; t < waiters; ++t) {
 379       threads.emplace_back([=,&sem] {
 380         for (uint32_t i = t; i < n; i += waiters) {
 381           sem.wait();
 382         }
 383       });
 384     }
 385     for (int t = 0; t < posters; ++t) {
 386       threads.emplace_back([=,&sem,&go] {
 387         while (!go.load()) {
 388           std::this_thread::yield();
 389         }
 390         for (uint32_t i = t; i < n; i += posters) {
 391           sem.post();
 392         }
 393       });
 394     }
 395   }
 396
 397   go.store(true);
 398   for (auto& thr : threads) {
 399     thr.join();
 400   }
 401 }
 402
 403 BENCHMARK_DRAW_LINE()
 404 BENCHMARK_NAMED_PARAM(contendedUse, 1_to_1, 1, 1)
 405 BENCHMARK_NAMED_PARAM(contendedUse, 1_to_4, 1, 4)
 406 BENCHMARK_NAMED_PARAM(contendedUse, 1_to_32, 1, 32)
 407 BENCHMARK_NAMED_PARAM(contendedUse, 4_to_1, 4, 1)
 408 BENCHMARK_NAMED_PARAM(contendedUse, 4_to_24, 4, 24)
 409 BENCHMARK_NAMED_PARAM(contendedUse, 8_to_100, 8, 100)
 410 BENCHMARK_NAMED_PARAM(contendedUse, 32_to_1, 31, 1)
 411 BENCHMARK_NAMED_PARAM(contendedUse, 16_to_16, 16, 16)
 412 BENCHMARK_NAMED_PARAM(contendedUse, 32_to_32, 32, 32)
 413 BENCHMARK_NAMED_PARAM(contendedUse, 32_to_1000, 32, 1000)
 414
 415 // sudo nice -n -20 _build/opt/folly/test/LifoSemTests
 416 //     --benchmark --bm_min_iters=10000000 --gtest_filter=-\*
 417 // ============================================================================
 418 // folly/test/LifoSemTests.cpp                     relative  time/iter  iters/s
 419 // ============================================================================
 420 // lifo_sem_pingpong                                            1.31us  762.40K
 421 // lifo_sem_oneway                                            193.89ns    5.16M
 422 // single_thread_lifo_post                                     15.37ns   65.08M
 423 // single_thread_lifo_wait                                     13.60ns   73.53M
 424 // single_thread_lifo_postwait                                 29.43ns   33.98M
 425 // single_thread_lifo_trywait                                 677.69ps    1.48G
 426 // single_thread_posix_postwait                                25.03ns   39.95M
 427 // single_thread_posix_trywait                                  7.30ns  136.98M
 428 // ----------------------------------------------------------------------------
 429 // contendedUse(1_to_1)                                       158.22ns    6.32M
 430 // contendedUse(1_to_4)                                       574.73ns    1.74M
 431 // contendedUse(1_to_32)                                      592.94ns    1.69M
 432 // contendedUse(4_to_1)                                       118.28ns    8.45M
 433 // contendedUse(4_to_24)                                      667.62ns    1.50M
 434 // contendedUse(8_to_100)                                     701.46ns    1.43M
 435 // contendedUse(32_to_1)                                      165.06ns    6.06M
 436 // contendedUse(16_to_16)                                     238.57ns    4.19M
 437 // contendedUse(32_to_32)                                     219.82ns    4.55M
 438 // contendedUse(32_to_1000)                                   777.42ns    1.29M
 439 // ============================================================================
 440
 441 int main(int argc, char ** argv) {
 442   testing::InitGoogleTest(&argc, argv);
 443   gflags::ParseCommandLineFlags(&argc, &argv, true);
 444   int rv = RUN_ALL_TESTS();
 445   folly::runBenchmarksOnFlag();
 446   return rv;
 447 }