tag:blogger.com,1999:blog-5246987755651065286.post883393892702986841..comments2024-02-22T16:15:42.388-08:00Comments on cbloom rants: 07-10-11 - Mystery - Do you ever need Total Order (seq_cst) -cbloomhttp://www.blogger.com/profile/10714564834899413045noreply@blogger.comBlogger15125tag:blogger.com,1999:blog-5246987755651065286.post-45006552727164160072012-05-31T20:00:10.411-07:002012-05-31T20:00:10.411-07:00"They complete the synchronize-with relations..."They complete the synchronize-with relations. Because those are there, no other non-atomics will be reordered across the fences..."<br /><br />Sorry, I was wrong in that case. In the example I gave, the seq_cst fence does order the neighboring atomics (<a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3337.pdf" rel="nofollow">section 29.3.6</a>), but no synchronize-with relation is completed. So you are right, in <i>that</i> example, any non-atomics could be reordered at will.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-85787656882438473622012-05-31T10:10:02.224-07:002012-05-31T10:10:02.224-07:00I took an interest in your post because I have the...I took an interest in your post because I have the same (or similar) question as you: Is there some algorithm where we really have no choice but to use sequentially consistent atomic variables? So far, they only seem to exist to offer a Java-like alternative. So you can plug in examples from Art of Multiprocessor Programming (which is pretty Java-focused) and they will just work. I guess that alone is a useful reason for them to exist, especially from the point of view of the C++ standards committee.<br /><br />"non-atomics can be essentially reordered at will" -- There are limits to this. If it was true, how could a spinlock protect anything? You'd technically have to wrap all shared memory in atomics (even bitfields) and it would be a huge pain. Anthony talks about this in section 5.3.6 of his book, "Ordering nonatomic operations with atomics." The key (in C++ legalspeak) is that non-atomics are included in the "happens-before" relations of a single thread, and "synchronize-with" is just a way to bridge those relations across threads.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-57898293370084473032012-05-31T08:46:04.285-07:002012-05-31T08:46:04.285-07:00"So according to Relacy, your shared variable..."So according to Relacy, your shared variables must be at least relaxed atomics for this to work."<br /><br />Yes, the standard says nothing about how the std::atomic stuff interacts with non-std::atomic stuff.<br /><br />"Though, I would be very interested to see an actual compiler & platform where a relaxed atomic int is treated differently from a plain int."<br /><br />You know GCC or someone will do it someday and break lots of perfectly reasonable code in order to make some synthetic test go 1% faster.<br /><br />"They complete the synchronize-with relations. Because those are there, no other non-atomics will be reordered across the fences..."<br /><br />Not sure what you mean there; non-atomics can be essentially reordered at will.<br /><br /><br />Anyway, I want to take a moment to repeat the original purpose of this post, which is :<br /><br />Do you ever actually need sequential consistency?<br /><br />I call out the use case of a seq_cst fence as a "phantom" need for sequential consistency. What we are actually trying to get there is a #StoreLoad, we don't need the sequential consistency part of it at all (which is a much heavier synchronization in theory, even if in practice on current chips they are equal (*)), but there's no way in C++0x to get the one without the other.<br /><br /><br />(* = there is every reason to believe that in the massively multicore future, full system-wide bus-locking ops like sequential consistency will become highly undesirable)cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-80094944516582803642012-05-31T04:51:18.863-07:002012-05-31T04:51:18.863-07:00*** Finally, I think those are the minimum shared ...*** Finally, I think those are the <i>minimum</i> shared vars which must be relaxed atomic in that example. They complete the synchronize-with relations. Because those are there, no <i>other</i> non-atomics will be reordered across the fences...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-62264858308670382582012-05-30T17:36:26.283-07:002012-05-30T17:36:26.283-07:00I've seen some ambiguous old info floating aro...I've seen some ambiguous old info floating around newsgroups, too.<br /><br />To be a bit more certain, I checked what Relacy had to say about it:<br /><br />struct iriw_test : rl::test_suite<iriw_test, 2><br />{<br /> std::atomic<int> X, Y;<br /> int r1, r2;<br /><br /> void before()<br /> {<br /> X($) = 0;<br /> Y($) = 0;<br /> }<br /><br /> void thread(unsigned index)<br /> {<br /> if (0 == index)<br /> {<br /> X.store(1, rl::memory_order_relaxed);<br /> std::atomic_thread_fence(rl::memory_order_seq_cst);<br /> r1 = Y.load(rl::memory_order_relaxed);<br /> }<br /> else<br /> {<br /> Y.store(1, rl::memory_order_relaxed);<br /> std::atomic_thread_fence(rl::memory_order_seq_cst);<br /> r2 = X.load(rl::memory_order_relaxed);<br /> }<br /> }<br /><br /> void after()<br /> {<br /> RL_ASSERT(r1 == 1 || r2 == 1);<br /> }<br />};<br /><br />This runs fine. If you remove the fences, it asserts and tells you one of loads took a value which was not current.<br /><br />Also, if you change std::atomic to plain int (rl::var), it reports a DATA RACE on one of the stores. So according to Relacy, your shared variables must be at least relaxed atomics for this to work. This is actually consistent with the wording of the standard and Anthony's Dekker example. And it suggests that the current page on <a href="http://en.cppreference.com/w/cpp/atomic/atomic_thread_fence" rel="nofollow">cppreference.com</a> gets it wrong. (It says non-atomic accesses get ordered.) Though, I would be very interested to see an actual compiler & platform where a relaxed atomic int is treated differently from a plain int.<br /><br />PS. I wrote atomic_memory_fence earlier, meant atomic_thread_fence, oops.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-36275685667059103302012-05-30T15:41:11.572-07:002012-05-30T15:41:11.572-07:00"Still, it seems misleading to say "you ..."Still, it seems misleading to say "you cannot just translate a #StoreLoad from another language into a fence(seq_cst)". You totally can."<br /><br />err, yeah I think you're right about that. Either I was mistaken or the wording about fences in the standard got stronger in one of the revisions. The new wording looks different from what I recall reading last.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-35032508819424330042012-05-30T13:59:03.412-07:002012-05-30T13:59:03.412-07:00I get your point about wanting to express StoreLoa...I get your point about wanting to express StoreLoad as a minimum guarantee requirement. Still, it seems misleading to say "you cannot just translate a #StoreLoad from another language into a fence(seq_cst)". You totally can. Also, <a href="http://g.oswego.edu/dl/jmm/cookbook.html" rel="nofollow">all CPU instructions that perform StoreLoad also obtain the other three barrier effects</a>, so it's not like C++11 missed out on the chance to use a better (single) instruction. FWIW, it's implemented as an XCHG in VS11 Beta x86.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-16397841625663241982012-05-30T10:01:02.235-07:002012-05-30T10:01:02.235-07:00Here are two more posts on the StoreLoad issue :
...Here are two more posts on the StoreLoad issue :<br /><br />http://cbloomrants.blogspot.com/2011/07/07-31-11-example-that-needs-seqcst_31.html<br /><br />http://cbloomrants.blogspot.com/2011/11/11-28-11-some-lock-free-rambling.html<br /><br />I think I'll just write a fresh post about fences because writing anything significant in this comment box sucks.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-83434102699716954042012-05-29T09:31:40.633-07:002012-05-29T09:31:40.633-07:00Preshing, good questions. I'll take the secon...Preshing, good questions. I'll take the second one first :<br /><br />I don't mean to imply that you cannot get a #StoreLoad in C++0x. Of course you can, and I do it often in different ways.<br /><br />What I'm saying is that you cannot *express* a #StoreLoad in C++0x. That is, there's no way to say "the only memory ordering required here is #StoreLoad".<br /><br />The whole point of memory-order specification is to require the absolute minimum to make a program correct. This is ideal for efficiency, but more than that is the mathematical truth at the heart of the algorithm.<br /><br />StoreLoad is the biggest omission in C++0x that I ran into on a regular basis in trying to write lockfree code. You often get to a situation where you know all you need to make a certain algorithm correct is to add a StoreLoad order constraint, but you cannot express that in C++0x. So you can either add a full seq_cst fence, or the slightly more minimal thing which I generally prefer is like this :<br /><br />1. Store<br />2. want #StoreLoad here<br />3. Load<br /><br />Change either #1 or #3 to a Load+Store op (like Exchange) , then use #LoadLoad or #StoreStore at #2.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-35606201656636599542012-05-28T22:08:12.111-07:002012-05-28T22:08:12.111-07:00I have found your low-level threading notes genera...I have found your low-level threading notes generally helpful, but I think you've made a couple of errors in this post:<br /><br />1. You say that a seq_cst fence does not order relaxed memory ops in C++0x. However <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3337.pdf" rel="nofollow">section 29.8.2 of the standard</a> uses the term "synchronizes with" to say that a release fence enforces ordering with respect to an acquire fence. <a href="http://en.cppreference.com/w/cpp/atomic/atomic_thread_fence" rel="nofollow">This page on cppreference.com</a> says the same thing in simpler language. A seq_cst fence is both kinds of fences, and therefore must enforce ordering too.<br /><br />2. You say there's no way to get a #StoreLoad barrier in C++0x. However <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2633.html#alternative" rel="nofollow">this proposal</a>, which I believe was accepted, says the intended implementation of std::atomic_memory_fence(std::memory_order_seq_cst) on a SPARC RMO is #LoadLoad | #LoadStore | <b>#StoreLoad</b> | #StoreStore. And in the <a href="http://www.justsoftwaresolutions.co.uk/threading/implementing_dekkers_algorithm_with_fences.html" rel="nofollow">post by Anthony</a> which you link, the first four paragraphs of his analysis explain what the seq_cst fences are doing; I don't know what that is if not a StoreLoad.<br /><br />When you mention "seq_cst fences don't act like you think they do", which of Dmitriy's posts are you referring to? Could you share the link?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-43691866030272014642011-07-13T11:36:39.631-07:002011-07-13T11:36:39.631-07:00Okay, should be fixed. Also added a better simple...Okay, should be fixed. Also added a better simpler example that you can actually run.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-84514871633761134252011-07-13T09:50:53.850-07:002011-07-13T09:50:53.850-07:00Yeah of course you're right, it's a terrib...Yeah of course you're right, it's a terrible toy example, I'll fix it in the post.<br /><br />Total order only applies to the memory bus, the threads that interact with it can still have races of course.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-17316931173900407732011-07-12T23:18:45.988-07:002011-07-12T23:18:45.988-07:00In the toy example isn't the following a valid...In the toy example isn't the following a valid sequence of ops even with seq_cst?<br /><br />thread4: A = a; <br />thread4: B = b; <br /><br />thread1: a = 1;<br /><br />thread3: A = a; B = b; C = c; D = d;<br /><br />thread1: b = 1;<br /><br />thread2: c = 1;<br />thread2: d = 1;<br /><br />thread4: C = c; <br />thread4: D = d;<br /><br />that will still give the output:<br /><br />thread3 :<br /> 1,0,0,0<br /><br />thread4 :<br /> 0,0,1,1<br /> <br />I might have misunderstood this completely but I can't see how seq_cst can guarantee that the output of thread 3 and 4 is be the same.Simon Mogensenhttps://www.blogger.com/profile/01267293199646037726noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-59655523114693364572011-07-12T19:20:53.117-07:002011-07-12T19:20:53.117-07:00...only if you have multiple agents (threads/cores......only if you have multiple agents (threads/cores) talking to the same MMIO device simultaneously, which in itself seems like a weird thing to do; it only works if the given MMIO port is completely stateless, for once!ryghttps://www.blogger.com/profile/03031635656201499907noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-6063172536535250902011-07-12T08:22:51.652-07:002011-07-12T08:22:51.652-07:00ahha! When your writing to memory mapped IO, you n...ahha! When your writing to memory mapped IO, you need total order. (a rare occurrence on some archs)https://www.blogger.com/profile/07698332535766464476noreply@blogger.com