Giovanni Piero Deretta writes:

On Wed, Mar 18, 2015 at 4:08 AM, Jeremy Maitin-Shepard wrote:

[snip]

I complely removed the current then/next implementation in favor of a generic then that works with any waitable. This makes it explicit that you can compose future types (and in fact any waitable) as long as they provide a get_event.

I removed 'next' completely to simplify the implementation. The optimization opportunity to save an allocation on the except case is probably not worth the complexity.

I think it is good to have, even if it is implemented using `then', since it has the advantage that the function passed does not have to deal in futures. It seems like implementing it more efficiently as you did could make sense in a more polished version, though, since futures are a basic primitive and it is best to minimize the overhead as much as possible.

...

3. Since invoking future::then and future::next release ownership, it is worth considering making them only work on rvalues. Whether the extra compile-time error checking this buys is worth the added verbosity of having to add std::move in some cases is not clear, though.

the new free function then takes its waitable by value (so you have to move it). I'll leave the current signature of then as is for now for compatibility with the standard proposal and boost::future.

The required RMW are definitely non neglegible. I tried to keep them at a minimum but they still have a cost. My original future implementation actually had thread safety switch but it would be terribly error prone.

Certainly it would be more error-prone than the thread-safe future, since there would be no compile-time way to verify that the user isn't incorrectly accessing it from multiple threads without external locking, but I'm not sure that is a reason not to provide it. It seems it would be possible to upgrade a thread-unsafe future to a thread-safe future, provided that there is no race between the upgrade and marking the future ready. I think the implementation would be pretty simple, in fact.

Instead I'm studying a way for future to start as simply a deferred synchronous computation, but that can become asynchronous on request of another thread (via work stealing or work requesting for example).

This would be pretty useful functionality to add support for; I guess it would complicate your approach a bit, though. 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. [snip]

...

Benchmarks (and unit tests) would also be particularly helpful.

I have yet to find a good, fair, small and realistic benchmark for futures. Ideas are welcome.

I was thinking microbenchmarks, that would at least show the cost of individual operations and allow comparing different design choices/implementations. For instance, cost of getting value from ready future, cost of waiting on ready future, cost of calling then on ready or not-yet-ready future, etc.

On 18 Mar 2015 at 22:07, Giovanni Piero Deretta wrote:

Regarding the 'atomic option', I was actually thinking of removing it, instead switching to specifying the memory order in get()/set_{value,exception}.

That's a good idea. Default heuristics for avoiding atomic are necessarily going to have to be too conservative.

I complely removed the current then/next implementation in favor of a generic then that works with any waitable. This makes it explicit that you can compose future types (and in fact any waitable) as long as they provide a get_event.

I removed 'next' completely to simplify the implementation. The optimization opportunity to save an allocation on the except case is probably not worth the complexity.

I think the ship has sailed on this at WG21. The present Concurrency TS delights no one, but it is the product of many years of negotiation and compromise. What you see now is highly likely to persist unless you can demonstrate a showstopping technical reason why not (e.g. like std::async).

...

4. In some contexts a thread-unsafe future/event that saves the cost of atomic operations would be useful (unless it turns out that this cost is negligible on modern CPUs, which I don't think is the case). However, it would be important for the thread-safe and thread-unsafe futures/events to interoperate in a reasonable way. (I'm not sure exactly what reasonable semantics would be.) Obviously there would have to be some caveats, but we would want to avoid another future-island situation.

The required RMW are definitely non neglegible. I tried to keep them at a minimum but they still have a cost. My original future implementation actually had thread safety switch but it would be terribly error prone.

The cost is to the lack of optimisation options, not at the hardware level. Atomic operations, even on weakly ordered systems, are not high when no other CPU core has visibility of that cache line.

Instead I'm studying a way for future to start as simply a deferred synchronous computation, but that can become asynchronous on request of another thread (via work stealing or work requesting for example).

I think that has the maximum chance of being useful to functional programming frameworks too.

...

Benchmarks (and unit tests) would also be particularly helpful.

I have yet to find a good, fair, small and realistic benchmark for futures. Ideas are welcome.

https://github.com/ned14/c11-permit-object/blob/master/pthread_permit_ speedtest.cpp might have some ideas for you. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/

On 19 Mar 2015 11:09, "Niall Douglas" wrote:

On 17 Mar 2015 at 21:42, Giovanni Piero Deretta wrote:.

...

* The wait strategy is not part of the future implementation (although a default is provided). future::get, future::wait, wait_all and wait_any are parametrized by the wait strategy.

* The design aims to streamline and make as fast as possible future and promise at the cost of a slower shared_future (although there is room for improvement).

Your future still allocates memory, and is therefore costing about 1000 CPU cycles.

1000 clock cycles seems excessive with a good malloc implementation. Anyways, the plan is to add support to a custom allocator. I do not think you can realistically have a non allocating future *in the general case* ( you might optimise some cases of course).

That is not "as fast as possible". The use of std::atomic also prevents the compiler optimiser from eliding the future implementation entirely, because atomic always forces code to be generated. As much as futures today are big heavy things, tomorrow's C++17 futures especially resumable function integrated ones must be completely elidable, then the compiler can completely eliminate and/or collapse a resumable function call or sequence of such calls where appropriate. If you have an atomic in there, it has no choice but to do the atomic calls needlessly.

I understand what you are aiming at, but I think that the elidability is orthogonal. Right now I'm focusing on making the actual synchronisation fast and composable in the scenario where the program has committed to make a computation async.

I think memory allocation is unavoidable for shared_future, or at least any realistically close to the STL implementation of one. But a future I think can be both STL compliant and never allocate memory and be optimisable out of existence.

...

* The wait strategy only deals with 'event' objects, which act as a bridge between the future and the promise.

The event object is really my the core of my contribution; it can be thought of as the essence of future<void>::then; alternatively it can be seen as a pure user space synchronization primitive.

Exactly as my C11 permit object is. Except mine allows C code and C++ code to interoperate and compose waits together.

Not at all. I admit not having studied permit in detail (the doc size is pretty daunting) but as far as I can tell the waiting thread will block in the kernel. It provides a variety of ways on how to block, the user can't add more. With event the decision of how to block ( or even whether to block at all) is done by the consumer and most importantly it can be delayed till the last moment. You can think of event as the bridge between the signal side and wait side of permit, or alternatively as a future<void> which only supports then (no get or wait). Regarding interfacing with a C event source , it can be done trivially right now now as long as it provides a callback (function pointer + context pointer) API, which is very common already. No need to wait for existing libraries to embrace a new synchronisation object (cue xkcd vignette about standards :) ) Allowing C to wait for events would require replacing the waiter vtable with the c equivalent, but is not something I care much right now.

...

Other features of this implementation:

* Other than in the blocking strategy itself, the future and promise implementation have no sources of blocking (no mutexes, not even spin locks).

* The shared state is not reference counted.

To demonstrate the generality of the waiting concept, I have implemented a few waiter objects.

* cv_waiter: this is simply a waiter on top of an std::mutex + cond

var.

...

* futex_waiter (linux): an atomic counter + a futex, possibly more efficient than the cv_waiter

* sem_waiter (posix): a waiter implemented on top of a posix semaphore. More portable than the futex waiter and possibly more efficient than the cv_waiter

* fd_waiter(linux, possibly posix): a waiter implemented on top of linux eventfd (for portability it can also be implemented on top of a pipe); you can use select with futures!

* task_waiter: a completely userspace based coroutine waiter which switches to another coroutine on wait and resumes the original coroutine on signal.

* scheduler_waiter: another coroutine based waiter, but on top of an userspace task scheduler. On wait switch to the next ready task, on signal enqueue the waiting task to the back of the ready queue.

I know that there is a plan to reimplement a new version of boost::threads, hopefully this implementation can contribute a few ideas.

My current best understanding of Vicente's plans is that each thread has a thread local condvar. The sole cause of a thread sleeping, apart from i/o, is on that thread local condvar. One therefore has a runtime which keeps a registry of all thread local condvars, and can therefore deduce the correct thread local condvars to wake when implementing a unified wait system also compatible with Fibers/resumable functions.

That doesn't work if a program wants to block for example in select or spin on a memory location, or on an hardware register, or wait for a signal, or interoperate with a different userspace thread library, or some other event queue (asio, qt or whatever) etc. and still also wait for a future. Well, you can use future::then, but it has overhead. -- gpd

On 19 Mar 2015 19:51, "Niall Douglas" wrote:

On 19 Mar 2015 at 18:05, Giovanni Piero Deretta wrote:

...

...

Your future still allocates memory, and is therefore costing about 1000 CPU cycles.

1000 clock cycles seems excessive with a good malloc implementation.

Going to main memory due to a cache line miss costs 250 clock cycles, so no it isn't. Obviously slower processors spin less cycles for a cache line miss.

Why would a memory allocation necessarily imply a cache miss. Eh you are even assuming an L3 miss, that must be a poor allocator!

...

Anyways, the plan is to add support to a custom allocator. I do not

think

...

you can realistically have a non allocating future *in the general case* ( you might optimise some cases of course).

We disagree. They are not just feasible, but straightforward, though if you try doing a composed wait on them then yes they will need to be converted to shared state. Tony van Eerd did a presentation a few C++ Now's ago on non-allocating futures. I did not steal his idea subconsciously one little bit! :)

I am aware of that solution My issue with that design is that it require an expensive rmw for every move. Do a few moves and it will quickly dwarf the cost of an allocation, especially considering that an OoO will happily overlap computation with a cache miss, while the required membar will stall the pipeline in current CPUs (I'm thinking of x86 of course). That might change in the near future though.

...

I understand what you are aiming at, but I think that the elidability is orthogonal. Right now I'm focusing on making the actual synchronisation fast and composable in the scenario where the program has committed to make a computation async.

This is fine until your compiler supports resumable functions.

This is funny :). A couple of months ago I was arguing with Gor Nishanov (author of MS resumable functions paper), that heap allocating the resumable function by default is unacceptable. And here I am arguing the other side :). OK my compromise is to not allocate while the async operation is merely deferred but can still be executed synchronously. Lazily convert to heap allocation only when the operation needs to be executed truly asynchronously, basically until you actually create the promise (at that point the cost of the async setup will provably dwarf the allocation; and even in this case the allocation can be skipped if we know we will sync before a move, then it us safe to allocate the shared state on the stack). This should allow to compiler to remove the abstraction completely if it can prove it safe. Still working on it, should have something in a few days. I guess I'm converging to your design.

...

...

Exactly as my C11 permit object is. Except mine allows C code and C++ code to interoperate and compose waits together.

Not at all. I admit not having studied permit in detail (the doc size is pretty daunting) but as far as I can tell the waiting thread will block

in

...

the kernel.

It can spin or sleep or toggle a file descriptor or HANDLE.

...

It provides a variety of ways on how to block, the user can't add more.

It provides a hook API with filter C functions which can, to a limited extent, provide some custom functionality. Indeed the file descriptor/HANDLE toggling is implemented that way. There is only so much genericity which can be done with C.

I believe my design is much simpler and flexible; then again is trying to solve a different and narrower problem than full scale synchronization of arbitrary threads. -- gpd

On 20 Mar 2015 13:07, "Niall Douglas" wrote:

On 20 Mar 2015 at 9:19, Giovanni Piero Deretta wrote:

...

...

...

...

Your future still allocates memory, and is therefore costing about 1000 CPU cycles.

1000 clock cycles seems excessive with a good malloc implementation.

Going to main memory due to a cache line miss costs 250 clock cycles, so no it isn't. Obviously slower processors spin less cycles for a cache line miss.

Why would a memory allocation necessarily imply a cache miss. Eh you are even assuming an L3 miss, that must be a poor allocator!

[Snip]

Newer architectures can be quite good at exchanging the S and O states if exactly the right two caches have that line (e.g. two CPUs on the same die). As soon as you go past two caches sharing a line though, all bets are off and everything gets synced through main memory.

All the above is why memory allocation is bad here because any shared state can usually ends up being worst case performance for MOESI.

What's special about memory allocation here? Intuitively sharing futures on the stack might actually be worse especially if you have multiple futures being serviced by different threads.

Modern memory allocators are very good at handling the same thread freeing a block it itself allocated when only that thread saw that allocation. They are poor at handling when a different thread frees, or even has visibility of, a block allocated by another thread.

...

I am aware of that solution My issue with that design is that it require an expensive rmw for every move. Do a few moves and it will quickly dwarf

Because of the way ownership is relinquished, in my implementation the consumer usually both allocates and frees the state. Unless you use shared futures, but then that's the last of your problems. [Snip] the

...

cost of an allocation, especially considering that an OoO will happily overlap computation with a cache miss, while the required membar will stall the pipeline in current CPUs (I'm thinking of x86 of course). That might change in the near future though.

On Intel RMW is the same speed as non-atomic ops unless the cache line is Owned or Shared.

Yes if the thread does not own the cache line the communication cost dwarfs everything else, but in the normal case of a exclusive cache line, mfence, xchg, cmpxchg and friends cost 30-50 Cycles and stall the CPU. Significantly more than the cost of non serialising instructions. Not something I want to do in a move constructor. [Snip]

...

A couple of months ago I was arguing with Gor Nishanov (author of MS resumable functions paper), that heap allocating the resumable function by default is unacceptable. And here I am arguing the other side :).

It is unacceptable. Chris's big point in his Concurrency alternative paper before WG21 is that future-promise is useless for 100k-1M socket scalability because to reach that you must have much lower latency than future-promise is capable of. ASIO's async_result system can achieve 100k-1M scalability. Future promise (as currently implemented) cannot.

Thankfully WG21 appear to have accepted this about resumable functions in so far as I am aware.

I'm a big fan of Chris' proposal as well. I haven't seen any new papers on resumable functions, I would love to know were the committee is heading. -- gpd

On Sat, Mar 21, 2015 at 2:33 PM, Niall Douglas wrote:

On 20 Mar 2015 at 19:32, Giovanni Piero Deretta wrote:

...

What's special about memory allocation here? Intuitively sharing futures on the stack might actually be worse especially if you have multiple futures being serviced by different threads.

I think memory allocation is entirely wise for shared_future. I think auto allocation is wise for future, as only exactly one of those can exist at any time per promise.

I wasn't talking about shared future. Think about something like this, assuming that the promise has a pointer to the future: future<X> a = async(...); future<X> b = async(...); ... do something which touch the stack... a and b are served by two different threads. if sizeof(future) is less than a cacheline, every time their corresponding threads move or signal the promise, they will interfere with each other and with this thread doing something. The cacheline starts bouncing around like crazy. And remember that with non allocating futures, promise and futures are touched by the other end at every move, not just on signal.

...

...

On Intel RMW is the same speed as non-atomic ops unless the cache line is Owned or Shared.

Yes if the thread does not own the cache line the communication cost dwarfs everything else, but in the normal case of a exclusive cache line, mfence, xchg, cmpxchg and friends cost 30-50 Cycles and stall the CPU. Significantly more than the cost of non serialising instructions. Not something I want to do in a move constructor.

You're right and I'm wrong on this - I stated the claim above on empirical testing where I found no difference in the use of the LOCK prefix. It would appear I had an inefficiency in my testing code: Agner says that for Haswell:

XADD: 5 uops, 7 latency LOCK XADD: 9 uops, 19 latency

CMPXCHG 6 uops, 8 latency LOCK CMPXCHG 10 uops, 19 latency

(Source: http://www.agner.org/optimize/instruction_tables.pdf)

So approximately one halves the throughput and triples the latency with the LOCK prefix irrespective of the state of the cache line.

That's already pretty good actually. On Sandy and Ivy was above 20 clocks. Also the comparison shouldn't be with their non-locked counterparts (which aren't really ever used and complete), but with plain operations. Finally there is the hidden cost of preventing any OoO execution which won't appear in a synthetic benchmark.

Additionally as I reported on this list maybe a year ago, first gen Intel TSX provides no benefits and indeed a hefty penalty over simple atomic RMW.

hopefully will get better in the future. I haven't had the chance to try it yet, but TSX might help with implementing wait_all and wait_any whose setup and teardown require a large amount of atomic ops..

ARM and other CPUs provide load linked store conditional, so RMW with those is indeed close to penalty free if the cache line is exclusive to the CPU doing those ops. It's just Intel is still incapable of low latency lock gets, though it's enormously better than the Pentium 4.

The reason of the high cost is that RMW have sequential consistency semantics. On the other hand on intel plain load and stores have desirable load_acquire and store_release semantics and you do not need extra membars. -- gpd

On Fri, Mar 20, 2015 at 5:19 AM, Giovanni Piero Deretta wrote:

On 19 Mar 2015 19:51, "Niall Douglas" wrote:

...

On 19 Mar 2015 at 18:05, Giovanni Piero Deretta wrote:

...

...

Your future still allocates memory, and is therefore costing about 1000 CPU cycles.

1000 clock cycles seems excessive with a good malloc implementation.

Going to main memory due to a cache line miss costs 250 clock cycles, so no it isn't. Obviously slower processors spin less cycles for a cache line miss.

Why would a memory allocation necessarily imply a cache miss. Eh you are even assuming an L3 miss, that must be a poor allocator!

...

...

Anyways, the plan is to add support to a custom allocator. I do not

think

...

...

you can realistically have a non allocating future *in the general case* ( you might optimise some cases of course).

We disagree. They are not just feasible, but straightforward, though if you try doing a composed wait on them then yes they will need to be converted to shared state. Tony van Eerd did a presentation a few C++ Now's ago on non-allocating futures. I did not steal his idea subconsciously one little bit! :)

I am aware of that solution My issue with that design is that it require an expensive rmw for every move. Do a few moves and it will quickly dwarf the cost of an allocation, especially considering that an OoO will happily overlap computation with a cache miss, while the required membar will stall the pipeline in current CPUs (I'm thinking of x86 of course). That might change in the near future though.

Just to be clear, my non-allocating promise/future was meant to be more of a proof-of-concept, not necessarily optimal efficiency. I would need to recheck, but I think most of it requires only acquire or release, not full sequential consistency, if that helps. I rarely write anything that requires full sequential consistency. Anyhow, carry on. I like that there are people looking into this stuff. Looking forward to the outcomes. Tony

On Fri, Mar 27, 2015 at 5:35 PM, Giovanni Piero Deretta wrote:

On Fri, Mar 27, 2015 at 8:24 PM, Gottlob Frege wrote:

...

...

Just to be clear, my non-allocating promise/future was meant to be more of a proof-of-concept, not necessarily optimal efficiency. I would need to recheck, but I think most of it requires only acquire or release, not full sequential consistency, if that helps. I rarely write anything that requires full sequential consistency.

Hum, I do not think you can implement it with just plain load and stores, I think you need at least one RMW there. Probably acq_rel is enough for that, but that's no less expensive than seq_cst on x86.

You are probably right, but for each move, all you are doing is publishing where you moved to, so you need a release, and then an acquire when you want to read that, not acq_rel together on one operation. But I haven't thought about it since I gave the presentation!, so I don't know. Maybe I'll have time to think about it at C++Now, which is coming up soon. (Feels soon to me at least - more things to prepare...) Tony