Created
March 3, 2015 19:27
-
-
Save mdakin/01aa816093a9259513c6 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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'; | |
import 'dart:profiler'; | |
const int MAX_ENTRIES=16; | |
UserTag linearSearchTag = new UserTag('Linear Search'); | |
UserTag lookup = new UserTag('lookup'); | |
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; | |
// Turns out, meet-in-the middle search really helps! Improvement is quite visible on size 16 | |
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; | |
} | |
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]; | |
} | |
} | |
UserTag linearSearchTag = new UserTag('Linear Search'); | |
operator [](key) { | |
if (fallbackMap!=null) { | |
return fallbackMap[key]; | |
} | |
int hash = key.hashCode; | |
var prevTag = linearSearchTag.makeCurrent(); | |
int index=_findIndex(hash); | |
prevTag.makeCurrent(); | |
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=10000000; | |
final randomStrings = new List(MAX_ENTRIES); | |
createRndStrings(int len) { | |
for (int i=0; i<MAX_ENTRIES; i++) { | |
randomStrings[i] = "${i.toRadixString(16)}" * len; | |
print ("Rand string: ${randomStrings[i]}"); | |
} | |
} | |
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, iters) { | |
var x=0; | |
var map=new SmallMap(); | |
for (int j=0; j<size; j++) { | |
map[randomStrings[j]]=j; | |
} | |
for (int i=0; i<iters; i++) { | |
for (int j=0; j<size; j++) { | |
String randomStr = randomStrings[j]; | |
var prevTag = lookup.makeCurrent(); | |
x|=map[randomStr]; | |
prevTag.makeCurrent(); | |
} | |
} | |
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++) { | |
String randomStr = randomStrings[j]; | |
var prevTag = lookup.makeCurrent(); | |
x|=map[randomStr]; | |
prevTag.makeCurrent(); | |
} | |
} | |
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++) { | |
// Warmup | |
x=func(size, 1000); | |
// Run | |
int start=new DateTime.now().millisecondsSinceEpoch; | |
x=func(size, ITERATIONS); | |
time=new DateTime.now().millisecondsSinceEpoch-start; | |
} | |
print("$name size: $size time: $time ms (${1000000*time/(ITERATIONS*2*size)} ns/op)"); | |
} | |
main() { | |
createRndStrings(10); | |
[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(""); | |
}); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment