Investigate improving scheduler work-stealing efficiency

[alexcrichton]

Right now the libgreen scheduler implements a work stealing algorithm in tandem with a global sleeper list in order to fan out work among all schedulers when there is work to do.

Sadly, this scheme has pathological performance in simple situations like lots of threads contending on a mutex. The reason for this is that every time a thread gets off a mutex a remote scheduler is woken up to run the thread. This remote scheduler is woken up with a syscall. The remote scheduler will run the task, but immediately go back to sleep as the task goes back to sleep on the mutex.

This process of waking up a remote scheduler is very expensive and shows painfully in benchmarks. This problem essentially boils down to a problem where all task enqueues require a syscall. The reason for this is that on some workloads there's almost always a scheduler that is asleep as the system isn't fully loaded. If the system is loaded with work, none of this is a problem because no remote scheduler needs to be woken up.

Right now, there are two ideas for mitigating this cost of a syscall.

1. Exponential backoff when sleeping. Right now whenever a scheduler goes to sleep, it falls back into epoll and gets woken up via write. Additionally, it puts a handle on a global sleeper list for other schedulers to grab and then wake up. Instead, a scheduler could have some sort of exponential backoff of sleeping. Only after the backoff was completed would a handle be placed on the sleeper list. The goal for this would be to avoid write syscalls because the handles wouldn't actually be on the list, but other schedulers would still successfully steal work. This exponential backoff would need to be tuneable, and it probably shouldn't happen if there are active I/O handles.
2. Schedulers should only wake up two other schedulers. Right now there is a global sleeper list where any scheduler can wake up any other scheduler. In addition to being a point of contention, this means that if any scheduler is sleeping that a task enqueue will be a syscall. On systems of lots of cores, I would imagine it's fairly likely that small programs don't fill up all the cores. In order to mitigate this problem, we would arrange the pool of schedulers as a ring of schedulers. Each scheduler would be responsible for waking up its left and right neighbors, but that's it. With this scheme, if one scheduler had lots of serial work, it would occasionally wake up its neighbors, but that's it. Additionally, its neighbors would likely be in the exponential backoff stage before they went to sleep, so there would be no syscalls.

I'm guessing that combining these two strategies will allow us to still distribute work to all cores quickly if there is a truly parallel workload, and also work well on many-task workloads that are mostly sequential (due to a mutex or some such). This is just a guess though, and definitely needs investigation.

[alexcrichton]

Nominating.

I recently investigated into the rust-http benchmarks which show the RPS for libnative is over 2x larger than libgreen. I found that with RUST_THREADS=1 libgreen was 7% faster than libnative (and libnative had the benefit of being concurrent).

In my opinion, this is a serious obstacle to widespread acceptance of libgreen. Until this issue is fixed, I feel that the common workloads will be much slower than they need to be. Another example of a workload showing this pathological performance is a highly contended mutex.

[pnkfelix]

Assigning P-high since it seems promising, but this should not block 1.0.

[derekchiang]

This sounds like a very interesting project to work on and I'd like to look into this. @alexcrichton, are there any benchmarks I can use to test green's performance under the kind of workload you described?

[alexcrichton]

One example of the pathological code is the example in this gist: https://gist.github.com/8813400. On my OSX laptop, this code runs in about 7s on libgreen and in 3s on libnative. I would expect libgreen to be much faster in this case.

Another example would be the benchmarks inside of https://github.com/chris-morgan/rust-http/. I found that libgreen was by default 2x slower than libnative, but with RUST_THREADS=1 libgreen was about 10% faster than libnative (and libnative was parallelized while libgreen wasnt). I never got the benchmarks to run reliably on any platform other than linux.

[alexcrichton]

Ah I should also mention that the gist I gave takes a command-line parameter of the number of threads to contend each other, and the numbers I gave were for 4 threads of contention. The numbers are pretty much the same for 1 thread, and it gets worse from there when more threads are added.

[derekchiang]

@alexcrichton do you have any suggestions regarding implementing the ring, ideally with a lock-free structure?

One approach would be to use the same SleepList structure (which uses an mpmc queue), except that instead of simply popping a scheduler and waking it up, we keep popping and re-pushing schedulers until we find a scheduler that is our neighbour, in which case we wake it up. A neighbour can just be defined as a scheduler whose id is our id +1 or -1.

The downside would be that waking up a scheduler now takes O(n). But since the total number of schedulers is probably small, this might be fine.

[derekchiang]

Well, I just realize schedulers don't have ids. So if the approach above were to be used, we would need schedulers to have ids as well. The implementation would be similar to pool_id.

[derekchiang]

Well this is very exciting indeed. I did this and, using the benchmark @alexcrichton provided, the time needed to run with 8 threads dropped from ~18 seconds to ~4 seconds on my machine :)

The code can be found here. I don't want to submit a PR just yet since there are obviously still many design issues to be sorted out.

[alexcrichton]

Those are some very promising results!

My idea for this would be to have some sort of a handle to your left and right neighbors. This handle might be a SchedHandle, but it may also be some other handle. One of the great parts about only caring about the left and right neighbors is that you avoid any global state, so that's something that I think that we'd definitely want to move towards (not having a global sleeper list).

I don't think that the handles will be so much of a lock-free structure as a wakeup mechanism for schedulers. They'll probably have a uv async handle along with a flag as to whether the scheduler is sleeping or not. Note that the crucial aspect is that the flag is false while the scheduler is performing exponential backoff before sleeping, and it's true only when the scheduler has completely blocked.

Those are just some scattered thoughts, though.

[derekchiang]

@alexcrichton Could you explain what you mean by exponential backoff of sleeping? Is it like, rather than directly going to sleep, a scheduler would first wait for like 1ms and try to run its current task again. If still blocked, it waits for like 2ms and tries again. Then 4ms, 8ms, until it hits a threshold, in which case it actually goes to sleep.

Also, I imagine the sleep flag will need to be an atomic boolean?

[alexcrichton]

Right now, when a scheduler goes to sleep (executes this code), it will go back to libuv, and the OS thread will be blocked in epoll. Waking up a scheduler from epoll is pretty expensive, so we were thinking that a scheduler should expoentially backoff in sleeping before hitting epoll.

The idea is that while doing this exponential backoff, the scheduler won't receive messages to wake up (it doesn't look like it's asleep). In doing so, when we have a high volume of serial work across many tasks, one scheduler will be doing all the work and fanning out the unblocked tasks to its neighbors. These neighbors would finish the work quickly, and then block the task again. These neighbor schedulers would never hit epoll and the main scheduler would never wake them up. The "I'm asleep" flag would indeed probably be an atomic, and it would be false during this backoff.

A complication is that I don't think that exponential backoff should happen while there are active I/O handles. Otherwise, this exponential backoff will starve any tasks which have an I/O completion callback to run.

The exact tuning of parameters is something I'm not quite sure about. The idea is something along the lines of wait for N units of time, then wait for 2N units of time, all the way up to 2^M * N units of time at which point you hit epoll. The values of N and M will likely need lots of tuning to get right.

[derekchiang]

@alexcrichton I might be missing something obvious, but how do you tell a scheduler to "wait" for N units of time, without making it sleep?

Also, any thoughts on how we might detect whether there are active I/O handles?

[alexcrichton]

Ah sorry, I should have clarified. When in backoff, the scheduler just plain old sleeps. It doesn't hit epoll, it just calls the equivalent of libc::usleep (or something like that).

I wouldn't worry too much about the I/O handle use-case right now. I had a patch for it awhile back but it got pretty hairy. I'd worry first about getting the work stealing under control, and then we can worry about the I/O.

[derekchiang]

@alexcrichton could you tell me exactly how to make it sleep like you described? I can't find any sleep code in Rust that does not rely on the runtime itself.

[alexcrichton]

I would start out with libc::usleep