Consider providing an option to steal more than one item

[carllerche]

In cases like Tokio (and Go), it is ideal to be able to steal more than one item at a time. I believe that ideally, the Tokio thread pool would like to steal half of a deque at a time. This is also what Go's scheduler does.

For reference, here's the batched steal function in Go's scheduler:
https://github.com/golang/go/blob/9d4215311ba573a5b676de85b053eec03e577478/src/runtime/proc.go#L4769

I'm unsure whether Go uses the Chase-Lev deque (there's no mention of "Chase-Lev"), but the code looks very similar.

There was previously some discussion on steal-half in crossbeam-rs/crossbeam#148

@jeehoonkang Are we still facing any unsolved challenges with regards to correctness of steal-half? What's the current of your half-stealing branch?

[jeehoonkang]

Go's scheduler is using bounded circular buffer for fairness. Actually, crossbeam-circbuf is partly inspired from Go's schedulers. Tokio also needs circular buffers, not double-ended queues, for fairness. It's much easier to add half-steal functionality in circular buffers, so I'd like to propose to merge the RFC and adopt the implementation, and add half-steal functionality in the newly introduced crate.

In the mean time, my colleague @hans89 is reviewing and significantly improving the proof for (original) Chase-Lev deque. I hope we can merge the RFC soon. The proof for half-stealing deque is not that different from that for original deque. It can be useful for Rayon, which doesn't care the fairness of jobs.

Would it be difficult to add a steal_half method for @carllerche to experiment with in Tokio?

I'd be willing to help if you're busy. Except I don't know how to do steal-half correctly yet... (we've hit a roadblack last time in crossbeam-rs/crossbeam#148) :)

[carllerche]

If circbuf is more suited, I can also try looking at that (I haven't dug in).

[jeehoonkang]

I just added Receiver::try_recv_half() in concurrent-circbuf: jeehoonkang/concurrent-circbuf@1b1d5dd

@carllerche I think concurrent_circbuf::unbounded::spmc can replace crossbeam_deque for Tokio. Please have a look!

[carllerche]

@jeehoonkang Ooops, I just saw this comment. I can try soon. Also, feel free to ping me on IRC / Gitter if I don't respond in a timely fashion.

[carllerche]

@jeehoonkang I'm working on a large change to the thread pool (see here: tokio-rs/tokio#317). Once I am done with that, I will try out the circlebuf. I'm really interested in using it because it is more suited and because there are no fences and it will make tsan happier :)