Re: Optimizing NSMutableDictionary Speed
Re: Optimizing NSMutableDictionary Speed
- Subject: Re: Optimizing NSMutableDictionary Speed
- From: Timothy Ritchey <email@hidden>
- Date: Fri, 11 Apr 2003 14:40:29 -0500
Ignoring the memory issue for the moment, the key to having good
NSDictionary performance is having a good -hash implementation in your
key object to ensure an even distribution of hash values. You can use
any object as the key, and implement your own -hash function. Just for
reference, the string hash value is based on a permutation of the first
two and last two characters in the string. If your IDs don't vary much
in these two ranges, you will have a few collisions that could cause
you performance problems.
The dictionary hash table is kept at no more than ~67% capacity to
ensure a low probability of a collision, For a million key/value
pairs, you will be using a few MB of extra memory that is just sitting
empty. The dictionary tables are sized as power-of-two, and
automatically grow as you add objects. As you cross the 67% capacity
threshold, the dictionary will resize itself. When it does, it must
rehash every single key, which is a bummer. If you KNOW you will be
using a large, fixed size dictionary, and have the room to spare, you
can create a fixed-size mutable dictionary, which is a bit faster than
a regular mutable dictionary. You have to get into the CF routines, but
a quick example of a 1024 item fixed-mutable dictionary is:
NSMutableDictionary *dict
= (NSMutableDictionary*)CFDictionaryCreateMutable(NULL, 1024,
&kCFTypeDictionaryKeyCallBacks,
&kCFTypeDictionaryValueCallBacks);
Just a note: this is NOT the same as calling -initWithCapacity, which
just gives you a normal mutable dictionary, but with a higher initial
capacity. The underlying CFDictionary code uses a couple different
implementations, including a mutable, and a fixed-mutable version. The
fixed mutable version avoids some work, and so is slightly faster. But,
you have to use the CF routines to make it. You end up with a toll-free
bridged NSMutableDictionary in any case.
Cheers,
tim
On Friday, April 11, 2003, at 10:20 AM, John Nairn wrote:
I am thinking of converting an application to Cocoa that may deal with
a large number of records. The data model fits logically into an
NSMutableDictionary with record IDs (which are unique) as keys. The
concern is how NSMutableDictionary will respond to frequent searching
by key? Typically files will have thousands of records; and an extreme
file might have a million records. Use of the application will require
frequent location of records by key.
All code examples I have seen use NSString's for keys in dictionaries,
but the documentation alludes to keys being any kind of object as long
as it responds to certain protocols. Are there ways to improve the
efficiency of dictionaries by defining key objects that might get
located faster?
------------
John Nairn (1-801-581-3413, FAX: 1-801-581-4816)
Web page: http://www.mse.utah.edu/~nairn
_______________________________________________
cocoa-dev mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/cocoa-dev
Do not post admin requests to the list. They will be ignored.
_______________________________________________
cocoa-dev mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/cocoa-dev
Do not post admin requests to the list. They will be ignored.