2 * Copyright 2016 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #include <folly/LifoSem.h>
19 #include <semaphore.h>
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>
29 using namespace folly;
30 using namespace folly::test;
32 typedef LifoSemImpl<DeterministicAtomic> DLifoSem;
33 typedef DeterministicSchedule DSched;
35 LIFOSEM_DECLARE_POOL(DeterministicAtomic, 100000)
37 TEST(LifoSem, basic) {
39 EXPECT_FALSE(sem.tryWait());
41 EXPECT_TRUE(sem.tryWait());
46 TEST(LifoSem, multi) {
49 const int opsPerThread = 10000;
50 std::thread threads[10];
51 std::atomic<int> blocks(0);
53 for (auto& thr : threads) {
54 thr = std::thread([&]{
56 for (int i = 0; i < opsPerThread; ++i) {
70 for (auto& thr : threads) {
74 LOG(INFO) << opsPerThread * sizeof(threads)/sizeof(threads[0])
75 << " post/wait pairs, " << blocks << " blocked";
78 TEST(LifoSem, pingpong) {
79 DSched sched(DSched::uniform(0));
81 const int iters = 100;
83 for (int pass = 0; pass < 10; ++pass) {
87 auto thr = DSched::thread([&]{
88 for (int i = 0; i < iters; ++i) {
90 // main thread can't be running here
91 EXPECT_EQ(a.valueGuess(), 0);
92 EXPECT_EQ(b.valueGuess(), 0);
96 for (int i = 0; i < iters; ++i) {
99 // child thread can't be running here
100 EXPECT_EQ(a.valueGuess(), 0);
101 EXPECT_EQ(b.valueGuess(), 0);
107 TEST(LifoSem, mutex) {
108 DSched sched(DSched::uniform(0));
110 const int iters = 100;
112 for (int pass = 0; pass < 10; ++pass) {
115 auto thr = DSched::thread([&]{
116 for (int i = 0; i < iters; ++i) {
121 for (int i = 0; i < iters; ++i) {
131 TEST(LifoSem, no_blocking) {
132 long seed = folly::randomNumberSeed() % 10000;
133 LOG(INFO) << "seed=" << seed;
134 DSched sched(DSched::uniform(seed));
136 const int iters = 100;
137 const int numThreads = 2;
138 const int width = 10;
140 for (int pass = 0; pass < 10; ++pass) {
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) {
148 for (int w = 0; w < width; ++w) {
154 for (auto& thr : threads) {
160 TEST(LifoSem, one_way) {
161 long seed = folly::randomNumberSeed() % 10000;
162 LOG(INFO) << "seed=" << seed;
163 DSched sched(DSched::uniformSubset(seed, 1, 6));
165 const int iters = 1000;
167 for (int pass = 0; pass < 10; ++pass) {
170 auto thr = DSched::thread([&]{
171 for (int i = 0; i < iters; ++i) {
175 for (int i = 0; i < iters; ++i) {
182 TEST(LifoSem, shutdown_race) {
183 long seed = folly::randomNumberSeed() % 10000;
184 LOG(INFO) << "seed=" << seed;
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)));
193 auto thr = DSched::thread([&]{
199 } catch (ShutdownSemError& x) {
201 EXPECT_TRUE(a.isShutdown());
204 EXPECT_TRUE(!a.isShutdown());
206 EXPECT_TRUE(a.isShutdown());
209 EXPECT_EQ(1, waitCount + a.valueGuess());
210 if (waitCount == 0) {
216 EXPECT_TRUE(shutdownWon);
217 EXPECT_TRUE(shutdownLost);
220 TEST(LifoSem, shutdown_multi) {
221 DSched sched(DSched::uniform(0));
223 for (int pass = 0; pass < 10; ++pass) {
225 std::vector<std::thread> threads;
226 while (threads.size() < 20) {
227 threads.push_back(DSched::thread([&]{
231 } catch (ShutdownSemError& x) {
233 EXPECT_TRUE(a.isShutdown());
238 for (auto& thr : threads) {
244 TEST(LifoSem, multi_try_wait_simple) {
247 auto n = sem.tryWait(10); // this used to trigger an assert
251 TEST(LifoSem, multi_try_wait) {
252 long seed = folly::randomNumberSeed() % 10000;
253 LOG(INFO) << "seed=" << seed;
254 DSched sched(DSched::uniform(seed));
257 const int NPOSTS = 1000;
260 for (int i=0; i<NPOSTS; ++i) {
265 DeterministicAtomic<bool> consumer_stop(false);
271 stop = consumer_stop.load();
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);
286 ASSERT_EQ(NPOSTS, consumed);
289 BENCHMARK(lifo_sem_pingpong, iters) {
292 auto thr = std::thread([&]{
293 for (size_t i = 0; i < iters; ++i) {
298 for (size_t i = 0; i < iters; ++i) {
305 BENCHMARK(lifo_sem_oneway, iters) {
307 auto thr = std::thread([&]{
308 for (size_t i = 0; i < iters; ++i) {
312 for (size_t i = 0; i < iters; ++i) {
318 BENCHMARK(single_thread_lifo_post, iters) {
320 for (size_t n = 0; n < iters; ++n) {
322 asm_volatile_memory();
326 BENCHMARK(single_thread_lifo_wait, iters) {
328 for (size_t n = 0; n < iters; ++n) {
330 asm_volatile_memory();
334 BENCHMARK(single_thread_lifo_postwait, iters) {
336 for (size_t n = 0; n < iters; ++n) {
338 asm_volatile_memory();
340 asm_volatile_memory();
344 BENCHMARK(single_thread_lifo_trywait, iters) {
346 for (size_t n = 0; n < iters; ++n) {
347 EXPECT_FALSE(sem.tryWait());
348 asm_volatile_memory();
352 BENCHMARK(single_thread_posix_postwait, iters) {
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);
359 EXPECT_EQ(sem_destroy(&sem), 0);
362 BENCHMARK(single_thread_posix_trywait, iters) {
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);
368 EXPECT_EQ(sem_destroy(&sem), 0);
371 static void contendedUse(uint32_t n, int posters, int waiters) {
372 LifoSemImpl<std::atomic> sem;
374 std::vector<std::thread> threads;
375 std::atomic<bool> go(false);
378 for (int t = 0; t < waiters; ++t) {
379 threads.emplace_back([=,&sem] {
380 for (uint32_t i = t; i < n; i += waiters) {
385 for (int t = 0; t < posters; ++t) {
386 threads.emplace_back([=,&sem,&go] {
388 std::this_thread::yield();
390 for (uint32_t i = t; i < n; i += posters) {
398 for (auto& thr : threads) {
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)
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 // ============================================================================
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();