mikeash.com: just this guy, you know?

Posted at 2008-09-05 23:31 | RSS feed (Full text feed) | Blog Index
Next article: NetAwake
Previous article: Welcome to iPhone: Your Crappy Mac of Tomorrow, Today!
Tags: atomic interview link threading
Late Night Cocoa
by Mike Ash  

Readers of this blog may be interested in my recent appearance on Late Night Cocoa. I discussed the fundamental principles and basic concepts behind lockless thread-safe data structures. You can access the episode here.

Did you enjoy this article? I'm selling whole books full of them! Volumes II and III are now out! They're available as ePub, PDF, print, and on iBooks and Kindle. Click here for more information.

Comments:

Thanks, this is relevant to my interests. The show started out a little slow but it got interesting about 20:00.
Glad you liked it. I'm not surprised that you found it slow at the beginning. I really wanted to justify the approach and put it into context, and that meant a discussion of more traditional multithreading which is pretty much just a retread for anyone who's already very familiar with it.
Hi Mike,

Really liked the episode, although you said that Apple had done the hard work you still made it comprehensible.

Do you have any example code that would demonstrate some of these operations? I do a lot of string searching in my app and it's be fun to see if I can improve performance with these.

Thanks,

Jonathan
Jonathan, thanks for your kind words.

I'd suggest that these techniques are probably not too useful for things like string searching. If you can break it up into smallish work units, then I recommend using NSOperation and NSOperationQueue (if you can require 10.5) to run them on all available CPU cores. But of course you know your problem space better than I do, so certainly check out everything and come to your own conclusions.

I will give some quick examples though. Beware that all of the below is written in this comment box and has not been tested.

First, a quick re-implementation of that atomic increment function I used as an example in the podcast. This gives an illustration of the fetch/update/commit loop that I discussed:

int32_t AtomicIncrementInt32(volatile int32_t *intptr)
{
    bool success;
    int32_t old;
    int32_t new;
    do {
        old = *intptr; // fetch
        new = old + 1; // update
        success = OSAtomicCompareAndSwap32Barrier(old, new, intptr); // commit
    } while(!success); // if commit failed, do it again
    
    return new; // it can be useful to know what the end result was
}


And now here's an illustration of inserting into a linked list. First we need to define a structure for the list nodes:

struct ListNode
{
    id payload;
    struct ListNode *next;
}


(The 'payload' member can be replaced with anything, even a whole collection of different members. What it contains is up to you.)

And now, the insert function:

void AtomicInsertListNodeAtHead(struct ListNode * volatile *head, struct ListNode *newnode)
{
    bool success;
    struct ListNode oldhead;
    do {
        oldhead = *head; // fetch
        newnode->next = oldhead; // update
        success = OSAtomicCompareAndSwapPtrBarrier(oldhead, newnode, head); // commit
    } while(!success);
}


This follows the same basic pattern. Here, we update the next pointer to point at the old head. Then we do the CAS to replace the head pointer. If it fails, something else updated the list before we could, so start over.

Note, avoid the temptation to write a AtomicRemoveListNodeAtHead function using this same basic pattern. It may look easy, but you run into that ABA problem I discussed and that is extremely non-trivial to solve.

So, what if you really do want to support removal? Well, that's where that built-in atomic queue stuff comes in. Instead of writing our own list node stuff, we can use Apple's:

OSQueueHead queue = OS_ATOMIC_QUEUE_INIT;

OSAtomicEnqueue(&queue, newnode, offsetof(struct ListNode, next));

struct ListNode *dequeued = OSAtomicDequeue(&queue, offsetof(struct ListNode, next));


And Apple takes care of solving all that ABA nastiness and wrapping it all up in a couple of really simple functions.
Hi Mike,

Thanks for those, I appreciate you taking the time to give examples too. It's far easier to read code than listen to it!

I'm using NSOperation at the moment, but now I have a good starting point to see what mileage I can get from these functions.

Thanks again,

Jonathan
Hi Mike,

The link is broken.

[]'s

Comments RSS feed for this page

Add your thoughts, post a comment:

Spam and off-topic posts will be deleted without notice. Culprits may be publicly humiliated at my sole discretion.

Name:
The Answer to the Ultimate Question of Life, the Universe, and Everything?
Comment:
Formatting: <i> <b> <blockquote> <code>.
NOTE: Due to an increase in spam, URLs are forbidden! Please provide search terms or fragment your URLs so they don't look like URLs.
Hosted at DigitalOcean.