Hello, my name is Vlad, I am a CEO and C++ developer with roughly eight years of experience.
Right now I work at a game dev company called Ubisoft, which some of you probably heard
about, with mostly low level networking and some bits of system programming.
And in Ubisoft, while doing a complete rewrite of our networking stack in one of game engines,
I managed to design, I hope, a cool algorithm for doing so-called task scheduling.
And today I share this algorithm in the form of this talk and an open source C++ implementation
of it.
Although, if you don't like C++, it doesn't have to be, today we focus just on the algorithms
and they can be implemented in some other language too, like in Rust, I'm sure it can
be done in Java, in C-sharp maybe.
So there will be a lot of content, so we will be going relatively quick and I ask you to
concentrate.
Talk will follow the plan firstly, what is task scheduling exactly, because many things
can be understood as it, then I explain how it's normally done, what are typical problems
with it.
I'm actually, at least, known to me and how worked an old task scheduler in my game engine
and how works the new one.
And then I will briefly show you the benchmarks, how it's verified and what are the future
plans for it.
So what is task scheduling exactly?
Today, in this talk, I mean, as task scheduling, any kind of execution of code, such as code
exec functions or something similar, and we just call it task, a generic term.
And so to give you a few examples, tasks can be callbacks in a thread pool, or tasks can
be watchers in an event loop like in LibF in C, we can have watchers as timers or wrapping
sockets and they also have callbacks, or we can also call tasks routines in some routine
engine like C++ routines or fibers in Toronto database.
So here is a very, very simple trivial scheduler implemented in C++ like pseudo code for simplicity,
which demonstrates this example.
So it's just a single thread.
It has a mutex locked queue for callbacks, and what it does is just executes those callbacks
one by one.
This is a very simple scheduler.
Now let's see if such a basic scheduler can solve a real task, which I had at Ubisoft.
Here, tasks execute requests coming to a server, and they handle save games, save game blobs.
And there might be tens of thousands of those requests per second, and they are also CPU
intensive.
So every task might take milliseconds of pure CPU time, and also they consist of multiple
steps like, I have to, in each task, lock user profile in some database, then I have
to download the save game blob from another database, then I have to do some pre-processing
of this blob, some stuff with some manipulations, then I have to upload it back and unlock the
user profile.
As you can guess, most of the time the task is not doing anything at all.
It just sleeps waiting for network input from the databases.
So literally more than 90% of times there is nothing happening in this task.
The trivial scheduler, which we just saw with single triad, it will not work here, it simply
will not scale.
Firstly, single triad is not enough to handle so many requests, so being so CPU intensive,
it will just choke on CPU.
Secondly, we can postpone blocked tasks and do other tasks while the first ones are waiting
for some events like network input.
So this means we need routines so that tasks could yield, so they could give up their time
to some other tasks in the same thread.
The game engine I'm working with had a good enough scheduler, which could do the job for
some years good enough.
This was just a thread pool where each thread had a list of own tasks, and when new tasks
were appearing, they were distributed to those threads in around Robin Manor one by one,
and they were pinned to those threads forever.
They could not migrate between threads.
And then what each worker thread does is updates all its tasks with some fixed hard-coded period
like once per 100 milliseconds or once per second.
Each task, after being updated, it can return false eventually, and it consider it done,
and it is deleted.
So this is some polling, basically, and we will call this scheduler updater because
there isn't much scheduling, really, it just updates those tasks without looking at their
state or anything, so we call it updater.
This updater thing had some typical problems, like schedulers of this type sometimes do.
Firstly, it was unfair, meaning that tasks were pinned to threads, they could not migrate.
This leads to a problem that your CPU usage will be unbalanced because some worker threads
will get heavy tasks, and a lot of them will stay in the queues, and other threads will
get light tasks and will be in idling most of the time.
This will happen even if you do perfect round robin, and all your tasks are the same because
actually tasks are never the same.
Like in my case, all the tasks do the same several steps, but save game blobs, they can
vary in size from kilobytes to megabytes, their processing, their downloading, obviously
takes not the same time, so some threads will be unfairly loaded, and they will perform
worse, at least in terms of latency, because they will have bigger queues, tasks will wait
longer in them, and that is not the only problem.
The other problem is polling, which in this case means the tasks, each task is updated
unconditionally with some fixed period regardless of task state, so every task is updated even
if it doesn't have work to do yet, so it's still waiting for network input.
What it means is that if you select too big polling interval, then you will have too high
latency, more than you could have.
For instance, imagine like we have a task with just three steps, each taking five milliseconds,
and in between it waits for some network input, and we will update it once per hundred milliseconds.
Then your task will always at least take 215 milliseconds.
The thing is, you don't always need so much time.
Most of the time, like almost always, the network response will arrive earlier than
100 milliseconds expire, and you have events to process, but you are not doing it because
it's not yet time to update the task, so we have higher latency than we could have.
If you try to fight it, try to set lower polling interval, then you will burn CPU without need,
because you will have spurious wakeups, so unnecessary wakeups.
You will sometimes wake up tasks before they have stuff to do.
Then it sounds too bad, like how expensive can it be, really, and imagine like spurious
update of a task would cost us just 10 microseconds.
To check a deadline or check an atomic flag, lock and lock, and you text and that's it.
It's not much, but if you have 10,000 tasks per second doing those unnecessary wakeups,
you just burned 10% of one CPU core, which already sounds worse, and this problem aggravates
if you have more threads than CPU cores.
Because then you didn't just burn the CPU time.
You stole it from other threads, which could spend it on something useful.
This problem was actually real, and during low tests, some servers were spending more
CPU time on spurious wakeups than on doing actual work, because they were just burning
so much for the green data clusters.
What we need on the summary from a really performance schedule, firstly, it should be
fair.
We are not allowed to pin tasks to threads.
It doesn't scale.
Secondly, we need routines, so that tasks could give up their time, so they could yield
and let the worker thread do some other work, other tasks.
And also, we have zero tolerance against polling, no polling at all, everything should be event
based.
And these goals are achieved in a new scheduler, which I do to lack of fantasy, just called
the task scheduler.
Although the name is a pretty self-explanatory, what it does, the plan is that we will go
firstly, we'll look at the big picture of the entire scheduler, and then we will look
at individual parts of the scheduler, when you will already know what they do.
Imagine like we have a process, this server running, it's a process.
It has multiple threads, and they produce tasks.
And we have a global object of type task scheduler in the process, like it can be C++ task scheduler,
Java task scheduler, whatever language you implemented it in, it is a global object in
the process.
And those threads, they produce tasks, so they receive some requests from clients and
post the, wrap them into tasks and post into the task scheduler in form of some callbacks
of some sort.
In the scheduler, they will gather in a so-called front queue.
Then the scheduler will periodically pick up, take all the tasks from the front queue,
and inspect them one by one.
It will see that some tasks are ready to be executed right now, the red ones on the slide.
They want to be executed at SAP, and some other tasks they do not want to be executed
right now, they just yielded.
We have routines, so there will be tasks which don't want to be executed now.
They are waiting for something.
For a deadline or for an explicit wake up for some event, they are moved into the wait
queue, where they will wait for their events.
So from the wait queue, we extract some older tasks which were already sleeping there for
some time, and now their deadline is up, or they were woken up explicitly, either way
we extract them from the queue, and all those red tasks go to the ready queue.
And from here, they are extracted by the worker threads, which take them from the ready queue
one by one and execute.
And this is basically the entire pipeline, it's not too complicated, although some of
you could already have a question, who does this part?
We have external threads posting tasks.
We have worker threads doing tasks, but who does the scheduling itself, managing management
of the queues?
The thing is, there is no dedicated thread doing just the scheduling.
Instead, the worker threads compete for doing the scheduling, depending on who of them is
idle.
Imagine, like this big rectangle with queues, it's a room with a single key to it.
And the worker threads, sometimes, depending on who of them is idle, again, will try to
pick out the key.
Whoever does it first, enters the room, does the scheduling, this queue management stuff,
leaves the room, and starts doing tasks.
So all the threads are the same.
There is no threads having goals of some sort, like a naive implementation could do.
And it's a bit like dining philosophers' problem, except that we have just one fork here.
And this big rectangle, in this case, is just a plate of spaghetti, but not on code, code
is clean.
To improve understanding, there is a short visual example I prepared.
Imagine, like, we have five tasks.
They are posted onto the front queue, and one of the worker threads has the scheduling
key right now.
It will extract the tasks from the queue.
We'll see that a couple of them yielded.
They go to the wait queue, waiting for something, and the others are moved into the ready queue.
From here, they are picked up by the worker threads.
Nobody is doing the scheduling right now.
All the threads are doing some actual work.
A couple of tasks are done, and suddenly, those waiting tasks are woken up, or their
deadline is up.
They want to be executed now.
So one of the worker threads will eventually pick up the scheduling key.
We'll notice this.
We'll move the tasks into the ready queue, and in parallel, some other thread finished
and older tasks.
Now, those two tasks are picked up by a couple of random threads.
They are done, and some other thread will pick up the scheduling key, and the process
repeats all the time when new tasks arrive.
This is it.
What we need to implement all this cool stuff, the language and the libraries, which we will
be using, need to provide us with the following stuff, at least.
We need mutexes, containers like race, lists, condition variables, and not important for
the algorithm, but for the implementation, for the performance, it's extremely important.
We will also need log-free atomic operations.
Just in case not all of you know what they are, here is a short pseudo code explaining
what these log-free atomics are, we will need three of them.
Firstly, it's atomic load, which is basically reading a variable, but with respect to so-called
memory models, which, again, Google afterwards, it's too complicated topic to dive in right
now.
We will also need atomic compare exchange, which is conditional assignment.
So we set a new value to some variable if it was equal to something else which we wanted
to check.
And we will also need atomic exchange.
So it sets a new value and returns the old value.
The cool stuff about those log-free atomics is that they are not only atomic, but they
are log-free.
There is no mutexes.
On the contrary, mutexes use this stuff inside.
And how they are implemented, they are special instructions right on the CPU.
So doing those operations doesn't even involve the kernel.
It's quite cheap if you use it efficiently.
And those three operations are basis for some very cool and extremely performant algorithms,
as we will see.
Not just here.
There are a lot of those algorithms based on those log-free atomic operations.
They are also called log-free algorithms.
And we will follow the task pipeline, looking at the scheduler parts, and we will start
from the front queue, just like the tasks.
We know that this queue has multiple producers, and it has a single consumer.
So it means this queue is multi-producer, single-consumer.
This is a common notation for naming queues.
We say multi-produce, multi- or single-producer, multi- or single-consumer, and we get four
combinations of queue types.
This is multi-producer, single-consumer.
We also know about this queue that it will experience high contention, because I want
my scheduler to be functional.
When I have tens of threads and millions of tasks per second, this means extreme contention
on the front queue.
This in turn means I should avoid mutexes, because mutexes most likely will choke here.
What you would do in a normal queue, not thread safe or anything, you would have to remember
two positions, head and tail, and maintain those positions.
If you try to turn this algorithm into a log-free thread safe implementation, it would be nightmare,
because the more variables you have to update in a log-free way, the more complicated the
algorithm gets, and queue, like with two variables, it's extremely hard to implement in a log-free
way.
We should try to avoid this if possible, and the idea is let's make it a stack instead
of queue.
So we will maintain just one position, the top item, and that's it.
We don't need two variables here, and then the algorithm becomes quite simple.
Pushing is, well, we try to link new item with the old top, set it, atomic compare exchange
will fail, if some other threads does it faster than we are in this push, and we don't retry
it.
It's pretty simple.
The more complicated part, although it looks shorter, is popping the items.
The thing is that how pop is implemented, we just replace top item with null, effectively
taking all the items at once.
We cannot pop them one by one.
And also, we have to reverse the list before we return it, because when we are pushing
items in FIFO order, pushing them on the stack, they are returned in LIFO order, and we want
to maintain the order, so we have to reverse it again.
These are two downsides that we can't pop one by one, and we have to reverse the result
before returning it.
On the other hand, what we get, it is completely lock free, thread safe, and it's weight free.
Who will win those drawbacks for being lock free and weight free?
We will see in the end in the benchmark section.
Next part of the task journey is weight queue.
As we know, it stores yielded tasks, so they are waiting for something, like in 99 percent
of cases, they are waiting for a deadline.
Since we are using tasks for requests, requests usually have a timeout, meaning that they
have a deadline.
So what we need is to be able to quickly pop all tasks with expired deadline, simply because
we have to do everything here quickly, there is a lot of tasks.
And we also know that this queue is always accessed by one third at a time.
The current scheduler worker who owns the scheduling key, so there is no concurrency
on this queue.
And that gives us quite a lot of freedom about what data structures we can use.
That basically means we can use binary heap.
It's ideal for such a job when you have to quickly pop something sorted by a thing like
deadline.
What happens is that we sort the tasks by deadlines here, basically.
So the task with the closest deadline will be on top and we will be able, for constant
time, tell immediately if any task has expired by just looking at the top.
And in case not all of you know what binary heap is, there is a brief explanation.
It's a perfectly balanced binary tree where each node value is less than values of its
child nodes.
We call this minimal heap.
If we reverse the order, it will be called maximal heap.
And this heap, it has quite good complexity.
Quite good complexity.
So for logarithmic time, we can pop any items even from the middle.
We can push new items also for logarithmic time, which is very nice, very fast.
From the weight queue, the tasks migrate to the ready queue, which as we know is populated
by one thread, current scheduler worker, and it is consumed by multiple threads, worker
threads.
So it means this is a multi-consumer single producer queue.
We also know that it will as well experience high contention because task scheduler should
be perfectly functional with like 10 worker threads.
Why not?
And with millions of tasks per second, we will have high contention.
We have to deal with it somehow.
Although unfortunately, I don't know a nice simple algorithm for doing unbounded and lock
free queue of this type.
For the reason why you can Google ABA problem, after the talk, it's also quite complicated.
We will not have time to dive into this, but just know that it is much more complicated
than multi-producer single consumer version.
Although I know a couple of other queues, unbounded log-based and bounded lock free.
I want my final queue to be exactly unbounded, meaning not limited in size.
So I don't want any limits inside the scheduler.
You can add them on top, but I don't want them to be inside the scheduler.
I don't want it to be limited by anything like queue size.
So let's see what we can do with those two queues.
The bounded lock free version, bounded lock free queue is simple.
It's just a cyclic rate, except that the read and write index will make atomic variables.
So in pushing, the only thing changes compared to normal cyclic buffer is that you increment
the write index atomic increment and that's it.
The popping is just a little bit more complicated.
We have to retry it sometimes because there will be multiple consumers.
They will compete for the same element sometimes.
So atomic compare exchange will eventually fail and we will have to retry, but it's still
quite simple.
And the unbounded lock queue is just trivial.
So it's a mutex and it's a list and we take mutex on every operation.
Then it becomes lock based, but it's unbounded.
So what we can do with the ready queue, what I had was the craziest idea.
The thing is, our enemy is not the mutex itself, it's the contention on the mutex.
So we could try to reduce the contention instead of deleting the mutex.
We could skip it, but somehow maybe not lock it so often.
Let's combine those two approaches together.
Let's take the bounded lock free queue and make unbounded lock based queue of those lock
free sub-queues.
So it will be like a stdq, but the blocks are lock free and the big queue of those blocks
is lock based.
And how producer works, it will push new items to the latest block in a lock free way.
When the block becomes full, it takes mutex, appends a new block, fills it in a lock free
way and so on.
And the consumers, they do their other thing vice versa, so they consume the first block
in a lock free way.
When it becomes empty, they take mutex, switch to the next block, consume it in a lock free
way and so on.
To see the benefit, imagine like sub-queue size, this block size, there's not four like
on the slide, but it's 10,000.
What happens then is we will take mutex lock not on IV operation, but once per 10,000 operations.
Mutex is still here, but it's locked so rarely that its cost is neglectable.
You will not see this mutex lock in any flame graphs anymore.
The only problem with this is that the consumers will need an explicit state, because if consumer
doesn't know which is the first block, in this queue of blocks, it will have to locate
it.
The queue of blocks, it's protected by a mutex, so if consumers don't have a state, if they
don't reference the first block having items, then on every pop, they would have to find
it, keeping the mutex, and that would mean mutex lock on every pop, if this is exactly
what we wanted to avoid.
Consumers need to register themselves, and then they can do the popping.
This is not a problem for a task scheduler itself, because it has fixed set of worker
threads which you specify at creation.
They can register themselves as consumers at start and leave just fine with it, so it's
just a problem for generic usage of this type of queue, but for task scheduler, it is just
fine.
Let's examine the visual example again.
Imagine like we have this queue, it's empty, just single block, one producer, two consumers.
Producer adds three items in a lock-free way.
Everything is lock-free so far, one consumer consumes one item, lock-free.
Now producer adds another item, lock-free.
It sees that the block became full, so we need to append a new block, we take mutex,
switch to the next, append a new block, switch to the next block, release the mutex, and
add three more items in a lock-free way.
Our consumers will work, they will finish consumption of the first block, consumer A will see that
the block is empty, so it takes mutex, switches to next block, releases the mutex, and continues
consumption in a lock-free way.
So we take mutex only when we switch from block to block.
And the other consumer, when we will try to consume something from it, it will see immediately
that its current block is empty, because those blocks, they are, as you remember, lock-free
bounded queues, there are read and write index, if we see that the read index of this block
equals its size, it means it's empty, so we don't even need to full scan it.
Anyway, consumer B will then lock mutex, switch to next block, release the mutex, and continue
the consumption.
And the old blocks, the completely consumed ones, can be discarded.
You can free them, you can reuse them, like have a pool of those blocks, and append them
to beginning again, if you want to, like, it's not cheap to allocate blocks having 10,000
items in them, so you might want to pull them, to have a pool of them.
About the benchmarks, we will see in the end, again, as I said, with everything combined.
And our progress so far is that we saw test-calular parts, those queues, and now we can have a
glimpse of the routines.
Unfortunately, we don't have enough time to dive deep into the implementation, but I can
show you some usage examples, show the features they have, and for the implementation, you
can look at the source code and ask me questions after the talk.
To see why do we need coroutines again, and what features we need from the coroutines,
let's inspect the simplified version of this save games example.
This time, we have just two steps.
Start download of a save game block, and then handle the result.
This is in just two steps.
What we know is that while the task is waiting for response from the network, it shouldn't
block other tasks, so it should be able to yield.
It should be able to step away.
But we also know that we can't, this task, it can't sleep infinitely.
There should be some sort of timeout.
Requests can't be executing infinitely, so we need some deadline after which the task
would be woken up and will cancel the request.
So if the response arrives in time, before the deadline, we have to wake up the task
before the deadline.
There should be some sort of explicit wake up for the task which is right now sleeping
in the wait queue, so it's not executing.
How exactly do we wake it up from there?
So we need an explicit wake up.
We need yield, deadlines, and wake ups, three main features of those coroutines.
Let's see an example.
It's almost exactly like it looks in real code.
Once there will be simplified version of C++, but it's very similar how it looks in reality.
We have a global task scheduler in the process and some HTTP client.
And imagine like a request from the client arrives, so we wrap it into a task and give
it a callback called download.
And we post it into the scheduler, so it will go into this front queue.
The scheduler will execute our callback in one of the worker threads.
This download callback, so what we do here is firstly set what will be the next step.
The next step will be handling the result.
Then we do the asynchronous HTTP request.
Assume that our HTTP client is able to do this.
So we start an asynchronous HTTP request and give it a future callback to execute when
the request is done, which we'll call wake up on our task.
While this will be explicit wake up when the request is done.
And then we start waiting.
So we post ourselves back into the scheduler with five seconds deadline.
Either the task will wake up in five seconds or it will be woken up explicitly when the
request is complete.
This goes into the scheduler, sleeps in the wait queue for some time and eventually our
callback handle result is executed.
We have to check what happened.
It could be two reasons.
It could be that the task is expired.
So five seconds passed and we were woken up by the deadline.
And we just literally check if it's expired.
If it is sold and we cancel the request and we start waiting for the cancellation to be
complete to properly free all the resources and to go back into the scheduler.
But now we wait for the cancellation.
Otherwise, if it's not expired, it means the request is finally complete with some result.
It could be success.
It could be an HTTP error code or it could be our own consolation done on a previous
wake up a few lines above.
Either way, we just handle it and delete the task.
This is literally, this is almost exactly how it looks in the source code.
There is no spurious wake ups at all, no sleeps and the request has clear state machine with
every state expressed at the callback.
And what is better, these entire routine stuff, all those wake ups, post deadlines, this is
all completely lock free.
There is no single mutics used to implement this all.
So this is to get you further interested into looking at the source code and asking questions
afterwards.
This is quite complicated stuff, as you can imagine, especially the implementation.
How do we verify such stuff?
Of course, there are unit tests, like literally hundreds and thousands of lines of unit tests.
But with multi-tried algorithms, the thing is, even if you have 100% code coverage, it
doesn't tell you anything.
It's better than, I think, not having 100% coverage, but it's still, there might be bugs
which can stay hidden for literally years.
And you will not find them except when this thing explodes in production.
There should be a way to at least verify the algorithm, maybe.
We can't verify the source code, but we can improve our confidence about the algorithm
itself.
And the solution is TLA+, TLA+, stands for temporal logic of actions, and it is a combination
of mathematics and temporal logic.
And it's also a language and runtime of this language.
This language allows you to verify literally any algorithms or systems, like you can verify
an algorithm of a queue, like I did, or how your microservices interact, or you can verify
how you go to a grocery store.
If you can algorithmize it, then you can verify it.
TLA+.
It's suitable for anything like this.
So in this TLA+, language, you write a specification and run the verification, and it will run
and it will split your system, your algorithm, into a set of all the possible states in which
this algorithm can be.
And verify your own invariance in every reachable state of your system.
So firstly, you define the algorithm, then you define what means validness for your algorithm,
the invariance, and TLA+, we'll verify all them.
Let's see an example, like I assume you have implemented a queue in any language, and we
want to verify the algorithm of this queue.
First you have to define what objects exist in your system, what agents you have there.
In my queue, I have just pipe for items, so some sort of storage, and a couple of counters
and limits.
Then you have to define actions.
In TLA+, every action is a set of mathematical conditions combined with some mathematical
operators, like you have operators and or operator, or list or set operator, or complex
operators like all items in the set comply with the condition operator, and many more
other operators which can use in your actions.
And the first action is always initialization, where you give initial values to your variables.
Here I say that storage pipe is an empty list, and my counters of sent and received items
are zero.
Then I start defining some actual actions doing stuff, like send or push or insert or
whatever.
And there are ways how to do it.
I'm not aware of any standard ways how to do it properly, so I invented my own.
Firstly, I split my actions into two groups.
And first group of conditions I define when the action is possible.
So here I say send is possible when queue is not full, and when I still have items to
send, so not everything pushed yet.
In the second group, I tell what changes should be done when the first group is true, so when
the condition is true.
Here I say if the first part is true, then I add a new item to the pipe storage, as items
I use numbers, and I increment the number of sent items, of pushed items.
The problem is, as you could see, probably there is no really distinction between those
two groups.
It's imaginary, and the only distinction is this small single code sign.
It means next value of the variable.
The problem is, since here it passes basically math, in math there is no assignment.
There is no action like assign new value to some variable.
There is only, the closest thing we have is equal operator in math, but there is no assignment.
But you can emulate it saying like next value of your variable equals old value and something
done with it.
So here I say literally last sent next equals last sent old plus one, which effectively results
into assignment and programming languages, but here you have to simulate it like this.
In theory plus there is no separation into groups, it's just several mathematical conditions,
but I do separate it for making the specification easier to read.
I do the same for the receive action.
It's possible when I have items to receive, and the changes are to receive.
And then you have to define what means validness for your system, so the invariance, which
will be validated in every Ritual state.
Here as they say that my queue is valid when all the items in the queue are ordered, like
I pushed them.
The queue never overflows, and then the items are received in the same order as sent.
And then with some technical steps, simple ones, I run the validation, and it will give
me a result like n states are found, like hundreds of thousands of millions of states
that are found, and they are valid, or it will say that I found an invalid state.
And here is how you get into the state from the initial one following this sequence of
actions.
And then you can turn those failure traces into unit tests in your actual code.
Now this actually works, and they call it a bug in the scheduler, thanks to this thing.
Here by links you can find the specifications for tax scheduler on the whole, and for the
multi-consumer queue, which was not trivial enough, so as I would try to validate it as
well.
Two specifications, they are quite big, but most of the lines are comments explaining
the algorithm.
So the specification, the code part of them is not too complicated.
You can read it like easily.
And also there are instructions how to install TLA+, in the source code repository, how to
run validation on those models, how to install TLA+, into the command line.
It's not trivial, surprisingly.
And there are also great course of lectures from the author of TLA+, Leslie Lampert.
Lectures are quite fun, if you are not even planning to use TLA+, they are still worth
watching, very entertaining.
All of this can be found on the source code repository, and now about the benchmarks.
How I did them, the benchmarks are comparative.
So I'm not just running the benchmarks against themselves in vacuum against some random stuff.
I compare the improved versions of those, my algorithms against trivial versions, naive
versions using mutexes, to see if stuff actually improved.
Like all the same benchmarks run on my algorithms and don't trivial implementations.
For example, the smart queues I benchmark against their mutex locked versions, or the
task scheduler I benchmark against thread pool, without coroutines, single queues, single
mutex and nothing else.
I run this on five different configurations of software and hardware with tens of scenarios
and all the reports, while the performance are available on GitHub, in human readable
markdown format.
And you can also run them on your system with just a single line of Python script.
It will generate the report for your case, and you can read it and see what's up.
And so there are quite a lot of results, I can show just a few of them on the slides.
I will use Debian Linux with eight cores running in Google Cloud, and I will show just some
average results, no shocking like 100 times faster, although there are extreme cases when
algorithms are almost the same, or when it's extremely faster, but I will show just some
average results which you can actually get in real production.
We start from the front queue again.
The benchmark uses five producer threads and one consumer thread, doing busy loop pushes
and pops all the time to get the worst case contention.
It's just for one and a half times faster, and this is all considering the two drawbacks
which you can remember, so we store items as stack in the front queue, we have to reverse
them, we can pop them one by one, and still it is one and a half times faster.
If we make it 10 producer threads, so we have more threads than CPU cores, worst case for
mutics contention, it becomes 2.6 times faster.
The ready queue, another benchmark, five consumer threads, one producer threads, one producer
thread, again busy loop pushes and pops, it becomes 2.6 times faster, already and you
can see that the mutics, the log contention is multiple orders slower than in a trivial
implementation.
This is thanks to us taking mutics log, not on every operation, but once per multiple
thousand operations, and this is the result.
Mutics is still here, but it almost doesn't affect the results at all.
When we make it 10, consumer threads, it becomes already four and a half times faster.
The naive queue degrades quite quick in this case.
And now everything combined, the task scheduler on the whole.
In this benchmark, tasks are empty, so they are just empty C++ functions.
Not doing anything, worst case for contention again.
And now we start from single worker thread, which will do both the scheduling and tasks,
it becomes right away 2.2 times faster.
Then a trivial thread pool without routine support, it becomes already 2.2 times faster.
And zero log contention, so log wasn't contended even once between the worker and producer.
When we make it five worker threads, it becomes three times faster, so it scales better than
naive implementation, but we make it 10 worker threads, it becomes seven and half times faster.
And these are not the best results, it can be even better.
I'm just not showing extreme cases here, but I saw like 15 times speed up as well.
It's just not something you will most likely get in production if you start using this,
but those benchmarks are also available.
And now about the real usage, not some random benchmarks in the vacuum, how it affects the
actual code.
Apply to this save games case from the beginning.
We reported one of the microservices from updater scheduler to task scheduler, and we immediately
without any further optimizations got 10 times speed up.
We went from 100s RPS to bigger than 10,000 RPS, and latency dropped five times like right
out of the box before we started doing some other optimizations.
And the algorithm is extendable.
Now, as you remember, there is this big rectangle where only one thread at a time can work.
It means this is thread safe space.
We can replace the binary heap with weighting task with something more complicated.
For instance, we can put LibF inside, or EPUL or IO completion ports from Windows inside,
and we get multi-threaded event loop, like multi-threaded LibF, we can store sockets
in tasks, and we get circuits with deadlines, with yields, and this is, in fact, what we
do have in Ubisoft, it's a fork of task scheduler where we just replaced weight queue with EPUL
on Linux and IO completion ports on Windows.
And we get more than millions, more than million messages per second with just several threads
on sockets.
With this thing, it's not too complicated to extend scheduler, it's just maybe next
time about this multi-threaded event loop.
What are the future plans for it?
Firstly, we could try to run it on ARM.
Maybe it already runs, but I just haven't tried.
Maybe it works, maybe not, I have no idea.
That's why it's open source.
You can try it, send a pull request if something's not working.
Also, it's currently implemented only in C++, and it's not even STL, although some people
might consider it good, like me.
I don't like STL, but it could use a port to STL as well, or to some other language.
And also, there could be optimizations done like the front queue.
Maybe there is a way not to store it as a stack, not to reverse the list of items before
returning it.
I just haven't found a simple way to do it, which would be worth trying, and this is the
end.
Thanks for your attention.
And here are the links to the source code, and to this talk.
It will be available, the animated versions with all the slides and my notes online by
this link and my other talks.
And also, there are bonus sections which some of you might ask as questions, and we will
quickly go for them, or you can click on them yourself after the talk if you're interested.
Okay, so time for questions, so show of hands, and we'll give you a mic.
So, for the front queue, you can use some of Dmitry Vyukov's NPSC queue, very fast, much
faster than the tribal stack, which is the thing you're using.
The other thing is for the wait queue, well, you answer this with IOCP, KQ, Epo, that would
be much more in line with something that uses timer or for networking.
And you said that we cannot have single produce, no, multi-multi-consumer single production.
Yes, you can, actually, you can use one of the chase left DQ, there's a paper for 2013
with formally verified primitives, including ARM, and those will work for you, use case.
I know that there exist implementations of such queues, I just couldn't find the simple
enough one.
The thing is, in Ubisoft, internally, above all, sometimes, in Harm to performance, can
value code simplicity, so it's not an option to use something extremely complicated, like
hazard pointers or stuff like this, or, for example, I saw implementations of such queues,
which are not wait-free, so they can be lock-free, let's say, but not wait-free, that also wasn't
an option, because that's basically a spin-lock.
There's 100 levels.