Re: Truly lock-free multi-processor card marking

Bytes work at the hardware level.  They pretty much have to.  Otherwise
adjacent structure fields protected by different locks wouldn't always
work.  (On some, now quite obsolete, hardware, this was the case.  With
ten years hindsight, and the advent of multicore processors, this now
seems like one of several bad ideas in cache coherence and memory system
design.  The current threads memory model proposal for C++0x will be
quite a challenge to implement on multiprocessor hardware that does not
support independent byte stores.  Bit fields are another story.)

Our garbage collector uses either bytes or bits, possibly with CAS, for
the mark bits.  Anecdotal evidence suggests that for parallel markers,
usually bytes win.  The down side is increased cache footprint during
marking.

Now if your question is whether a C or C++ compiler is guaranteed to
leave your byte assignment alone, or whether it may choose to compile to
code that overwrites adjacent bytes, the current answer is that it can
do all sorts of nasty things and remain standard conforming.  But it
probably won't.

Hans

> -----Original Message-----
> From: [email protected] 
> [mailto:[email protected]] On Behalf Of David Chase
> Sent: Monday, July 02, 2007 10:38 PM
> To: [email protected]
> Subject: Re: [gclist] Truly lock-free multi-processor card marking
> 
> > I have searched in vain for several hours now, trying to find any 
> > information for amd64/x86_64 about the minimum quantum that can be 
> > written to without danger of the write being converted to read- 
> > modify-write.  Any information, whether specific or 
> general, is much 
> > appreciated.
> 
> I think the answer is "it depends".  I have had good luck 
> writing bytes, but that was some years ago, and the envelope 
> might be more pushed now.
> 
> You should probably write a test program that checks this; I 
> was able to quickly convince myself that a simple CMPXCHG 
> (with no LOCK
> prefix) was not adequate.
> 
> David Chase
> 
> 
>