gistfile1.txt

import 'dart:typed_data';
class SmallMap {
  static const int MAX_ENTRIES=16;
  var keys=new List(MAX_ENTRIES);
  var hashCodes=new Int32List(MAX_ENTRIES);
  var values=new List(MAX_ENTRIES);
  var fallbackMap;
  int currentSize=0;
  // 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=["0000000000","1111111111","222222222","3333333333","4444444444","5555555555","6666666666","7777777777",
                     "8888888888","9999999999","aaaaaaaaaa","bbbbbbbbbb","ccccccccc","dddddddddd","eeeeeeeeee","ffffffffff"
];
final randomStringsCopy=new List<String>(randomStrings.length);
// to see what happens when strings are equal, but not identical
void initRandomStringsCopy() {
  for (int i=0; i<randomStrings.length; i++) {
    randomStringsCopy[i]=randomStrings[i].substring(0,1)+randomStrings[i].substring(1);
  }
}
testSmallMap(size) {
  var x=0;
  for (int i=0; i<ITERATIONS; i++) {
    var map=new SmallMap();
    for (int j=0; j<size; j++) {
      map[randomStrings[j]]=j;
    }
    
    for (int j=0; j<size; j++) {
       x|=map[randomStrings[j]];
    }
  }
  return x;
}
testStandardMap(size) {
  var x=0;
  for (int i=0; i<ITERATIONS; i++) {
    var map=new Map();
    for (int j=0; j<size; j++) {
      map[randomStrings[j]]=j;
    }
    
    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 elapsed time=$time milliseconds = ${1000000*time/(ITERATIONS*2*size)} nanoseconds/operation result=$x");
}
main() {
  initRandomStringsCopy();
   [6,8,10,12,14,16].forEach((size){
     run(testSmallMap,"small map",size);
     run(testStandardMap,"standard map",size);
   });

}