Re: Grand Central

[Jamie Ramone]

On Mon, Jun 15, 2009 at 6:42 AM, David Chisnall<address@hidden> wrote:
> 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.

No I haven't, I'll look it up later. Thanx dude. Not that much
off-topic as we're mainly talking about concurrency. If you like, we
can just splinter this thread and keep presenting different
concurrency algorithms to consider and compare there.

> 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).

I don't know much about that, don't really like Etoile and never heard
of MediaKit until now. I should point out that my algorithm was
created to replace both NSLocks and NSMutableArrays inside of
NSConnecions. It is much simpler and smaller, as well as faster. That
said there is room for improvement as the other algorithm included for
the case where the only reader removes the last remaining element
while the writers insert new ones does actually perform a kind of
locking (not the ususual kind), but it does so ALL the sime. This
detail I must work out in order to publish something usefull to us.
But don't worry, I've already got an idea of how to solve this
problem...

> 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.

Aha, and what does that matter? My algorithm and the one you mentioned
require an atomic SWAP. T&C's are another type of atomic operation,
what I'm talking about is an instruction like the 80x86 exchg one
which exchanges the content of two registers or memory addresses. Is
this one included? If so...SWEET!

> David

-- 
Besos, abrazos, confeti y aplausos.
Jamie Ramone
"El Vikingo"