Small map

gistfile1.dart

// Copyright (c) 2015, <your name>. All rights reserved. Use of this source code
// is governed by a BSD-style license that can be found in the LICENSE file.

import 'dart:typed_data';

const int MAX_ENTRIES=16;

class SmallMap {
  var keys=new List(MAX_ENTRIES);
  var hashCodes=new Int32List(MAX_ENTRIES);
  var values=new List(MAX_ENTRIES);
  var fallbackMap;
  int currentSize=0;
  
  int _findIndexMtf(hashCode) {
    int i=0;
    for (; i<currentSize; ++i) {
      if (hashCodes[i] == hashCode) break;
    }
    if (i < currentSize) {
      if (i > 0) {
        int t = hashCodes[0];
        hashCodes[0] = hashCodes[i];
        hashCodes[i] = t;
      }
      return i;
    }
    return -1;
  }
  
  // Turns out, meet-in-the middle search really helps! Improvement is quite visible on size 16
  int _findIndex(hashCode) {
     for (int i=0, j=currentSize-1; j>=i; i++, j--) {
        if (hashCodes[i]==hashCode) return i;
        if (hashCodes[j]==hashCode) return j;
     }
     return -1;
  }
  
  _createFallback() {
    print ("creating fallback!");
    fallbackMap=new Map();
    for (int i=0; i<currentSize; i++) {
      fallbackMap[keys[i]]=values[i];
    }
  }
  operator [](key) {
     if (fallbackMap!=null) {
       return fallbackMap[key];
     }
     int index=_findIndex(key.hashCode);
     return index>=0 && keys[index]==key ? values[index] : null;
  }
  operator []=(key,value) {
    if (fallbackMap!=null) {
      fallbackMap[key]=value;
      return;
    }
    int hashCode=key.hashCode;    
    int index=_findIndex(hashCode);
    // there are 3 cases: 1) adding new key 2) replacing value for old key 3) fallback
    // case 1) is statistically most important so we try it first
    // NOTE: don't "optimize" the redandant comparison of index with 0, it's intentional
    if (index<0 && currentSize<MAX_ENTRIES) { // case 1: new key
      keys[currentSize]=key;
      values[currentSize]=value;
      hashCodes[currentSize]=hashCode;
      currentSize++;
    } else if (index>=0 && keys[index]==key) { // case 2: replacement
      values[index]=value;
    } else { // case 3: fallback
      _createFallback();
      fallbackMap[key]=value;
    }
  }
}
const int ITERATIONS=1000000;

final randomStrings = new List(MAX_ENTRIES);

createRndStrings(int len) {
  for (int i=0; i<MAX_ENTRIES; i++) {
    randomStrings[i] = "$i" * len;
  }
}

testSmallMapFill(size) {
  var x=0;
  var map=new SmallMap();
  for (int i=0; i<ITERATIONS; i++) {
    for (int j=0; j<size; j++) {
      map[randomStrings[j]]=j;
      ++x;
    }
  }
  return x;
}

testSmallMapLookup(size) {
  var x=0;
  var map=new SmallMap();
  for (int j=0; j<size; j++) {
    map[randomStrings[j]]=j;
  }
  for (int i=0; i<ITERATIONS; i++) {
    for (int j=0; j<size; j++) {
       x|=map[randomStrings[j]];
    }
  }
  return x;
}

testStandardMapFill(size) {
  var x=0;
  var map=new Map();
  for (int i=0; i<ITERATIONS; i++) {
    for (int j=0; j<size; j++) {
      map[randomStrings[j]]=j;
      ++x;
    } 
  }
  return x;
}

testStandardMapLookup(size) {
  var x=0;
  var map=new Map();
  for (int j=0; j<size; j++) {
    map[randomStrings[j]]=j;
  } 
  for (int i=0; i<ITERATIONS; i++) {
    for (int j=0; j<size; j++) {
       x|=map[randomStrings[j]];
    }
  }
  return x;
}
run(func, name, size) {
  int time, x; // saving result to print, to make sure nothing is optimized away miraculously
  for (int i=0; i<3; i++) {
    int start=new DateTime.now().millisecondsSinceEpoch;
    x=func(size);
    time=new DateTime.now().millisecondsSinceEpoch-start;
  }
  print("$name size: $size time: $time ms (${1000000*time/(ITERATIONS*2*size)} ns/op)");
}
main() {
  createRndStrings(2);
   [1,2,4,6,8,10,12,14,16].forEach((size){
     run(testSmallMapFill,"sml map fill",size);
     run(testStandardMapFill,"std map fill",size);
     run(testSmallMapLookup,"sml map look",size);
     run(testStandardMapLookup,"std map look",size);
     print("");
   });
 
}