Next article: NetAwake
Previous article: Welcome to iPhone: Your Crappy Mac of Tomorrow, Today!
Tags: atomic interview link threading
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.
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.
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)
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 *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)
struct ListNode oldhead;
oldhead = *head; // fetch
newnode->next = oldhead; // update
success = OSAtomicCompareAndSwapPtrBarrier(oldhead, newnode, head); // commit
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
AtomicRemoveListNodeAtHeadfunction 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.
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.
The link is broken.
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.