slide-rs / fibe-rs Goto Github PK

Naughty Dog fibers

Destiny multi-threading

ND seems to be fond of spawning child tasks, waiting for them, and then continuing. They achieve it with atomic counters:

Counter* pJobCounter = NULL;
RunJobs(&jobDecls, 100, &pJobCounter);
WaitForCounterAndFree(pJobCounter, 0);

Not sure if it's a good idea to allow this. It's certainly easier to scale this way, since you don't need to re-think the way you schedule tasks and instead just tweak existing tasks. But it's not obvious that it's worth the complexity.

The amount of options a Task can have is growing a bit to quickly:

• Is the task a child of the parent, or a true fork
• Is the task a Trait, Closure, or Coroutine
• Does the task need to run on a thread, or in the threadpool?

All in all, I think this needs to be moved to a builder style api to avoid some of this confusion.

Something like low/med/high would be useful. Thinking about how these would differ, we could have the next job selector to look for the highest priority first, which makes sense within the limited number of execution contexts.

The idea here is that the Main thread can be added as part of the thread pool. This works with #21 and allows your IO/GL threads to be used for other work if they are waiting on input.

We could have a Future trait for the following things:

• same code to work on plain data, std::sync::Future, and our custom futures
• simpler implementations for futures with no dependencies, or a single dependency
• way to get implicit parallelism

This is pretty simple, we can have a task (or collection of tasks) that do not implement Send. This means the task must run on the local thread (via local queues of course). The purpose of this is that a Pinned task needs to run on a specific thread because of Some TLS reason.

An example would be a thread that needs to run the input processing or to use an OpenGL context.

Possible interface could be:

enum SpawnMode {
   Unlimited, // currently implemented mode, one thread per task
   ThreadPool(u8), //count
   AffinityMask(u64), //mask
}

Currently the work stealing scheduler has very odd scaling characteristics. I will place a * that these numbers are not realistic for a real application, since a real application would probably have more then a nop as a task. But still, the scheduler does not scale as well as I would have hoped.

1 thread

test bench_fibb_steal     ... bench:    291708 ns/iter (+/- 18080)
test chain_10_use_die     ... bench:     53808 ns/iter (+/- 5997)
test chain_10_wait        ... bench:     84236 ns/iter (+/- 5503)
test chain_1_000_use_die  ... bench:    421437 ns/iter (+/- 195312)
test chain_1_000_wait     ... bench:    418457 ns/iter (+/- 6165)
test fanout_1_000         ... bench:    596724 ns/iter (+/- 7209)
test repeat_100_x_100     ... bench:   7239210 ns/iter (+/- 5359287)
test repeat_1_000         ... bench:   1008281 ns/iter (+/- 330520)
test repeat_1_000_x_1_000 ... bench: 362229939 ns/iter (+/- 18925219)
test start_die            ... bench:     51569 ns/iter (+/- 6169)

4 threads

test bench_fibb_steal     ... bench:   2318548 ns/iter (+/- 516592)
test chain_10_use_die     ... bench:    148295 ns/iter (+/- 12029)
test chain_10_wait        ... bench:    119859 ns/iter (+/- 39196)
test chain_1_000_use_die  ... bench:    474476 ns/iter (+/- 89795)
test chain_1_000_wait     ... bench:    591176 ns/iter (+/- 164828)
test fanout_1_000         ... bench:  10284883 ns/iter (+/- 1993024)
test repeat_100_x_100     ... bench:   2194172 ns/iter (+/- 2243956)
test repeat_1_000         ... bench:   1203489 ns/iter (+/- 186731)
test repeat_1_000_x_1_000 ... bench: 180651629 ns/iter (+/- 31147220)
test start_die            ... bench:    141690 ns/iter (+/- 10331)

12 threads

test bench_fibb_steal     ... bench:   4266370 ns/iter (+/- 1680482)
test chain_10_use_die     ... bench:    782393 ns/iter (+/- 2540535)
test chain_10_wait        ... bench:    178198 ns/iter (+/- 32233)
test chain_1_000_use_die  ... bench:    774855 ns/iter (+/- 1612068)
test chain_1_000_wait     ... bench:    704695 ns/iter (+/- 196897)
test fanout_1_000         ... bench:  18206514 ns/iter (+/- 4213723)
test repeat_100_x_100     ... bench:   1432300 ns/iter (+/- 99255)
test repeat_1_000         ... bench:   1127044 ns/iter (+/- 462414)
test repeat_1_000_x_1_000 ... bench: 111746427 ns/iter (+/- 8963304)
test start_die            ... bench:   1875302 ns/iter (+/- 2491521)

A few of the tests are basically benchmarks of spawning threads start_die, chain_10_use_die for example.

It worries me that bench_fibb_steal gets worse as threads are added (it should be very parallel). And repeat_1_000_x_1_000 is at best a 3 times increase.

Perhaps, use coroutine-rs