11

Late Night Cocoa

 4 years ago
source link: https://www.mikeash.com/pyblog/late-night-cocoa.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
Late Night Cocoa
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.

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK