Run results for: FastStringMap test3

Run details:

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:74.0) Gecko/20100101 Firefox/74.0

Browser: Firefox 74

Operating system: Mac OS X 10.15

Device Platform: Desktop

Date tested: 4 years ago

Test name	Executions per second
Map random get	1465594.0 Ops/sec
Fast string map random get	8370.1 Ops/sec
object random get	9724908.0 Ops/sec

Script Preparation code:

"use-strict";

const HASH_SIZE = 64,
  FNV_PRIME_64 = 1099511628211n,
  FNV_OFFSET_64 = 14695981039346656037n;

let char;
function FNV1aHash64(string) {
  const { length } = string;
  let hash = FNV_OFFSET_64,
    i = 0;
  for (
    ;
    i < length;
    char = BigInt(string.charCodeAt(i++)),
      hash = BigInt.asUintN(HASH_SIZE, (hash ^ char) * FNV_PRIME_64)
  );
  return hash;
}

const DEFAULT_TABLE_SIZE_L_SHIFT = 9;

function fastRemoveElem(arr, i) {
  const tmp = arr[arr.length - 1];
  arr[arr.length - 1] = arr[i];
  arr[i] = tmp;
  arr.pop();
}

// TODO: use mersenne primes for table size
// TODO: handle grow
// TODO: values method
class FastStringMap {
  constructor() {
    this._size_factor = DEFAULT_TABLE_SIZE_L_SHIFT;
    const capacity = 0x2 << this._size_factor;
    this._capacity = BigInt(capacity);
    this._table = new Array(capacity);
    this.size = 0;
  }

  _indexOfKey(key) {
    return FNV1aHash64(key) & (this._capacity - 1n);
  }

  /**
   * @param key unique key
   * @returns the value stored in the key, or undefined if it doesnt exist
   */
  get(key) {
    const bucket = this._table[this._indexOfKey(key)];
    if (!bucket) {
      return undefined;
    }
    let { length } = bucket,
      i = 0;
    for (; i < length; ++i) {
      if (bucket[i][0] === key) {
        return bucket[i][1];
      }
    }
    return undefined;
  }

  /**
   * @param key unique key
   * @param value the value to store
   * @returns this
   */
  set(key, value) {
    let bucket,
      table = this._table,
      index = this._indexOfKey(key);
    if ((bucket = table[index]) !== undefined) {
      bucket.push([key, value]);
    } else {
      table[index] = [[key, value]];
    }
    ++this.size;
    return this;
  }

  /**
   * @param key unique key
   * @returns this
   */
  remove(key) {
    const bucket = this._table[this._indexOfKey(key)];
    if (!bucket) {
      return this;
    }
    let { length } = bucket,
      i = 0;
    for (; i < length; ++i) {
      if (bucket[i][0] === key) {
        fastRemoveElem(bucket, i);
        return this;
      }
    }
    return this;
  }
}

var uuids = [
  "eb421274-6f9a-11ea-bc55-0242ac130003",
  "eb4214ae-6f9a-11ea-bc55-0242ac130003",
  "eb42159e-6f9a-11ea-bc55-0242ac130003",
  "eb4216d4-6f9a-11ea-bc55-0242ac130003",
  "eb4217e2-6f9a-11ea-bc55-0242ac130003"
];
var fastStringMap = new FastStringMap();
var map = new Map();
var obj = {};

Tests:

Map random get
const [a,b,c,d,e] = uuids; map.set(a); map.set(b); map.set(c); map.set(d); map.set(e); map.get(a); map.get(b); map.get(c); map.get(d); map.get(e);
Fast string map random get
const [a,b,c,d,e] = uuids; fastStringMap.set(a); fastStringMap.set(b); fastStringMap.set(c); fastStringMap.set(d); fastStringMap.set(e); fastStringMap.get(a); fastStringMap.get(b); fastStringMap.get(c); fastStringMap.get(d); fastStringMap.get(e);
object random get
const [a,b,c,d,e] = uuids; obj[a] = a; obj[b] = b; obj[c] = c; obj[d] = d; obj[e] = e; obj[a]; obj[b]; obj[c]; obj[d]; obj[e];

Run results for: FastStringMap test3

Map random get

Fast string map random get

object random get