Re: Grand Central

[David Chisnall]

On 15 Jun 2009, at 09:28, Jamie Ramone wrote:

> This "block thingy" looks interesting. Oh, while we're on the topic of
> multi-processors, I've invented an algorithm that allows parallel
> lock-less insertions on a linked list. Could be useful for
> NSConnections, as it's WAY more efficient than anything else I've ever
> seen (and, yes, I am including NSMutableArray methods here). It does
> come at a price: it requires an atomic swap operation i.e. assembly.
> The good news is that only one instruction is needed so the
> portability issue isn't at the "I feel like kissing the barrel of a
> shotgun". I'll submit the paper for it as soon as Ive finished
> polishing it, shoulda been this week (I am so fuckin' lazy...and
> studying...and trying to work, don't ask).

We're straying off-topic here, but have you read Keir Fraser's PhD  
thesis?  He presents a lockless way of inserting into a linked list  
which only requires an atomic swap and a proof of its correctness.  
EtoileThread and MediaKit both use a hybrid structure based on the  
lockless ring buffer from this thesis (modified to permit it to enter  
a locked mode when there is no traffic and avoid polling; if the  
buffer stays full, there is no locking, when it empties the consumer  
thread waits on a condition variable).  He also describes a  
concurrency-safe skip list implementation; this would be worth using  
for NSMutableArray if people want to use it concurrently (or to  
provide a GSConcurrentMutableArray, as a thread-safe NSMutableArray  
subclass).

Atomic compare-and-swap is one of the builtins provided by clang and  
recent GCCs.  Assembly is only needed while we continue to support  
archaic compilers.

David