Re: [Sbcl-devel] compare-and-exchange

[Nathan F. <fr...@gm...>]

On 4/7/07, Alexander Kjeldaas <ale...@gm...> wrote:
> On 4/7/07, Nikodemus Siivola <nik...@ra...> wrote:
> > This is well enough for our internal needs, but it just dawned to me
> > that it would be nice to support CMPXCHG semantics for users too (how
> > else are they supposed to implement lockless algorithms in Lisp?)
> >
> > Any ideas what such an interface should / could look like?
>
> Two things to consider. It should be possible to use cmpxchg16b (on
> 64-bit), so that you can have some payload in (car x) and do the
> cmpxchg16b on the full cons.  In C, you often encode stuff in the
> lower bits of a pointer to avoid cmpxchg16b.   In lisp, I think
> cmpxchg16b will be needed more often (still - for 64-bit).

Let's get the single compare-and-swap case down before we
start to worry about the double compare-and-swap case. :)  Also,
DCAS is not supported on all CPUs--if we want to make SBCL an
x86/x86-64 only Lisp implementation, that's fine, but we do have to
cater a bit to the lowest common denominator.

> Secondly, it would be nice to be able to allocate a cons or something
> like that that was guaranteed to be on a separate cache line so that
> you are guaranteed not to have unintended ping-pong effects between
> CPUs.

The initial allocation part of this is not difficult--the allocation routine can
simply ensure that the starting address is appropriately aligned.  Ensuring
that the object *stays* on an appropriately aligned address after GCs is
a bit more difficult.  If we do decide to do something like this, I think we
should introduce a separate type that the GC can deal with appropriately,
rather than having the GC attempt to preserve allocation in all cases.

-Nathan