Write a parallel deque for work stealing

[brson]

The work stealing algorithm uses a deque. Their algorithm has some properties that might make further optimizations possible later (one end is used only by a single thread). We only need something simple to start with, a locked vector that just pushes and pops and shifts and unshifts. Using a circular buffer would be better, lock-free better still (maybe).

Also probably relevant is the paper on data locality in work stealing though I haven't read it yet.

There are some useful data structures for atomically reference counted types and mutexes in core::private.

[brson]

Related to #3095

[brson]

Since I'm not sure that lock-free deques even exist I've scaled back the scope of this slightly.

[nikomatsakis]

The deques used in work-stealing typically have a special property that one thread (the owner) only PUSHES and POP and other threads (the thieves) only ever DEQUEUE. Nobody ever queues. This lets you get better efficiency for multi-threading, but means that they are not multi-purpose.

[brson]

Somebody pointed out that the 'Chase / Lev' deque is a lock-free parallel deque for work stealing. Sounds good to me.

[ILyoan]

Is there any progress on this?

[brson]

@ILyoan No. There is a type in place at rt::work_queue but it is not implemented.

[brson]

A related paper http://www.cs.bgu.ac.il/~hendlerd/papers/dynamic-size-deque.pdf, "A Dynamic-Sized Nonblocking Work Stealing Deque", by Hendler, Lev, Moir, Shavit

[emberian]

@Aatch was working on this at some point but stopped.

[toddaaro]

http://www.di.ens.fr/~zappa/readings/ppopp13.pdf

This recent paper is a wonderfully detailed description of the atomic memory issues involved with the data structure. Includes pseudocode for a C11 memory model version with every atomic operation specified.

[cartazio]

a good example implementation of such a scheduler can be found in this haskell lib: https://github.com/ekmett/structures/blob/master/src/Control/Concurrent/Deque.hs

[brson]

I am wondering whether we really want to use a work-stealing deque as or per-thread work queue. Something that allows for random access would prevent the starvation problems we have to hack around and would be more fair. Is there such a data structure that is lock free?