Subject: Re: [boost] [thread] Alternate future implementation and future islands.
From: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2015-03-19 04:59:05
[On a phone right now, just wanted ro comment on something]
On 19 Mar 2015 00:23, "Jeremy Maitin-Shepard" <jeremy_at_[hidden]> wrote:
> One other issue that came to mind: your current approach of using a
> singly-linked list of waiters seems to pose a problem for a timed wait or
> other "recovable" waits, since you can only remove a waiter if it is at
> front of the list. With only unique-ownership futures this might be okay,
> if you prohibit waiting on a future from multiple threads at once, since
> then the waiter for be guaranteed to remain at the front of the list.
> However, with shared-ownership futures the problem would be unavoidable.
> Therefore it might make sense to switch to a doubly-linked list; I guess
> this will make the lock-free algorithms trickier.
There is actually no lock free wait list. The event object only allows one
waiter. Shared future is implemented with a boring lock protected deque of
N hidden future/promise pairs used only for signaling.
The singly linked list you are seeing is just the ready queue for the
coroutine scheduler which is unrelated to the future implementation.
I have considered adding multiple waiter support to event, but if I do it
it will be via a spinlock protected queue. A lock free list which supports
removal in the middle (which BTW is also required for wait any, not just
timed waits) requires too much infrastructure (hazard ptrs or some other
deferred reclamation scheme) and wouldn't be competitive with a plain
spinlock. I have in mind an hybrid design that allows wait free signal and
waits and pushes the complexity to dismiss_wait.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk