Dave Korn wrote:
Particularly lock-free queues whose correct
operation is critically dependent on the order in which the loads and
stores are performed.
No, absolutely not. Lock-free queues work by (for example) having a single
producer and a single consumer, storing the queue in a circular buffer, and
assigning ownership of the queue's head pointer to the producer and the
(chasing) tail pointer to the consumer.
[snip]
The ordering is critical within a single thread of execution; e.g. you must
fill in all the details of the new entry you are adding to the queue
/before/
you increment the head pointer,
Exactly. Guess what the compiler did to us? :-) "Oh, no, I'm /sure/ it's
OK if I re-order your code so that those assignments happen /after/ I
handle this dinky little increment for you." Now our code may have been
wrong in this instance (see below), but...
Let's be clear. Order matters. /You/ said so yourself. :-) And even if
the programmer correctly tells the compiler what to do, what (unless the
compiler inserts memory barriers) keeps the CPU from circumventing both?
That said, I've seen even stranger things, too. For example:
foo->bar = make_a_bar();
foo->bar->none = value;
being rendered as:
call make_a_bar
foo->bar->none = value
foo->bar = <result of make_a_bar()>
So what was wrong with my C code in that instance? :-)
This is a very real, entirely legitimate example
where the compiler thinking it knows how to do my job better than I do
is wrong.
Nope, this is a very real example of a bug in your algorithmic design, or of
you misleading the compiler, or relying on undefined or implementation-defined
behaviour.
[snip]
This simply means you have failed to correctly declare a variable volatile
that in fact /is/ likely to be spontaneously changed by a separate thread of
execution.
/That/ is very possible. I'm talking about /OLD/ code here, i.e. code
that was written back in K&R days, back before there /was/ a volatile
keyword. (Although I had understood that 'volatile' was a no-op in most
modern compilers? Does it have the semantics that loads/stores of
volatile variables are not re-ordered with respect to each other?)
At any rate, I don't recall now if making the variable in question
'volatile' helped or not. Maybe this is an exercise in why changing
long-standing semantics has an insidious and hard to correct effect.
(Does that conversation sound familiar?)
And relying on a library call to act as a memory barrier is risky.
[snip]
Now, the compiler *does* know not to optimise moves across library calls, but
you're investing too much trust in them if you think the CPU's internal units
know or care whether you're in a libcall or your mainline code.
You're preaching to the choir. Unfortunately adding proper assembly
modules to our build system didn't go over so well, and I am /not/ going
to try to write inline assembler that works on six-or-more different
compilers. :-) So I know this is just a 'cross your fingers and hope it
works' approach on non-x86 platforms. On x86 I use the correct,
previously-quoted inline assembly, which as mentioned acts as a barrier
for both the compiler /and/ the CPU. As you say, all it's really
ensuring in other cases is that the compiler remains honest, but that
was the intent, and I know it isn't perfect.
--
Matthew
Hi! I'm a .signature virus! Copy me into your ~/.signature, please!
