Testing (lookup) performance of different hash map algorithms for constant keys (pointer is hash)

README.md

Hash maps for Objective-C

A set of different implementations for solving the following use-case:

• Objective-C Objects map to heap-allocated keys (void*)
• Keys' addresses are constant, thus it's memory address can be used instead of a calculated hash
• Writes can be expensive
• Reads must be fast and inexpensive

Conclusions

• NSDictionary is not very suitable for this use-case as reads are on average 2x slower than HHashMap and 5x slower than HUnorderedMap.
• HHashMap is slower than HUnorderedMap even though they are based on the same algorithm. HHashMap spends 40% of its time in CFBasicHashFindBucket, 10% in its "callback" functions (returning the hash int value) and 10% in objc_msgSend. This means roughly 20% overhead for using Objective-C (message passing, internal selector-to-implementation lookup).
• For this use-case, use HUnorderedMap (or std::tr1::unordered_map straight up).

MIT license

Copyright (c) 2010 Rasmus Andersson http://hunch.se/

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

cocoa-hash-map-tests.sh

#
# - HUnorderedMap is a C++ class with cocoa support wrapping
#   std::tr1::unordered_map
#
# - HHashMap is a Objective-C class wrapping the "classic" (C) NSHashTable
#
# - NSDictionary is a standard NSMutableDictionary. It should be noted that this
#   is implemented using a red-black tree (AFAIK) and not a hash table
#
$ time ./nshashtable-test hunorderedmap 1000000 1000 && time ./nshashtable-test hhashmap 1000000 1000 && time ./nshashtable-test nsdictionary 1000000 1000
running hunorderedmap with 1000000 objects in 1000 iterations
real	0m51.256s
user	0m50.820s
sys	0m0.368s
running hhashmap with 1000000 objects in 1000 iterations
real	2m16.145s
user	2m14.844s
sys	0m0.478s
running nsdictionary with 1000000 objects in 1000 iterations
real	4m17.856s
user	4m16.099s
sys	0m0.764s

HUnorderedMap.hh

#ifndef H_UNORDERED_MAP_
#define H_UNORDERED_MAP_

#import <tr1/unordered_map>

template<class K, class T>
class HUnorderedMap {
 public:
  typedef typename std::tr1::unordered_map<K, T > Map;
  typedef typename Map::value_type ValueType;
  typedef typename Map::const_iterator ConstIterator;
  typedef typename Map::iterator Iterator;

 protected:
  Map map_;
 
 public:
  HUnorderedMap(size_t nbuckets=0) : map_(nbuckets) { }
  virtual ~HUnorderedMap() {
    // TODO: release all
  }
  
  inline void put(K key, T value) {
    map_.insert(ValueType(key, value));
  }
  
  inline T get(K key) {
    Iterator it = map_.find(key);
    return (it != map_.end()) ? it->second : NULL;
  }
};

#endif  // H_UNORDERED_MAP_

main.mm

#import <Foundation/Foundation.h>
#import <err.h>
#import "HUnorderedMap.h"

@interface HHashMapEntry : NSObject {
 @public
  void const *key;
  id object;
}
@end
@implementation HHashMapEntry

- (id)initWithObject:(id)obj forKey:(void const *)k {
  self = [super init];
  key = k;
  object = [obj retain];
  return self;
}

- (void)dealloc {
  [object release];
  [super dealloc];
}

- (NSUInteger)hash {
  return (pointer_t)key;
}

- (BOOL)isEqual:(HHashMapEntry*)other {
  return [self hash] == [other hash];
}

- (NSString*)description {
  return [NSString stringWithFormat:@"<%@: {%p => %@}>",
                                    NSStringFromClass([self class]),
                                    key, object];
}

@end


static NSUInteger khm_hash(NSHashTable *table, const void *ptr) {
  return [(id)ptr hash];
}

static BOOL khm_isEqual(NSHashTable *table, const void *a, const void *b) {
  return [(id)a isEqual:(id)b];
}

static void khm_retain(NSHashTable *table, const void *ptr) {
  [(id)ptr retain];
}

static void khm_release(NSHashTable *table, void *ptr) {
  [(id)ptr release];
}

static NSString *khm_describe(NSHashTable *table, const void *ptr) {
  return [(id)ptr description];
}

static const NSHashTableCallBacks khm_callbacks = {
  khm_hash,
  khm_isEqual,
  khm_retain,
  khm_release,
  khm_describe
};

/**
 * Universal hash map (and table)
 *
 * How to provide a custom entry type:
 *
 * 1. Create a subclass of HHashMapEntry
 *    1.1. Overload hash and optionally isEqual:
 *
 * 2.a. Initialize a new HHashMap using initWithCapacity:entryClass: passing
 *      [MyHashMapEntry class] as the last argument.
 * -- or --
 * 2.b. Create a subclass of HHashMap and overload initWithCapacity: to call
 *      [self initWithCapacity:initialCapacity
 *                  entryClass:[MyHashMapEntry class]];
 *
 */
@interface HHashMap : NSObject {
  NSHashTable* ht_;
  HHashMapEntry* lookupEntry_;
  Class entryClass_;
  unsigned long revision_;
}

/// Monotonically increasing for each change to this map
@property(readonly, nonatomic) unsigned long revision;

/// Initialize with initial capacity and custom entry class
- (id)init; // initialCapacity=0
- (id)initWithCapacity:(NSUInteger)initialCapacity;
- (id)initWithCapacity:(NSUInteger)initialCapacity entryClass:(Class)entryClass;

/// Set object for the specified key, possibly replacing an existing entry.
- (void)setObject:(id)object forKey:(void const *)key;
- (void)setEntry:(HHashMapEntry*)entry;

/**
 * Set object for the specified key only if the key does not exist in this map,
 * in which case the existing object is returned. Returns nil if inserted.
 */
- (id)setOrFetchObject:(id)object forKey:(void const *)key;
- (HHashMapEntry*)setOrFetchEntry:(HHashMapEntry*)entry;

/**
 * Set object for key. Unlike setObject:forKey:, this method raises
 * NSInvalidArgumentException if map already includes the key.
 */
- (void)setKnownAbsentObject:(id)object forKey:(void const *)key;
- (void)setKnownAbsentEntry:(HHashMapEntry*)entry;

/// Returns an object associated with key or nil if not found.
- (id)objectForKey:(void const *)key;
- (HHashMapEntry*)entryForKey:(void const *)key;

- (NSUInteger)count;  /// Number of entries

- (NSArray*)entries;
- (NSIndexSet*)keys;
- (NSArray*)objects;

/// Fast enumeration over entries: for (HHashMapEntry *entry in map) {...}
- (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state
                                  objects:(id *)stackbuf
                                    count:(NSUInteger)len;

/// Remove any entry associated with key
- (void)removeEntryForKey:(void const *)key;

/// Empties the map of its entries
- (void)removeAllEntries;

@end
@implementation HHashMap

@synthesize revision = revision_;

- (id)initWithCapacity:(NSUInteger)initialCapacity entryClass:(Class)entryClass{
  self = [super init];
  ht_ = NSCreateHashTable(khm_callbacks, initialCapacity);
  if (!entryClass) {
    entryClass_ = [HHashMapEntry class];
  } else if (![entryClass isKindOfClass:[HHashMapEntry class]]) {
    [NSException raise:NSInvalidArgumentException
                format:@"entryClass is not a subclass of HHashMapEntry"];
  } else {
    entryClass_ = entryClass;
  }
  lookupEntry_ = [entryClass_ alloc];
  return self;
}

- (id)initWithCapacity:(NSUInteger)initialCapacity {
  return [self initWithCapacity:initialCapacity entryClass:nil];
}

- (id)init {
  return [self initWithCapacity:0];
}

- (void)dealloc {
  NSFreeHashTable(ht_);
  ht_ = nil;
  [lookupEntry_ release];
  [super dealloc];
}

- (void)setEntry:(HHashMapEntry*)entry {
  NSHashInsert(ht_, (const void *)entry);
  revision_++;
}

- (void)setObject:(id)object forKey:(void const *)key {
  HHashMapEntry *entry =
      [[entryClass_ alloc] initWithObject:object forKey:key];
  [self setEntry:entry];
  [entry release];
}

- (HHashMapEntry*)setOrFetchEntry:(HHashMapEntry*)entry {
  entry = (HHashMapEntry*)NSHashInsertIfAbsent(ht_, (const void *)entry);
  if (entry) return entry; // no-op
  revision_++;
  return nil;
}

- (id)setOrFetchObject:(id)object forKey:(void const *)key {
  HHashMapEntry *entry =
      [[entryClass_ alloc] initWithObject:object forKey:key];
  HHashMapEntry *existingEntry = [self setOrFetchEntry:entry];
  [entry release];
  return existingEntry ? existingEntry->object : nil;
}

- (void)setKnownAbsentEntry:(HHashMapEntry*)entry {
  NSHashInsertKnownAbsent(ht_, (const void *)entry);
  revision_++;
}

- (void)setKnownAbsentObject:(id)object forKey:(void const *)key {
  // autoreleased since setKnownAbsentEntry: might throw
  HHashMapEntry *entry =
      [[[entryClass_ alloc] initWithObject:object forKey:key] autorelease];
  [self setKnownAbsentEntry:entry];
}

- (HHashMapEntry*)entryForKey:(void const *)key {
  lookupEntry_->key = key;
  return (HHashMapEntry*)NSHashGet(ht_, lookupEntry_);
}

- (id)objectForKey:(void const *)key {
  lookupEntry_->key = key;
  HHashMapEntry *entry = (HHashMapEntry*)NSHashGet(ht_, lookupEntry_);
  return entry ? entry->object : nil;
}

- (NSUInteger)count {
  return NSCountHashTable(ht_);
}

- (NSArray*)entries {
  return NSAllHashTableObjects(ht_);
}

- (NSIndexSet*)keys {
  NSMutableIndexSet* keys = [NSMutableIndexSet indexSet];
  NSHashEnumerator enumerator = NSEnumerateHashTable(ht_);
  HHashMapEntry *entry;
  while ((entry = (HHashMapEntry*)NSNextHashEnumeratorItem(&enumerator))) {
    [keys addIndex:(pointer_t)entry->key];
  }
  NSEndHashTableEnumeration(&enumerator);
  return keys;
}

- (NSArray*)objects {
  NSUInteger count = NSCountHashTable(ht_), index = 0;
  NSMutableArray* objects = [NSMutableArray arrayWithCapacity:count];
  if (count != 0) {
    NSHashEnumerator enumerator = NSEnumerateHashTable(ht_);
    HHashMapEntry *entry;
    while ((entry = (HHashMapEntry*)NSNextHashEnumeratorItem(&enumerator))) {
      [objects insertObject:entry->object atIndex:index++];
    }
    NSEndHashTableEnumeration(&enumerator);
  }
  return objects;
}


- (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state
                                  objects:(id *)stackbuf
                                    count:(NSUInteger)fetchCount {
  NSArray *entries;
  
  if (state->state == 0) {
    // - (void)getObjects:(id *)aBuffer range:(NSRange)aRange
    state->mutationsPtr = (unsigned long *)&revision_;
    // entries is autorelease, thus a mutation exception should not cause leaks
    entries = NSAllHashTableObjects(ht_);
    state->extra[0] = (pointer_t)entries;
    state->extra[1] = [entries count];
  } else {
    entries = (NSArray *)state->extra[0];
  }
  
  if (state->state < state->extra[1]) {
    // Copy entry pointers
    fetchCount = MIN(fetchCount, state->extra[1] - state->state);
    NSRange fetchRange = NSMakeRange(state->state, fetchCount);
    [entries getObjects:stackbuf range:fetchRange];
    state->state += fetchCount;
    state->itemsPtr = stackbuf;
    return fetchCount;
  }
  
  // We've already provided all our items, so we signal we are done by returning 0.
  return 0;
}


- (void)removeEntryForKey:(void const *)key {
  lookupEntry_->key = key;
  NSHashRemove(ht_, lookupEntry_);
  revision_++; // _possibly_ mutated, but better be sure
}

- (void)removeAllEntries {
  NSResetHashTable(ht_);
  revision_++; // _possibly_ mutated, but better be sure
}

- (NSString*)description {
  return NSStringFromHashTable(ht_);
}

@end


//#import <map>



#define DLOG(...) ((void)0)
#ifndef DLOG
#define DLOG(fmt, ... ) NSLog(@fmt, ##__VA_ARGS__)
#endif

void test_hunorderedmap(NSString const **keys, id *objects, int count, int iterations) {
  HUnorderedMap<void const*,id> *kpht = new HUnorderedMap<void const*,id>();

  // write
  for (int i=count;i--;) {
    kpht->put((void const *)keys[i], objects[i]);
  }
  
  for (int x=iterations;x--;) {
    // read
    for (int i=count;i--;) {
      id object = kpht->get((const void *)keys[i]);
      if (objects[i] != object)
        [NSException raise:NSInvalidArgumentException
                    format:@"objects[i] != object"];
    }
  }
}

void test_hhashmap(NSString const **keys, id *objects, int count, int iterations) {
  HHashMap *hmap = [HHashMap new];
  /*
  NSString const * key1 = [NSString stringWithString:@"key1"];
  NSString const * key2 = [NSString stringWithString:@"key2"];
  NSString const * key3 = [NSString stringWithString:@"key3"];
  [hmap setObject:@"object1" forKey:key1];
  [hmap setObject:@"object2" forKey:key2];
  [hmap setObject:@"object3" forKey:key3];
  DLOG("objectForKey:%@ => %@", key1, [hmap objectForKey:key1]);
  DLOG("objectForKey:%@ => %@", key2, [hmap objectForKey:key2]);
  DLOG("objectForKey:%@ => %@", key3, [hmap objectForKey:key3]);
  [hmap setObject:@"object333" forKey:key3];
  DLOG("objectForKey:%@ => %@", key3, [hmap objectForKey:key3]);
  DLOG("keys => %@", [hmap keys]);
  DLOG("objects => %@", [hmap objects]);*/
  
  // write
  for (int i=count;i--;) {
    [hmap setObject:objects[i] forKey:keys[i]];
  }
  
  for (int x=iterations;x--;) {
    // read
    for (int i=count;i--;) {
      id object = [hmap objectForKey:keys[i]];
      if (objects[i] != object)
        [NSException raise:NSInvalidArgumentException
                    format:@"objects[i] != object"];
    }
  }
  
  // enumerate and write
  /*HHashMap *seen = [HHashMap new];
  for (HHashMapEntry *entry in hmap) {
    [seen setKnownAbsentEntry:entry];
    //DLOG("entry: %@", entry);
  }*/
  
  DLOG("done");
}


void test_nsdictionary(NSString const **keys, id *objects, int count, int iterations) {
  NSMutableDictionary *dict = [NSMutableDictionary new];

  // write
  for (int i=count;i--;) {
    [dict setObject:objects[i] forKey:keys[i]];
  }
  
  for (int x=iterations;x--;) {
    // read
    for (int i=count;i--;) {
      id object = [dict objectForKey:keys[i]];
      if (objects[i] != object)
        [NSException raise:NSInvalidArgumentException
                    format:@"objects[i] != object"];
    }
  }
  
  /*NSMutableDictionary *seen = [NSMutableDictionary new];
  [dict enumerateKeysAndObjectsUsingBlock:^(id key, id obj, BOOL *stop){
    [seen setObject:obj forKey:key];
  }];*/
}


int main (int argc, const char * argv[]) {
  NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
  const char *testname = argc > 1 ? argv[1] : "hunorderedmap";
  int count = 100000;
  int iterations = 1000;
  if (argc > 2) count = atoi(argv[2]);
  if (argc > 3) iterations = atoi(argv[3]);
  if (iterations < 1) {
    fprintf(stderr, "error: less than 1 iterations\n");
    exit(1);
  }
  void (*testfun)(NSString const**,id*,int,int) = NULL;
  if (strcasecmp(testname, "hunorderedmap") == 0) {
    testfun = test_hunorderedmap;
  } else if (strcasecmp(testname, "hhashmap") == 0) {
    testfun = test_hhashmap;
  } else if (strcasecmp(testname, "nsdictionary") == 0) {
    testfun = test_nsdictionary;
  } else {
    errx(1, "unknown test %s -- see source code for details.", testname);
  }
  
  // create key symbols
  NSString const **keys =
      (NSString const **)CFAllocatorAllocate(NULL, sizeof(id)*count, 0);
  id *objects = (id*)CFAllocatorAllocate(NULL, sizeof(id)*count, 0);
  for (int i=count;i--;) {
    keys[i] = [NSString stringWithFormat:@"key%d", i];
    objects[i] = [NSString stringWithFormat:@"object%d", i];
  }

  printf("running %s with %d objects in %d iterations",
         testname, count, iterations);
  testfun(keys, objects, count, iterations);

  [pool drain];
  return 0;
}