Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #367 > unrolled thread

Re: C++0x, 29.3 p13 "[...] atomic stores visible [...] within a reasonable amount of time."

Back to article view | Back to comp.programming.threads

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: C++0x, 29.3 p13 "[...] atomic stores visible [...] within a   reasonable amount of time." Alexander Terekhov <terekhov@web.de> - 2011-06-27 20:55 +0200
    Re: C++0x, 29.3 p13 "[...] atomic stores visible [...] within a reasonable amount of time." Joshua Maurice <joshuamaurice@gmail.com> - 2011-07-01 04:06 -0700
      Re: C++0x, 29.3 p13 "[...] atomic stores visible [...] within a  reasonable amount of time." Alexander Terekhov <terekhov@web.de> - 2011-07-01 17:35 +0200
        Re: C++0x, 29.3 p13 "[...] atomic stores visible [...] within a reasonable amount of time." Joshua Maurice <joshuamaurice@gmail.com> - 2011-07-01 15:23 -0700
          Re: C++0x, 29.3 p13 "[...] atomic stores visible [...] within a  reasonable amount of time." Alexander Terekhov <terekhov@web.de> - 2011-07-02 10:18 +0200
            Re: C++0x, 29.3 p13 "[...] atomic stores visible [...] within a reasonable amount of time." Joshua Maurice <joshuamaurice@gmail.com> - 2011-07-05 15:10 -0700
      Re: C++0x, 29.3 p13 "[...] atomic stores visible [...] within a reasonable amount of time." Edek <edek.pienkowski@gmail.com> - 2011-07-02 13:59 +0200
        Re: C++0x, 29.3 p13 "[...] atomic stores visible [...] within a  reasonableamount of time." Alexander Terekhov <terekhov@web.de> - 2011-07-05 10:12 +0200
          Re: C++0x, 29.3 p13 "[...] atomic stores visible [...] within a  reasonableamount of time." Edek <edek.pienkowski@gmail.com> - 2011-07-05 11:36 +0200

#367 — Re: C++0x, 29.3 p13 "[...] atomic stores visible [...] within a reasonable amount of time."

<moving away from comp.std.c++>

Joshua Maurice wrote:
> 
> I have a question regarding C++0x, 29.3 p13. In draft n3242, the exact
> text is:
> 
> "Implementations should make atomic stores visible to atomic loads
> within a reasonable amount of time."
> 
> I am wondering if there is a well known intent as to the meaning of
> "reasonable". Allow me to explain. I apologize up front if I'm
> mistaken in any of my understandings, and please point out any such
> misunderstandings. I also understand this is a QoI issue, but I think
> that this particular answer greatly affects how one should write
> portable code, which is why it's not quite something we ought to be
> allowed to handwave as "implementation defined".
> 
> Consider:
>    std::atomic<int> x;
>    //...
>    while(x.load(std::memory_order_relaxed)) {}
> That is, suppose we have an atomic variable x, and perhaps
> specifically the type which is guaranteed to be lock-free. (I can't
> quite find the text for that offhand.) It's my understanding that the
> intent is for that load to be implemented by whatever passes for the
> normal, common assembly load on that platform.
> 
> So, that simple assembly load may be satisfied by a core local cache.
> If it is satisfied by a core-local cache, then the changes are high in
> that busy waiting loop that future loads will be satisfied by a core
> local cache, and thus it may not see a new write, ever, barring other
> things. Other things, such as the common multi-tasking, preemptive
> threading, OS. For that, eventually that busy loop will exhaust the
> thread's timeslice, and it will be taken off the core. At some later
> point, it will be put back on the core, which as I understand commonly
> invalidates any core local caches, which means that the next load of
> that busy waiting loop will go to main memory (or non-core local
> cache, etc.), and it will see a new value.
> 
> So, would such an implementation be "conforming in spirit"? I
> understand this is a QoI issue, but it is relevant. Specifically, is
> there some understood intent and meaning that "reasonable" means
> "maybe the next time the thread is scheduled out and scheduled back
> in", or is "reasonable" meant to be something sooner than that?
> 
> This may be relevant to real world code for cooperative thread
> cancelling. I assume the default way of handling cooperative thread
> cancelling is to have a lock-free std::atomic bool variable which is
> global to the "job" which can be cancelled. Call that the "stop flag".
> Threads doing the jobs will periodically check the stop flag, and if
> read true, then they will bail out and end the job. The question is
> whether the stop flag should use memory_order_relaxed loads and stores
> or seq_cst loads and stores. If relaxed loads and stores can be
> delayed until the thread is scheduled out and back in, then that may
> be too high of a delay for responsive cooperative job cancellation.
> It's my understanding that with seq_cst loads and stores to the stop
> flag, then that cannot be delayed by anything more than a "few"
> assembly instructions, due to the total order S.

C++11 aside (the latest draft is not public and I have no idea what it
says), on assembly level, in order to read the last value you need
read-modify-write operation such as fetch_add(0) and relaxed RMW reads
last value just fine. 

> 
> Of course, in practice, on "normal desktop processors", for non-
> trivial code aka code which isn't just a busy waiting loop like above,
> I expect that the caches will eventually get flushed, probably usually
> much before a thread exhausts its timeslice, so the above reasoning is
> rare worst case scenario. Perhaps it's still practical to use relaxed
> loads and stores for the stop flag, despite the low probability
> possibility that the stop flag may be delayed a very long time?
> 
> Then again, what about more exotic architectures, like NUMA
> processors? How would that interact with this? I am woefully ignorant
> on such details, and that is why I ask. Does C++0x, 29.3 p13 require
> some intelligence from the compiler so that the compiler must
> implement relaxed loads and stores as something more than the simple
> assembly loads and stores? Perhaps most are simple assembly loads and
> stores, but the compiler puts whatever assembly magic in loops and
> here and there to fulfill the "within reasonable amount of time"
> guarantee?

regards,
alexander.

[toc] | [next] | [standalone]

#375 — Re: C++0x, 29.3 p13 "[...] atomic stores visible [...] within a reasonable amount of time."

On Jun 27, 11:55 am, Alexander Terekhov <terek...@web.de> wrote:
> <moving away from comp.std.c++>
>
>
>
>
>
>
>
>
>
> Joshua Maurice wrote:
>
> > I have a question regarding C++0x, 29.3 p13. In draft n3242, the exact
> > text is:
>
> > "Implementations should make atomic stores visible to atomic loads
> > within a reasonable amount of time."
>
> > I am wondering if there is a well known intent as to the meaning of
> > "reasonable". Allow me to explain. I apologize up front if I'm
> > mistaken in any of my understandings, and please point out any such
> > misunderstandings. I also understand this is a QoI issue, but I think
> > that this particular answer greatly affects how one should write
> > portable code, which is why it's not quite something we ought to be
> > allowed to handwave as "implementation defined".
>
> > Consider:
> >    std::atomic<int> x;
> >    //...
> >    while(x.load(std::memory_order_relaxed)) {}
> > That is, suppose we have an atomic variable x, and perhaps
> > specifically the type which is guaranteed to be lock-free. (I can't
> > quite find the text for that offhand.) It's my understanding that the
> > intent is for that load to be implemented by whatever passes for the
> > normal, common assembly load on that platform.
>
> > So, that simple assembly load may be satisfied by a core local cache.
> > If it is satisfied by a core-local cache, then the changes are high in
> > that busy waiting loop that future loads will be satisfied by a core
> > local cache, and thus it may not see a new write, ever, barring other
> > things. Other things, such as the common multi-tasking, preemptive
> > threading, OS. For that, eventually that busy loop will exhaust the
> > thread's timeslice, and it will be taken off the core. At some later
> > point, it will be put back on the core, which as I understand commonly
> > invalidates any core local caches, which means that the next load of
> > that busy waiting loop will go to main memory (or non-core local
> > cache, etc.), and it will see a new value.
>
> > So, would such an implementation be "conforming in spirit"? I
> > understand this is a QoI issue, but it is relevant. Specifically, is
> > there some understood intent and meaning that "reasonable" means
> > "maybe the next time the thread is scheduled out and scheduled back
> > in", or is "reasonable" meant to be something sooner than that?
>
> > This may be relevant to real world code for cooperative thread
> > cancelling. I assume the default way of handling cooperative thread
> > cancelling is to have a lock-free std::atomic bool variable which is
> > global to the "job" which can be cancelled. Call that the "stop flag".
> > Threads doing the jobs will periodically check the stop flag, and if
> > read true, then they will bail out and end the job. The question is
> > whether the stop flag should use memory_order_relaxed loads and stores
> > or seq_cst loads and stores. If relaxed loads and stores can be
> > delayed until the thread is scheduled out and back in, then that may
> > be too high of a delay for responsive cooperative job cancellation.
> > It's my understanding that with seq_cst loads and stores to the stop
> > flag, then that cannot be delayed by anything more than a "few"
> > assembly instructions, due to the total order S.
>
> C++11 aside (the latest draft is not public and I have no idea what it
> says),

C++0x, 29.3 p13. In draft n3242, the exact text is:
"Implementations should make atomic stores visible to atomic loads
within a reasonable amount of time."

>on assembly level, in order to read the last value you need
> read-modify-write operation such as fetch_add(0) and relaxed RMW reads
> last value just fine.

True. After I wrote that, I considered that using atomic RMW is
another option. It seems using relaxed writes and reads for a stop
flag is a bad idea. I'd guess that an atomic RMW operation with
std::memory_order_relaxed would translate into a "cheaper" or as cheap
as operation than a read with std::memory_order_seqcst, as the RMW
only needs to synchronize on that single memory location.

I'm wondering what people do in practice on this, besides using a
mutex. They use RMW operations for the "set" of the stop flag and all
"tests" of the stop flag?

Also, AFAIK, when using the C++0x "interface" for RMW operations, you
need to write a value. Thus, each thread when testing the stop flag
would write 0 with a RMW, and if it read 1 with that RMW, then it
would have to reset the stop flag for the benefit of other threads
(and other tests later in this thread). I'm wondering if there is some
sort of C++0x primitive that is an atomic test-and-set. I failed to
notice one, but I haven't exactly read the entire thing thoroughly
either.

[toc] | [prev] | [next] | [standalone]

#377 — Re: C++0x, 29.3 p13 "[...] atomic stores visible [...] within a reasonable amount of time."

Joshua Maurice wrote:
[...]
> >on assembly level, in order to read the last value you need
> > read-modify-write operation such as fetch_add(0) and relaxed RMW reads
> > last value just fine.
> 
> True. After I wrote that, I considered that using atomic RMW is
> another option. It seems using relaxed writes and reads for a stop
> flag is a bad idea. I'd guess that an atomic RMW operation with

Relaxed write is just fine (if you don't want to communicate some state
to the to-be-stopped thread(s), if you do want it then release write is
what you need). 

fetch_add(0) (relaxed or acquire) RMW is meant to read the flag, not
write.

> std::memory_order_relaxed would translate into a "cheaper" or as cheap
> as operation than a read with std::memory_order_seqcst, as the RMW
> only needs to synchronize on that single memory location.

RMW is needed to observe the last value within duration of RMW
instruction. 

OTOH seqcst read may yield 'old' value for "a reasonable amount of time"
just like relaxed read. 

> 
> I'm wondering what people do in practice on this, besides using a
> mutex. They use RMW operations for the "set" of the stop flag and all
> "tests" of the stop flag?

Most people are mostly wrong. :-) You might want to check various
implementations of lock-free sem_getvalue()/GETVAL for use of fully
fenced RMW to read the semaphore value.

> 
> Also, AFAIK, when using the C++0x "interface" for RMW operations, you
> need to write a value. Thus, each thread when testing the stop flag

fetch_add(0) simply writes old value. Think of x86 LOCK XADD(0).

> would write 0 with a RMW, and if it read 1 with that RMW, then it
> would have to reset the stop flag for the benefit of other threads
> (and other tests later in this thread). I'm wondering if there is some
> sort of C++0x primitive that is an atomic test-and-set. I failed to
> notice one, but I haven't exactly read the entire thing thoroughly
> either.

Search the entire thing for "atomics.flag".

regards,
alexander.

[toc] | [prev] | [next] | [standalone]

#378 — Re: C++0x, 29.3 p13 "[...] atomic stores visible [...] within a reasonable amount of time."

On Jul 1, 8:35 am, Alexander Terekhov <terek...@web.de> wrote:
> Joshua Maurice wrote:
>
> [...]
>
> > >on assembly level, in order to read the last value you need
> > > read-modify-write operation such as fetch_add(0) and relaxed RMW reads
> > > last value just fine.
>
> > True. After I wrote that, I considered that using atomic RMW is
> > another option. It seems using relaxed writes and reads for a stop
> > flag is a bad idea. I'd guess that an atomic RMW operation with
>
> Relaxed write is just fine (if you don't want to communicate some state
> to the to-be-stopped thread(s), if you do want it then release write is
> what you need).
>
> fetch_add(0) (relaxed or acquire) RMW is meant to read the flag, not
> write.
>
> > std::memory_order_relaxed would translate into a "cheaper" or as cheap
> > as operation than a read with std::memory_order_seqcst, as the RMW
> > only needs to synchronize on that single memory location.
>
> RMW is needed to observe the last value within duration of RMW
> instruction.
>
> OTOH seqcst read may yield 'old' value for "a reasonable amount of time"
> just like relaxed read.
>
>
>
> > I'm wondering what people do in practice on this, besides using a
> > mutex. They use RMW operations for the "set" of the stop flag and all
> > "tests" of the stop flag?
>
> Most people are mostly wrong. :-) You might want to check various
> implementations of lock-free sem_getvalue()/GETVAL for use of fully
> fenced RMW to read the semaphore value.
>
>
>
> > Also, AFAIK, when using the C++0x "interface" for RMW operations, you
> > need to write a value. Thus, each thread when testing the stop flag
>
> fetch_add(0) simply writes old value. Think of x86 LOCK XADD(0).
>
> > would write 0 with a RMW, and if it read 1 with that RMW, then it
> > would have to reset the stop flag for the benefit of other threads
> > (and other tests later in this thread). I'm wondering if there is some
> > sort of C++0x primitive that is an atomic test-and-set. I failed to
> > notice one, but I haven't exactly read the entire thing thoroughly
> > either.
>
> Search the entire thing for "atomics.flag".

Thank you very much kind sir.

One thing though. You said:
> OTOH seqcst read may yield 'old' value for "a reasonable amount of time"
> just like relaxed read.

Is this true? I'm not disputing it. However, I don't think this is
quite correct. I think I could use 29.3 p4 to maybe show otherwise. We
know that there is a total order S on all seqcst operations. I am
presuming that this has some semblance to the time at which a core
actually executes it - which may be our point of contention. I would
think an implementation would need to be malicious to start doing this
and to preserve the guarantees of 29.3 p4 through p7. I'd have to
think more about this, but suffice to say I also prefer the simple
guaranteed things over the of the fuzzy "maybe in practice" things.

[toc] | [prev] | [next] | [standalone]

#379 — Re: C++0x, 29.3 p13 "[...] atomic stores visible [...] within a reasonable amount of time."

Joshua Maurice wrote:
[...]
> > OTOH seqcst read may yield 'old' value for "a reasonable amount of time"
> > just like relaxed read.
> 
> Is this true? I'm not disputing it. However, I don't think this is

See 

http://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html

"Load Seq_Cst: MOV (from memory)"

> quite correct. I think I could use 29.3 p4 to maybe show otherwise. We
> know that there is a total order S on all seqcst operations. I am
> presuming that this has some semblance to the time at which a core
> actually executes it - which may be our point of contention. I would
> think an implementation would need to be malicious to start doing this
> and to preserve the guarantees of 29.3 p4 through p7. I'd have to
> think more about this, but suffice to say I also prefer the simple
> guaranteed things over the of the fuzzy "maybe in practice" things.

People won't be happy with XADD(0) for seqcst reads.

regards,
alexander.

[toc] | [prev] | [next] | [standalone]

#385 — Re: C++0x, 29.3 p13 "[...] atomic stores visible [...] within a reasonable amount of time."

On Jul 2, 1:18 am, Alexander Terekhov <terek...@web.de> wrote:
> Joshua Maurice wrote:
>
> [...]
>
> > > OTOH seqcst read may yield 'old' value for "a reasonable amount of time"
> > > just like relaxed read.
>
> > Is this true? I'm not disputing it. However, I don't think this is
>
> See
>
> http://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html
>
> "Load Seq_Cst: MOV (from memory)"
>
> > quite correct. I think I could use 29.3 p4 to maybe show otherwise. We
> > know that there is a total order S on all seqcst operations. I am
> > presuming that this has some semblance to the time at which a core
> > actually executes it - which may be our point of contention. I would
> > think an implementation would need to be malicious to start doing this
> > and to preserve the guarantees of 29.3 p4 through p7. I'd have to
> > think more about this, but suffice to say I also prefer the simple
> > guaranteed things over the of the fuzzy "maybe in practice" things.
>
> People won't be happy with XADD(0) for seqcst reads.

Indeed. Nevermind.

It appears that your options for guaranteed visible "now-ish" are
atomic RMW operations, and stronger blocking operations like mutexes
and semaphores.

[toc] | [prev] | [next] | [standalone]

#380 — Re: C++0x, 29.3 p13 "[...] atomic stores visible [...] within a reasonable amount of time."

>> C++11 aside (the latest draft is not public and I have no idea what it
>> says),
>
> C++0x, 29.3 p13. In draft n3242, the exact text is:
> "Implementations should make atomic stores visible to atomic loads
> within a reasonable amount of time."
>

If you have the time, this point somehow interests me a lot.

To start: does it apply to relaxed only?

The main question: Does it apply to release (and acquire/consume)?
(I am ignoring other orderings on purpose, as irrelevant for
release/acquire, or consume, pair)

What I am basically wondering about, is how to release a lock
(or anything else blocking another thread)
in a way that assures it is done 'now' [1]; I care more
about the standard - > how to write code < - than how it is
on architecture X  - > how to implement a compiler <.

Edek

[1] I do have a notion of relativity of now. I mean 'without any
costly delay'

[toc] | [prev] | [next] | [standalone]

#383 — Re: C++0x, 29.3 p13 "[...] atomic stores visible [...] within a reasonableamount of time."

Edek wrote:
> 
> >> C++11 aside (the latest draft is not public and I have no idea what it
> >> says),
> >
> > C++0x, 29.3 p13. In draft n3242, the exact text is:
> > "Implementations should make atomic stores visible to atomic loads
> > within a reasonable amount of time."
> >
> 
> If you have the time, this point somehow interests me a lot.
> 
> To start: does it apply to relaxed only?

It applies to all stores.

> 
> The main question: Does it apply to release 

Yes.

> (and acquire/consume)?

There are no acquire/consume stores.

> (I am ignoring other orderings on purpose, as irrelevant for
> release/acquire, or consume, pair)
> 
> What I am basically wondering about, is how to release a lock
> (or anything else blocking another thread)
> in a way that assures it is done 'now' [1]; I care more

Simply do a store or RMW. The lock acquiring thread will perform an RMW
attempting to acquire the lock.

regards,
alexander.

[toc] | [prev] | [next] | [standalone]

#384 — Re: C++0x, 29.3 p13 "[...] atomic stores visible [...] within a reasonableamount of time."

My understanding is not _that_ shallow.

>>> C++0x, 29.3 p13. In draft n3242, the exact text is:
>>> "Implementations should make atomic stores visible to atomic loads
>>> within a reasonable amount of time."
>>>
>>
>> If you have the time, this point somehow interests me a lot.
>>
>> To start: does it apply to relaxed only?
>
> It applies to all stores.

Different question: are any stores with a guarantee of better
immediacy?

>
>>
>> The main question: Does it apply to release
>
> Yes.
>
>> (and acquire/consume)?
>
> There are no acquire/consume stores.

Thread1: store, Thread2: consume. For me these two are a pair;
of course these are not stores, these are the points where the store
should be visible.

>
>> (I am ignoring other orderings on purpose, as irrelevant for
>> release/acquire, or consume, pair)
>>
>> What I am basically wondering about, is how to release a lock
>> (or anything else blocking another thread)
>> in a way that assures it is done 'now' [1]; I care more
>
> Simply do a store or RMW. The lock acquiring thread will perform an RMW
> attempting to acquire the lock.

Again: which memory ordering should I use to make a store which will
be visible sooner than "within a reasonable amount of time",
and which load will see this?

Locked RMW on x86_64 will work, but that's not the point.

>
> regards,
> alexander.

Thanks,
Edek

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming.threads

csiph-web