Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming.threads > #269 > unrolled thread
| Started by | Masakuni Oishi <yamasa@bsdhouse.org> |
|---|---|
| First post | 2011-06-13 09:40 -0700 |
| Last post | 2011-06-15 02:06 -0700 |
| Articles | 20 on this page of 84 — 6 participants |
Back to article view | Back to comp.programming.threads
questions about memory_order_seq_cst fence Masakuni Oishi <yamasa@bsdhouse.org> - 2011-06-13 09:40 -0700
Re: questions about memory_order_seq_cst fence Edek <edek.pienkowski@gmail.com> - 2011-06-13 22:39 +0200
Re: questions about memory_order_seq_cst fence Masakuni Oishi <yamasa@bsdhouse.org> - 2011-06-14 08:27 -0700
Re: questions about memory_order_seq_cst fence Edek <edek.pienkowski@gmail.com> - 2011-06-16 00:21 +0200
Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-15 15:48 -0700
Re: questions about memory_order_seq_cst fence Masakuni Oishi <yamasa@bsdhouse.org> - 2011-06-16 05:03 -0700
Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-16 08:35 +0100
Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-16 12:05 +0200
Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-16 11:19 +0100
Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-16 13:57 +0200
Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-16 13:51 +0100
Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-16 16:53 +0200
Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-16 16:17 +0100
Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-16 17:37 +0200
Re: questions about memory_order_seq_cst fence "Chris M. Thomasson" <cristom@charter.net> - 2011-06-16 08:47 -0700
Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-16 16:54 +0100
Re: questions about memory_order_seq_cst fence "Chris M. Thomasson" <cristom@charter.net> - 2011-06-16 09:01 -0700
Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-16 17:07 +0100
Re: questions about memory_order_seq_cst fence "Chris M. Thomasson" <cristom@charter.net> - 2011-06-16 13:59 -0700
Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-16 14:32 -0700
Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-17 08:03 +0100
Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-17 16:19 +0200
Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-17 15:40 +0100
Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-30 14:26 +0200
Re: questions about memory_order_seq_cst fence "Chris M. Thomasson" <cristom@charter.net> - 2011-06-17 15:24 -0700
Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-18 03:49 -0700
Re: questions about memory_order_seq_cst fence "Chris M. Thomasson" <cristom@charter.net> - 2011-06-18 14:40 -0700
Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-18 15:46 -0700
Re: questions about memory_order_seq_cst fence "Chris M. Thomasson" <cristom@charter.net> - 2011-06-18 20:27 -0700
Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-18 21:31 -0700
Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-18 21:37 -0700
Re: questions about memory_order_seq_cst fence "Chris M. Thomasson" <cristom@charter.net> - 2011-06-20 15:45 -0700
Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-20 20:05 -0700
Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-18 14:06 +0200
Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-16 18:32 +0200
Re: questions about memory_order_seq_cst fence "Chris M. Thomasson" <cristom@charter.net> - 2011-06-16 15:42 -0700
Re: questions about memory_order_seq_cst fence Edek <edek.pienkowski@gmail.com> - 2011-07-10 19:47 +0200
Re: questions about memory_order_seq_cst fence "Chris M. Thomasson" <cristom@charter.net> - 2011-06-16 08:51 -0700
Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-16 17:23 +0100
Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-16 18:49 +0200
Re: questions about memory_order_seq_cst fence "Chris M. Thomasson" <cristom@charter.net> - 2011-06-16 08:51 -0700
Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-16 17:25 +0200
Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-16 16:56 +0100
Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-18 14:28 +0200
Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-20 09:54 +0100
Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-20 15:39 +0200
Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-22 13:24 +0200
Re: questions about memory_order_seq_cst fence Edek <edek.pienkowski@gmail.com> - 2011-06-16 14:39 +0200
Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-16 13:55 +0100
Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-16 12:03 +0200
Re: questions about memory_order_seq_cst fence Edek <edek.pienkowski@gmail.com> - 2011-07-10 19:10 +0200
Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-13 16:00 -0700
Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-13 23:31 -0700
Re: questions about memory_order_seq_cst fence Masakuni Oishi <yamasa@bsdhouse.org> - 2011-06-14 08:32 -0700
Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-14 23:05 +0100
Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-14 16:44 -0700
Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-15 08:34 +0100
Re: questions about memory_order_seq_cst fence Masakuni Oishi <yamasa@bsdhouse.org> - 2011-06-15 02:11 -0700
Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-15 15:58 -0700
Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-16 08:26 +0100
Re: questions about memory_order_seq_cst fence Masakuni Oishi <yamasa@bsdhouse.org> - 2011-06-16 05:05 -0700
Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-16 13:11 +0100
Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-18 15:42 +0200
Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-20 09:27 +0100
Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-20 15:30 +0200
Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-20 15:00 +0100
Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-21 14:54 +0200
Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-21 18:37 +0200
Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-21 15:59 +0200
Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-22 09:01 -0700
Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-20 15:41 +0100
Re: questions about memory_order_seq_cst fence Masakuni Oishi <yamasa@bsdhouse.org> - 2011-06-20 23:24 -0700
Re: questions about memory_order_seq_cst fence Masakuni Oishi <yamasa@bsdhouse.org> - 2011-06-22 10:46 -0700
Re: questions about memory_order_seq_cst fence Masakuni Oishi <yamasa@bsdhouse.org> - 2011-06-22 11:19 -0700
Re: questions about memory_order_seq_cst fence Masakuni Oishi <yamasa@bsdhouse.org> - 2011-06-22 11:57 -0700
Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-27 14:05 +0200
Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-29 16:14 -0700
Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-06-24 01:42 -0700
Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-06-27 13:24 +0200
Re: questions about memory_order_seq_cst fence Anthony Williams <anthony.ajw@gmail.com> - 2011-07-01 02:25 -0700
Re: questions about memory_order_seq_cst fence Alexander Terekhov <terekhov@web.de> - 2011-07-01 12:48 +0200
Re: questions about memory_order_seq_cst fence Masakuni Oishi <yamasa@bsdhouse.org> - 2011-06-15 01:53 -0700
Re: questions about memory_order_seq_cst fence Joshua Maurice <joshuamaurice@gmail.com> - 2011-06-15 02:57 -0700
Re: questions about memory_order_seq_cst fence "Chris M. Thomasson" <cristom@charter.net> - 2011-06-15 02:06 -0700
Page 3 of 5 — ← Prev page 1 2 [3] 4 5 Next page →
| From | "Chris M. Thomasson" <cristom@charter.net> |
|---|---|
| Date | 2011-06-16 08:51 -0700 |
| Message-ID | <9EpKp.6158$PA5.3093@newsfe01.iad> |
| In reply to | #300 |
"Anthony Williams" <anthony.ajw@gmail.com> wrote in message news:87oc1xajr3.fsf@justsoftwaresolutions.co.uk... > Alexander Terekhov <terekhov@web.de> writes: > >> Anthony Williams wrote: >> [...] >>> LOCKed instructions have a total order (7.2.3.8 in my copy of the Intel >>> 64 and IA-32 SDM Vol 3A), so if you use XCHG for stores (as per my blog >>> post) then all processors/threads must agree on the order of the writes. >>> >>> This is the key to SC --- all SC stores must have a single total order >>> which is agreed across all threads. >>> >>> Why do you think this is not enough? >> >> x.store(44, memory_order_relaxed); // or _release >> r1 = y.load(memory_order_seq_cst); >> >> there should be a store-load reordering constraint, just like in >> >> x.store(44, memory_order_seq_cst); >> r1 = y.load(memory_order_relaxed); // or _acquire/_consume > > Why? Can you give an example that would be broken by the lack of such a > constraint, and a reference to the FDIS that guarantees the presence of > that constraint? I think I can see this breaking an SMR implementation in which the author thinks that the seq_cst on the load will prevent it from being hoisted up above the preceding store. I am having some trouble trying to understanding why: x.store(44, memory_order_relaxed); // or _release r1 = y.load(memory_order_seq_cst); would not ensure that the store will be rendered visible before the load is performed... What am I missing here?
[toc] | [prev] | [next] | [standalone]
| From | Alexander Terekhov <terekhov@web.de> |
|---|---|
| Date | 2011-06-16 17:25 +0200 |
| Message-ID | <4DFA2086.5791E46@web.de> |
| In reply to | #299 |
Addition re "Incorrect implementation" below: Alexander Terekhov wrote: > > Anthony Williams wrote: > [...] > > LOCKed instructions have a total order (7.2.3.8 in my copy of the Intel > > 64 and IA-32 SDM Vol 3A), so if you use XCHG for stores (as per my blog > > post) then all processors/threads must agree on the order of the writes. > > > > This is the key to SC --- all SC stores must have a single total order > > which is agreed across all threads. > > > > Why do you think this is not enough? > > In > > x.store(44, memory_order_relaxed); // or _release > r1 = y.load(memory_order_seq_cst); > > there should be a store-load reordering constraint, just like in > > x.store(44, memory_order_seq_cst); > r1 = y.load(memory_order_relaxed); // or _acquire/_consume > > Implementation 1: > > Load Seq_Cst: LOCK XADD(0) > Store Seq_Cst: LOCK XCHG > > Implementation 2: > > Load Seq_Cst: LOCK XADD(0) > Store Seq_Cst: MOV, MFENCE > > Implementation 3: > > Load Seq_Cst: MFENCE, MOV > Store Seq_Cst: LOCK XCHG > > Incorrect implementation > > Load Seq_Cst: MFENCE, MOV > Store Seq_Cst: MOV, MFENCE > > is busted because IRIW won't work. That is my thinking... but according to http://portal.acm.org/citation.cfm?id=1926394 the "Incorrect implementation" above is actually correct (probably because according to them, MFENCE has the same semantics as PPC's hwsync). (I'm personally still in doubt). regards, alexander.
[toc] | [prev] | [next] | [standalone]
| From | Anthony Williams <anthony.ajw@gmail.com> |
|---|---|
| Date | 2011-06-16 16:56 +0100 |
| Message-ID | <87fwn9ahxw.fsf@justsoftwaresolutions.co.uk> |
| In reply to | #301 |
Alexander Terekhov <terekhov@web.de> writes: >> Incorrect implementation >> >> Load Seq_Cst: MFENCE, MOV >> Store Seq_Cst: MOV, MFENCE >> >> is busted because IRIW won't work. > > That is my thinking... but according to > > http://portal.acm.org/citation.cfm?id=1926394 > > the "Incorrect implementation" above is actually correct (probably > because according to them, MFENCE has the same semantics as PPC's > hwsync). That paper also says: "Sequentially consistent atomics The proposal above includes two implementations of sequentially consistent atomic reads and writes; one with the x86 locked instructions, and the other with fence instructions on both the reads and writes. However, we can prove that it suffices either to place an mfence before every sc read, or after every sc write, but that it is not necessary to do both. In practice, placing the fence after the sc writes is expected to yield higher performance." i.e. they think that Load SC: MOV Store SC: MOV, MFENCE is a valid implementation. Anthony -- Author of C++ Concurrency in Action http://www.stdthread.co.uk/book/ just::thread C++0x thread library http://www.stdthread.co.uk Just Software Solutions Ltd http://www.justsoftwaresolutions.co.uk 15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976
[toc] | [prev] | [next] | [standalone]
| From | Alexander Terekhov <terekhov@web.de> |
|---|---|
| Date | 2011-06-18 14:28 +0200 |
| Message-ID | <4DFC99EA.5E824F96@web.de> |
| In reply to | #307 |
Anthony Williams wrote: > > Alexander Terekhov <terekhov@web.de> writes: > > >> Incorrect implementation > >> > >> Load Seq_Cst: MFENCE, MOV > >> Store Seq_Cst: MOV, MFENCE > >> > >> is busted because IRIW won't work. > > > > That is my thinking... but according to > > > > http://portal.acm.org/citation.cfm?id=1926394 > > > > the "Incorrect implementation" above is actually correct (probably > > because according to them, MFENCE has the same semantics as PPC's > > hwsync). > > That paper also says: > > "Sequentially consistent atomics The proposal above includes > two implementations of sequentially consistent atomic reads and > writes; one with the x86 locked instructions, and the other with > fence instructions on both the reads and writes. However, we can > prove that it sufï¬ces either to place an mfence before every sc read, > or after every sc write, but that it is not necessary to do both. In > practice, placing the fence after the sc writes is expected to yield > higher performance." > > i.e. they think that > > Load SC: MOV > Store SC: MOV, MFENCE > > is a valid implementation. They are talking about X86-TSO (not actual X86), which is equivalent to SPARC-TSO (with #StoreLoad spelled as MFENCE), see http://www.decadent.org.uk/pipermail/cpp-threads/2008-December/001947.html (obviously, it was meant that two consecutive #StoreLoad/MFENCE barriers, like in "store x, load y" both seq_cst, ought to be reduced to just one by the compiler.) regards, alexander.
[toc] | [prev] | [next] | [standalone]
| From | Anthony Williams <anthony.ajw@gmail.com> |
|---|---|
| Date | 2011-06-20 09:54 +0100 |
| Message-ID | <87hb7ksx0t.fsf@justsoftwaresolutions.co.uk> |
| In reply to | #323 |
Alexander Terekhov <terekhov@web.de> writes: > Anthony Williams wrote: >> >> Alexander Terekhov <terekhov@web.de> writes: >> >> >> Incorrect implementation >> >> >> >> Load Seq_Cst: MFENCE, MOV >> >> Store Seq_Cst: MOV, MFENCE >> >> >> >> is busted because IRIW won't work. >> > >> > That is my thinking... but according to >> > >> > http://portal.acm.org/citation.cfm?id=1926394 >> > >> > the "Incorrect implementation" above is actually correct (probably >> > because according to them, MFENCE has the same semantics as PPC's >> > hwsync). >> >> That paper also says: >> >> "Sequentially consistent atomics The proposal above includes >> two implementations of sequentially consistent atomic reads and >> writes; one with the x86 locked instructions, and the other with >> fence instructions on both the reads and writes. However, we can >> prove that it suffices either to place an mfence before every sc read, >> or after every sc write, but that it is not necessary to do both. In >> practice, placing the fence after the sc writes is expected to yield >> higher performance." >> >> i.e. they think that >> >> Load SC: MOV >> Store SC: MOV, MFENCE >> >> is a valid implementation. > > They are talking about X86-TSO (not actual X86), which is equivalent to > SPARC-TSO (with #StoreLoad spelled as MFENCE), Their X86-TSO paper says that it tries to model actual X86 cpus, and tries to be consistent with the documented semantics, but favouring actual CPU behaviour over the specs. Anyway, it was you that cited this paper; if you don't think it is relevant then drop it, and focus purely on the published Intel/AMD specs. > see > > http://www.decadent.org.uk/pipermail/cpp-threads/2008-December/001947.html That is a SPARC implementation; I see no relevance here other than your claim that x86-TSO is equivalent to SPARC-TSO (the x86-TSO paper describes it as "broadly similar"). > (obviously, it was meant that two consecutive #StoreLoad/MFENCE > barriers, like in "store x, load y" both seq_cst, ought to be reduced to > just one by the compiler.) Yes, that part is "obvious". Anthony -- Author of C++ Concurrency in Action http://www.stdthread.co.uk/book/ just::thread C++0x thread library http://www.stdthread.co.uk Just Software Solutions Ltd http://www.justsoftwaresolutions.co.uk 15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976
[toc] | [prev] | [next] | [standalone]
| From | Alexander Terekhov <terekhov@web.de> |
|---|---|
| Date | 2011-06-20 15:39 +0200 |
| Message-ID | <4DFF4D79.767E8F71@web.de> |
| In reply to | #332 |
Anthony Williams wrote: [...] > >> "Sequentially consistent atomics The proposal above includes > >> two implementations of sequentially consistent atomic reads and > >> writes; one with the x86 locked instructions, and the other with > >> fence instructions on both the reads and writes. However, we can > >> prove that it suffices either to place an mfence before every sc read, > >> or after every sc write, but that it is not necessary to do both. In > >> practice, placing the fence after the sc writes is expected to yield > >> higher performance." > >> > >> i.e. they think that > >> > >> Load SC: MOV > >> Store SC: MOV, MFENCE > >> > >> is a valid implementation. > > > > They are talking about X86-TSO (not actual X86), which is equivalent to > > SPARC-TSO (with #StoreLoad spelled as MFENCE), > > Their X86-TSO paper says that it tries to model actual X86 cpus, and > tries to be consistent with the documented semantics, but favouring > actual CPU behaviour over the specs. > > Anyway, it was you that cited this paper; if you don't think it is > relevant then drop it, and focus purely on the published Intel/AMD specs. It was meant to show that mfence/load/mfence has more fencing than needed. > > > see > > > > http://www.decadent.org.uk/pipermail/cpp-threads/2008-December/001947.html > > That is a SPARC implementation; I see no relevance here other than your The relevance here is that for TSO, implementation with Load: MOV, Store: MOV, MFENCE is SC. > claim that x86-TSO is equivalent to SPARC-TSO (the x86-TSO paper > describes it as "broadly similar"). > > > (obviously, it was meant that two consecutive #StoreLoad/MFENCE > > barriers, like in "store x, load y" both seq_cst, ought to be reduced to > > just one by the compiler.) > > Yes, that part is "obvious". regards, alexander.
[toc] | [prev] | [next] | [standalone]
| From | Alexander Terekhov <terekhov@web.de> |
|---|---|
| Date | 2011-06-22 13:24 +0200 |
| Message-ID | <4E01D0D9.5DF5C281@web.de> |
| In reply to | #332 |
Anthony Williams wrote: [...] > >> > http://portal.acm.org/citation.cfm?id=1926394 > >> > > >> > the "Incorrect implementation" above is actually correct (probably > >> > because according to them, MFENCE has the same semantics as PPC's > >> > hwsync). > >> > >> That paper also says: > >> > >> "Sequentially consistent atomics The proposal above includes > >> two implementations of sequentially consistent atomic reads and > >> writes; one with the x86 locked instructions, and the other with > >> fence instructions on both the reads and writes. However, we can > >> prove that it suffices either to place an mfence before every sc read, > >> or after every sc write, but that it is not necessary to do both. In > >> practice, placing the fence after the sc writes is expected to yield > >> higher performance." > >> > >> i.e. they think that > >> > >> Load SC: MOV > >> Store SC: MOV, MFENCE > >> > >> is a valid implementation. > > > > They are talking about X86-TSO (not actual X86), which is equivalent to > > SPARC-TSO (with #StoreLoad spelled as MFENCE), > > Their X86-TSO paper says that it tries to model actual X86 cpus, and > tries to be consistent with the documented semantics, but favouring > actual CPU behaviour over the specs. I've just checked the recent Intel specs... and according to http://www.intel.com/Assets/PDF/manual/253668.pdf (May 2011) recent X86 hardware (P6 and More Recent Processor Families) *is* a step back to TSO, see "8.2.2 Memory Ordering in P6 and More Recent Processor Families . . . Any two stores are seen in a consistent order by processors other than those performing the stores" and "8.2.3.7 Stores Are Seen in a Consistent Order by Other Processors" (IRIW without any fencing or XCHG) More googling... http://blogs.oracle.com/dave/entry/x86_platform_memory_model_clarifications David Dice reported it back in 2009: "Intel has taken steps toward addressing some of the concerns about potential platform memory model relaxations that I identified in a previous blog entry. Specifically see section 7.2.3.7 of their latest Software Developer's Manual which now guarantees global store ordering." 2009's 7.2.3.7 is current 8.2.3.7 regards, alexander.
[toc] | [prev] | [next] | [standalone]
| From | Edek <edek.pienkowski@gmail.com> |
|---|---|
| Date | 2011-06-16 14:39 +0200 |
| Message-ID | <itcti5$ddh$1@node2.news.atman.pl> |
| In reply to | #288 |
On 06/16/2011 09:35 AM, Anthony Williams wrote: > Edek<edek.pienkowski@gmail.com> writes: > >> As a side note, I compiled all ops on x86_64, and atomic<int>::load >> is mfence/load/mfence even for relaxed. I'd need some time to analyse >> the thing from perspective of other ops implementations in all >> orderings, and this leads me to the not so subtle question: > > Ouch. That is a seriously over-cautious implementation. Atomics should > not need any fences on x86_64 unless you actually write > atomic_thread_fence(memory_order_seq_cst) > > See my blog entry for the required operations: > > http://www.justsoftwaresolutions.co.uk/threading/intel-memory-ordering-and-c++-memory-model.html > > The only one that is not a plain MOV is a seq_cst store, which is an > XCHG. > > Anthony From Joshua Maurice: >> PS. >> > As a side note, I compiled all ops on x86_64, and atomic<int>::load >> > is mfence/load/mfence even for relaxed. > This is very wrong. At least, very counter to intent. What > implementation of C++0x threading are you using? Maybe it's a first > attempt implementation, and they're going to "fix" it later? > Answering this: it is certainly possible that this is a 'quick-and-dirty' implementation. I wouldn't care now, given the status is experimental, if it gives worse performance [1]. I am not fit to argue, but maybe there are technical details why currently in this compiler it is necessary [3]. I do care whether it is correct, and correct me if I'm wrong, there is nothing wrong with stricter ordering than asked for [2], and looser language lawyering done by the compiler at the moment. Edek [1] Performance: In all cases? In some cases, and not in others? [2] Unless someone tries to say 'I had a proof: my algorithm did not fail on compilers X and Y on platforms A,B,C. My proof was wrong, because the compiler implemented a more strict ordering, and this caused me to think my algorithm was right when it was not' [3] what comes to my mind: missing alignment requirements, or something of this kind, in the current state of the compiler.
[toc] | [prev] | [next] | [standalone]
| From | Anthony Williams <anthony.ajw@gmail.com> |
|---|---|
| Date | 2011-06-16 13:55 +0100 |
| Message-ID | <87sjra9brm.fsf@justsoftwaresolutions.co.uk> |
| In reply to | #296 |
Edek <edek.pienkowski@gmail.com> writes: > I do care whether it is correct, and correct me if I'm wrong, there is > nothing wrong with stricter ordering than asked for [2], and looser > language lawyering done by the compiler at the moment. Sticking additional fences in will not make the implementation incorrect, just slower. Anthony -- Author of C++ Concurrency in Action http://www.stdthread.co.uk/book/ just::thread C++0x thread library http://www.stdthread.co.uk Just Software Solutions Ltd http://www.justsoftwaresolutions.co.uk 15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976
[toc] | [prev] | [next] | [standalone]
| From | Alexander Terekhov <terekhov@web.de> |
|---|---|
| Date | 2011-06-16 12:03 +0200 |
| Message-ID | <4DF9D4EB.81CDF399@web.de> |
| In reply to | #284 |
Edek wrote: [...] > As a side note, I compiled all ops on x86_64, and atomic<int>::load > is mfence/load/mfence even for relaxed. I'd need some time to analyse > the thing from perspective of other ops implementations in all > orderings, and this leads me to the not so subtle question: > > I understand people _should definitely_ use the default. > I assume the goal, or the official word for it is 'rationale', was > to let people 'who understand' write code that would be both portable > and more efficient than the default. I am somehow beginning to doubt > both my capabilities and whether this will be at all possible - I mean > the efficiency, not portability (the latter can be simply done right). > Though maybe the bottom line is that at least the precise implementation > will have at least a couple of fences less than the default, at the > price of - I think no one argues about that - complexity. Try http://www.decadent.org.uk/pipermail/cpp-threads/2008-December/001933.html (Brief tentative example x86 Implementation for C/C++ Memory Model) and http://portal.acm.org/citation.cfm?id=1926394 (Mathematizing C++ concurrency) regards, alexander.
[toc] | [prev] | [next] | [standalone]
| From | Edek <edek.pienkowski@gmail.com> |
|---|---|
| Date | 2011-07-10 19:10 +0200 |
| Message-ID | <ivcmbm$ajq$1@node2.news.atman.pl> |
| In reply to | #289 |
On 06/16/2011 12:03 PM, Alexander Terekhov wrote: > > Edek wrote: > [...] >> As a side note, I compiled all ops on x86_64, and atomic<int>::load >> is mfence/load/mfence even for relaxed. I'd need some time to analyse >> the thing from perspective of other ops implementations in all >> orderings, and this leads me to the not so subtle question: >> >> I understand people _should definitely_ use the default. >> I assume the goal, or the official word for it is 'rationale', was >> to let people 'who understand' write code that would be both portable >> and more efficient than the default. I am somehow beginning to doubt >> both my capabilities and whether this will be at all possible - I mean >> the efficiency, not portability (the latter can be simply done right). >> Though maybe the bottom line is that at least the precise implementation >> will have at least a couple of fences less than the default, at the >> price of - I think no one argues about that - complexity. > > Try > > http://www.decadent.org.uk/pipermail/cpp-threads/2008-December/001933.html > (Brief tentative example x86 Implementation for C/C++ Memory Model) > > and > > http://portal.acm.org/citation.cfm?id=1926394 > (Mathematizing C++ concurrency) > > regards, > alexander. I wanted to say something after I digest them, but that seems to be a future task. So: thanks. It is a pity I cannot follow everything interesting. I have read those, but I need to dig deeper sometime later. Edek
[toc] | [prev] | [next] | [standalone]
| From | Joshua Maurice <joshuamaurice@gmail.com> |
|---|---|
| Date | 2011-06-13 16:00 -0700 |
| Message-ID | <ab15b741-0150-4bc9-b903-f215ce50e1fc@e17g2000prj.googlegroups.com> |
| In reply to | #269 |
On Jun 13, 9:40 am, Masakuni Oishi <yam...@bsdhouse.org> wrote:
> Hi,
>
> I have some questions about C++0x memory model.
>
> /*** code 1 ***/
> // Initially
> atomic<int> x(0), y(0);
>
> // Thread 1:
> y.store(1, memory_order_release);
> atomic_thread_fence(memory_order_seq_cst);
> r1 = x.load(memory_order_acquire);
>
> // Thread 2:
> x.store(1, memory_order_release);
>
> // Thread 3:
> r2 = x.load(memory_order_acquire);
> atomic_thread_fence(memory_order_seq_cst);
> r3 = y.load(memory_order_acquire);
> /***************/
I don't claim to be correct or knowledgeable, but let me take a crack
at this. Please double check my reasoning.
/*** code 1 ***/
// Initially
atomic<int> x(0), y(0);
// Thread 1:
y.store(1, memory_order_release);
atomic_thread_fence(memory_order_seq_cst); //fence 1
r1 = x.load(memory_order_acquire);
// Thread 2:
x.store(1, memory_order_release);
// Thread 3:
r2 = x.load(memory_order_acquire);
atomic_thread_fence(memory_order_seq_cst); //fence 2
r3 = y.load(memory_order_acquire);
So,
>In the above code, is r1 == 0 && r2 == 1 && r3 == 0 possible?
Let us see.
Let's try a proof by contradiction. Let's assume r1 == 0 && r2 == 1 &&
r3 == 0 as end conditions is possible.
Case 1 - fence 1 happens-before fence 2.
Thus "y.store(1, memory_order_release);" happens-before "r3 =
y.load(memory_order_acquire);". But then r3 == 1, which contradicts
our assumption, so false.
Case 2 - fence 2 happens-before fence 1.
Thus "r2 = x.load(memory_order_acquire);" happens-before "r1 =
x.load(memory_order_acquire);".
To get r1 == 0 and r2 == 1, the modification order of x needs to be:
r1 = x.load(memory_order_acquire);
x.store(1, memory_order_release);
r2 = x.load(memory_order_acquire);
The required modification order of x is inconsistent with the happens-
before relationship, which is disallowed. Thus false.
End cases.
We got false on both cases, thus we can complete our proof by
contradiction, and thus one of our assumptions must be false. Thus our
only assumption, r1 == 0 && r2 == 1 && r3 == 0 as possible end
conditions, must be false.
Please, someone double check my reasoning. I hate (yet love) thinking
about this stuff. So easy to make a little mistake.
----
Also, note the following.
Note that thread 2 has only a single memory action. It is an atomic
write of memory_order_release. There are no other memory actions in
that thread, so the write might as well be memory_order_relaxed. (At
least, maybe. There's something nagging me about release sequences,
but I don't think that's relevant in this example.)
Now, we have two reads of x. As there are no writes to x besides
memory_order_relaxed writes, the memory_order_acquire reads of x are
equivalent to memory_order_relaxed.
The rule of I use for acquire and release semantics is: "If the
acquire sees the release, then all reads after the acquire must see
all writes before the release." There are two operations on y, one
read acquire, one write release. There are no reads after the read
acquire, and there are no writes before the write release, so both of
these memory_order types are equivalent to memory_order_relaxed. (With
the same qualification about maybe - release sequences maybe
withstanding.)
Thus, your acquires and releases are red herrings. They don't do
anything to change the nature of your little program.
[toc] | [prev] | [next] | [standalone]
| From | Joshua Maurice <joshuamaurice@gmail.com> |
|---|---|
| Date | 2011-06-13 23:31 -0700 |
| Message-ID | <a7538b28-ec77-489e-8923-303132509c11@18g2000prd.googlegroups.com> |
| In reply to | #272 |
On Jun 13, 4:00 pm, Joshua Maurice <joshuamaur...@gmail.com> wrote:
> On Jun 13, 9:40 am, Masakuni Oishi <yam...@bsdhouse.org> wrote:
>
> > Hi,
>
> > I have some questions about C++0x memory model.
>
> > /*** code 1 ***/
> > // Initially
> > atomic<int> x(0), y(0);
>
> > // Thread 1:
> > y.store(1, memory_order_release);
> > atomic_thread_fence(memory_order_seq_cst);
> > r1 = x.load(memory_order_acquire);
>
> > // Thread 2:
> > x.store(1, memory_order_release);
>
> > // Thread 3:
> > r2 = x.load(memory_order_acquire);
> > atomic_thread_fence(memory_order_seq_cst);
> > r3 = y.load(memory_order_acquire);
> > /***************/
>
> I don't claim to be correct or knowledgeable, but let me take a crack
> at this. Please double check my reasoning.
>
> /*** code 1 ***/
> // Initially
> atomic<int> x(0), y(0);
>
> // Thread 1:
> y.store(1, memory_order_release);
> atomic_thread_fence(memory_order_seq_cst); //fence 1
> r1 = x.load(memory_order_acquire);
>
> // Thread 2:
> x.store(1, memory_order_release);
>
> // Thread 3:
> r2 = x.load(memory_order_acquire);
> atomic_thread_fence(memory_order_seq_cst); //fence 2
> r3 = y.load(memory_order_acquire);
>
> So,>In the above code, is r1 == 0 && r2 == 1 && r3 == 0 possible?
>
> Let us see.
>
> Let's try a proof by contradiction. Let's assume r1 == 0 && r2 == 1 &&
> r3 == 0 as end conditions is possible.
>
> Case 1 - fence 1 happens-before fence 2.
> Thus "y.store(1, memory_order_release);" happens-before "r3 =
> y.load(memory_order_acquire);". But then r3 == 1, which contradicts
> our assumption, so false.
>
> Case 2 - fence 2 happens-before fence 1.
> Thus "r2 = x.load(memory_order_acquire);" happens-before "r1 =
> x.load(memory_order_acquire);".
>
> To get r1 == 0 and r2 == 1, the modification order of x needs to be:
> r1 = x.load(memory_order_acquire);
> x.store(1, memory_order_release);
> r2 = x.load(memory_order_acquire);
>
> The required modification order of x is inconsistent with the happens-
> before relationship, which is disallowed. Thus false.
>
> End cases.
>
> We got false on both cases, thus we can complete our proof by
> contradiction, and thus one of our assumptions must be false. Thus our
> only assumption, r1 == 0 && r2 == 1 && r3 == 0 as possible end
> conditions, must be false.
>
> Please, someone double check my reasoning. I hate (yet love) thinking
> about this stuff. So easy to make a little mistake.
>
> ----
>
> Also, note the following.
>
> Note that thread 2 has only a single memory action. It is an atomic
> write of memory_order_release. There are no other memory actions in
> that thread, so the write might as well be memory_order_relaxed. (At
> least, maybe. There's something nagging me about release sequences,
> but I don't think that's relevant in this example.)
>
> Now, we have two reads of x. As there are no writes to x besides
> memory_order_relaxed writes, the memory_order_acquire reads of x are
> equivalent to memory_order_relaxed.
>
> The rule of I use for acquire and release semantics is: "If the
> acquire sees the release, then all reads after the acquire must see
> all writes before the release." There are two operations on y, one
> read acquire, one write release. There are no reads after the read
> acquire, and there are no writes before the write release, so both of
> these memory_order types are equivalent to memory_order_relaxed. (With
> the same qualification about maybe - release sequences maybe
> withstanding.)
>
> Thus, your acquires and releases are red herrings. They don't do
> anything to change the nature of your little program.
Actually, I'm wrong. Well, I had the right conclusion I think, but
entirely wrong reasoning. (I still think that I was right that all of
loads and stores are equivalent to memory_order_relaxed, but the rest
of my reasoning is wrong.) Allow me to try to correct myself. (For
some weird reason, I wrote assuming that reads are part of the
modification order. Silly me - that's wrong. Brain fart.)
/*** code 1 ***/
// Initially
atomic<int> x(0), y(0);
// Thread 1:
y.store(1, memory_order_release);
atomic_thread_fence(memory_order_seq_cst); //fence 1
r1 = x.load(memory_order_acquire);
// Thread 2:
x.store(1, memory_order_release);
// Thread 3:
r2 = x.load(memory_order_acquire);
atomic_thread_fence(memory_order_seq_cst); //fence 2
r3 = y.load(memory_order_acquire);
/* **** end code */
The modification order for x is:
atomic<int> x(0);
x.store(1, memory_order_release);
Case 1- fence 1 comes before fence 2.
Thus
y.store(1, memory_order_release);
happens-before
r3 = y.load(memory_order_acquire);
Thus r3 == 1.
Case 2- fence 2 happens-before fence 1.
Thus
r2 = x.load(memory_order_relaxed);
happens-before
r1 = x.load(memory_order_relaxed);
Consider C++0x, n3242, 1.10 / 16, aka read-read coherence. In my
hopefully correct translation, it says:
[]
For atomic reads A and B on M, if A happens-before B, then A sees the
same write as B, or the write which A sees must come before the write
which B sees in the modification order of M.
[/]
Let's suppose, for a moment, that r1 == 0 and r2 == 1.
We know that the atomic read r2 happens-before the atomic read r1.
We know that the read r2 sees the write x=1.
We know that the read r1 sees the write x=0.
We can thus conclude from 1.10 / 16 that the write x=1 is the write
x=0 (nope), or the write x=1 comes before x=0 in the modification
order of x (also nope).
Thus we know that r1 == 0 and r2 == 1 is impossible ala proof by
contradiction.
End cases
Thus we know
(r3 == 1) OR NOT (r1 == 0 AND r2 == 1)
NOT (r3 == 0) OR NOT (r1 == 0 AND r2 == 1)
NOT (r3 == 0 AND r1 == 0 AND r2 == 1)
NOT (r1 == 0 AND r2 == 1 AND r3 == 0)
I am so feeling totally not confident about all of this. I post this
merely as my next best guess. Of course I feel better about it, or I
wouldn't be posting it, but damn this is hard to reason about. I have
a lot to learn.
[toc] | [prev] | [next] | [standalone]
| From | Masakuni Oishi <yamasa@bsdhouse.org> |
|---|---|
| Date | 2011-06-14 08:32 -0700 |
| Message-ID | <e3b8348f-109e-4efd-8419-fc574a07d7b4@z15g2000prn.googlegroups.com> |
| In reply to | #273 |
Joshua Maurice <joshuamaur...@gmail.com> wrote: [snip] > Case 1- fence 1 comes before fence 2. > Thus > y.store(1, memory_order_release); > happens-before > r3 = y.load(memory_order_acquire); > Thus r3 == 1. > > Case 2- fence 2 happens-before fence 1. > Thus > r2 = x.load(memory_order_relaxed); > happens-before > r1 = x.load(memory_order_relaxed); Total order S described in FDIS 29.3 is not equivalent to happens- before. "If fence 2 happens before fence 1, then fence 2 precedes fence 1 in S" is always satisfied. But the conversion -- "If fence 2 precedes fence 1 in S, then fence 2 happens before fence 1" -- is not always satisfied. Since S is a total order, either "fence 2 precedes fence 1 in S" or "fence 1 precedes fence 2 in S" must be true. But happens-before relation is not a total order. -- masakuni
[toc] | [prev] | [next] | [standalone]
| From | Anthony Williams <anthony.ajw@gmail.com> |
|---|---|
| Date | 2011-06-14 23:05 +0100 |
| Message-ID | <87tybsm5kq.fsf@justsoftwaresolutions.co.uk> |
| In reply to | #269 |
Masakuni Oishi <yamasa@bsdhouse.org> writes: > /*** code 1 ***/ > // Initially > atomic<int> x(0), y(0); > > // Thread 1: > y.store(1, memory_order_release); > atomic_thread_fence(memory_order_seq_cst); > r1 = x.load(memory_order_acquire); > > // Thread 2: > x.store(1, memory_order_release); > > // Thread 3: > r2 = x.load(memory_order_acquire); > atomic_thread_fence(memory_order_seq_cst); > r3 = y.load(memory_order_acquire); > /***************/ > > In the above code, is r1 == 0 && r2 == 1 && r3 == 0 possible? > I think it should be prohibited, but I couldn't make sure that > from the C++0x FDIS. Premise 1: r3 == 0. Since the only store to y is the store of 1 by thread 1, r3 == 0 implies that the load from y on thread 3 is reading the initial value of y. 29.3p6 of N3290 says: "For atomic operations A and B on an atomic object M, where A modifies M and B takes its value, if there are memory_order_seq_cst fences X and Y such that A is sequenced before X, Y is sequenced before B, and X precedes Y in S, then B observes either the effects of A or a later modification of M in its modification order." If the fence in thread 1 precedes the fence in thread 3 in S, then the read at r3 must therefore see the value written by the store in thread 1. Consequently, the fence in thread 3 must precede the fence in thread 1 in S. Premise 2: r2 == 1. The load of x in thread 3 reading 1 implies it has read the value of the store to x from thread 2. We already know that the fence in thread 3 precedes the fence in thread 1 in S. 29.3p7 of N3290 says: "For atomic operations A and B on an atomic object M, if there are memory_order_seq_cst fences X and Y such that A is sequenced before X, Y is sequenced before B, and X precedes Y in S, then B occurs later than A in the modification order of M." In our case, the fence in thread 3 occurs before the fence in thread 1 in S. The fence in thread 3 is thus X, the fence in thread 1 Y, the read from x in thread 3 is A and the read from x in thread 1 is B. Thus the read of x in thread 1 must occur later in the modification order of x than the read in thread 3. Since the read in thread 3 is of the last store to x (1), the read in thread 1 must also read that value, and r1 == 1. Therefore r1==0, r2 == 1 and r3 == 0 is not possible. > So, my questions are: > For code 1, is r1 == 0 && r2 == 1 && r3 == 0 allowed in the C++0x > FDIS? No. Anthony -- Author of C++ Concurrency in Action http://www.stdthread.co.uk/book/ just::thread C++0x thread library http://www.stdthread.co.uk Just Software Solutions Ltd http://www.justsoftwaresolutions.co.uk 15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976
[toc] | [prev] | [next] | [standalone]
| From | Joshua Maurice <joshuamaurice@gmail.com> |
|---|---|
| Date | 2011-06-14 16:44 -0700 |
| Message-ID | <35ec803e-2871-41ce-97ea-8b615b29050f@r33g2000prh.googlegroups.com> |
| In reply to | #277 |
On Jun 14, 3:05 pm, Anthony Williams <anthony....@gmail.com> wrote: > Masakuni Oishi <yam...@bsdhouse.org> writes: > > /*** code 1 ***/ > > // Initially > > atomic<int> x(0), y(0); > > > // Thread 1: > > y.store(1, memory_order_release); > > atomic_thread_fence(memory_order_seq_cst); > > r1 = x.load(memory_order_acquire); > > > // Thread 2: > > x.store(1, memory_order_release); > > > // Thread 3: > > r2 = x.load(memory_order_acquire); > > atomic_thread_fence(memory_order_seq_cst); > > r3 = y.load(memory_order_acquire); > > /***************/ > > > In the above code, is r1 == 0 && r2 == 1 && r3 == 0 possible? > > I think it should be prohibited, but I couldn't make sure that > > from the C++0x FDIS. > > Premise 1: r3 == 0. > > Since the only store to y is the store of 1 by thread 1, r3 == 0 implies > that the load from y on thread 3 is reading the initial value of y. > > 29.3p6 of N3290 says: > > "For atomic operations A and B on an atomic object M, where A modifies M > and B takes its value, if there are memory_order_seq_cst fences X and Y > such that A is sequenced before X, Y is sequenced before B, and X > precedes Y in S, then B observes either the effects of A or a later > modification of M in its modification order." > > If the fence in thread 1 precedes the fence in thread 3 in S, then the > read at r3 must therefore see the value written by the store in thread > 1. Consequently, the fence in thread 3 must precede the fence in thread > 1 in S. > > Premise 2: r2 == 1. > > The load of x in thread 3 reading 1 implies it has read the value of the > store to x from thread 2. I agree with your proof up to this point. > We already know that the fence in thread 3 precedes the fence in thread > 1 in S. > > 29.3p7 of N3290 says: > > "For atomic operations A and B on an atomic object M, if there are > memory_order_seq_cst fences X and Y such that A is sequenced before X, Y > is sequenced before B, and X precedes Y in S, then B occurs later than A > in the modification order of M." > > In our case, the fence in thread 3 occurs before the fence in thread 1 > in S. The fence in thread 3 is thus X, the fence in thread 1 Y, the read > from x in thread 3 is A and the read from x in thread 1 is B. > > Thus the read of x in thread 1 must occur later in the modification > order of x than the read in thread 3. Since the read in thread 3 is of > the last store to x (1), the read in thread 1 must also read that value, > and r1 == 1. I disagree with this. I think you made the same mistake which I made in my first post of this thread. Only /modifications/ appear in a modification order. Reads do not appear in the modification order. At least, this is the simple reading of 1.10 / 7, and its name is "modification order", not "access order". Also note that the definition of a "release sequence" in 1.10 / 8 does not make sense if reads may appear in modification orders. Also note that the definition of "visible sequence of side effects" in 1.10 / 14 does not make sense if reads may appear in modification orders. (Note that there's some ambiguity w.r.t. volatile atomic objects, as volatile reads do count as side effects, but non-volatile reads AFAIK are not side effects.) As I'm beginning to understand this, there is a typo in 29.3 / 7. The exact text is: [] For atomic operations A and B on an atomic object M, if there are memory_order_seq_cst fences X and Y such that A is sequenced before X, Y is sequenced before B, and X precedes Y in S, then B occurs later than A in the modification order of M. [/] I think it's meant to read: [] For atomic **write (and atomic read-modify-write operations)** A and B on an atomic object M, if there are memory_order_seq_cst fences X and Y such that A is sequenced before X, Y is sequenced before B, and X precedes Y in S, then B occurs later than A in the modification order of M. [/] When you said "the read from x in thread 3 is A and the read from x in thread 1 is B.", that is where you went wrong. You cannot apply "29.3 / 7" to atomic reads A and B on an atomic object M, only atomic writes (and atomic read-modify-write operations). I'm still dealing with the implication that A precedes B in the total order S of seq_cst operations does not imply that A happens-before B nor A inter-thread happens before B nor A synchronizes-with B - and that's irritating and slightly surprising. At least, I haven't yet found a rule which states that, and I've looked decently hard, and I've even found a note saying as much in 29.3 / 8. I'm still looking at the standard and the code of the OP, if only for my own sake. I'm leaning towards Masakuni Oishi's interpretation at the moment. Have I mentioned non-seq_cst code is a bitch to reason about? As always, please correct me when I'm wrong.
[toc] | [prev] | [next] | [standalone]
| From | Anthony Williams <anthony.ajw@gmail.com> |
|---|---|
| Date | 2011-06-15 08:34 +0100 |
| Message-ID | <87hb7r5z03.fsf@justsoftwaresolutions.co.uk> |
| In reply to | #278 |
Joshua Maurice <joshuamaurice@gmail.com> writes: >> We already know that the fence in thread 3 precedes the fence in thread >> 1 in S. >> >> 29.3p7 of N3290 says: >> >> "For atomic operations A and B on an atomic object M, if there are >> memory_order_seq_cst fences X and Y such that A is sequenced before X, Y >> is sequenced before B, and X precedes Y in S, then B occurs later than A >> in the modification order of M." >> >> In our case, the fence in thread 3 occurs before the fence in thread 1 >> in S. The fence in thread 3 is thus X, the fence in thread 1 Y, the read >> from x in thread 3 is A and the read from x in thread 1 is B. >> >> Thus the read of x in thread 1 must occur later in the modification >> order of x than the read in thread 3. Since the read in thread 3 is of >> the last store to x (1), the read in thread 1 must also read that value, >> and r1 == 1. > > I disagree with this. I think you made the same mistake which I made > in my first post of this thread. Only /modifications/ appear in a > modification order. Reads do not appear in the modification order. At > least, this is the simple reading of 1.10 / 7, and its name is > "modification order", not "access order". Also note that the > definition of a "release sequence" in 1.10 / 8 does not make sense if > reads may appear in modification orders. Also note that the definition > of "visible sequence of side effects" in 1.10 / 14 does not make sense > if reads may appear in modification orders. (Note that there's some > ambiguity w.r.t. volatile atomic objects, as volatile reads do count > as side effects, but non-volatile reads AFAIK are not side effects.) I used "modification order" here because that is what is used in 29.3p7. I realise that this has caused confusion because reads are indeed not included in the modification order. > As I'm beginning to understand this, there is a typo in 29.3 / 7. Agreed. > I think it's meant to read: > [] > For atomic **write (and atomic read-modify-write operations)** A and B > on an atomic object M, if there are memory_order_seq_cst fences X and > Y such that A is sequenced before X, Y is sequenced before B, and X > precedes Y in S, then B occurs later than A in the modification order > of M. > [/] When we drafted this words, I think we meant "operation". It is the reference to "modification order" that is the typo. What is meant is that if A is a write and B is a read then B must read the value written by A, or something later in the modification order; if A is a write and B is a write then B must be later than A in the MO; if A is a read and B is a write then A must read a value prior to B in the MO, and if A is a read and B is a read then B must read the same value as A or a value later in the MO. It is based on this understanding that I applied my reasoning. It is of course possible that I have misremembered the discussions of the concurrency working group. After rereading this section of the standard several times, I'm no longer sure. I'll have to check my notes. > I'm still dealing with the implication that A precedes B in the total > order S of seq_cst operations does not imply that A happens-before B > nor A inter-thread happens before B nor A synchronizes-with B - and > that's irritating and slightly surprising. At least, I haven't yet > found a rule which states that, and I've looked decently hard, and > I've even found a note saying as much in 29.3 / 8. You're right there. Note that 29.3p4-7 explicitly apply to **fences**, so plain memory_order_seq_cst operations do not impose any ordering on other operations beyond what they would if they were acquire/release/acq_rel as appropriate. Anthony -- Author of C++ Concurrency in Action http://www.stdthread.co.uk/book/ just::thread C++0x thread library http://www.stdthread.co.uk Just Software Solutions Ltd http://www.justsoftwaresolutions.co.uk 15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976
[toc] | [prev] | [next] | [standalone]
| From | Masakuni Oishi <yamasa@bsdhouse.org> |
|---|---|
| Date | 2011-06-15 02:11 -0700 |
| Message-ID | <5cfd36a3-e799-4bcb-a5e7-436183619684@l14g2000pro.googlegroups.com> |
| In reply to | #279 |
On Jun15, Anthony Williams <anthony....@gmail.com> wrote: > if A is a write and B is a read then B must read the value written > by A, or something later in the modification order; if A is a write and > B is a write then B must be later than A in the MO; if A is a read and B > is a write then A must read a value prior to B in the MO, and if A is a > read and B is a read then B must read the same value as A or a value > later in the MO. I completely agree this sentences itself. But I'm not sure 29.3p7 means that. -- masakuni
[toc] | [prev] | [next] | [standalone]
| From | Joshua Maurice <joshuamaurice@gmail.com> |
|---|---|
| Date | 2011-06-15 15:58 -0700 |
| Message-ID | <1612cc19-5ac8-4aef-bc10-f26bc5a1c5d5@q14g2000prh.googlegroups.com> |
| In reply to | #279 |
On Jun 15, 12:34 am, Anthony Williams <anthony....@gmail.com> wrote: > Joshua Maurice <joshuamaur...@gmail.com> writes: > >> We already know that the fence in thread 3 precedes the fence in thread > >> 1 in S. > > >> 29.3p7 of N3290 says: > > >> "For atomic operations A and B on an atomic object M, if there are > >> memory_order_seq_cst fences X and Y such that A is sequenced before X, Y > >> is sequenced before B, and X precedes Y in S, then B occurs later than A > >> in the modification order of M." > > >> In our case, the fence in thread 3 occurs before the fence in thread 1 > >> in S. The fence in thread 3 is thus X, the fence in thread 1 Y, the read > >> from x in thread 3 is A and the read from x in thread 1 is B. > > >> Thus the read of x in thread 1 must occur later in the modification > >> order of x than the read in thread 3. Since the read in thread 3 is of > >> the last store to x (1), the read in thread 1 must also read that value, > >> and r1 == 1. > > > I disagree with this. I think you made the same mistake which I made > > in my first post of this thread. Only /modifications/ appear in a > > modification order. Reads do not appear in the modification order. At > > least, this is the simple reading of 1.10 / 7, and its name is > > "modification order", not "access order". Also note that the > > definition of a "release sequence" in 1.10 / 8 does not make sense if > > reads may appear in modification orders. Also note that the definition > > of "visible sequence of side effects" in 1.10 / 14 does not make sense > > if reads may appear in modification orders. (Note that there's some > > ambiguity w.r.t. volatile atomic objects, as volatile reads do count > > as side effects, but non-volatile reads AFAIK are not side effects.) > > I used "modification order" here because that is what is used in > 29.3p7. I realise that this has caused confusion because reads are > indeed not included in the modification order. > > > As I'm beginning to understand this, there is a typo in 29.3 / 7. > > Agreed. > > > I think it's meant to read: > > [] > > For atomic **write (and atomic read-modify-write operations)** A and B > > on an atomic object M, if there are memory_order_seq_cst fences X and > > Y such that A is sequenced before X, Y is sequenced before B, and X > > precedes Y in S, then B occurs later than A in the modification order > > of M. > > [/] > > When we drafted this words, I think we meant "operation". It is the > reference to "modification order" that is the typo. What is meant is > that if A is a write and B is a read then B must read the value written > by A, or something later in the modification order; if A is a write and > B is a write then B must be later than A in the MO; if A is a read and B > is a write then A must read a value prior to B in the MO, and if A is a > read and B is a read then B must read the same value as A or a value > later in the MO. > > It is based on this understanding that I applied my reasoning. It is > of course possible that I have misremembered the discussions of the > concurrency working group. > > After rereading this section of the standard several times, I'm no > longer sure. I'll have to check my notes. > > > I'm still dealing with the implication that A precedes B in the total > > order S of seq_cst operations does not imply that A happens-before B > > nor A inter-thread happens before B nor A synchronizes-with B - and > > that's irritating and slightly surprising. At least, I haven't yet > > found a rule which states that, and I've looked decently hard, and > > I've even found a note saying as much in 29.3 / 8. > > You're right there. Note that 29.3p4-7 explicitly apply to **fences**, > so plain memory_order_seq_cst operations do not impose any ordering on > other operations beyond what they would if they were > acquire/release/acq_rel as appropriate. Somehow, I missed this post earlier. I just read this now. Thank you for this cool discussion. If you could figure this out, it would be most welcome. I'm about to post something to comp.lang.c++ now, and I'll include a reference to this possible interpretation and this thread.
[toc] | [prev] | [next] | [standalone]
| From | Anthony Williams <anthony.ajw@gmail.com> |
|---|---|
| Date | 2011-06-16 08:26 +0100 |
| Message-ID | <87fwnafd9j.fsf@justsoftwaresolutions.co.uk> |
| In reply to | #279 |
Anthony Williams <anthony.ajw@gmail.com> writes: > Joshua Maurice <joshuamaurice@gmail.com> writes: > >>> 29.3p7 of N3290 says: >>> >>> "For atomic operations A and B on an atomic object M, if there are >>> memory_order_seq_cst fences X and Y such that A is sequenced before X, Y >>> is sequenced before B, and X precedes Y in S, then B occurs later than A >>> in the modification order of M." >>> >> I think it's meant to read: >> [] >> For atomic **write (and atomic read-modify-write operations)** A and B >> on an atomic object M, if there are memory_order_seq_cst fences X and >> Y such that A is sequenced before X, Y is sequenced before B, and X >> precedes Y in S, then B occurs later than A in the modification order >> of M. >> [/] > > When we drafted this words, I think we meant "operation". It is the > reference to "modification order" that is the typo. What is meant is > that if A is a write and B is a read then B must read the value written > by A, or something later in the modification order; if A is a write and > B is a write then B must be later than A in the MO; if A is a read and B > is a write then A must read a value prior to B in the MO, and if A is a > read and B is a read then B must read the same value as A or a value > later in the MO. > After rereading this section of the standard several times, I'm no > longer sure. I'll have to check my notes. I've checked my notes. My recollection was wrong. We *discussed* requiring seq_cst fences to order loads like this, but decided to explicitly limit the orderings to writes. The approved wording said "where A and B modify M", but this somehow got lost. In particular, it was felt that requiring this would add complexity to the IA-64 implementation of fences, and potentially require that relaxed operations on that architecture would also have to be more expensive, thus requiring people to pay for features they didn't need. Anthony -- Author of C++ Concurrency in Action http://www.stdthread.co.uk/book/ just::thread C++0x thread library http://www.stdthread.co.uk Just Software Solutions Ltd http://www.justsoftwaresolutions.co.uk 15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976
[toc] | [prev] | [next] | [standalone]
Page 3 of 5 — ← Prev page 1 2 [3] 4 5 Next page →
Back to top | Article view | comp.programming.threads
csiph-web