> > > "While the processor may spin and attempt the atomic operation more
> > > than once before it is successful, research indicates this is
> > > extremely uncommon." I don't understand this sentence, what do you
> > > mean?
> >
> > I'm not sure I can pinpoint the paper from which the statement is
> > based, but I seem to recall something similar in the original LL-SC
> > papers (Maurice Herlihy, DEC Western Research Labs?) It's a
> > foundation for lock-free algorithms.
>
> Well, the statement says that often you have low contention. But that's
> something you want, not necessarily something you will get, and depends
> on the workload/algorithm. I'm missing the context. Is the actual
> statement as obvious as that you should try to use the atomic
> instructions offered by your processor, instead of doing blocking
> algorithms?
LL/SC is not a blocking algorithm. I'm going to be changing some of
the nomenclature on the page to reflect this, but while it spins, it
does not actually lock. The idea (as I understand it, and I'm still
hoping Scott can find the reference he gave me to a DEC paper
outlining this) is that the spin only occurs if another process does
something breaking atomicity for that _particular_ LL/SC pairing. Even
when the spin occurs, it should only occur until that particular
process gets through the op without interruption. This needs some
statistical analysis however, and hopefully the research in the
literature can be located and referenced.
Okay, now I know what you wanted to say (and btw, I know that). But I still
wouldn't put that into the proposal because we don't care how the hardware
implements it. CAS could be implemented the same way. The point is whether
you got something as powerful as CAS or LL/SC that is still nonblocking (or
looks nonblocking).
I'd suggest having a look at the so-called consensus hierarchy (and why
TAS/get-and-set is less powerful than CAS).
> > > You probably don't need to require CAS (compare-and-set) to return
> > > the previous value (I think some architectures don't), but just
> > > return a boolean value (success/failure).
> >
> > compare and swap?
>
> Well, do you need the swap, or is a compare-and-set sufficient most of
> the time? What do other architectures offer?
All of the architectures offer swap, or have no penalty for swapping.
This allows much easier algorithm development to my mind, as you have
the best of both worlds -- success/failure information, and the value
from memory.
Here is an example what can happen if you want to support an architecture
that does only return a success flag on CAS or LLSC, but not the value (no
swap).
1) What you could do to return the value is returning a load before or after
the CAS. Without blocking, you can't (easily?) make the load atomic with
the operation.
2) Suppose a user wants to use CAS for a simple spin-lock (because you don't
offer TAS, for example). You need to return a value instead of the success
boolean flag. Neither the previous nor the later load are useful. So you
have to pick a "different" value (e.g., expected value + 1, or sth like
that).
3) Now user want to use CAS for something else, for example, swinging a
pointer. How do you pick a different value? You can do, but then the user
can't use this value for anything else.
As a result, you can't support the CAS for this hardware without blocking.
Because of that, I would choose the conservative way of returning just the
success flag. And most of the concurrent implementations I've seen have the
load in it anyway (sth like while(1) { load; set up; if (CAS) break;}).
The overhead that you can get is one more load, if you need to retry.
However, I don't think that is an issue, both regarding ease of use and
performance-wise.
You usually won't need a membar for this load, because some value from after
the CAS is sufficient in most algorithms, and the CAS usually ensures that.
If the CAS failed and your CAS is a swap, then the new value is already
either in the cache (load is cheap) or in a register. You could try to
supply subsequent loads from the register, but that might be difficult to
implement in the code generator. In any case, do you have performed
measurements to test whether the potential additional load actually matters
performance-wise?
> What you would want is to have a model that is (1) easy-to-use for the
> developers and (2) close to what the hardware offers. L/S membars are
> easy to use, but I think some architectures such as Itanium offer
> different membars with different costs. So if you pick the wrong model
> and have to use stronger membars (mfence Itanium) to implement your
> model, than you pay for that by decreased performance.
Itanium was the only architecture to offer these semantics, while the
L/S membars are offered to varying levels of detail on several
architectures. As Itanium is not yet a fully functional target, it was
not prioritized.
Moreover, as the only instructions (to my knowledge) on Itanium to
have memory synchronization components are cmpxchg and fetchadd, these
could be implemented correctly when implementing the lowering for the
instructions in this proposal, while still providing full memory
barriers when needed outside of the atomic instructions. If there is
serious demand for building memory semantics into the atomic
instructions, "aquire" and "release" flags could be used, and
implementations appropriately handle them. This doesn't seem to anull
the need for non-operation-based memory barriers.
At the programming level, the membar is always conceptually associated to
some operation. You need the ordering at some point in your algorithm (when
the processor would execute a particular operation). If you wouldn't need
ordering constraints for any operation, then you wouldn't need the membar
at all.
The implementations for the current proposal came from architecture
manuals, the Linux kernel, and the Apache Portable Runtime. I will
definitely be looking at the atomic_ops implementations to see if
there are improvements that can be made, but ultimately this provides
another model, but not a re-usable component as this must be done
through codegen at some point.
To me, letting codegen emit the same instructions as the macros do _is_
reuse.
You might even be able to write a script that generates codegen-code from
the macros...
> Second, I guess there has been some serious effort put into selecting
> the specific model. So, for example, if you look at some of Hans'
> published slides etc., there are some arguments in favor of associating
> membars with specific instructions. Do you know reasons why LLVM
> shouldn't do this?
My reason for not associating them is due to the majority of hardware
implementations not associating them. The override motive was to
remain very close to the hardware. Could libraries and intrinsic
functions in the FE provide these different interfaces to the
constructs?
It might be more difficult because the membars modify operations, and can't
be easily "added" as new instructions,calls, or intrinsics.
Regarding the frontends, we're back at the language integration question, I
guess. If you don't want to change syntax or add modifiers, I guess the
best way would be to provide a function call interface for CAS, loads, ...
(either plus membars or with membars attached as in atomic_ops), and
then "inline"/lower the code to the to-be-added LLVM IR constructs in the
frontend, or in an extra pass. You might even get a fallback to library
code (requires lib to be linked, of course), when the codegen doesn't
support the atomic ops for a certain architecture.
> Has anyone looked at the memory models that are being in discussion for
> C/C++? Although there is no consensus yet AFAIK, it should be good for
> LLVM to stay close.
Not that LLVM should shun C/C++, but those aren't its only languages.
I think its better to approach the problem from the hardware, than the
language. This keeps LLVM an accurate layer for expressing hardware
operations, and allows languages to translate their constructs to
appropriately use the hardware.
I don't know any language besides Java that does have an official memory
model? Are there any?
In all other languages I've seen so far, synchronization is either only via
critical sections, or they revert to using some C/C++ library (that then
uses asm code).
I absolutely agree. This is why every aspect of the current proposal
came from a hardware representation, combined with the Linux kernel
representations. We deviated toward the hardware to ensure the ability
of these intrinsics to fully exploit and expose the hardware
capabilities while remaining lowerable (if that were a word) across
all targets.
Does this clarify some? I am quite open to trying to add support for
Itanium-style hardware representations if this is a significant issue,
it was simply not a priority, and not a problem that I well
understand. (The Linux kernel does not use these semantics that I
could find, but then it may not be the best example.)
I really do thank you for the effort you put into this. All that I want is
that LLVM gets the best option.
The whole memory-model issue is really difficult, and if you do it wrong,
you're going to pay. Just look at Java and its memory-model troubles...
For this reason, I'd like to see more discussion about it, about
alternatives, models, implementations, etc. And the decisions should be
documented somewhere (e.g., by archives of mailing lists...).
torvald
