I like to talk about the difference between different NSDictionary keys. I know it’s cliché.[1]
We all know that building a dictionary is slower than querying it, and that the time it takes to insert or update values depends on the hash function of the key – the interesting part is how incredibly inefficient the hashes of built in objective-c components can be.
I first noticed it when I was working on a new landscape week view for Cal. I was using a third party library, and while instrumenting I noticed that a certain method in this library was taking a surprisingly large amount of time.
When I inspected this method I saw that all it did was building a dictionary (of about 2000 items), and that the keys that it was using was NSIndexPath – a very simple native class (just a section and row integers). I tried replacing the key with an NSNumber hash of the indexPath and saw a 100 times (!) improvement in the performance of the method.
Most of my dictionaries use either strings, numbers or dates as keys, but I also had a rather small dictionary (20-30 keys) that was using a UIColor as a key, so I decided to do a small benchmark of these key types.
Personally – I was rather shocked by the results:
building dictionary with datesArray for 1000 items took Time: 0.001115 seconds querying dictionary with datesArray for 1000 items took Time: 0.000096 seconds building dictionary with stringsArray for 1000 items took Time: 0.001470 seconds querying dictionary with stringsArray for 1000 items took Time: 0.000098 seconds building dictionary with intsArray for 1000 items took Time: 0.001840 seconds querying dictionary with intsArray for 1000 items took Time: 0.000104 seconds building dictionary with indexPathsArray for 1000 items took Time: 0.030987 seconds querying dictionary with indexPathsArray for 1000 items took Time: 0.000101 seconds building dictionary with colorDataArray for 1000 items took Time: 0.196662 seconds querying dictionary with colorDataArray for 1000 items took Time: 0.002577 seconds building dictionary with datesArray for 10000 items took Time: 0.014806 seconds querying dictionary with datesArray for 10000 items took Time: 0.000111 seconds building dictionary with stringsArray for 10000 items took Time: 0.014884 seconds querying dictionary with stringsArray for 10000 items took Time: 0.000107 seconds building dictionary with intsArray for 10000 items took Time: 0.017746 seconds querying dictionary with intsArray for 10000 items took Time: 0.000105 seconds building dictionary with indexPathsArray for 10000 items took Time: 1.441603 seconds querying dictionary with indexPathsArray for 10000 items took Time: 0.000100 seconds building dictionary with colorDataArray for 10000 items took Time: 28.365735 seconds querying dictionary with colorDataArray for 10000 items took Time: 0.002187 seconds
As you can see, while all key types take about the same to query, the differences in building the dictionary are incredible. Using a simple class as NSIndexPath is a 100 times slower than using a string, and using a UIColor is over 2000 times slower!
Needless to say, in my app I changed both the NSIndexPath and UIColor hashes to custom hashes which made a noticeable improvement in the overall performance in my app.
To conclude – even though the purpose of a dictionary is to improve the fetch time, a lot of times it’s also important to watch the build (or update) times. And most importantly, don’t assume that Apple engineers write good hashes 🙂
[1] A quote by the hilarious Mitch Hedberg. If you don’t know who he is – stop coding immediately and watch this show. Your welcome.
Core-Cocoa 