Subj : Re: posix and lock-free algorithms
To   : comp.programming.threads
From : Joe Seigh
Date : Thu Aug 04 2005 12:09 pm

John Doug Reynolds wrote:
>>Scott Meyers and Andre Alexandrescu wrote a two-part article
>>for Dr. Dobbs Journal on this exact subject.
>>I found a link to a revised copy here:
>>http://www.aristeia.com/Papers/DDJ_Jul_Aug_2004_revised.pdf
> 
> 
> Sean, thanks for the article!
> 
> The authors seem to conclude that DCSI could be implemented portably
> in C/C++ under Posix, if Posix supported explicit memory barriers.
> They do not discuss constructing a memory barrier from the available
> Posix synchronization primitives, or explain why
> 
>      void memory_barrier() { mutex m; m.lock(); m.unlock(); }
> 
> does not work for that purpose.  According to David Schwartz,
> 
>  "In principle, that could be optimized by a sufficiently smart
>   implementation to nothing."

That's arguable.  Posix has no formal semantics so you can't really
say what has to happen.  It's a good idea for Posix implementations
to be on the conservative side and not so aggressive since you don't
wan't to be the one implementation most likely to make programs
crash.

You can see what's Java currently says about this sort of optimization.
I know an early Java compiler optimized out empty synchronized blocks and
later had to fix it.  But I don't know if it's allowed with current
Java semantics.  If Posix does go with formal semantics it's likely
to be similar to Java.

> 
> If so, then as you say, it is a language issue, not a failure of Posix
> to provide the necessary tools.  But I wonder about David's claim.
> While it's obvious to the human reader that my function is an
> expensive no-op, the compiler has to actually prove this, right?  And
> from what Meyers and Alexandrescu said in their article, wouldn't the
> implementions of pthread_mutex_lock() and pthread_mutex_unlock() act
> as "hard sequence points" and so stop the compiler from combining and
> removing them?  But perhaps I misunderstand.  In any case, this sounds
> like a question for a different news group.
> 
> 
>>The whole point of DCL is to avoid the cost of a mutex lock whenever
>>possible, so this method makes little sense.
> 
> 
> I'm only trying to avoid locking _contention_ between reader threads,
> and while this may not be the most efficient solution possible, it
> does at least have the property that the function will never be
> hindered by another thread.

Lock/unlock will block if a thread time slice end while holding the
lock.  Even using adaptive spin waiting won't help here.
> 
> So I'm left with my original question: if it just requires the use of
> portable memory barriers to implement DCSI in C/C++ under Posix, why
> is it so generally considered to be impossible?  What really is the
> reason why a memory barrier can't be constructed from other
> synchronization primitives?
> 
Well, pthread_once.  It's an awkward interface and Posix doesn't actually
*say* it's as efficient as DCL which in retrospect was a really bad
design decision.

There's a list somewhere of the Posix functions that "synchronize" memory
but again no performance claims there either.

-- 
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

.