Benchmark: FastStringMap test3

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];

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Map random get
Fast string map random get
object random get

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 4 years ago)

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

Browser/OS: Firefox 74 on Mac OS X 10.15

View result in a separate tab

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

Autogenerated LLM Summary (model llama3.2:3b, generated one month ago):

LLMs can make mistakes. Check important info.

Let's break down what is being tested on the provided JSON.

**Benchmark Definition**

The benchmark definition is a JavaScript code snippet that tests the performance of three different data structures:

1. **Map**: A built-in JavaScript object that stores key-value pairs.
2. **FastStringMap**: A custom implementation of a hash map, as defined in the `FastStringMap` class.
3. **Object**: A generic JavaScript object that can store key-value pairs.

**Options being compared**

The options being compared are:

* Using the built-in `Map` data structure
* Using the custom `FastStringMap` implementation
* Using a generic JavaScript object

**Pros and Cons of each approach**

1. **Built-in Map**: Pros:
	* Widely supported and optimized by browsers.
	* Easy to use and understand.
Cons:
	* May not be as fast or efficient for large datasets.
2. **FastStringMap**: Pros:
	+ Optimized for performance, especially for hash-based operations.
	+ Custom implementation can be tuned for specific use cases.
Cons:
	+ Requires understanding of the underlying implementation.
	+ May have additional overhead due to custom code.
3. **Generic JavaScript Object**: Pros:
	+ Easy to implement and understand.
	+ Works well for small datasets or simple use cases.
Cons:
	+ Not optimized for performance, especially for large datasets.

**Individual Test Cases**

The three test cases are designed to stress different aspects of each data structure:

1. **Map random get**: Tests the performance of retrieving values from a `Map` object using random keys.
2. **Fast string map random get**: Tests the performance of retrieving values from a custom `FastStringMap` implementation using random keys.
3. **Object random get**: Tests the performance of retrieving values from a generic JavaScript object using random keys.

**Latest Benchmark Result**

The latest benchmark result shows that:

* The generic JavaScript object is the slowest, with approximately 8 executions per second.
* The custom `FastStringMap` implementation is faster than the generic object, but slower than the built-in `Map`, with approximately 84 executions per second.
* The built-in `Map` data structure is the fastest, with approximately 9725 executions per second.

Overall, the benchmark suggests that the built-in `Map` data structure is the best choice for performance-critical applications, while the custom `FastStringMap` implementation may be suitable for specific use cases where optimization is crucial.

Related benchmarks:

FastStringMap test3 (version: 0)

Comparing performance of: Map random get vs Fast string map random get vs object random get

Created: 4 years ago by: Guest

Jump to the latest result

Map random get

Fast string map random get

object random get

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated one month ago):