sergeymakeev/taskscheduler

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

About

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

Written under the influence by great GDC talk "Parallelizing the Naughty Dog engine using fibers" by Christian Gyrling

Compiled and worked on : Clang 3.4, GCC 4.8.2, MSVC 2010/2012/2015/2017, XCODE 6.4

Commercial games using Task Scheduler

• Skyforge (PC, PS4, X1)

Build status

Linux + OS X

Windows

Usage examples

Minimal example

#include <MTScheduler.h>

// Declare simple task
struct SimpleTask
{
  MT_DECLARE_TASK(SimpleTask, MT::StackRequirements::STANDARD, MT::TaskPriority::NORMAL, MT::Color::Blue);

  void Do(MT::FiberContext&)
  {
    // ... do thing here ...
  }
};

int main()
{
  // Create scheduler
  MT::TaskScheduler scheduler;

  // Declare tasks
  static const int TASK_COUNT = 1000;
  SimpleTask tasks[TASK_COUNT];

  // Run everything
  scheduler.RunAsync(MT::TaskGroup::Default(), &tasks[0], MT_ARRAY_SIZE(tasks));

  // Wait and help to execute unfinished tasks
  scheduler.WaitAll(1000)

  return 0;
}

You can find a lot of usage examples in the test folder: https://github.com/SergeyMakeev/TaskScheduler/tree/master/SchedulerTests/Tests

Useful reading (in random order):

Parallelizing the Naughty Dog engine using fibers by Christian Gyrling

http://www.swedishcoding.com/wp-content/uploads/2015/03/parallelizing_the_naughty_dog_engine_using_fibers.pdf

id Tech 5 Challenges From Texture Virtualization to Massive Parallelization by J.M.P. van Waveren

http://s09.idav.ucdavis.edu/talks/05-JP_id_Tech_5_Challenges.pdf

Doom3 BFG Source Code Review: Multi-threading by Fabien Sanglard

http://fabiensanglard.net/doom3_bfg/threading.php

How Ubisoft Develops Games for Multicore - Before and After C++11 by Jeff Preshing

http://www.youtube.com/watch?v=X1T3IQ4N-3g

Killzone Shadow Fall: Threading the Entity Update on PS4 by Jorrit Rouwe

http://www.slideshare.net/jrouwe/killzone-shadow-fall-threading-the-entity-update-on-ps4

Killzone Shadow Fall Demo Postmortem by Michal Valient

http://www.guerrilla-games.com/presentations/Valient_Killzone_Shadow_Fall_Demo_Postmortem.pdf

Infamous Second Son : Engine Postmortem by Adrian Bentley

http://adruab.net/wp-images/GDC14_infamous_second_son_engine_postmortem.pdf

Multithreading the Entire Destiny Engine - GDC 2015 by Barry Genova

http://www.gdcvault.com/play/1022164/Multithreading-the-Entire-Destiny (members only) http://chomikuj.pl/dexio21/GDC+2015/GDC+Vault+-+Multithreading+the+Entire+Destiny+Engine,4690817362.mp4%28video%29

Intel Threading Building Blocks - Scheduling Algorithm

https://www.threadingbuildingblocks.org/docs/help/reference/task_scheduler/scheduling_algorithm.htm

CILK/CILK++ and Reducers

http://www.slideshare.net/yunmingzhang/yunming-zhang-presentations

Task Scheduling Strategies by Dmitry Vyukov

http://www.1024cores.net/home/scalable-architecture/task-scheduling-strategies

Implementing a Work-Stealing Task Scheduler on the ARM11 MPCore

http://www.rtcgroup.com/arm/2007/presentations/211%20-%20Implementing%20a%20Work-Stealing%20Task%20Scheduler.pdf

Lost Planet graphics course for 3D game fan of Nishikawa Zenji

http://game.watch.impress.co.jp/docs/20070131/3dlp.htm

Dragged Kicking and Screaming: Source Multicore by Tom Leonard

http://www.valvesoftware.com/publications/2007/GDC2007_SourceMulticore.pdf

Games: Playing with Threads by Ben Nicholson

http://www2.epcc.ed.ac.uk/downloads/lectures/BenNicholson/BenNicholson.pdf

Work Stealing by Pablo Halpern

https://github.com/CppCon/CppCon2015/tree/master/Presentations/Work%20Stealing

Enki Task Scheduler by Doug Binks

http://www.enkisoftware.com/devlogpost-20150822-1-Implementing_a_lightweight_task_scheduler.html

http://www.enkisoftware.com/devlogpost-20150905-1-Internals_of_a_lightweight_task_scheduler.html

Molecule Engine blog - Job System 2.0 by Stefan Reinalter

http://blog.molecular-matters.com/2015/08/24/job-system-2-0-lock-free-work-stealing-part-1-basics/

http://blog.molecular-matters.com/2015/09/08/job-system-2-0-lock-free-work-stealing-part-2-a-specialized-allocator/

http://blog.molecular-matters.com/2015/09/25/job-system-2-0-lock-free-work-stealing-part-3-going-lock-free/

Molecule Engine blog - Building a load-balanced task scheduler by Stefan Reinalter

http://blog.molecular-matters.com/2012/04/05/building-a-load-balanced-task-scheduler-part-1-basics/

http://blog.molecular-matters.com/2012/04/12/building-a-load-balanced-task-scheduler-part-2-task-model-relationships/

http://blog.molecular-matters.com/2012/04/25/building-a-load-balanced-task-scheduler-part-3-parent-child-relationships/

http://blog.molecular-matters.com/2012/07/09/building-a-load-balanced-task-scheduler-part-4-false-sharing/

Do-it-yourself Game Task Scheduling by Jerome Muffat-Meridol

https://software.intel.com/en-us/articles/do-it-yourself-game-task-scheduling

Acquire and Release Semantics by Jeff Preshing

http://preshing.com/20120913/acquire-and-release-semantics/

Lockless Programming Considerations for Xbox 360 and Microsoft Windows

https://msdn.microsoft.com/en-us/library/windows/desktop/ee418650(v=vs.85).aspx

C/C++11 mappings to processors by Peter Sewell

https://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html

Memory Ordering in Modern Microprocessors, Part I by Paul E. McKenney http://www.linuxjournal.com/node/8211/print

Memory Ordering in Modern Microprocessors, Part II by Paul E. McKenney http://www.linuxjournal.com/node/8212/print

Barrier Litmus Tests and Cookbook by ARM https://developer.arm.com/documentation/genc007826/latest https://documentation-service.arm.com/static/5ece8d6a56a54774bd17a1f4

taskscheduler's Issues

hasNewTasksEvent signal results in infinite look on Apple Silicon

Hey, I noticed that the example project does not work on Apple Silicon. It causes an infinite loop in MTScheduler.cpp
line 719 (the context.hasNewTasksEvent.Signal(); takes infinite time).

The Run(MT::FiberContext& context) function is empty so it should finish immediately.

Im using the latest version from Github.
MacOS version: 11.2.2

Windows CreateFiber performance

I was curious about this comment in the code:

I don't use standard Windows Fibers since they are wasteful use of Virtual Memory space for the stack. ( 1Mb for each Fiber )

The CreateFiberEx function allows you to specify reserve & commit stack sizes. 1Mb seems to be only the default stack size if these are set to 0.

I'd love to hear your thoughts about this.

The ::CreateFiberEx stack size issue...

To make it work correctly dwStackCommitSize must be less than dwStackReserveSize.

I did some research about this and I found these hints: ReactOS BaseCreateStack

ReactOS implementation follows somehow Thread Stack Size:

To change the initially committed stack space, use the dwStackSize parameter (...).This value is rounded up to the nearest page. Generally, the reserve size is the default reserve size specified in the executable header. However, if the initially committed size specified by dwStackSize is larger than or equal to the default reserve size, the reserve size is this new commit size rounded up to the nearest multiple of 1 MB.
To change the reserved stack size, set the dwCreationFlags parameter of CreateThread or CreateRemoteThread to STACK_SIZE_PARAM_IS_A_RESERVATION and use the dwStackSize parameter. In this case, the initially committed size is the default size specified in the executable header. For fibers, use the dwStackReserveSize parameter of CreateFiberEx. The committed size is specified in the dwStackCommitSize parameter.

IMO native Windows ::CreateFiberEx is implemented similary (wrongly) to what ReactOS provides, so, e.g.: ::CreateFiberEx(0, 1<<16, ...); or ::CreateFiberEx((1<<16)-1, 1<<16, ...); does the job and gives fiber with one page stack... enjoy :)

Emscripten Support

Hi,

Thank you for this great library. Is it possible to have emscripten support using its fiber library https://emscripten.org/docs/api_reference/fiber.h.html ?

Test "YieldTasks" fails on CPUs with more than 8 physical threads

In SimpleTests.cpp, line 192, this vector is declared:

MT::StaticVector<YieldTask, 512> tasks;

which is then filled with taskCount elements. On CPUs with many threads, taskCount easily exceeds 512, it is 900 with 16 threads for example.

Subsequently if raising that limit to a "safe" maximum, like 2048, line 206 has to be adjusted as well to pass taskCount instead of tasks.Size() to RunAsync:

scheduler.RunAsync(MT::TaskGroup::Default(), tasks.Begin(), (uint32)taskCount);

Sadly the test fails on my CPU even after this fix at the check in line 163:

CHECK_EQUAL(TASK_COUNT_PER_WORKER, state1->counterPhase0);

Where TASK_COUNT_PER_WORKER is 60, but state1->counterPhase0 is 0.

System:
Win10 1809
VS19 Toolset v142
Ryzen 2700X

Fails to compile in Xcode 9.2

Compiler complains about include paths

Added preprocessor-check on exist support SSE

ENG:
Added check on exist support SSE on compiler, if not exist, will use equal C-code.(Is needed for porting on Android
patch.zip

RU:
Добавлена проверка на наличие SSE, если поддержки нету, используется C код.

LockFreeQueueMPMC optimization due to superfluous MoveCtor

Based on lessons-learned from my games with FiberTaskingLib: WaitFreeQueue item-copy I want to address here our TaskScheduler LockFreeQueueMPMC current implementation:

(ed. WFQ by definition) ...stores elements by value semantics, returning by copy is correct, as the items don't have further identity than what their value is.

Now, let's notice that we have got only, well defined three usages of LockFreeQueueMPMC:

• Groups pool: availableGroups;
• Fibers pool: standartFibersAvailable and extendedFibersAvailable;

All of these have a simple POD content (again: well defined) TaskGroup, FiberContext* respectively, so a simple copy in LockFreeQueueMPMC::TryPush and LockFreeQueueMPMC::TryPop is actually enough here, memory for Cell:data is already there on LockFreeQueueMPMC stack - instead of going through move semantics with MoveCtor.
This, lets say a patch, resembles on what Dmitri shows on his blog and also a general idea of WFQ (i.e.: store/return by value semantics).

FYI: I have got ~25% speedup during TaskSchedulerTests with value-copy approach (12.75s to 9.50s) on my 8-core x64, compiled in Debug config by VS 15.9.0 preview 2.0.