Google Git
Sign in
swiftshader / SwiftShader / 269f38fd6aaddbc3fc1d6768f871ef4edcccd421
commit269f38fd6aaddbc3fc1d6768f871ef4edcccd421[log] [tgz]
authorBen Clayton <bclayton@google.com>Fri Oct 02 13:24:32 2020 +0100
committerBen Clayton <bclayton@google.com>Fri Oct 02 13:24:32 2020 +0100
tree5aa02927b824582b736b5510e024b560ba521c04
parentfd00a00137be04f666ad54454a2ba209ff0aa47c [diff]
Squashed 'third_party/marl/' changes from d29553a3730..f1c446ccdc0

f1c446ccdc0 Fix instances of bugprone-move-forwarding-reference
8719a54cbe0 Kokoro: Get tar directories around the right way!
3a21f30c54e Kokoro: Package build artifacts into a .tar
57da063f48f Kokoro: Fix line continuation in release.bat
ecaa2602da1 Kokoro: Rename release script names
787cf0686d2 Kokoro: Add release configs
3ce8637191a Kokoro: Test ucontext fibers on linux.
62f0a0f9e39 osfiber_ucontext: Fix memory leak & warning
20dc482b9a0 CMake: Add flag for ucontext fibers
3815666523e Kokoro: Fix define_artifacts.regex
f51513856b6 Kokoro: Add define_artifacts action
d2d77650ec1 CMake: Put marl-benchmarks in a named FOLDER
95e505a3071 Fix markdown lint warnings in README.md
71d86a2bc04 Kokoro: Add config for continuous + so builds
5f897319c18 Reduce scheduler fiber stack size for tests
bc65ef5ebe5 Scheduler: Make the fiber stack size configurable
b61e279881c Remove deprecated scheduler [gs]etters
1a28daf0d89 Add license checker config and kokoro presubmit
3448974c1b0 Add marl::DAG - a AoT declarative task graph
9e77dcdd5a4 Kokoro: Migrate to new Windows VM instance
ac517aa6784 Fix schedule() with function arguments
834e558a138 Add missing include to export.h
1e8acb5695e MSVC build fixes.
84f047c114c Migrate from VERSION to CHANGES.md
0a1012317ab Annotate all public API inlines with MARL_NO_EXPORT
3689793cb1d Only notify one fiber in ConditionVariable::notify_one()
596e172322d CMake: Use -fvisibility=hidden by default
1d51df92c71 Disable by default deprecated scheduler [gs]etters
45be9b24830 README: Add FreeBSD and iOS to the list of OSes
4d68ade048a Export DLL public symbols for building marl as dll
1efb1e70228 Kokoro: Add configs for Android

git-subtree-dir: third_party/marl
git-subtree-split: f1c446ccdc0c611d1aeec4a6266a77693ae48c92
79 files changed
tree: 5aa02927b824582b736b5510e024b560ba521c04
  1. cmake/
  2. docs/
  3. examples/
  4. include/
  5. kokoro/
  6. src/
  7. third_party/
  8. tools/
  9. .clang-format
  10. .gitignore
  11. .gitmodules
  12. AUTHORS
  13. BUILD.bazel
  14. CHANGES.md
  15. CMakeLists.txt
  16. CONTRIBUTING.md
  17. LICENSE
  18. license-checker.cfg
  19. README.md
  20. WORKSPACE
README.md

Marl

Marl is a hybrid thread / fiber task scheduler written in C++ 11.

About

Marl is a C++ 11 library that provides a fluent interface for running tasks across a number of threads.

Marl uses a combination of fibers and threads to allow efficient execution of tasks that can block, while keeping a fixed number of hardware threads.

Marl supports Windows, macOS, Linux, FreeBSD, Fuchsia, Android and iOS (arm, aarch64, mips64, ppc64 (ELFv2), x86 and x64).

Marl has no dependencies on other libraries (with an exception on googletest for building the optional unit tests).

Example:

#include "marl/defer.h"
#include "marl/event.h"
#include "marl/scheduler.h"
#include "marl/waitgroup.h"

#include <cstdio>

int main() {
  // Create a marl scheduler using all the logical processors available to the process.
  // Bind this scheduler to the main thread so we can call marl::schedule()
  marl::Scheduler scheduler(marl::Scheduler::Config::allCores());
  scheduler.bind();
  defer(scheduler.unbind());  // Automatically unbind before returning.

  constexpr int numTasks = 10;

  // Create an event that is manually reset.
  marl::Event sayHello(marl::Event::Mode::Manual);

  // Create a WaitGroup with an initial count of numTasks.
  marl::WaitGroup saidHello(numTasks);

  // Schedule some tasks to run asynchronously.
  for (int i = 0; i < numTasks; i++) {
    // Each task will run on one of the 4 worker threads.
    marl::schedule([=] {  // All marl primitives are capture-by-value.
      // Decrement the WaitGroup counter when the task has finished.
      defer(saidHello.done());

      printf("Task %d waiting to say hello...\n", i);

      // Blocking in a task?
      // The scheduler will find something else for this thread to do.
      sayHello.wait();

      printf("Hello from task %d!\n", i);
    });
  }

  sayHello.signal();  // Unblock all the tasks.

  saidHello.wait();  // Wait for all tasks to complete.

  printf("All tasks said hello.\n");

  // All tasks are guaranteed to complete before the scheduler is destructed.
}

Benchmarks

Graphs of several microbenchmarks can be found here.

Building

Marl contains many unit tests and examples that can be built using CMake.

Unit tests require fetching the googletest external project, which can be done by typing the following in your terminal:

cd <path-to-marl>
git submodule update --init

Linux and macOS

To build the unit tests and examples, type the following in your terminal:

cd <path-to-marl>
mkdir build
cd build
cmake .. -DMARL_BUILD_EXAMPLES=1 -DMARL_BUILD_TESTS=1
make

The resulting binaries will be found in <path-to-marl>/build

Windows

Marl can be built using Visual Studio 2019's CMake integration.

Using Marl in your CMake project

You can build and link Marl using add_subdirectory() in your project's CMakeLists.txt file:

set(MARL_DIR <path-to-marl>) # example <path-to-marl>: "${CMAKE_CURRENT_SOURCE_DIR}/third_party/marl"
add_subdirectory(${MARL_DIR})

This will define the marl library target, which you can pass to target_link_libraries():

target_link_libraries(<target> marl) # replace <target> with the name of your project's target

You may also wish to specify your own paths to the third party libraries used by marl. You can do this by setting any of the following variables before the call to add_subdirectory():

set(MARL_THIRD_PARTY_DIR <third-party-root-directory>) # defaults to ${MARL_DIR}/third_party
set(MARL_GOOGLETEST_DIR  <path-to-googletest>)         # defaults to ${MARL_THIRD_PARTY_DIR}/googletest
add_subdirectory(${MARL_DIR})

Usage Recommendations

Capture marl synchronization primitves by value

All marl synchronization primitves aside from marl::ConditionVariable should be lambda-captured by value:

marl::Event event;
marl::schedule([=]{ // [=] Good, [&] Bad.
  event.signal();
})

Internally, these primitives hold a shared pointer to the primitive state. By capturing by value we avoid common issues where the primitive may be destructed before the last reference is used.

Create one instance of marl::Scheduler, use it for the lifetime of the process

The marl::Scheduler constructor can be expensive as it may spawn a number of hardware threads.
Destructing the marl::Scheduler requires waiting on all tasks to complete.

Multiple marl::Schedulers may fight each other for hardware thread utilization.

For these reasons, it is recommended to create a single marl::Scheduler for the lifetime of your process.

For example:

int main() {
  marl::Scheduler scheduler(marl::Scheduler::Config::allCores());
  scheduler.bind();
  defer(scheduler.unbind());

  return do_program_stuff();
}

Bind the scheduler to externally created threads

In order to call marl::schedule() the scheduler must be bound to the calling thread. Failure to bind the scheduler to the thread before calling marl::schedule() will result in undefined behavior.

marl::Scheduler may be simultaneously bound to any number of threads, and the scheduler can be retrieved from a bound thread with marl::Scheduler::get().

A typical way to pass the scheduler from one thread to another would be:

std::thread spawn_new_thread() {
  // Grab the scheduler from the currently running thread.
  marl::Scheduler* scheduler = marl::Scheduler::get();

  // Spawn the new thread.
  return std::thread([=] {
    // Bind the scheduler to the new thread.
    scheduler->bind();
    defer(scheduler->unbind());

    // You can now safely call `marl::schedule()`
    run_thread_logic();
  });
}

Always remember to unbind the scheduler before terminating the thread. Forgetting to unbind will result in the marl::Scheduler destructor blocking indefinitely.

Don't use externally blocking calls in marl tasks

The marl::Scheduler internally holds a number of worker threads which will execute the scheduled tasks. If a marl task becomes blocked on a marl synchronization primitive, marl can yield from the blocked task and continue execution of other scheduled tasks.

Calling a non-marl blocking function on a marl worker thread will prevent that worker thread from being able to switch to execute other tasks until the blocking function has returned. Examples of these non-marl blocking functions include: std::mutex::lock(), std::condition_variable::wait(), accept().

Short blocking calls are acceptable, such as a mutex lock to access a data structure. However be careful that you do not use a marl blocking call with a std::mutex lock held - the marl task may yield with the lock held, and block other tasks from re-locking the mutex. This sort of situation may end up with a deadlock.

If you need to make a blocking call from a marl worker thread, you may wish to use marl::blocking_call(), which will spawn a new thread for performing the call, allowing the marl worker to continue processing other scheduled tasks.

Note: This is not an officially supported Google product