SynchronizedBenchmark.cpp

Go to the documentation of this file.

/*
 * Copyright 2017-present Facebook, Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
#include <folly/Synchronized.h>

#include <folly/Benchmark.h>
#include <folly/portability/GTest.h>

#include <algorithm>
#include <condition_variable>
#include <map>
#include <memory>
#include <mutex>
#include <shared_mutex>
#include <thread>

using namespace folly;
using namespace folly::detail;

DEFINE_uint64(iterations, 100, "The number of iterations with lock held");

namespace {
template <typename NonMovableType>
std::vector<std::unique_ptr<NonMovableType>> makeVector(int num);

void spin(int n);

template <typename Mutex>
void ordered(
    std::size_t iters,
    int threads,
    std::vector<std::unique_ptr<Mutex>> mutexes);
template <typename Mutex>
void smart(
    std::size_t iters,
    int threads,
    std::vector<std::unique_ptr<Mutex>> mutexes);
template <typename Mutex>
void persistent(
    std::size_t iters,
    int threads,
    std::vector<std::unique_ptr<Mutex>> mutexes);

template <typename LockingFunc>
void pathological(std::size_t iters, LockingFunc func);

template <typename LockingFunc>
void simple(std::size_t iters, LockingFunc func);

template <typename LockingFunc>
void uncontended(std::size_t iters, LockingFunc func);

class BenchmarkStartBarrier {
 public:
  explicit BenchmarkStartBarrier(int threads) : threads_{threads + 1} {}

  void wait() {
    auto lck = std::unique_lock<std::mutex>{mutex_};
    ++started_;

    // if all the threads have started the benchmarks
    if (started_ == threads_) {
      cv_.notify_all();
      return;
    }

    // wait till all the threads have started
    while (started_ != threads_) {
      cv_.wait(lck);
    }
  }

  std::mutex mutex_;
  std::condition_variable cv_;
  const int threads_;
  int started_{0};
};
} // namespace

BENCHMARK(UncontendedFollyLock, iters) {
  uncontended(iters, [](auto& one, auto& two) { folly::lock(one, two); });
}

BENCHMARK(UncontendedStdLock, iters) {
  uncontended(iters, [](auto& one, auto& two) { std::lock(one, two); });
}

BENCHMARK(UncontendedOrdered, iters) {
  uncontended(iters, [](auto& one, auto& two) {
    one.lock();
    two.lock();
  });
}

BENCHMARK(UncontendedReverseOrdered, iters) {
  uncontended(iters, [](auto& one, auto& two) {
    two.lock();
    one.lock();
  });
}

BENCHMARK_DRAW_LINE();

BENCHMARK(ThreeThreadsSimpleFollyLock, iters) {
  simple(iters, [](auto& one, auto& two) { folly::lock(one, two); });
}

BENCHMARK(ThreeThreadsSimpleStdLock, iters) {
  simple(iters, [](auto& one, auto& two) { std::lock(one, two); });
}

BENCHMARK(ThreeThreadsSimpleOrdered, iters) {
  simple(iters, [](auto& one, auto& two) {
    one.lock();
    two.lock();
  });
}

BENCHMARK(ThreeThreadsSimpleReverseOrdered, iters) {
  simple(iters, [](auto& one, auto& two) {
    two.lock();
    one.lock();
  });
}

BENCHMARK_DRAW_LINE();

BENCHMARK(ThreeThreadsPathologicalFollyLock, iters) {
  pathological(iters, [](auto& one, auto& two, auto& three) {
    folly::lock(one, two, three);
  });
}

BENCHMARK(ThreeThreadsPathologicalStdLock, iters) {
  pathological(iters, [](auto& one, auto& two, auto& three) {
    std::lock(one, two, three);
  });
}

BENCHMARK(ThreeThreadsPathologicalOrdered, iters) {
  pathological(iters, [](auto& one, auto& two, auto& three) {
    one.lock();
    two.lock();
    three.lock();
  });
}

BENCHMARK(ThreeThreadsPathologicalCarefullyOrdered, iters) {
  pathological(iters, [](auto& one, auto& two, auto& three) {
    two.lock();
    three.lock();
    one.lock();
  });
}

BENCHMARK_DRAW_LINE();

BENCHMARK(TwoThreadsTwoMutexesOrdered, iters) {
  ordered(iters, 2, makeVector<std::mutex>(2));
}
BENCHMARK(TwoThreadsTwoMutexesSmart, iters) {
  smart(iters, 2, makeVector<std::mutex>(2));
}
BENCHMARK(TwoThreadsTwoMutexesPersistent, iters) {
  persistent(iters, 2, makeVector<std::mutex>(2));
}

BENCHMARK_DRAW_LINE();

BENCHMARK(TwoThreadsFourMutexesOrdered, iters) {
  ordered(iters, 2, makeVector<std::mutex>(4));
}
BENCHMARK(TwoThreadsFourMutexesSmart, iters) {
  smart(iters, 2, makeVector<std::mutex>(4));
}
BENCHMARK(TwoThreadsFourMutexesPersistent, iters) {
  persistent(iters, 2, makeVector<std::mutex>(4));
}

BENCHMARK_DRAW_LINE();

BENCHMARK(TwoThreadsEightMutexesOrdered, iters) {
  ordered(iters, 2, makeVector<std::mutex>(8));
}
BENCHMARK(TwoThreadsEightMutexesSmart, iters) {
  smart(iters, 2, makeVector<std::mutex>(8));
}
BENCHMARK(TwoThreadsEightMutexesPersistent, iters) {
  persistent(iters, 2, makeVector<std::mutex>(8));
}

BENCHMARK_DRAW_LINE();

BENCHMARK(TwoThreadsSixteenMutexesOrdered, iters) {
  ordered(iters, 2, makeVector<std::mutex>(16));
}
BENCHMARK(TwoThreadsSixteenMutexesSmart, iters) {
  smart(iters, 2, makeVector<std::mutex>(16));
}
BENCHMARK(TwoThreadsSixteenMutexesPersistent, iters) {
  persistent(iters, 2, makeVector<std::mutex>(16));
}

BENCHMARK_DRAW_LINE();

BENCHMARK(FourThreadsTwoMutexesOrdered, iters) {
  ordered(iters, 4, makeVector<std::mutex>(2));
}
BENCHMARK(FourThreadsTwoMutexesSmart, iters) {
  smart(iters, 4, makeVector<std::mutex>(2));
}
BENCHMARK(FourThreadsTwoMutexesPersistent, iters) {
  persistent(iters, 4, makeVector<std::mutex>(2));
}

BENCHMARK_DRAW_LINE();

BENCHMARK(FourThreadsFourMutexesOrdered, iters) {
  ordered(iters, 4, makeVector<std::mutex>(4));
}
BENCHMARK(FourThreadsFourMutexesSmart, iters) {
  smart(iters, 4, makeVector<std::mutex>(4));
}
BENCHMARK(FourThreadsFourMutexesPersistent, iters) {
  persistent(iters, 4, makeVector<std::mutex>(4));
}

BENCHMARK_DRAW_LINE();

BENCHMARK(FourThreadsEightMutexesOrdered, iters) {
  ordered(iters, 4, makeVector<std::mutex>(8));
}
BENCHMARK(FourThreadsEightMutexesSmart, iters) {
  smart(iters, 4, makeVector<std::mutex>(8));
}
BENCHMARK(FourThreadsEightMutexesPersistent, iters) {
  persistent(iters, 4, makeVector<std::mutex>(8));
}

BENCHMARK_DRAW_LINE();

BENCHMARK(FourThreadsSixteenMutexesOrdered, iters) {
  ordered(iters, 4, makeVector<std::mutex>(16));
}
BENCHMARK(FourThreadsSixteenMutexesSmart, iters) {
  smart(iters, 4, makeVector<std::mutex>(16));
}
BENCHMARK(FourThreadsSixteenMutexesPersistent, iters) {
  persistent(iters, 4, makeVector<std::mutex>(16));
}

BENCHMARK_DRAW_LINE();

BENCHMARK(EightThreadsTwoMutexesOrdered, iters) {
  ordered(iters, 8, makeVector<std::mutex>(2));
}
BENCHMARK(EightThreadsTwoMutexesSmart, iters) {
  smart(iters, 8, makeVector<std::mutex>(2));
}
BENCHMARK(EightThreadsTwoMutexesPersistent, iters) {
  persistent(iters, 8, makeVector<std::mutex>(2));
}

BENCHMARK_DRAW_LINE();

BENCHMARK(EightThreadsFourMutexesOrdered, iters) {
  ordered(iters, 8, makeVector<std::mutex>(4));
}
BENCHMARK(EightThreadsFourMutexesSmart, iters) {
  smart(iters, 8, makeVector<std::mutex>(4));
}
BENCHMARK(EightThreadsFourMutexesPersistent, iters) {
  persistent(iters, 8, makeVector<std::mutex>(4));
}

BENCHMARK_DRAW_LINE();

BENCHMARK(EightThreadsEightMutexesOrdered, iters) {
  ordered(iters, 8, makeVector<std::mutex>(8));
}
BENCHMARK(EightThreadsEightMutexesSmart, iters) {
  smart(iters, 8, makeVector<std::mutex>(8));
}
BENCHMARK(EightThreadsEightMutexesPersistent, iters) {
  persistent(iters, 8, makeVector<std::mutex>(8));
}

BENCHMARK_DRAW_LINE();

BENCHMARK(EightThreadsSixteenMutexesOrdered, iters) {
  ordered(iters, 8, makeVector<std::mutex>(16));
}
BENCHMARK(EightThreadsSixteenMutexesSmart, iters) {
  smart(iters, 8, makeVector<std::mutex>(16));
}
BENCHMARK(EightThreadsSixteenMutexesPersistent, iters) {
  persistent(iters, 8, makeVector<std::mutex>(16));
}

BENCHMARK_DRAW_LINE();

BENCHMARK(SixteenThreadsTwoMutexesOrdered, iters) {
  ordered(iters, 16, makeVector<std::mutex>(2));
}
BENCHMARK(SixteenThreadsTwoMutexesSmart, iters) {
  smart(iters, 16, makeVector<std::mutex>(2));
}
BENCHMARK(SixteenThreadsTwoMutexesPersistent, iters) {
  persistent(iters, 16, makeVector<std::mutex>(2));
}

BENCHMARK_DRAW_LINE();

BENCHMARK(SixteenThreadsFourMutexesOrdered, iters) {
  ordered(iters, 16, makeVector<std::mutex>(4));
}
BENCHMARK(SixteenThreadsFourMutexesSmart, iters) {
  smart(iters, 16, makeVector<std::mutex>(4));
}
BENCHMARK(SixteenThreadsFourMutexesPersistent, iters) {
  persistent(iters, 16, makeVector<std::mutex>(4));
}

BENCHMARK_DRAW_LINE();

BENCHMARK(SixteenThreadsEightMutexesOrdered, iters) {
  ordered(iters, 16, makeVector<std::mutex>(8));
}
BENCHMARK(SixteenThreadsEightMutexesSmart, iters) {
  smart(iters, 16, makeVector<std::mutex>(8));
}
BENCHMARK(SixteenThreadsEightMutexesPersistent, iters) {
  persistent(iters, 16, makeVector<std::mutex>(8));
}

BENCHMARK_DRAW_LINE();

BENCHMARK(SixteenThreadsSixteenMutexesOrdered, iters) {
  ordered(iters, 16, makeVector<std::mutex>(16));
}
BENCHMARK(SixteenThreadsSixteenMutexesSmart, iters) {
  smart(iters, 16, makeVector<std::mutex>(16));
}
BENCHMARK(SixteenThreadsSixteenMutexesPersistent, iters) {
  persistent(iters, 16, makeVector<std::mutex>(16));
}

int main(int argc, char** argv) {
  gflags::ParseCommandLineFlags(&argc, &argv, true);
  folly::runBenchmarks();
}

namespace {
std::pair<int, int> getMutexIndices(int threadId, int mutexListSize) {
  // assign two mutexes to the current thread, we need to prevent
  // deadlocks here by resorting the indexes in increasing order,
  // because a thread might pick the last mutex as the one it locks and
  // then adding one to that will make it wrap around, breaking the
  // ordering
  auto index = threadId % mutexListSize;

  auto firstMutexIndex = ((index + 1) == mutexListSize) ? 0 : index;
  auto secondMutexIndex =
      ((index + 1) == mutexListSize) ? (mutexListSize - 1) : (index + 1);

  return std::make_pair(firstMutexIndex, secondMutexIndex);
}

template <typename NonMovableType>
std::vector<std::unique_ptr<NonMovableType>> makeVector(int num) {
  auto vector = std::vector<std::unique_ptr<NonMovableType>>{};
  vector.reserve(num);
  for (auto i = 0; i < num; ++i) {
    vector.push_back(std::make_unique<NonMovableType>());
  }
  return vector;
}

template <typename Mutex>
void ordered(
    std::size_t iters,
    int numThreads,
    std::vector<std::unique_ptr<Mutex>> mutexes) {
  auto suspender = BenchmarkSuspender{};

  // Sort the mutexes so there is no deadlock because of lock acquisition
  // ordering
  std::sort(mutexes.begin(), mutexes.end(), [](auto& one, auto& two) {
    return one.get() < two.get();
  });

  auto threads = std::vector<std::thread>{};
  auto&& barrier = BenchmarkStartBarrier{numThreads};

  for (auto thread = 0; thread < numThreads; ++thread) {
    threads.emplace_back([&mutexes, iters, thread, &barrier] {
      barrier.wait();

      auto indices = getMutexIndices(thread, mutexes.size());
      for (auto i = std::size_t{0}; i < iters; ++i) {
        // lock the mutexes
        mutexes[indices.first]->lock();
        mutexes[indices.second]->lock();

        spin(FLAGS_iterations);

        mutexes[indices.first]->unlock();
        mutexes[indices.second]->unlock();
      }
    });
  }

  barrier.wait();
  suspender.dismissing([&] {
    for (auto& thread : threads) {
      thread.join();
    }
  });
}

template <typename Mutex>
void smart(
    std::size_t iters,
    int numThreads,
    std::vector<std::unique_ptr<Mutex>> mutexes) {
  auto suspender = BenchmarkSuspender{};

  auto threads = std::vector<std::thread>{};
  auto&& barrier = BenchmarkStartBarrier{numThreads};

  for (auto thread = 0; thread < numThreads; ++thread) {
    threads.emplace_back([iters, &mutexes, thread, &barrier] {
      barrier.wait();

      auto indices = std::make_pair(
          thread % mutexes.size(), (thread + 1) % mutexes.size());
      for (auto iter = std::size_t{0}; iter < iters; ++iter) {
        while (true) {
          mutexes[indices.first]->lock();
          if (mutexes[indices.second]->try_lock()) {
            break;
          }

          mutexes[indices.first]->unlock();
          std::swap(indices.first, indices.second);
          std::this_thread::yield();
        }

        spin(FLAGS_iterations);

        mutexes[indices.first]->unlock();
        mutexes[indices.second]->unlock();
      }
    });
  }

  barrier.wait();
  suspender.dismissing([&] {
    for (auto& thread : threads) {
      thread.join();
    }
  });
}

template <typename Mutex>
void persistent(
    std::size_t iters,
    int numThreads,
    std::vector<std::unique_ptr<Mutex>> mutexes) {
  auto suspender = BenchmarkSuspender{};

  auto threads = std::vector<std::thread>{};
  auto&& barrier = BenchmarkStartBarrier{numThreads};

  for (auto thread = 0; thread < numThreads; ++thread) {
    threads.emplace_back([iters, &mutexes, thread, &barrier] {
      barrier.wait();

      auto indices = std::make_pair(
          thread % mutexes.size(), (thread + 1) % mutexes.size());
      for (auto iter = std::size_t{0}; iter < iters; ++iter) {
        // lock the mutexes by first locking a mutex and then acquiring the
        // next mutex (or mutexes) with a try_lock()
        while (true) {
          mutexes[indices.first]->lock();
          if (mutexes[indices.second]->try_lock()) {
            break;
          }

          mutexes[indices.first]->unlock();
        }

        spin(FLAGS_iterations);

        mutexes[indices.first]->unlock();
        mutexes[indices.second]->unlock();
      }
    });
  }

  barrier.wait();
  suspender.dismissing([&] {
    for (auto& thread : threads) {
      thread.join();
    }
  });
}

template <typename LockingFunc>
void simple(std::size_t iters, LockingFunc func) {
  auto&& suspender = BenchmarkSuspender{};
  auto&& one = std::mutex{};
  auto&& two = std::mutex{};
  auto&& barrier = BenchmarkStartBarrier{3};

  auto threadOne = std::thread{[&] {
    barrier.wait();

    for (auto i = std::size_t{0}; i < iters; ++i) {
      auto lckOne = std::unique_lock<std::mutex>{one, std::defer_lock};
      auto lckTwo = std::unique_lock<std::mutex>{two, std::defer_lock};
      func(lckOne, lckTwo);

      spin(FLAGS_iterations);
    }
  }};

  auto threadTwo = std::thread{[&] {
    barrier.wait();

    for (auto i = std::size_t{0}; i < iters; ++i) {
      auto lck = std::unique_lock<std::mutex>{one};
      spin(FLAGS_iterations * FLAGS_iterations);
    }
  }};

  auto threadThree = std::thread{[&] {
    barrier.wait();

    for (auto i = std::size_t{0}; i < iters; ++i) {
      auto lck = std::unique_lock<std::mutex>{two};
      spin(FLAGS_iterations * FLAGS_iterations);
    }
  }};

  barrier.wait();
  suspender.dismissing([&] {
    threadOne.join();
    threadTwo.join();
    threadThree.join();
  });
}

template <typename LockingFunc>
void pathological(std::size_t iters, LockingFunc func) {
  auto&& suspender = BenchmarkSuspender{};
  auto&& one = std::mutex{};
  auto&& two = std::mutex{};
  auto&& three = std::mutex{};
  auto&& barrier = BenchmarkStartBarrier{3};

  auto threadOne = std::thread{[&] {
    barrier.wait();

    for (auto i = std::size_t{0}; i < iters; ++i) {
      auto lckOne = std::unique_lock<std::mutex>{one, std::defer_lock};
      auto lckTwo = std::unique_lock<std::mutex>{two, std::defer_lock};
      auto lckThree = std::unique_lock<std::mutex>{three, std::defer_lock};
      func(lckOne, lckTwo, lckThree);

      spin(FLAGS_iterations);
    }
  }};

  auto threadTwo = std::thread{[&] {
    barrier.wait();

    for (auto i = std::size_t{0}; i < iters; ++i) {
      auto lck = std::unique_lock<std::mutex>{one};

      spin(FLAGS_iterations * FLAGS_iterations);
    }
  }};

  auto threadThree = std::thread{[&] {
    barrier.wait();

    for (auto i = std::size_t{0}; i < iters; ++i) {
      auto lckTwo = std::unique_lock<std::mutex>{two};
      auto lckThree = std::unique_lock<std::mutex>{three};

      spin(FLAGS_iterations * FLAGS_iterations);
    }
  }};

  barrier.wait();
  suspender.dismissing([&] {
    threadOne.join();
    threadTwo.join();
    threadThree.join();
  });
}

template <typename LockingFunc>
void uncontended(std::size_t iters, LockingFunc func) {
  auto&& suspender = BenchmarkSuspender{};
  auto&& one = std::mutex{};
  auto&& two = std::mutex{};

  suspender.dismissing([&] {
    for (auto i = std::size_t{0}; i < iters; ++i) {
      func(one, two);

      spin(FLAGS_iterations);

      one.unlock();
      two.unlock();
    }
  });
}

void spin(int iterations) {
  for (auto i = 0; i < iterations; ++i) {
    doNotOptimizeAway(i);
  }
}

} // namespace