Re: [boost] Non-allocating future promise... Re: ASIO into the standard (was: Re: C++ committee meeting report)

Subject: Re: [boost] Non-allocating future promise... Re: ASIO into the standard (was: Re: C++ committee meeting report)
From: Gottlob Frege (gottlobfrege_at_[hidden])
Date: 2014-07-08 23:12:07

On Tue, Jul 8, 2014 at 7:57 AM, Niall Douglas <s_sourceforge_at_[hidden]> wrote:
> On 7 Jul 2014 at 1:50, Gottlob Frege wrote:
>
>> https://github.com/boostcon/cppnow_presentations_2013/blob/master/mon/future_promise.pdf?raw=true
>>
>> 2013.  The talk is called "Non-Allocating std::future/promise".  I
>> think most of it is about a... non-allocating future-promise.
>> Hopefully. That was at least the idea.
>
> Dear dear dear ... given that I was working at BlackBerry with you at
> the time, and went with you to C++ Now, I really don't know how I
> missed this.
>
> I'm going to assume that I didn't miss this and instead choose to
> forget and then pretend that your idea was my idea. So, my apologies,
> and I'll credit you in the docs when the time comes.
>

I _thought_ you were in the audience, but that could have been one of
my other talks.
At work, I hardly talked about it, so if you weren't at the talk, you
could have easily missed it.
Chandler said that Google also ended up with similar code, so we are
all thinking along the same lines.
Chandler had some good ideas for handling the exceptions as well (ie
if thrown when setting the value).
It is hard to be 100% standards compliant (since the standard
basically assumes every implementation uses an allocated storage
location, and those assumptions leak into the interface).

>> In brief:
>> - each has a pointer to the other
>> - the result is stored in the future
>> - if one moves or is destroyed, it is... tricky. But basically a CAS
>> and a small spin lock in a rare case when you need to wait for the
>> other side to update the pointer.
>
> The problem with this is it isn't space optimal. Space optimal means
> storing the spinlock in the low bits of the memory pointer instead of
> wasting another four or eight bytes on it, which is what I've done.
> Performance is indeed impacted by a bit, but not that much - after
> all it's all the same cache line anyway.
>

Yeah, it looks like I have about 5 states, but I think that is mostly
for exposition.  Probably only need 2 bits.

> I also didn't see lock backoff in your example code i.e. where both
> the promise and future are concurrently moved from different threads.
> Did I miss something?
>

Yeah, there is definitely potential for spinning there.  Each side
could mark their own state as MOVING then check the other side, sees
it is MOVING, so goes back to the 0 state and retries.  So without
backoff this could go on forever.  In this case an easy "let the
future side win" rule could be done (since the two sides are _not_
equal, in particular you expect the promise to be slower anyhow).

In my slides I have a pause() function.  Not sure if I mentioned that
it could/should do backoff.  I can never remember what I said during a
talk, and the slides often don't make sense on their own. :-(

>> Yes, replacing the spin and pointer updating with TM would be nice.
>
> And here is where things become very interesting.
>
<...interesting TM stuff...>

Yes, keep us informed.  I've been assuming TM won't work well for
"big" transactions, but I have no idea yet what is big and what is
small.
Of course, we could also just ask the TM guys, like Michael Wong et
al.  But nothing beats experiencing it for yourself.

Tony