<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 10pt;
font-family:Verdana
}
--></style>
</head>
<body class='hmmessage'>
Ah, ok.<BR>
<BR>
btw another "common" primitive is InterlockedCompareExchange"Double".<BR>
As in InterlockedCompareExchange64 that's been in x86 a while and InterlockedCompareExchange128 that is newer.<BR>
<BR>
There are also often alignment requirements for these things, like to not cross cache line boundaries.<BR>
We're already ok that way?<BR>
At least for globals?<BR>
<BR>
- Jay<BR><BR> <BR>
<HR id=stopSpelling>
Subject: Re: [M3devel] cas/casp?<BR>From: hosking@cs.purdue.edu<BR>Date: Fri, 18 Dec 2009 14:12:44 -0500<BR>CC: m3devel@elegosoft.com<BR>To: jay.krell@cornell.edu<BR><BR><BASE>
<DIV><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span>
<DIV style="WORD-WRAP: break-word"><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: 12px Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; COLOR: rgb(0,0,0); WORD-SPACING: 0px" class=ecxApple-style-span>
<DIV><SPAN style="FONT-SIZE: medium" class=ecxApple-style-span>On 18 Dec 2009, at 14:06, Jay K wrote:</SPAN></DIV></SPAN></SPAN></SPAN></SPAN></SPAN></SPAN></SPAN></SPAN></DIV></SPAN></SPAN></DIV>
<DIV><BR class=ecxApple-interchange-newline>
<BLOCKQUOTE><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: medium Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; WORD-SPACING: 0px" class=ecxApple-style-span>
<DIV style="FONT-FAMILY: Verdana; FONT-SIZE: 10pt" class=ecxhmmessage>oh. I already got it working. ok.<BR><BR>Atomic confuses me in a few ways.<BR> <BR>I find it terribly confusing on Windows that there are separate compiler and memory fences.<BR>I'd like there to be a very simple full fence that forces all reads/writes before it to finish before any reads/writes after it, both for the compiler and processor.<BR></DIV></SPAN></BLOCKQUOTE>
<DIV><BR></DIV>
<DIV>MemoryFence does that. CompilerFence is strictly weaker than MemoryFence.</DIV><BR>
<BLOCKQUOTE><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: medium Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; WORD-SPACING: 0px" class=ecxApple-style-span>
<DIV style="FONT-FAMILY: Verdana; FONT-SIZE: 10pt" class=ecxhmmessage>It makes no sense to me to allow the processor or compiler to reorder but not both.<BR> <BR> <BR>What is weak cas?<BR></DIV></SPAN></BLOCKQUOTE>
<DIV><BR></DIV>
<DIV>It's a CAS that can fail spuriously. i.e., even if the old value was ==.</DIV><BR>
<BLOCKQUOTE><SPAN style="TEXT-TRANSFORM: none; TEXT-INDENT: 0px; BORDER-COLLAPSE: separate; FONT: medium Helvetica; WHITE-SPACE: normal; LETTER-SPACING: normal; WORD-SPACING: 0px" class=ecxApple-style-span>
<DIV style="FONT-FAMILY: Verdana; FONT-SIZE: 10pt" class=ecxhmmessage>Is that loadlocked/storecondition and the caller can loop?<BR> <BR> <BR>Um. There is the Windows terminology InterlockedWhatever.<BR>There is the gccc builtins.<BR>Can we "sound" close to one of them?<BR>Or is this based on some other widely known system?<BR></DIV></SPAN></BLOCKQUOTE>
<DIV><BR></DIV>
<DIV>The Atomic interface I posted is based on a proposal for the C++ standard:</DIV>
<DIV><BR></DIV>
<DIV><A href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2047.html">http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2047.html</A></DIV><BR>
<BLOCKQUOTE>
<DIV style="FONT-FAMILY: Verdana; FONT-SIZE: 10pt" class=ecxhmmessage> And we don't care about older x86 processors like 386?486 I assume?<BR>There seem to have been at least two leaps in functionality here.<BR>Old Win32 operating systems provide very few interlocked functions.<BR>They provide increment and decrement, that only return <0, 0, >0 of the new value.<BR>And Exchange. (This is based on the Visual C++ 2.0 winbase.h)<BR>All just on 32bit values.<BR> <BR>Later on there is a much larger suite, Exchange, ExchangeAdd, Inc/Dec that return new value, all on 32 bit values.<BR> <BR>And then later, stuff added for 16 values, bit operations, maybe 8 bit values, and, or, xor. I don't think this requires newer processors though.<BR> <BR>And then also at some point InterlockedCompareExchange64 which requires the "newest" processors, but is still quite old.<BR>>From this you can synthesize inc/dec/and/or/xor with loops and that is done with inline functions in winbase.h.<BR> <BR> <BR> - Jay<BR><BR> <BR>> From:<SPAN class=ecxApple-converted-space> </SPAN><A href="mailto:hosking@cs.purdue.edu">hosking@cs.purdue.edu</A><BR>> Date: Fri, 18 Dec 2009 13:32:57 -0500<BR>> To:<SPAN class=ecxApple-converted-space> </SPAN><A href="mailto:jay.krell@cornell.edu">jay.krell@cornell.edu</A><BR>> CC:<SPAN class=ecxApple-converted-space> </SPAN><A href="mailto:m3devel@elegosoft.com">m3devel@elegosoft.com</A><BR>> Subject: Re: [M3devel] cas/casp?<BR>><SPAN class=ecxApple-converted-space> </SPAN><BR>> Hold your horses. I am in the middle of working up a more portable "Atomic" interface along the following lines. We can choose to implement with compiler intrinsics like Word/LongWord (if available), but otherwise will provide a call interface. I envision instantiating for ADDRESS, CHAR, and Word.T. This means CAS/CASP will go away.<BR>><SPAN class=ecxApple-converted-space> </SPAN><BR>> GENERIC INTERFACE Atomic(Rep);<BR>><SPAN class=ecxApple-converted-space> </SPAN><BR>> IMPORT RTMachine;<BR>><SPAN class=ecxApple-converted-space> </SPAN><BR>> TYPE T = Rep.T;<BR>><SPAN class=ecxApple-converted-space> </SPAN><BR>> PROCEDURE MemoryFence();<BR>> (* Guarantees explicit memory ordering for otherwise unordered atomics, and<BR>> for other memory references wrt atomics. Not useful for ordering<BR>> ordinary memory references, since those may not race and, if they don't<BR>> race, always appear to be ordered. *)<BR>><SPAN class=ecxApple-converted-space> </SPAN><BR>> PROCEDURE CompilerFence();<BR>> (* Ensures that prior memory operations appear in the instruction stream<BR>> before subsequent ones, i.e. the compiler is not allowed to reorder<BR>> around this. This really has only implementation-defined semantics, but<BR>> it seems to be useful in ensuring ordering with respect to signal<BR>> handlers and the like. *)<BR>><SPAN class=ecxApple-converted-space> </SPAN><BR>> PROCEDURE Store(VAR var: T; val: T); (* No ordering guarantees. *)<BR>> PROCEDURE StoreRelease(VAR var: T; val: T);<BR>><SPAN class=ecxApple-converted-space> </SPAN><BR>> PROCEDURE Load(READONLY var: T): T; (* No ordering guarantees. *)<BR>> PROCEDURE LoadAcquire(READONLY var: T): T;<BR>><SPAN class=ecxApple-converted-space> </SPAN><BR>> TYPE Order = { Raw, Acquire, Release, Ordered };<BR>> (* "Raw" ==> This operation is unordered, and may become visible to other<BR>> threads in an order that is constrained only by ordering constraints<BR>> on other operations.<BR>><SPAN class=ecxApple-converted-space> </SPAN><BR>> "Release" ==> All prior memory operations (including ordinary<BR>> assignments) become visible to a an acquire operation on the same<BR>> object that sees the resulting value.<BR>><SPAN class=ecxApple-converted-space> </SPAN><BR>> "Acquire" ==> See above.<BR>><SPAN class=ecxApple-converted-space> </SPAN><BR>> "Ordered" ==> Both acquire and release ordering properties.*)<BR>><SPAN class=ecxApple-converted-space> </SPAN><BR>> CONST HasCas = RTMachine.HasCas;<BR>> CONST HasWaitFreeCas = RTMachine.HasWaitFreeCas;<BR>> PROCEDURE Cas(VAR var: T; old, new: T; order := Ordered): T;<BR>> (* Most architectures provide a way to return the old value. On those that<BR>> do not, it can be emulated with an additional load, at the expense of<BR>> wait-freedom or spurious failure. *)<BR>><SPAN class=ecxApple-converted-space> </SPAN><BR>> CONST HasWeakCas = RTMachine.HasWeakCas;<BR>> PROCEDURE WeakCas(VAR var: T; old, new: T; order := Ordered): T;<BR>> (* Similar to "Cas", but may fail spuriously, and must be wait-free, if<BR>> provided. *)<BR>><SPAN class=ecxApple-converted-space> </SPAN><BR>> CONST HasFetchAdd = RTMachine.HasFetchAdd;<BR>> PROCEDURE FetchAdd(VAR var; incr: T; order := Raw): T;<BR>><SPAN class=ecxApple-converted-space> </SPAN><BR>> CONST HasFetchOr = RTMachine.HasFetchOr;<BR>> PROCEDURE FetchOr(VAR var; mask: T; order := Raw): T;<BR>><SPAN class=ecxApple-converted-space> </SPAN><BR>> CONST HasFetchAnd = RTMachine.HasFetchAnd;<BR>> PROCEDURE FetchOr(VAR var; mask: T; order := Raw): T;<BR>><SPAN class=ecxApple-converted-space> </SPAN><BR>> END Atomic.<BR>><SPAN class=ecxApple-converted-space> </SPAN><BR>><SPAN class=ecxApple-converted-space> </SPAN><BR>> On 18 Dec 2009, at 13:04, Jay K wrote:<BR>><SPAN class=ecxApple-converted-space> </SPAN><BR>> > Tony is this right?<BR>> ><SPAN class=ecxApple-converted-space> </SPAN><BR>> ><SPAN class=ecxApple-converted-space> </SPAN><BR>> > conceptually:<BR>> ><SPAN class=ecxApple-converted-space> </SPAN><BR>> ><SPAN class=ecxApple-converted-space> </SPAN><BR>> > result := CAS(VAR destination, compare, exchange)<BR>> ><SPAN class=ecxApple-converted-space> </SPAN><BR>> ><SPAN class=ecxApple-converted-space> </SPAN><BR>> > old := destination<BR>> > if old := compare then<BR>> > destination = exchange<BR>> > return old<BR>> ><SPAN class=ecxApple-converted-space> </SPAN><BR>> ><SPAN class=ecxApple-converted-space> </SPAN><BR>> > bool result := CASP(VAR destination, compare, exchange)<BR>> > P for predicate aka returning bool<BR>> ><SPAN class=ecxApple-converted-space> </SPAN><BR>> ><SPAN class=ecxApple-converted-space> </SPAN><BR>> > old := destination<BR>> > if old = compare then<BR>> > destination := exchange<BR>> > return true<BR>> > return false<BR>> ><SPAN class=ecxApple-converted-space> </SPAN><BR>> ><SPAN class=ecxApple-converted-space> </SPAN><BR>> > I'm pretty sure it is.<BR>> ><SPAN class=ecxApple-converted-space> </SPAN><BR>> ><SPAN class=ecxApple-converted-space> </SPAN><BR>> > I'll have this for 16 bit and 32 bit values shortly, for now requiring<BR>> > a recent Microsoft compiler and it generates function calls.<BR>> > But inlining should be easy enough.<BR>> > And then 8bit and 64bit.<BR>> ><SPAN class=ecxApple-converted-space> </SPAN><BR>> ><SPAN class=ecxApple-converted-space> </SPAN><BR>> > Also this will probably not work on 386 or 486 but require Pentium or somesuch.<BR>> > I don't know when various instructions were introduced but I know<BR>> > 386 is much poorer here than modern processors.<BR>> ><SPAN class=ecxApple-converted-space> </SPAN><BR>> ><SPAN class=ecxApple-converted-space> </SPAN><BR>> > I assume only support int8, uint8, int16, uint16, int32, uint32, int64, uint64, size_t, ptrdiff_t<BR>> > and not e.g. floating point.<BR>> ><SPAN class=ecxApple-converted-space> </SPAN><BR>> ><SPAN class=ecxApple-converted-space> </SPAN><BR>> > - Jay<BR>><SPAN class=ecxApple-converted-space> </SPAN><BR></DIV></BLOCKQUOTE></DIV><BR> </body>
</html>