<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Hi Jay,<div><br></div><div>Please note that we already have support in the compiler (middle and back ends) for these primitives. They manifest as calls to the functions defined as intrinsics to gcc (e.g., synch_synchronize) so they can be inlined where appropriate. On platforms that don't support the intrinsics (such as non-gcc backends) all we need to do is to implement the corresponding functions in C (much as you have started to do with the atomic.c). What I propose is that we add a MEMBAR builtin to the Modula-3 compiler (to add to the existing CAS and CASP builtins that I have already implemented) which will bottom out as calls to these intrinsic functions. My only concern is that we should have better support for the other forms of primitive (other than CAS) that are widely available, notably load-linked/store-conditional. These are readily implemented using CAS, but not the other way around (load-linked => no-op, store-conditional => CAS). Unfortunately, LL/SC are not implemented by the gcc intrinsics.</div><div><br></div><div>On the other hand, I still question your motivation for avoiding the global lock on the slots table. Most of these are for simple lookups (as opposed to insertions), which have very short critical sections:</div><div><br></div><div> lock slots</div><div> load slots[me.slot]</div><div> unock slots</div><div><br></div><div>So, the chances of contention are *very* low. A lightly contended pthread_mutex will typically involve spinning at worst, so I doubt there will be much of any benefit to your proposal, at the cost of introducing target dependencies into the code. I am concerned that this is premature and non-portable optimization.</div><div><br></div><div>Nevertheless, I applaud considering use of non-blocking synchronization primtives in the threads implementations, which may ultimately have benefit to our implementation of Thread.Mutex and Thread.Condition (we can avoid inflating a pthread_mutex_t except when there is contention).</div><div><br></div><div>So, the upshot is that I think the approach you are taking needs revising, and you should think hard about whether what you are trying to do with ThreadWin32 will lead to real performance improvements at the cost of code clarity.</div><div><br><div> <span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><div><font class="Apple-style-span" color="#0000FF"><font class="Apple-style-span" face="Gill Sans"><span class="Apple-style-span" style="color: rgb(0, 0, 255); font-family: 'Gill Sans'; "><span class="Apple-style-span" style="color: rgb(0, 0, 255); font-family: 'Gill Sans'; ">Antony Hosking</span></span></font></font><font class="Apple-style-span" face="Gill Sans"><span class="Apple-style-span" style="font-family: 'Gill Sans'; "><span class="Apple-style-span" style="font-family: 'Gill Sans'; "><span class="Apple-converted-space"> </span>|<span class="Apple-converted-space"> </span></span></span><span class="Apple-style-span" style="font-family: 'Gill Sans'; "><span class="Apple-style-span" style="font-family: 'Gill Sans'; ">Associate Professor</span></span><span class="Apple-style-span" style="font-family: 'Gill Sans'; "><span class="Apple-style-span" style="font-family: 'Gill Sans'; "> | Computer Science | Purdue University</span></span></font></div><div><font class="Apple-style-span" face="GillSans-Light"><span class="Apple-style-span" style="font-family: GillSans-Light; ">305 N. University Street | West Lafayette | IN 47907 | USA</span></font></div><div><font class="Apple-style-span" color="#0000FF" face="Gill Sans"><span class="Apple-style-span" style="color: rgb(0, 0, 255); font-family: 'Gill Sans'; "><span class="Apple-style-span" style="color: rgb(0, 0, 255); font-family: 'Gill Sans'; ">Office</span></span></font><font class="Apple-style-span" face="GillSans-Light"><span class="Apple-style-span" style="font-family: GillSans-Light; "><span class="Apple-style-span" style="font-family: GillSans-Light; "> +1 765 494 6001 |<span class="Apple-converted-space"> </span></span></span></font><font class="Apple-style-span" color="#0000FF" face="Gill Sans"><span class="Apple-style-span" style="color: rgb(0, 0, 255); font-family: 'Gill Sans'; "><span class="Apple-style-span" style="color: rgb(0, 0, 255); font-family: 'Gill Sans'; ">Mobile</span></span></font><font class="Apple-style-span" face="GillSans-Light"><span class="Apple-style-span" style="font-family: GillSans-Light; "><span class="Apple-style-span" style="font-family: GillSans-Light; "><span class="Apple-converted-space"> </span>+1 765 427 5484</span></span></font></div><div><font class="Apple-style-span" face="GillSans-Light"><br class="khtml-block-placeholder"></font></div></span></span></span></span></span></span></span><br class="Apple-interchange-newline"></span></div></span></div></span><br class="Apple-interchange-newline"> </div><br><div><div>On 8 Nov 2009, at 23:23, Jay K wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div class="hmmessage" style="font-size: 10pt; font-family: Verdana; ">How about a per thread never contented pthread_mutex_t?<br>As a fallback.<br>And add what we can as we do the research for others?<br>Anything using gcc would probably be supported right away.<br>Win32 would be supported.<br>Leaving only SOLgnu for now but probably we can find out what to do there.<br> <br>Hm. a little bit of searching the web:<br> <br> <br><a href="http://gcc.gnu.org/onlinedocs/gcc/Atomic-Builtins.html">http://gcc.gnu.org/onlinedocs/gcc/Atomic-Builtins.html</a><br><a href="http://gee.cs.oswego.edu/dl/jmm/cookbook.html">http://gee.cs.oswego.edu/dl/jmm/cookbook.html</a><br><br>It looks like:<br> <br>#if defined(__sun)<br>#Include <atomic.h><br>void Atomic__MemoryBarrier(void)<br>{<br> membar_producer();<br> membar_consumer();<br>}<br><br>#elif defined(__GNUC__)<br><br>void Atomic__MemoryBarrier(void)<br>{<br> __sync_synchronize();<br>}<br><br>#elif defined(_WIN32)<br><br>void Atomic__MemoryBarrier(void)<br>{<br> MemoryBarrier();<br>}<br> <br>#else<br> <br>#error or consider uncontended pthread_mutex?<br> <br> <br>#endif<br><br>?<br> <br> - Jay<br><br> <br><hr id="stopSpelling">CC:<span class="Apple-converted-space"> </span><a href="mailto:m3devel@elegosoft.com">m3devel@elegosoft.com</a><br>From:<span class="Apple-converted-space"> </span><a href="mailto:hosking@cs.purdue.edu">hosking@cs.purdue.edu</a><br>To:<span class="Apple-converted-space"> </span><a href="mailto:jay.krell@cornell.edu">jay.krell@cornell.edu</a><br>Subject: Re: [M3devel] Self() locking slots almost unnecessary -- if only we had "MemoryBarrier".<br>Date: Sun, 8 Nov 2009 21:54:06 -0500<br><br><div><span class="ecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><div style="word-wrap: break-word; "><span class="ecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><div style="word-wrap: break-word; "><span class="ecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><span class="ecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><span class="ecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><span class="ecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><span class="ecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><span class="ecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><span class="ecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><span class="ecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><div><font class="ecxApple-style-span" color="#0000ff" face="'Gill Sans'"><span class="ecxApple-style-span" style="font-size: medium; ">It would be nice to use CAS and friends (load-linked/store-conditional) but they are not portable. It would require target-dependencies.</span></font></div></span></span></span></span></span></span></span></span></div></span></div></span></div><br><div><div>On 8 Nov 2009, at 19:44, Jay K wrote:</div><br class="ecxApple-interchange-newline"><blockquote><span class="ecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal medium/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><div class="ecxhmmessage" style="font-family: Verdana; font-size: 10pt; ">I don't know. I just look at all code overly critically..including for overly coarse grained locking (which includes some vs. none).<br>I guess the argument could be that the critical section -- the part of code that executes under the lock -- is very short, so it can't make much of a difference.<br> <br>Writing the global with an "InterlockedExchange" might be good.<br> <br>Maybe we should add this as a portably available interface?<br>"This" being MemoryBarrier and/or well, er, um, I guess you already did, the IA64 stuff, which is similar to the Win32 stuff.<br>I should update the NT/x86 backend for that stuff and then we can move on and use them.<br> <br> - Jay<br><br> <br><hr id="ecxstopSpelling">From:<span class="ecxApple-converted-space"> </span><a href="mailto:hosking@cs.purdue.edu">hosking@cs.purdue.edu</a><br>To:<span class="ecxApple-converted-space"> </span><a href="mailto:jay.krell@cornell.edu">jay.krell@cornell.edu</a><br>Date: Sun, 8 Nov 2009 19:39:00 -0500<br>CC:<span class="ecxApple-converted-space"> </span><a href="mailto:m3devel@elegosoft.com">m3devel@elegosoft.com</a><br>Subject: Re: [M3devel] Self() locking slots almost unnecessary -- if only we had "MemoryBarrier".<br><br><div><span class="ecxecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><div style="word-wrap: break-word; "><span class="ecxecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><div style="word-wrap: break-word; "><span class="ecxecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><span class="ecxecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><span class="ecxecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><span class="ecxecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><span class="ecxecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><span class="ecxecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><span class="ecxecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><span class="ecxecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><div><span class="ecxecxApple-style-span" style="font-size: medium; "><font class="ecxecxApple-style-span" color="#0000ff" face="'Gill Sans'">Not portably. Different memory models will behave differently. For safety we need the lock. But, seriously, how much contention will there be?</font></span></div></span></span></span></span></span></span></span></span></div></span></div></span></div><br><div><div>On 8 Nov 2009, at 19:35, Jay K wrote:</div><br class="ecxecxApple-interchange-newline"><blockquote><span class="ecxecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal medium/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><div class="ecxecxhmmessage" style="font-family: Verdana; font-size: 10pt; ">Self() doesn't have to lock slots AS LONG AS in AssignSlot:<br> <br> SUBARRAY (new_slots^, 0, n) := slots^;<br> slots := new_slots;<br><br>occurs in the order written.<br>That SUBARRAY() := finishes before slots := runs.<br>Aggressively compilers/processors need not execute these in the order written.<br> <br>Do we have a way to guarantee that?<br> <br>Something like:<br> SUBARRAY (new_slots^, 0, n) := slots^;<br>> MemoryBarrier();<br> slots := new_slots;<br><br>?<br> <br>MemoryBarrier on Windows is implemented as one "special" instruction -- for x86, AMD64, and IA64.<br>Those implementations are portable to any OS running those architectures.<br>Though they aren't expressed in a portable form (x86 inline assembly and C compiler intrinsincs).<br>In particular:<br> <br>winnt.h:<br>amd64:<br>#define MemoryBarrier __faststorefence<br><br>x86:<br>FORCEINLINE<br>VOID<br>MemoryBarrier (<br> VOID<br> )<br>{<br> LONG Barrier;<br> __asm {<br> xchg Barrier, eax<br> }<br>}<br><br>ia64:<br>#define MemoryBarrier __mf<br><br> <br> - Jay<br> <br></div></span></blockquote></div><br></div></span><br class="ecxApple-interchange-newline"></blockquote></div><br></div></span><br class="Apple-interchange-newline"></blockquote></div><br></div></body></html>