On 6/19/15 12:52 PM, Niall Douglas wrote:

On 19 Jun 2015 at 10:50, Robert Ramey wrote: Does this help Robert?

It's a good start. Actually, you could might want to include most of the text in this email in the document as an introduction. At a minimum, it would save you trouble of answering the same question again. And it wouldn't cost you anything since you just did most of the work. Robert Ramey

On 20 Jun 2015 at 12:44, Avi Kivity wrote:

On 06/19/2015 08:03 PM, Niall Douglas wrote:

...

Some may remember the thread starting from http://boost.2283326.n4.nabble.com/next-gen-future-promise-What-to-cal l-the-monadic-return-type-td4676039.html and that I would firstly prepare an optimally lightweight monad<T> for review here before going on to base a next-gen lightweight future-promise on that monad<T>.

BOOST_SPINLOCK_FUTURE_MSVC_HELP future_type get_future() { // If no value stored yet, I need locks on from now on if(!_need_locks && _storage.type==value_storage_type::storage_type::empty) { _need_locks=true; new (&_lock) spinlock<bool>(); }

Isn't that the common case? Usually if you already have a value, you return it with make_ready_future(). Otherwise, at the time of get_future(), the promise still doesn't have a value.

This came up in the discussion a month ago with some feeling that this was a pointless optimisation. I disagree for the same reasons I outlined back then, just because you should use make_ready_future() doesn't mean in generic programming you always can. A very good example of that is in the WG21 coroutines proposal where if the operations are correctly ordered and if you never enter a suspend point, the compiler can set the promise before getting the future and therefore its optimiser can completely elide the promise-future construct entirely. I've already raised that idea with Gor as a non-compiler-magic way of completely eliding future-promise overheads in the non-suspending coroutine outcome. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/

On 20 Jun 2015 at 13:48, Bjorn Reese wrote:

On 06/19/2015 07:03 PM, Niall Douglas wrote:

...

https://github.com/ned14/boost.spinlock/blob/master/include/boost/spinlock/m...

This starts with the words "The world's most simple C++ monad" followed by 1200 lines of code... makes one scared of monads.

Firstly, thanks for the review. As I know you know, STL quality C++ is amazingly verbose. And I haven't implemented monad<void> yet, which will require doubling the existing lines of code to stamp out an almost identical monad<void> specialisation. I am currently strongly considering an automatically generated source solution to that. (One could use enable_if everywhere to get a void and non-void single implementation, but I want minimal build time costs).

Here are some random throughts I had while reading the code.

Minor comment, consider letting monad_error inherit from system_error instead of logic_error.

http://en.cppreference.com/w/cpp/thread/future_error I agree with you, but that's the C++ standard. Of course, monad need not duplicate future here, but I think if I claim "future semantics" then it ought to.

When throwing monad_error, you cast to int (presumably to satisfy some compiler.) Can't you simply use make_error_code() instead? That will also ensure that you set the correct category.

VS2015 RC was the problem. The current cast to int workaround is the first thing I'll try fixing when VS2015 RTM comes out. The category is correct though. The throw_error() function is a template parameter, and that is a struct detail::throw_monad_error which in turn throws monad_error(monad_errc). monad_error takes a std::error_code, and the C++ 11 STL uses the std::is_error_code_enum<> trait to auto convert the monad_errc enum into the correct error code and monad_category category. I lifted that pattern of how to throw a future_error straight from Boost and two STLs I examined. It's identical to std::future<T> and boost::future<T>.

Why does one of the value_storage constructors call abort() rather than throwing an exception?

value_storage lives in the detail namespace, and its ability to carry a future<T>* in its variant space is an internal implementation detail nor exposed to public users. The only users of that facility are lightweight future-promise. They (should) never ever copy construct a value_storage, so if a copy construction ever occurs when the contents are a future<T>*, that's memory corruption and/or bad programming by me. It was purely defensive programming on my part.

Why does monad::get_error() throw on no_state, rather than simply returning an error_code that says so?

A very good question. I purely did it that way round for these two reasons: 1. Any attempt to get any state from an empty monad always throws no_state consistenty no matter what you call. 2. future-promise always throws a no_state if either has no state, so boost::future<T>::get_exception_ptr() will throw a no_state instead of returning an exception_ptr of no_state. monad<T> matches that behaviour. Actually, I just lied. The monad get_or(), get_error_or(), get_exception_or() functions never throw no_state, they return the OR value. I am unsure if that is a wise design choice. There is also another potential design problem in that get_error() returns a null error_code if the monad is not errored even if it is excepted. I did it that way to match get_exception() as boost::future<T>::get_exception_ptr() returns a null exception_ptr if there is no exception. However there is a discrepency, because if the monad is errored not excepted and you call get_exception(), you'll get an exception_ptr to the system_error for the error_code, and it's not the same the other way round. There is a logic to this though. monad<T> is effectively a tribool state of empty/value/excepted where an errored state always converts when needed into an exception state, but never the other way round. The errored state is therefore a non-type-erased excepted state, while the excepted state is a type-erased state. I am just unsure if that is a wise design.

Is there any difference between monad::get() and monad::value()? If they are synonyms, then you may consider removing monad::get() to keep the class interface smaller, and instead overload std/boost::get().

They are identical. I hate multiple names for the same function. However, Expected's value fetcher function is called value(), and I was hoping for an easy swap for code using Expected. That said, if there is any opposition here I will gladly remove value() and leave it with just get(). Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/

On 29 Jun 2015 at 20:08, Gavin Lambert wrote:

...

There is also another potential design problem in that get_error() returns a null error_code if the monad is not errored even if it is excepted. I did it that way to match get_exception() as boost::future<T>::get_exception_ptr() returns a null exception_ptr if there is no exception. However there is a discrepency, because if the monad is errored not excepted and you call get_exception(), you'll get an exception_ptr to the system_error for the error_code, and it's not the same the other way round.

Perhaps there should be an error code that represents "has an exception"? (Either from a custom category or finding an appropriate system error to hijack for this purpose.)

I already have a monad_category and a monad_errc which can do this.

I don't like the idea of someone writing code that only tests the error_code (because they weren't expecting exceptions), but which claims there is no error because there really was an exception instead. Exceptions are errors are exceptions, and neither is an ordinary result value.

It's definitely a very valid concern. I'll sleep on it and make a decision. Thanks for commenting on this problem, it's a particular worry of mine. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/

On 29 Jun 2015 at 17:54, Vicente J. Botet Escriba wrote:

Niall, I don't see why do you need to define a concrete monad class that is used to define other monadic types. The implementation of each specific monadic type has its own trade-offs.

We can provide monadic operations for optional/expected/future/....

Why do you need to have a concrete monad class? What is the added value?

Let me flip the question to you. Why does it matter how the monadic types are implemented? All the user needs to care about is that monad<T>, result<T>, option<T>, future<T>, future_result<T> and future_option<T> behave according to strict and sensible rules which make sense to program against. You could of course implement them separately. I chose not to, but that's an internal implementation detail. Each correctly SFINAE's out those functionalities they don't provide and/or provides a static_assert when you try doing something you can't. If you're really asking why are they all so similar, I'd also flip the question: "why is experimental::optional<T> not the same pattern as future<T>?" Both transport a T, so why aren't they the same? There are many advantages and very few costs if they were. I especially like that I can use the same mental model for both, both have identical APIs where that makes sense, and both work the same way in my head. Both are also each absolutely minimum impact on build and runtime costs, I have a suite of unit tests verifying that per commit. BTW there is absolutely nothing ruling out a later monad. I deliberately left that open for the future, all the existing design an API assumes an implict monad>. Any code written against the current design would work with a recompile with a later monad. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/

On 1 Jul 2015 at 19:22, Vicente J. Botet Escriba wrote:

...

...

Niall, I don't see why do you need to define a concrete monad class that is used to define other monadic types. The implementation of each specific monadic type has its own trade-offs.

Could we then avoid to mention the monad class on these threads as it is an implementation detail.

basic_monad is the base class of everything. You probably wouldn't use it directly, so it's an implementation detail. monad<T> is a user facing specialisation for convenient use.

So what are the public classes you would present for review?

Documentation for lightweight future promise: https://ci.nedprod.com/view/Boost%20Thread-Expected-Permit/job/Boost.S pinlock%20Test%20Linux%20GCC%204.8/doxygen/group__future__promise.html Documentation for monads, which are base classes of the futures: https://ci.nedprod.com/view/Boost%20Thread-Expected-Permit/job/Boost.S pinlock%20Test%20Linux%20GCC%204.8/doxygen/group__monad.html Note the futures are not finished yet. I don't expect them to be considered finished until around 11th July. I have yet to do: - [ ] Implement N4399 continuations extended with monadic bind etc. - [ ] wait() should sleep the thread as necessary. - [ ] Implement wait_for()/wait_until(). - [ ] when_any/when_all composure. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/

Le 21/06/15 09:07, Vicente J. Botet Escriba a écrit :

Le 19/06/15 19:03, Niall Douglas a écrit :

...

Some may remember the thread starting from http://boost.2283326.n4.nabble.com/next-gen-future-promise-What-to-cal l-the-monadic-return-type-td4676039.html and that I would firstly prepare an optimally lightweight monad<T> for review here before going on to base a next-gen lightweight future-promise on that monad<T>.

Nial, I don't understand why you call this class monad. I see it much more as a generalized optional_expected that allows the user to say which exception is thorw when there is an error type and not an exception type.

IMO, the last parameter throw_error is really not needed.

You can always wrap an error code with a class that states how to throw an exception. That means that we need an additional Error concept that defines the throw_error function, e.g.

We could have a class that wraps an error with an exception

template struct ThrowError { Error value; };

template void throw_error(ThrowError const& e) { throw Exception(e.value); }

Now the generalized optional/expected class will use the throw error whenever it needs to throw an exception and has an error type stored.

BTW, why have you chosen a Callable for throw_error instead of directly the Exception?

BTH, expected could already store an error or an exception_ptr. All you need is to have a class

template struct ErrorOrException;

Resuming you monad class is in some way an alias of

expected, Exception>>

possibly optimized with a specific specialization.

BTW, why your class accepts only on Exception type and not a variadic set of Exceptions types?

I have some trouble with the is_ready function. You say "True if monad is not empty.". Do you mean that oi will not be ready

optional<int> oi;

You need to add the preconditions of each function. No precondition mean the function is not partial.

I don't see comparison operators, neither hash customization, was this intentional?

I suspect that the exception thown by value() when an instance is empty is not future_error,and that there is a type on the documentation. Or was this intentional?

In the function value()&& you say "If contains a value_type, returns a rvalue reference to it, else throws an exception of future_error(no_state), system_error or the exception_type."

Why system_error? Do you mean that when the exception_type given as parameter is exception_ptr, the exception throw is exception_ptr and not the stored exception? In the Expected proposal and in std::future, the exception throw will be the stored exception.

The function has_exception is not coherent with the others state observer functions empty/has/value/has_error.

What is the exact signature (or valid signatures) of the functions passed to map/bind/then? BTW, are these functions proposed?

Last can the map function be applied to an empty instance? What would be the result?

I would like to suggest a different approach. Given a class optionals, which is a variant accepting to be empty we can see optionals as an Error Monad, when all the Ei are instances of the Error concept. A class is a model of the Error concept if it defines the rethrow_exception function. When the optionals is empty the exception thrown is bad_optionals_access. exception_ptr is a type erased Error that rethrows the stored exception. std::error_code and std::error_condition can be seen as instances of the type class Error if we define the rethrow_exception on them throwing an system_error exception. optionals can not define all the function that your class monad defines as they are too specific. Instead of defining member functions we can define non-member functions. has_value/has_error/value/set_value/set_error/get_error/emplace/map/bind/then optionals should be default constructible from Ti and convertible to Ti using maybe a specific cast function. optionals must be implicitly convertible from the result of throw_error(e). We could also define a specific class as you propose with specific semantic for the first argument that would defines member functions. I'm not against this approach, nevertheless the main issue I have is how to name this class :( result doesn't conveys the fact that it can be empty. monad is not good as Monad is a type class not a concrete type. optional_result is too long optional_value_or_errors is too long HTH, Vicente

On 21 Jun 2015 at 9:07, Vicente J. Botet Escriba wrote:

Le 19/06/15 19:03, Niall Douglas a écrit :

...

Some may remember the thread starting from http://boost.2283326.n4.nabble.com/next-gen-future-promise-What-to-cal l-the-monadic-return-type-td4676039.html and that I would firstly prepare an optimally lightweight monad<T> for review here before going on to base a next-gen lightweight future-promise on that monad<T>.

Firstly Vicente your three emails contained a ton of gold quality observations. From those I have generated this task list: Boost review feedback work items: - [x] Documentation incorrectly says exceptions thrown are future_error when they are in fact monad_error. - [ ] Add template aliases for different configurations of monad<T> (one of maybe, result, holder, value, retval, potential, likely). Add two additional aliases, one for a monad without exception_ptr, and another for a monad with neither error_code nor exception_ptr (option<T>?). - [ ] Make how error_type is converted into exception_type configurable. - [ ] Make the tribool nature of monad<T> much more formally obvious. - [ ] In addition to value_or(), error_or() etc add value_and(), error_and() etc. - [ ] As .then() is defined in a future as executing the callable when the value is set, and monad<T>.then() executes immediately and does not execute when the value is next changed, does this make monad<T>.then() deceptively named? (I think yes). Perhaps and() is a better name for then()? What about simply operator() i.e. make the monad callable? What about operator[]? - [ ] Add match() function which visits a callable on the contents. - [ ] Look into member operator overloads for bind() and map() e.g. monad<int> &m; auto r = m >> [](int a){return a;}; Can't use operator

...

=() from Haskell as has same precedence to operator=().

Thank you *hugely* for your feedback Vicente. It was extremely valuable to me. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/

2015-06-26 3:11 GMT+02:00 Niall Douglas :

On 22 Jun 2015 at 1:43, Niall Douglas wrote:

...

Firstly Vicente your three emails contained a ton of gold quality observations. From those I have generated this task list: [snip] Thank you *hugely* for your feedback Vicente. It was extremely valuable to me.

For those interested, the final version of lightweight monad hit github earlier today. Highlights:

monad is now space optimal, consuming as little as two bytes depending on configuration. monad<void> is now working, plus these new specialisations were added:

* result<T>: empty/T/error_code (no exception_ptr).

To what run-time condition does an empty state correspond here? I used to thing that you either have a result (T) or a reason why you do not have one (error_code), but what does it mean that you have neither? Regards, &rzej

On 26 Jun 2015 at 10:42, Andrzej Krzemienski wrote:

...

...

monad is now space optimal, consuming as little as two bytes depending on configuration. monad<void> is now working, plus these new specialisations were added:

* result<T>: empty/T/error_code (no exception_ptr). To what run-time condition does an empty state correspond here? I used to thing that you either have a result (T) or a reason why you do not have one (error_code), but what does it mean that you have neither? Semantically speaking, after feedback from this list, and having attended Charley's C++ Now Presentation on ternary logic programming "Your CPU is Binary", I realised that it's worthwhile to formally specify future/monad/result as ternary logic primitives with ternary logic operators. option<T> remains boolean. This gives the following logic table:

Empty => False (future/monad/result/option) Errored/Excepted => Indeterminate (future/monad/result) Value => True (future/monad/result/option) The meaning of empty in optional/option and future is not the same. For

Le 26/06/15 13:00, Niall Douglas a écrit : the fist is a valid state, for the second is an invalid state. In addition asynchronous types have an additional state not-ready, e.g. future can be invalid, not-ready, exceptional or valued. Vicente

On 29 Jun 2015 at 10:05, Andrzej Krzemienski wrote:

...

...

Empty => False (future/monad/result/option) Errored/Excepted => Indeterminate (future/monad/result) Value => True (future/monad/result/option)

The meaning of empty in optional/option and future is not the same. For the fist is a valid state, for the second is an invalid state.

If "empty" means something different in the case of three-type "result", perhaps it deserves a different name?

In my synchronous monad, empty is always an invalid state, just as with future. States T/errored/excepted are always valid states.

...

In addition asynchronous types have an additional state not-ready, e.g. future can be invalid, not-ready, exceptional or valued.

So it looks like you have two sets of error codes: 1. The one represented by E in result 2. A set of error conditions inherent to asynchronous state processing: "invalid", "not ready" (maybe also "already retrieved").

You have nailed another design tradeoff I made on the head. Right now if lightweight future experiences an error condition, it makes the future valid in order to set the state to that error condition which is of type future_errc. monad behaves identically, as it maps future as closely as possible, except it uses type monad_errc (which is a subset of future_errc). This, as you correctly observe means that one cannot disambiguate between a user who tries to transport a monad_errc with monad<T> and a monad<T> which set itself to an errored state due to some problem. As the docs say, "don't use monad<T> to transport a monad_errc nor a future_errc. Misoperation is likely". Note also that lightweight monad<T> and future<T> both explicitly static_assert prevent you from using a T which is an error_type or an exception_type. In other words, monadstd::error_code or monadstd::exception_ptr will fail to compile. In the docs I suggest that if you really need to transport those, wrap them in a wrapper type. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/

On 29 Jun 2015 at 13:29, Andrzej Krzemienski wrote:

...

...

If "empty" means something different in the case of three-type "result", perhaps it deserves a different name?

In my synchronous monad, empty is always an invalid state, just as with future.

In that case, perhaps name "empty" is not the best choice? It has positive connotations like "empty optional" or "empty vector" which are as valid states as only a state can be. I believe "invalid state" would reflect your intention more clearly.

It's a tricky one this. On the one hand, empty means that get()/get_error()/get_exception() will throw no_state, so in that sense it is invalid. On the other hand, the monadic operators bind/map/next etc see empty as a valid state i.e. you can write the bind expression: monad<T> >> [](monad<T>::empty_type) { /* executed if empty */ ); ... and that's just fine too. Similarly, the AND OR operators treat empty as equal to errored/excepted, so: monad<int> & 5 | 2 ... means that if the monad has a value, emit a monad with 5, else emit a monad with 2. Finally, the specialisation option<T> (which is simply a monad missing the ability to be errored or excepted) has only the two state options of empty or T. Otherwise it's a monad in every other way, and can interact with monads like result or monad (i.e. option<T> will implicitly convert to monad<T>, and monad<T> can be explicitly converted to option<T>). For option<T>, an empty state might be invalid, but it is also valid in the sense of state being not a T. If that makes sense. In other words, my "dirty monad" doesn't just act like a future, it also acts like an optional. Identical semantics. Your big win of choosing option<T> over monad<T> is far lighter weight overheads on runtime because exception_ptr is *expensive* when you are working in hundreds of cycles. I can see already that all this ambiguity and lack of clear design goals will smack of a poor design not fully baked and thought through. I can assure boost-dev that I have been pondering this design for over a year and half a dozen designs were considered and thrown away before I settled on this design. So far, I am pleased with it as it ticks all the "red boxes" i.e. the absolute hard red line requirements I needed (specifically a minimal runtime and build time overhead). The rest of the design has been allowed to float to wherever it falls naturally, and you can see what we've now got - a real "mongrel" of a design where it is up to the programmer to not shoot themselves in the foot. This is not to say I don't have qualms and concerns and worries with this design. All I am claiming is that it solves my pressing problems in what I think is a neat way, and I am therefore pleased with it so far. I may later discover I have made a serious design boo boo. Thanks everyone for your feedback. Designing this stuff is hard, and your comments have been very useful and helpful. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/

2015-06-25 22:11 GMT-03:00 Niall Douglas :

plus these new specialisations were added:

* result<T>: empty/T/error_code (no exception_ptr). * option<T>: empty/T (no error code nor exceptions).

I like these specialisations. Makes the code clearer. What do you think about renaming monad to async_monad? -- Vinícius dos Santos Oliveira https://about.me/vinipsmaker

2015-06-28 17:52 GMT-03:00 Niall Douglas :

monad<T>, result<T> and option<T> are all *synchronous* value transports. Just like Rust's Result and Option.

So, why can result<t> be empty? Sorry about the silly question, but you could use the answer to improve the documentation for dumb users like me. -- Vinícius dos Santos Oliveira https://about.me/vinipsmaker

On 6/28/2015 5:02 PM, Vinícius dos Santos Oliveira wrote:

2015-06-28 17:52 GMT-03:00 Vinícius dos Santos Oliveira < vini.ipsmaker@gmail.com>:

...

2015-06-28 17:52 GMT-03:00 Niall Douglas :

...

monad<T>, result<T> and option<T> are all *synchronous* value transports. Just like Rust's Result and Option.

So, why can result<t> be empty?

I mean: result is like "give me T or it's an error". There is no empty state. Empty would already be an error state. I'd only understand empty if it's an async operation that didn't finish already.

What's the state of a default constructed result? Is it an error state? Is it empty? Or is it not default constructible?

On 28 Jun 2015 at 17:52, Vinícius dos Santos Oliveira wrote:

...

monad<T>, result<T> and option<T> are all *synchronous* value transports. Just like Rust's Result and Option.

So, why can result<t> be empty?

The idea was that the synchronous transport editions map semantically onto the asynchronous transport editions. So: Empty <= Unsignalled/Default constructed. Value <= Value. Errored/Excepted <= Errored/Excepted. If you consider a default constructed future, you will see you have to have a default constructed monad be empty. What else could it be? There is also the truth that allowing an empty state makes everything vastly more efficient to implement. For example, I can hard assume that monad<T> will always have a default constructor, and that makes implementing monad considerably easier. If an exception throws during a move or copy constructor, I can throw the exception out with the monad left empty. In a situation with (de)serialisation, the ability to guarantee default construction no matter what T is is also very valuable. All this turns into a minimum number of assembler instructions output by the compiler, and is why I chose this design.

I mean: result is like "give me T or it's an error". There is no empty state. Empty would already be an error state. I'd only understand empty if it's an async operation that didn't finish already.

In case others on boost-dev don't realise, Vinicius here is referring to Rust, not C++. Myself and Vinicius currently work for the same client writing code in Rust, at least until he replaces me in a few week's time! :) Rust's Result, and any traditional monad, has no empty state. I would call those "pure monads". My monad is not a pure monad, it is a "dirty" monad with an impure design which I hope/believe is better suited to the typical C++ programmer. For example, monadic parsing is not well suited to my impure design, it does work if you throw an exception to carry the failure to parse state so it "works", but nobody should be doing that in any real world code. I may be wrong in those design tradeoffs and assumptions - just because I've been working on the right design for over a year (I have a presentation I did on these design deliberations February 2014 with many of the same unsolved problems) doesn't mean I am 100% confident in it being the correct balance between all the exigencies. However, the AFIO review is in two weeks, and boost-dev wanted a final AFIO design, so here it is coming best as I can make it. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/

On 26 Jun 2015 at 2:11, Niall Douglas wrote:

This weekend I'll get started on lightweight future-promise which derives from monad and indeed is also a basic_monad but with different implementation policy class. These future-promise ought to be 98% compatible with the WG21 Concurrency TS spec and will be able to participate in hetereogeneous when_any/when_all i.e. you can mash them in with std::future.

It'll likely take me a week to come up with some benchmarks comparing std::future and my future in a 4-SHA256 engine so you can see the benefits of the new design. After that I'll replace AFIO's std::future with these lightweight futures in its public API, and we should be ready to rock for the 17th July when AFIO's review begins.

I have the first set of benchmarks for lightweight non-allocating futures ready. They aren't final, but they are representative of what to expect as compared to the STL future-promise. Note these futures are configured with a *superset* of the facilities of STL future-promise, so you have all your monadic programming goodness in there as a lightweight future inherits from basic_monad plus you can return error_code as well as exception_ptr: clang 3.7 libstdc++ 4.9: about 3x faster single threaded (~260 CPU cycles versus ~780) and 3.2x faster multithreaded. GCC 5.1 libstdc++ 5.1: about 3x faster single threaded (~260 CPU cycles versus ~780) and 3.7x faster multithreaded. VS2015: about 6.8x faster single threaded (~243 CPU cycles versus ~1668). For shared_future things aren't as good due to the shared_ptr. However: clang 3.7 libstdc++ 4.9: about 2x faster single threaded (~380 CPU cycles versus ~780). GCC 5.1 libstdc++ 5.1: about 2x faster single threaded (~380 CPU cycles versus ~780). VS2015: about 2 faster single threaded (~750 CPU cycles versus ~1433). These are worst case improvements. My next step is future_option<T>, and that should be dramatically faster than future<T>. I definitely know it will be at least around the 100 CPU cycle mark, the question is how much lower I can push it. I'll know in a few days. Gory detail can be found at https://github.com/ned14/boost.spinlock/blob/master/Readme.md. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/

On 30 Jun 2015 at 22:37, Michael Marcin wrote:

Forgive me if this is dumb I haven't looked at the implementation of a future/promise solution before and I was curious.

It seems the basic strategy is to have a member variant called value_storage in both the promise and the future.

Let me see if I can enumerate the flows:

- If you set_value on a promise twice you get an already_set error.

- If you set_value on a promise that noone has gotten the future of you set the storage of the promise to the value

- If you set_value on a promise that someone has gotten the future of you set the storage of the future to the value and detach the promise from the future

- If no one ever gets the future and the value is set then the value gets destroyed in the promise's storage when the promise is destroyed

- If someone gets the future before the value is set then a future is constructed and the promise's storage stores a pointer to the future

- If someone gets the future then gets it again while the first future still exists it throws future_already_retrieved

Sounds about right so far.

- If someone gets the future then destroys the future then gets the future again it is now safe to call get_future again on the promise so long as the value was never set (This seems rather complicated, is it necessary?)

That's a bug! So thank you. What should happen is that the future destructor should set the promise to detached if no value was set. I'll fix that shortly.

- If someone sets the promise value then gets the future this is the fast path no lock is ever taken, the promise is left detached with empty storage and the value has been moved to the future's storage

Until late last night, this was the case. I found I could shave off 15% CPU cycles by removing this optimisation as it makes the output code less branchy and I'm overloading the branch predictor, so it makes a big difference. It's still in there for the unit testing to prevent me writing code which causes failure to constant expression reduce, but #ifdef'd out by default.

Is this about right?

I'm not sure that _need_locks being changed inside of get_future is always going to be visible other threads. The documentation says it will be thread safe after you have called get_future but I don't see anything that necessarily creates a happens-before relationship between other threads reading _needs_locks. I am not an expert though.

It's a good question, and thank you for taking the time to review the code and the design. What you are missing is that we assume that whoever is calling get_future() must issue some form of memory synchronisation to transmit the newly constructed future to another thread. That synchronises the changed _needs_locks to other threads. I suppose it is possible that someone could send the future to one thread, and have a different thread do a state read and in theory the state reading thread doesn't see any new state. However, that is part of the design in general anyway, and it will be documented that any examination of promise-future state between synchronisation points (I have still to document which APIs are those) may be stale. I've taken care to make sure that unlocked state reads cannot be racy. Modulo bugs of course. I have yet to write this up into the docs, but a very strong advice will be given to not concurrently consume lightweight future promise from more than one thread. Multiple threads able to set the promise are fine, but there should be only one thread able to inspect and get from the future at any one time. Lightweight future-promise should still be safe to get() from multiple threads concurrently as wait() synchronises, but any inspection of state from multiple threads concurrently will be racy. Any design where multiple threads can consume a future concurrently is likely a very bad design. Use a shared_future instead where concurrent get() is intended. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/

On 2 Jul 2015 at 11:39, Gavin Lambert wrote:

On 1/07/2015 22:29, Niall Douglas wrote:

...

What you are missing is that we assume that whoever is calling get_future() must issue some form of memory synchronisation to transmit the newly constructed future to another thread. That synchronises the changed _needs_locks to other threads. I suppose it is possible that someone could send the future to one thread, and have a different thread do a state read and in theory the state reading thread doesn't see any new state.

The most common case is to transport the promise to another thread (sometimes via packaged_task) and to return the future on the calling thread.

I suppose designs that pass the future to another thread instead are possible but they seem a lot weirder and more convoluted.

Now locks are always on, and as both promise's and future's move constructors are acquire release points, transporting either works. I've documented the exact deviations from the STL in the docs, copying and pasting from those: Known deviations from the ISO C++ standard specification: * No memory allocation is done, so if your code overrides the STL allocator for promise-future it will be ignored. * T must implement either or both the copy or move constructor, else it will static_assert. * T cannot be error_type nor exception_type, else it will static_assert. set_value_at_thread_exit() and set_exception_at_thread_exit() are not implemented, nor probably ever will be. * promise's and future's move constructor and move assignment are guaranteed noexcept in the standard. This promise's and future's move constructor and assignment is noexcept only if type T's move constructor is noexcept. * Only the APIs marked "SYNC POINT" in both promise and future synchronise memory. Calling APIs not marked "SYNC POINT" can return stale information, so don't write code which has a problem with that (specifically, do NOT have multiple threads examining a future for state concurrently unless they are exclusively using SYNC POINT APIs to synchronise memory between them). When might this be a problem in real world code? For example, valid() which is not a SYNC POINT API may return true when it is in fact false. If your code uses a synchronisation mechanism which is not a SYNC POINT API - most usually, this is "synchronised by time/sleep" - and then executes code which depends on valid() being correct as it would always be with STL future promise as valid() there synchronises memory, your code will be racy. The simplest solution is to call any SYNC POINT API before examining valid(), or issue a memory fence (std::atomic_thread_fence), or best of all refactor your code to not use synchronised by time/sleep in the first place. The thread sanitiser tsan reports any use of time to synchronise as a failure which is the correct thing to do - just don't do it in your code. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/

On 2 Jul 2015 at 14:26, Gottlob Frege wrote:

But without looking at all the code, I'm not sure who/what/when _needs_locks ever changes. Assuming both the promise and the future side READ it, and one of them can WRITE it, then the writer needs a release on setting, and the other side needs an acquire on every read. If only one side can set, the setter side never needs anything beyond the release, and only needs release after the other side has gone off onto its own thread.

That facility is disabled by default now. It always locks in the APIs documented "SYNC POINT".

As for multiple threads reading the future: No. IIUC, std::future isn't thread-safe on its own. It can only be used by one thread (without extra external synchronization). It only guarantees no data races relative to the other thread holding the promise, not to other threads trying to read the same future.

This surprises me. As you saying that if two threads try to get() from a future concurrently, that both may succeed due to racing? I had thought that exactly one succeeds and exactly one will receive a no_state exception throw? Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/