Diogo Tridapalli - 2013-01-29 20:25:37

Tue, 29 Jan 2013 20:25:37 GMT

Hi Mike,

The link is broken.

[]'s

Jonathan Dann - 2008-09-19 06:36:50

Fri, 19 Sep 2008 06:36:50 GMT

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

mikeash - 2008-09-09 02:13:39

Tue, 09 Sep 2008 02:13:39 GMT

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.

Jonathan Dann - 2008-09-06 20:40:57

Sat, 06 Sep 2008 20:40:57 GMT

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

mikeash - 2008-09-06 10:39:31

Sat, 06 Sep 2008 10:39:31 GMT

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.

foobaz - 2008-09-06 10:22:45

Sat, 06 Sep 2008 10:22:45 GMT