Any thing can be a dictionary key? Yes, but with a price

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: