[On a phone right now, just wanted ro comment on something]
On 19 Mar 2015 00:23, "Jeremy Maitin-Shepard"
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
the
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. -- gpd