Cheap and reliable Node.js hosting starts at $3/month, and $1/month static HTML hosting

Created with love in Canada, visit hostnodejs.com today

Feel like to post an Ad? Learn Details

All Projects → RichieSams → Fibertaskinglib

RichieSams / Fibertaskinglib

Licence: other

A library for enabling task-based multi-threading. It allows execution of task graphs with arbitrary dependencies.

Programming Languages

cpp

1120 projects

Labels

coroutines multithreading task-scheduler fibers

Projects that are alternatives of or similar to Fibertaskinglib

AIO

Coroutine-based multithreading library for Delphi

Stars: ✭ 99 (-85.42%)

Mutual labels: coroutines, fibers, multithreading

Concurrencpp

Modern concurrency for C++. Tasks, executors, timers and C++20 coroutines to rule them all

Stars: ✭ 340 (-49.93%)

Mutual labels: coroutines, multithreading, task-scheduler

Minicoro

Single header asymmetric stackful cross-platform coroutine library in pure C.

Stars: ✭ 164 (-75.85%)

Mutual labels: coroutines, fibers

muco

Multithreaded Coroutines library

Stars: ✭ 20 (-97.05%)

Mutual labels: coroutines, fibers

asynchronous

A D port of Python's asyncio library

Stars: ✭ 35 (-94.85%)

Mutual labels: coroutines, fibers

Boson

A C++14 framework for asynchronous I/O, cooperative multitasking and green threads scheduling

Stars: ✭ 154 (-77.32%)

Mutual labels: coroutines, fibers

Zewo

Lightweight library for web server applications in Swift on macOS and Linux powered by coroutines.

Stars: ✭ 1,856 (+173.34%)

Mutual labels: coroutines, fibers

TaskManager

A C++14 Task Manager / Scheduler

Stars: ✭ 81 (-88.07%)

Mutual labels: multithreading, task-scheduler

bikeshed

Lock free hierarchical work scheduler

Stars: ✭ 78 (-88.51%)

Mutual labels: multithreading, task-scheduler

Weave

A state-of-the-art multithreading runtime: message-passing based, fast, scalable, ultra-low overhead

Stars: ✭ 305 (-55.08%)

Mutual labels: multithreading, task-scheduler

Umka Lang

Umka: a statically typed embeddable scripting language

Stars: ✭ 308 (-54.64%)

Mutual labels: coroutines, fibers

Mioco

[no longer maintained] Scalable, coroutine-based, fibers/green-threads for Rust. (aka MIO COroutines).

Stars: ✭ 125 (-81.59%)

Mutual labels: coroutines, fibers

Venice

Coroutines, structured concurrency and CSP for Swift on macOS and Linux.

Stars: ✭ 1,501 (+121.06%)

Mutual labels: coroutines, fibers

Poseidon

Poseidon Server Framework (refactor WIP)

Stars: ✭ 162 (-76.14%)

Mutual labels: coroutines, fibers

May

rust stackful coroutine library

Stars: ✭ 909 (+33.87%)

Mutual labels: coroutines, fibers

Swiftcoroutine

Swift coroutines for iOS, macOS and Linux.

Stars: ✭ 690 (+1.62%)

Mutual labels: coroutines, multithreading

Fibry

The first Java Actor System supporting fibers from Project Loom

Stars: ✭ 146 (-78.5%)

Mutual labels: multithreading, fibers

Px sched

Single Header C++11 Task Scheduler

Stars: ✭ 182 (-73.2%)

Mutual labels: multithreading, task-scheduler

lucy job system

Fiber-based job system with extremely simple API

Stars: ✭ 78 (-88.51%)

Mutual labels: fibers, multithreading

Taskscheduler

Cross-platform, fiber-based, multi-threaded task scheduler designed for video games.

Stars: ✭ 402 (-40.8%)

Mutual labels: multithreading, fibers

View All Similar Projects ➔

= Fiber Tasking Lib

This is a library for enabling task-based multi-threading. It allows execution of task graphs with arbitrary dependencies. Dependencies are represented as atomic counters.

Under the covers, the task graph is executed using fibers, which in turn, are run on a pool of worker threads (one thread per CPU core). This allows the scheduler to wait on dependencies without task chaining or context switches.

This library was created as a proof of concept of the ideas presented by Christian Gyrling in his 2015 GDC Talk 'Parallelizing the Naughty Dog Engine Using Fibers'

http://gdcvault.com/play/1022186/Parallelizing-the-Naughty-Dog-Engine[Free GDC Vault Recorded Presentation] + http://twvideo01.ubm-us.net/o1/vault/gdc2015/presentations/Gyrling_Christian_Parallelizing_The_Naughty.pdf[Slides]

:blank: pass:[ +] {blank}

Example

//// I'd love to have the below be an include:: block, so it's not possible to be out of date However, Github doesn't support include blocks. :( So we have to do it manually.

!! If you update this example, make sure it matches the code in examples/triangle_num.cpp !! ////

[source,cc]

#include "ftl/task_counter.h" #include "ftl/task_scheduler.h"

#include <assert.h> #include <stdint.h>

struct NumberSubset { uint64_t start; uint64_t end;

uint64_t total;

};

void AddNumberSubset(ftl::TaskScheduler *taskScheduler, void *arg) { (void)taskScheduler; NumberSubset *subset = reinterpret_cast<NumberSubset *>(arg);

subset->total = 0;

while (subset->start != subset->end) {
	subset->total += subset->start;
	++subset->start;
}

subset->total += subset->end;

}

/**

Calculates the value of a triangle number by dividing the additions up into tasks
A triangle number is defined as:
```
    Tn = 1 + 2 + 3 + ... + n
```
The code is checked against the numerical solution which is:
```
    Tn = n * (n + 1) / 2
```

*/ int main() { // Create the task scheduler and bind the main thread to it ftl::TaskScheduler taskScheduler; taskScheduler.Init();

// Define the constants to test
constexpr uint64_t triangleNum = 47593243ULL;
constexpr uint64_t numAdditionsPerTask = 10000ULL;
constexpr uint64_t numTasks = (triangleNum + numAdditionsPerTask - 1ULL) / numAdditionsPerTask;

// Create the tasks
// FTL allows you to create Tasks on the stack.
// However, in this case, that would cause a stack overflow
ftl::Task *tasks = new ftl::Task[numTasks];
NumberSubset *subsets = new NumberSubset[numTasks];
uint64_t nextNumber = 1ULL;

for (uint64_t i = 0ULL; i < numTasks; ++i) {
	NumberSubset *subset = &subsets[i];

	subset->start = nextNumber;
	subset->end = nextNumber + numAdditionsPerTask - 1ULL;
	if (subset->end > triangleNum) {
		subset->end = triangleNum;
	}

	tasks[i] = {AddNumberSubset, subset};

	nextNumber = subset->end + 1;
}

// Schedule the tasks
ftl::TaskCounter counter(&taskScheduler);
taskScheduler.AddTasks(numTasks, tasks, ftl::TaskPriority::High, &counter);

// FTL creates its own copies of the tasks, so we can safely delete the memory
delete[] tasks;

// Wait for the tasks to complete
taskScheduler.WaitForCounter(&counter);

// Add the results
uint64_t result = 0ULL;
for (uint64_t i = 0; i < numTasks; ++i) {
	result += subsets[i].total;
}

// Test
assert(triangleNum * (triangleNum + 1ULL) / 2ULL == result);

// Cleanup
delete[] subsets;

// The destructor of TaskScheduler will shut down all the worker threads
// and unbind the main thread

return 0;

}

{blank}

Automatic Test Matrix

{blank}

How it works

Honestly, the best explanation is to watch Christian Gyrling's talk. It's free to watch (as of the time of writing) from the GDC vault. His explaination of fibers as well as how they used the fiber system in their game engine is excellent. However, I will try to give a TL;DR; version here.

What are fibers

A https://msdn.microsoft.com/en-us/library/windows/desktop/ms682661%28v=vs.85%29.aspx[fiber] consists of a stack and a small storage space for registers. It's a very lightweight execution context that runs inside a thread. You can think of it as a shell of an actual thread.

Why go though the hassle though? What's the benefit?

The beauty of fibers is that you can switch between them extremely quickly. Ultimately, a switch consists of saving out registers, then swapping the execution pointer and the stack pointer. This is much much faster than a full-on thread context switch.

How do fibers apply to task-based multithreading?

To answer this question, let's compare to another task-based multithreading library: Intel's https://www.threadingbuildingblocks.org/[Threading Building Blocks]. TBB is an extremely well polished and successful tasking library. It can handle really complex task graphs and has an excellent scheduler. However, let's imagine a scenario:

. Task A creates Tasks B, C, and D and sends them to the scheduler . Task A does some other work, but then it hits the dependency: B, C, and D must be finished. . If they aren't finished, we can do 2 things: a. Spin-wait / Sleep b. Ask the scheduler for a new task and start executing that . Let's take path b . So the scheduler gives us Task G and we start executing . But Task G ends up needing a dependency as well, so we ask the scheduler for another new task . And another, and another . In the meantime, Tasks B, C, and D have completed . Task A could theoretically be continued, but it's buried in the stack under the tasks that we got while we were waiting . The only way we can resume A is to wait for the entire chain to unravel back to it, or suffer a context switch.

Now, obviously, this is a contrived example. And as I said above, TBB has an awesome scheduler that works hard to alleviate this problem. That said, fibers can help to eliminate the problem altogether by allowing cheap switching between tasks. This allows us to isolate the execution of one task from another, preventing the 'chaining' effect described above.

{blank}

The Architecture from 10,000 ft

(Christian has some great illustrations on pages 8 - 17 of his slides that help explain the flow of fibers and tasks. I suggest looking at those while you're reading)

Task Queue - An 'ordinary' queue for holding the tasks that are waiting to be executed. In the current code, there is only one queue. However, a more sophisticated system might have multiple queues with varying priorities.

Fiber Pool - A pool of fibers used for switching to new tasks while the current task is waiting on a dependency. Fibers execute the tasks

Worker Threads - 1 per logical CPU core. These run the fibers.

Waiting Tasks - A list of the tasks that are waiting for a dependency to be fufilled. Dependencies are represented with atomic counters

Tasks can be created on the stack. They're just a simple struct with a function pointer and an optional void *arg to be passed to the function:

[source,cc]

struct Task { TaskFunction Function; void *ArgData; };

[source,cc]

Task tasks[10]; for (uint i = 0; i < 10; ++i) { tasks[i] = {MyFunctionPointer, myFunctionArg}; }

You schedule a task for execution by calling TaskScheduler::AddTasks()

[source,cc]

ftl::TaskCounter counter(taskScheduler); taskScheduler->AddTasks(10, tasks, ftl::TaskPriority::High, &counter);

The tasks get added to the queue, and other threads (or the current one, when it is finished with the current task) can start executing them when they get popped off the queue.

AddTasks can optionally take a pointer to a TaskCounter. If you do, the value of the counter will incremented by the number of tasks queued. Every time a task finishes, the counter will be atomically decremented. You can use this functionality to create depencendies between tasks. You do that with the function

[source,cc]

void TaskScheduler::WaitForCounter(TaskCounter *counter);

This is where fibers come into play. If the counter == 0, the function trivially returns. If not, the scheduler will move the current fiber into the Waiting Tasks list and grab a new fiber from the Fiber Pool. The new fiber pops a task from the Task Queue and starts execution with that.

But what about the task we stored in Waiting Tasks? When will it finish being executed?

When the TaskCounter hit zero from decrements, we add all the waiting fibers to the Ready Fibers list in the TaskScheduler. Before a fiber tries to pop a task off the Task Queue, it checks if there are any Ready Fibers. If so, it will return itself to the Fiber Pool and switch to the fiber that is ready. The ready fiber will continue execution right where it left off

{blank}

Advanced Features

FullAtomicCounter

TaskCounters are implemented with an internal atomic counter. However, access to this atomic counter is protected from the user for performance and algorithmic simplicity reasons. That said, it can be useful to be able to use WaitForCounter on something non task-related. That's where FullAtomicCounter comes in.

FullAtomicCounter has member functions correlaries for all the "regular" atomic functions (load, store, fetch_add, etc). Each time they're called, we check all waiting fibers if they're equal to their target value. In comparison, TaskCounter only checks when the final value is zero. Therefore, FullAtomicCounter has more overhead than TaskCounter, but much greater flexibility

Fibtex

Generally, you shouldn't use Mutexes in fiber code, for two reasons:

If you take a mutex, and call WaitForCounter(), when WaitForCounter resumes, your code could be on another thread. The mutex unlock will be undefined behavior, and probably lead to a deadlock
Mutex contention will block the worker threads. And since we generally don't oversubscribe the threads to the cores, this leaves cores idle.

To solve this, we created Fibtex. It implements the std lockable interface, so you can use it with all your favorite wrappers (std::lock_guard, std::unique_lock, etc.) It's implemented behind the scenes with a TaskCounter, so if a Fibtex is locked, a waiter can switch to another task and do valuable work

{blank}

Dependencies

C++11 Compiler
CMake 3.2 or greater

{blank}

Supported Platforms

{blank}

Building

FiberTaskingLib is a standard CMake build. However, for detailed instructions on how to build and include the library in your own project, see the https://github.com/RichieSams/FiberTaskingLib/blob/master/documentation/build_guide.asciidoc[documentation page].

{blank}

License

The library is licensed under the https://tldrlegal.com/license/apache-license-2.0-(apache-2.0)[Apache 2.0 license]. However, FiberTaskingLib distributes and uses code from other Open Source Projects that have their own licenses:

Boost Context Fork: https://github.com/RichieSams/FiberTaskingLib/tree/master/third_party/boost_context[Boost License v1.0]
Catch2: https://github.com/RichieSams/FiberTaskingLib/tree/master/third_party/catch2[Boost License v1.0]
Nonius: https://github.com/RichieSams/FiberTaskingLib/tree/master/third_party/nonius[CC0 1.0 Universal]

{blank}

Contributing

Contributions are very welcome. See the https://github.com/RichieSams/FiberTaskingLib/blob/master/CONTRIBUTING.asciidoc[contributing page] for more details.

{blank}

Request for Criticism

This implementation was something I created because I thought Christian's presentation was really interesting and I wanted to explore it myself. The code is still a work in progress and I would love to hear your critiques of how I could make it better. I will continue to work on this project and improve it as best as possible.

Note that the project description data, including the texts, logos, images, and/or trademarks, for each open source project belongs to its rightful owner. If you wish to add or remove any projects, please contact us at [email protected].

Stars: ✭ 679

Visit Git Page 🔗Visit User Page 🔗Visit Issues Page (21) 🔗