Re: [boost] [lockfree] review

Subject: Re: [boost] [lockfree] review
From: Dave Abrahams (dave_at_[hidden])
Date: 2011-08-01 11:00:59

on Mon Aug 01 2011, Tim Blechmann <tim-AT-klingt.org> wrote:

> [quick post, have some more in my outbox, but i'm at a conference this week,
> where they cut imap/smtp ports]
>
>>> Anyway, what's the "wrong order?"  If one thread is depending on the
>>> order of things that happen in another thread without both threads using
>>> the synchronization necessary to ensure that order, it's a race
>>> condition (a.k.a. a bug), right?
>>
>> All of the classic lock-free algorithms, including those that are
>> the basis for the synchronization primitives we should usually use,
>> have data races.  At a low level it is sometimes necessary to use a
>> variable for synchronization.
>
> the fifo code for example contains code like:
>
> atomic<> head_, tail_;
>
> head = head_.load();
> tail = tail_.load();
>
> head2 = head_.load();
>
> if (head == head2)
>    do something
>
> the correctness of this algorithm depends on the order of the loads: load head
> before tail and load tail before head2. without a memory model, both
> the compiler
> and the CPU are allowed to reorder loads (or head2 could simply use
> the value of
> head without actually reloading it)

But I never said we don't need a memory model!  Of course, we do need
rules that allow us to ensure temporal sequencing of operations.  All I
said was that sequential consistency doesn't seem to make parallelism
much easier.

In particular, in C++ we're only talking about sequential consistency
for data-race-free programs, which is kind of a funny hedge.  It means
that your atomics and the code around them as a whole blob respect some
plausible interleaving of the instructions in single threads, but it
doesn't say anything about the interaction of most variables, which (I
hope) are not atomic.  In other words, sequential consistency only helps
those people already working in the rarified air of atomics and
lock-free algorithms, where if you're going to play you'd better have a
firm grasp of even lower-level concepts like memory barriers.

OK, I guess this all scales up to those of us using locks... if you
don't have sequential consistency among sections using the same mutex,
the mutex can hardly be said to be working.  So let me try saying what I
mean differently: even a hypothetical programming model where
*everything* (including non-atomics) is guaranteed to be sequentially
consistent still seems insufficient to make parallel programming
tractable.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com