7 ms·

TheKitchenSync - A Tool Belt for iOS Concurrency

34 points by asarazan 13y ago

asarazan 13y ago
As a small post-mortem, one interesting thing we learned while building this library: The reason Apple never included a read/write lock. They're hard to get right (probably not a problem for Apple), and their overhead usually counterbalances any potential performance gains (possibly a problem for the unwary developer). We've got some optimization work to do :-)
- coolsunglasses 13y ago
  As opposed to what?
  - asarazan 13y ago
    As opposed to using a simple or recursive mutex while forgoing concurrent reads, in this case. There was an order of magnitude speed difference in raw lock/unlock performance. Obviously this can still be useful in read-heavy systems where the lock has to be held for long spans, but for our synchronized collections, we switched to std::mutex, which was massively faster.
    - mikeash 13y ago
      Have you tried GCD barriers for this? A custom parallel queue basically gives you a reader/writer lock, with dispatch_sync or _async acting as a reader lock, and dispatch_sync_barrier or _async_barrier acting as a writer lock. GCD has a heavy emphasis on performance so I'd be interested to know how the speed of that approach is.
      - asarazan 13y ago
        Fascinating. I'll have to give that a shot. Thanks!
        blakewatters 13y ago
        I recently reimplemented some of the caches within RestKit using a `NSMutableDictionary` guarded by a dispatch queue instead of a `NSCache`/`NSMutableDictionary` + `NSRecursiveLock`. The general idea is that you use a concurrent dispatch queue to provide concurrent read access and then use barriers to obtain an exclusive write lock to the resource. There were significant performance benefits from the change as I was able to shift the cache updates on a miss into the background. The dispatch queue approach also outperformed `NSCache` significantly under the workloads I was testing -- it appears that some of its internal calculations on add/remove can be quite costly if you are adding/removing rapidly. Its also very flexible, as you can do `dispatch_sync` if you need a synchronous fetch of the resource or use callback blocks to go as async as possible.
        asarazan 13y ago
        I've been thinking about this since yesterday, and it seems like a really good solution for some use cases, but isn't there quite a bit of overhead to using a dispatche queue for fine-grained operations? I mean it seems like the overhead of cross-thread communication would severely outweigh a simple synchronous lock call. Then again, if you can do things like background non-essential operations, then the higher-level benefits can probably outweigh that.
        mikeash 13y ago
        Like I said, GCD has a heavy emphasis on performance. For example, a dispatch_sync will involve no cross-thread communication in the uncontended case, and the cost is comparable to taking a spinlock. A bit heavier, but not too much. dispatch_async will necessarily be slower, but don't overestimate how much work is really going to happen in the cases where it matters.
  - pjscott 13y ago
    As opposed to an ordinary lock which can be acquired only once. Compared to that, a read/write lock can have significantly lower lock contention, since multiple readers can acquire it at once.
- PaulHoule 13y ago
  It's pretty well known that reader-writer locks don't really work.
stcredzero 13y ago
What about a subset of Hoare's CSP, as in Golang/Erlang? Objective-C already has support for immutables. How hard would it be to implement channels?
- asarazan 13y ago
  That would certainly be an interesting project, although the performance implications on a mobile platform may be an issue (although that's becoming more moot with each generation). In this case, however, our goal was to take common, familiar interfaces and idioms in Objective C, and make them safer/more powerful. Something more like channels-like would be quite useful, but it would likely be published under a different project.
rogerbinns 13y ago
I love that Objective C/Foundation provides a distinction between mutable and non-mutable collections and tends to favour the latter. (I also hate they make it impossible to test which a collection is.) Pet peeve: "insure" is used on the page. For some bizarre reasons Americans use that word when they mean "ensure". The difference is very important - insure is when you don't want something to happen and ensure is when you do!
- asarazan 13y ago
  Hah, good catch! Fixing.
- andrewroycarter 13y ago
  You can test easily! [array isKindOfClass:[NSMutableArray class]] or [array respondsToSelector:@selector(insertObject:)]
  - rogerbinns 13y ago
    Have you actually tried it? Because the people who have (me included) found that both tests will return YES, yet when you try a mutable operation you get an exception. http://stackoverflow.com/questions/1788690/objective-c-how-to-check-if-variable-is-nsarray-or-nsmutablearray http://stackoverflow.com/questions/1788690/objective-c-how-t... http://www.cocoabuilder.com/archive/cocoa/224795-nsdictionary-mutability-test.html http://www.cocoabuilder.com/archive/cocoa/224795-nsdictionar...
  - blakewatters 13y ago
    You cannot use `isKindOfClass:` to introspect an array like this. Most of the toll-free bridged foundation classes such as arrays/dictionaries/sets are implemented as class clusters.
- aaronbrethorst 13y ago
  they make it impossible to test which a collection is. Couldn't you just test with the following? // NSMutableDictionary [dict respondsToSelector:@selector(setObject:forKey:] // NSMutableArray [arr respondsToSelector:@selector(addObject:)] // NSMutableString [str respondsToSelector:@selector(replaceCharactersInRange:withString:)] // NSMutableSet [set respondsToSelector:@selector(addObject:)] Although, personally, I'd rather just, either at the class or method boundary depending on the circumstances, only expose the non-mutable variants.

34 points by asarazan 13y ago

As a small post-mortem, one interesting thing we learned while building this library: The reason Apple never included a read/write lock. They're hard to get right (probably not a problem for Apple), and their overhead usually counterbalances any potential performance gains (possibly a problem for the unwary developer). We've got some optimization work to do :-)

coolsunglasses 13y ago
As opposed to what?
- asarazan 13y ago
  As opposed to using a simple or recursive mutex while forgoing concurrent reads, in this case. There was an order of magnitude speed difference in raw lock/unlock performance. Obviously this can still be useful in read-heavy systems where the lock has to be held for long spans, but for our synchronized collections, we switched to std::mutex, which was massively faster.
  - mikeash 13y ago
    Have you tried GCD barriers for this? A custom parallel queue basically gives you a reader/writer lock, with dispatch_sync or _async acting as a reader lock, and dispatch_sync_barrier or _async_barrier acting as a writer lock. GCD has a heavy emphasis on performance so I'd be interested to know how the speed of that approach is.
    - asarazan 13y ago
      Fascinating. I'll have to give that a shot. Thanks!
      - blakewatters 13y ago
        I recently reimplemented some of the caches within RestKit using a `NSMutableDictionary` guarded by a dispatch queue instead of a `NSCache`/`NSMutableDictionary` + `NSRecursiveLock`. The general idea is that you use a concurrent dispatch queue to provide concurrent read access and then use barriers to obtain an exclusive write lock to the resource. There were significant performance benefits from the change as I was able to shift the cache updates on a miss into the background. The dispatch queue approach also outperformed `NSCache` significantly under the workloads I was testing -- it appears that some of its internal calculations on add/remove can be quite costly if you are adding/removing rapidly. Its also very flexible, as you can do `dispatch_sync` if you need a synchronous fetch of the resource or use callback blocks to go as async as possible.
        asarazan 13y ago
        I've been thinking about this since yesterday, and it seems like a really good solution for some use cases, but isn't there quite a bit of overhead to using a dispatche queue for fine-grained operations? I mean it seems like the overhead of cross-thread communication would severely outweigh a simple synchronous lock call. Then again, if you can do things like background non-essential operations, then the higher-level benefits can probably outweigh that.
        mikeash 13y ago
        Like I said, GCD has a heavy emphasis on performance. For example, a dispatch_sync will involve no cross-thread communication in the uncontended case, and the cost is comparable to taking a spinlock. A bit heavier, but not too much. dispatch_async will necessarily be slower, but don't overestimate how much work is really going to happen in the cases where it matters.
- pjscott 13y ago
  As opposed to an ordinary lock which can be acquired only once. Compared to that, a read/write lock can have significantly lower lock contention, since multiple readers can acquire it at once.
PaulHoule 13y ago
It's pretty well known that reader-writer locks don't really work.

stcredzero 13y ago

What about a subset of Hoare's CSP, as in Golang/Erlang? Objective-C already has support for immutables. How hard would it be to implement channels?

asarazan 13y ago
That would certainly be an interesting project, although the performance implications on a mobile platform may be an issue (although that's becoming more moot with each generation). In this case, however, our goal was to take common, familiar interfaces and idioms in Objective C, and make them safer/more powerful. Something more like channels-like would be quite useful, but it would likely be published under a different project.

rogerbinns 13y ago

I love that Objective C/Foundation provides a distinction between mutable and non-mutable collections and tends to favour the latter. (I also hate they make it impossible to test which a collection is.) Pet peeve: "insure" is used on the page. For some bizarre reasons Americans use that word when they mean "ensure". The difference is very important - insure is when you don't want something to happen and ensure is when you do!

asarazan 13y ago
Hah, good catch! Fixing.
andrewroycarter 13y ago
You can test easily! [array isKindOfClass:[NSMutableArray class]] or [array respondsToSelector:@selector(insertObject:)]
- rogerbinns 13y ago
  Have you actually tried it? Because the people who have (me included) found that both tests will return YES, yet when you try a mutable operation you get an exception. http://stackoverflow.com/questions/1788690/objective-c-how-to-check-if-variable-is-nsarray-or-nsmutablearray http://stackoverflow.com/questions/1788690/objective-c-how-t... http://www.cocoabuilder.com/archive/cocoa/224795-nsdictionary-mutability-test.html http://www.cocoabuilder.com/archive/cocoa/224795-nsdictionar...
- blakewatters 13y ago
  You cannot use `isKindOfClass:` to introspect an array like this. Most of the toll-free bridged foundation classes such as arrays/dictionaries/sets are implemented as class clusters.
aaronbrethorst 13y ago
they make it impossible to test which a collection is. Couldn't you just test with the following? // NSMutableDictionary [dict respondsToSelector:@selector(setObject:forKey:] // NSMutableArray [arr respondsToSelector:@selector(addObject:)] // NSMutableString [str respondsToSelector:@selector(replaceCharactersInRange:withString:)] // NSMutableSet [set respondsToSelector:@selector(addObject:)] Although, personally, I'd rather just, either at the class or method boundary depending on the circumstances, only expose the non-mutable variants.