Jan 14 2013

dispatch_once upon a time

Grand Central Dispatch, a.k.a libdispatch and usually referred to as GCD, is a low-level API known for performing asynchronous background work. dispatch_async is its poster child: “Throw this block on a background thread to do some work, and inside of that block toss another block on the main thread to update the UI.”

Not all of GCD is asynchronous, though. There’s dispatch_sync to do some work synchronously. There’s also dispatch_once that’s used to guarantee that something happens exactly once, no matter how violent the program’s threading becomes. It’s actually a very simple idiom:

    static dispatch_once_t onceToken;

    dispatch_once (&onceToken, ^{
        // Do some work that happens once
    });

You first declare a static or global variable of type dispatch_once_t. This is an opaque type that stores the “done did run” state of something. It’s important that your dispatch_once_t be a global or a static. If you forget the static, you may have weird behavior at run time.

Then you pass that dispatch_once_t token to dispatch_once, along with a block. GCD will guarantee that the block will run no more than one time, no matter how many threads you have contending for this one spot.

The usual example you see for dispatch_once is creating shared instances, such as the object returned from calls like -[NSFileManager defaultManager]. Wrap the allocation and initialization of your shared instance in a dispatch_once, and return it. Done.

Recently, though, I had an opportunity to use dispatch_once outside of a sharedBlah situation. Another Rancher and I were working on some sample code for a class. It populated a scrolling view with Lots And Lots Of Stuff. Rather than manually coming up with labels for everything, we used the list of words at /usr/share/dict/words to construct random names. Just a couple of words and string them together. The results were often nonsensical, but sometimes we’d get something delightfully random. Here’s the function:

static NSString *RandomName (int wordCount) {

    static NSArray *words;

    if (!words) {
        NSString *allTheWords =
            [NSString stringWithContentsOfFile: @"/usr/share/dict/words"
                      encoding: NSUTF8StringEncoding
                      error: nil];

        NSPredicate *shortWords = [NSPredicate predicateWithFormat:@"length < 8"];
        words = [[allTheWords componentsSeparatedByString:@"\n"]
                    filteredArrayUsingPredicate: shortWords];
    }

    NSMutableArray *nameParts = [NSMutableArray array];

    for (int i = 0; i < wordCount; i++) {
        NSString *word = [words objectAtIndex: random() % words.count];
        [nameParts addObject: word];
    }

    NSString *name = [nameParts componentsJoinedByString: @" "];

    return name;

} // RandomName

Pretty straightforward. A static local variable that points to an NSArray of words. Make a check for nilness, then load the file and remove the long words. And it worked great.

Then we decided to emulate network latency by using dispatch_async and coded delays to act like words were dribbling in over a network connection. Performance took an insane nose-dive, as in “there is no way I am checking this in and keeping my job”. A quick check with Instruments showed RandomName being the bottleneck. Every thread was running it. Whoa.

In retrospect, it’s an obvious mistake: accessing global state unprotected in a threaded environment. Here’s the scenario:

Thread A starts doing stuff. It goes to get a RandomName. It sees that words is nil, so it starts loading the words. GCD, when it sees a thread start blocking (say by going into the kernel reading a largish file), it realizes that it can start another thread running to keep those CPUs busy. So Thread B goes to get a RandomName. Thread A isn’t done loading the words, so words is still nil. Therefore Thread B starts reading the words file. It blocks, and goes to sleep, and Thread C starts up. Eventually all of the reads complete, and they all start processing this 235,886 line file. That’s a crazy amount of work.

It’s pretty to fix. You can slap an @synchronized around it. Or use NSLock, pthread_mutex, etc. I didn’t like those options because you do pay a locking price on each access. Granted, it’s a toy app purely for demonstration purposes, but I still think about that stuff. You can also put stuff like that into +initialize (with the proper class check), knowing the limited circumstances +initialize would get called. That didn’t excite me either. It was nice having RandomName being entirely self-contained and not dependent on some other entity initializing the set of words.

Taking a step back and evaluating the problem: words needs to be loaded and initialized exactly once, and then used forever more. What’s an existing library call that lets you do something exactly once? dispatch_once. We threw a dispatch_once at it, and now performance was decent again:

static NSString *RandomName (int wordCount) {
    static NSArray *words;

    static dispatch_once_t onceToken;

    dispatch_once (&onceToken, ^{
        NSString *allTheWords =
            [NSString stringWithContentsOfFile: @"/usr/share/dict/words"
                      encoding: NSUTF8StringEncoding
                      error: nil];

        NSPredicate *shortWords = [NSPredicate predicateWithFormat:@"length < 8"];
        words = [[allTheWords componentsSeparatedByString:@"\n"]
                    filteredArrayUsingPredicate: shortWords];
    });

    NSMutableArray *nameParts = [NSMutableArray array];
    ...

We didn’t even have to modify the code in the block. Performance was back to reasonable levels, and we could get back to demonstrating our concept.

So what’s the point of all of this? Mainly that GCD is not just for running things concurrently – it’s a small pile of useful concurrency tools. dispatch_once is one of those tools, and has applicability outside of making shared class instances. It’s very low overhead, with dispatch_once_t being four or eight bytes, and not requiring a heavyweight lock every time it’s run.

18 Comments

  1. Craig S. Cottingham

    I’m not sure if I missed something. Is dispatch_once executed synchronously, or is it treated like a mutex (with the second and subsequent times through the code equivalent to noops), or something entirely different? It seems like a second thread could enter RandomName, skip the dispatch_once block, and plow right into accessing the words array before it has been initialized. I really hope that’s not the case. :-)

    • It’s a barrier. If one thread is currently inside of the block protected by a dispatch_once, and another one hits that dispatch_once, then the second thread will pause until the first one finishes. Once the onceToken transitions to the “done did run” state, then all threads will pass through dispatch_once without stopping. (Kind of hard to talk about this stuff when threads are blocking and a block is there running causing the blocking block block….)

  2. SSteve

    How many random names were you generating and what kind of nosedive did you see? I tried this on my Core 2 Duo machine (OS X 10.8.2, SSD drive) calling RandomName like this:


    NSOperationQueue *q = [[NSOperationQueue alloc] init];

    for (int i=0; i<1000; i++) {
    [q addOperationWithBlock:^{NSLog(@"%d: %@", i, RandomName(2));}];
    }

    [q waitUntilAllOperationsAreFinished];

    It took 1.2-1.5 seconds for the first approach and 1.1-1.2 seconds with the dispatch_once approach. I tried having the block just call RandomName without NSLog and that changed the execution time to .45-.95 and .3-.4 seconds. So a definite difference, but not enough for the first approach to make me fear for my job and reputation.

    • Thousands upon thousands of objects needing names. I think we ended up with several dozens of threads running at once doing the word splitting (so there was definite embarrassment all around :-). Wasn’t minutes to start up, but definitely going from instant-startup to SPOD city, Arizona.

  3. Steve Weller

    A note to those not using ARC: save yourself some debugging time by adding a retain to the assignment to words.

    A place I use dispatch_once is in performance-critical code when assigning lots of small UIImages to globals instead of repeatedly using imageNamed.

  4. Ahmet Karalar

    A quick note irrelevant of the main topic: I think the use of dot notation should be limited to properties and bracket notation should be used everything else. count is an instance method, not a property, therefore imho it seems somewhat improper to use it with dot notation in terms of style.

    • And of course I respectfully disagree :-) It’s just a historical artifact that -count is not a @property. If someone were creating NSArray now, count would be a “property”. There’s nothing magical about @property – it’s just syntactic sugar for declaring one or two methods. That’s it. The count of something is an inherent property of a collection. I don’t see the need to go “well, even though in most modern designs, this would be a @property and so I can use dot notation, *but* because this didn’t happen to have the property declared just so, I shall contort my code.” Or if the creator of a class has some kind of bizarre allergy to @property, should I totally eschew what could be more compact, more readable syntax?

      Hey UILabel, give me your text. albumLabel.text. Hey UIColor, give me your CGColor. burntUmber.CGColor. Hey NSArray, give me your count. badgers.count.

      • Ahmet Karalar

        i beg to differ :) i don’t think array.count is much more readable than [array count], there seems a negligible difference between the two in terms of readability. also although the count of an array might be rightfully regarded as an inherent property, since the count of an array is a computed value in C languages rather than an inherent property, I like to think of it as a method rather than a @property. (ie. i do not think of count as a noun as in “count of items in array”, i think of it as a verb as in “count the items in this array”). one last thing is @property is more than syntactic sugar, it makes your object work with KVO and KVC in that given @property. count is not a @property, hence would not be eligible for KVC if it wasn’t for special collection operators. The matter of the fact is it all boils down to preference, it’s nice to hear justifications from different points of view :)

        • I don’ see how C arrays being computed values translate to NSArrays being computed values. That’s like assuming [NSString length] is O(N) because C strings are zero terminated.

          @proptery doesn’t have anything to do with proper KVO and KVC. The @synthesize (whether explicit or implicit) can make KVO/KVC complaint accessors, but there’s nothing preventing you from having a @property be backed with accessors that break KVO and KVC. And -count does work with KVC. Here’s a program with a -count, no @property, no KVO/KVC specifc code: https://gist.github.com/4595129 -valueForKey[Path] is quite explicit in how it looks for properties – looking for methods of particular names, then looking for instance variables of particular names. A bit of trivia, KVO/KVC existed before @property did.

          I’ll give you that one on count being a verb :-). The voices in my head treat it as a noun (like length for NSStrings).

  5. Raphael Schaad

    I once was debugging a deadlock that turned out the be caused by a dispatch_once.

    To avoid deadlocking on dispatch_once when called recursively, wrap the dispatch_once-block into a nil-check for the static variable pointing to the resource (in our case words).

    The initializer being called recursively seems to surface a suboptimal design but can happen (think large code base; complex initializer; jimmy the coder joins the team and modifies code that you smartly wrapped into a block to only dispatch once; …) and weather you should do it depends on what you execute inside the block and how defensive you want your code to be (deadlocking causes you to get killed by the watchdog, which results in a crash, which results in poor user experience, …).

    Best,
    Raphael

    PS Thought Experiment: The reason why this can occur actually seems like an implementation detail of dispatch_once: it creates a lightweight normal lock (Probably rightly so!) blocking the thread synchronously waiting for the block to return; if it would use a reentrant mutex (recursive lock), the second call on the same thread would not get stuck when trying to acquire the same lock again and just return nil.

  6. ????shinete

    Quit hard to understand to me. I had use dispatch_async before, but for once never use it. But great explain. It make me feel deep in obj-c. Thanks

  7. Charles Hart

    I’m interested in using a dispatch_once, but i’m a little unsure how it will work for my error handling. Suppose the loading of the file fails (in my case, it’s a much more likely network operation, but i’m interested in the problem generally speaking). In the process of error handling, at some point I will attempt the dispatch_once block again. Will i have issues with that? Thanks.

Leave a Comment

Join the discussion. Do not worry, your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>