NSMutableDictionary Vs std::tr1::unordered_map

[David Chisnall]

Hi Everyone,

I'm not sure if this is interesting to anyone else, but I thought I'd share it 
anyway.

One of the interesting things about ARC is that it makes it trivial to use C++ 
collections with Objective-C objects: the compiler will insert the relevant 
read / write barriers on every assignment, including ones in templates.  This 
means that you can do things like std::map<int, __weak id> and get a map from 
integers to zeroing weak references to objects.  

With this in mind, I thought I'd see how GNUstep's NSMutableDictionary 
implementation held up against the C++ TR1 / C++0x unordered_map, as 
implemented in GNU libstdc++.  I generated a large array of NSNumber instances 
containing pseudorandom values, then populated each of the collections with 
them (same key and value) and then searched for each one.

The three collections I tested were:

- The stock NSMutableDictionary, as returned by +new
- A new NSMutableDictionary subclass (CXXMap), which is a thin wrapper around 
unordered_map
- Using unordered_map directly.

I tested on a couple of machines.  Unfortunately, modern CPUs are rubbish for 
benchmarking, because there is no longer a strong correlation between CPU 
seconds and work done.  My rough tests showed:

- Inserting into CXXMap was roughly 20-30% faster than inserting into 
NSMutableDictionary
- Searching CXXMap was about 10% faster than searching NSMutableDictionary
- The performance difference between CXXMap and using unordered_map directly 
was negligible.

I've attached my CXXMap code at the end of this email.  Feel free to use it in 
your own workloads and see if you see anything different.

David

-- Sent from my IBM 1620

namespace {
struct eqid
{
    bool operator()(const id s1, const id s2) const
    {
        return (s1 == s2) || [s1 isEqual: s2];
    }
};

struct hashid
{
    size_t operator()(const id s1) const
    {
        return (size_t)[s1 hash];
    }
};
}

@interface CXXMap : NSMutableDictionary
{
    std::tr1::unordered_map<id, id, hashid, eqid> map;
}
@end
@implementation CXXMap
- (void)setObject: (id)obj forKey: (id)key
{
    key = [key copy];
    map[key] = obj;
}
- (void)removeObjectForKey:(id)aKey
{
    map.erase(aKey);
}
- (NSUInteger)count
{
    return (NSUInteger)map.size();
}
- (id)objectForKey: (id)key
{
    return map[key];
}
@end