Benchmark: FastStringMap test1

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 fastStringMap = new FastStringMap();
var map = new Map();

Tests:

test map
for(let i=0; i<100; ++i){ map.set(i.toString(), i); } for(let i=0; i<100000; ++i){ map.get(i.toString()); }
test fast string map
for(let i=0; i<100; ++i){ fastStringMap.set(i.toString(), i); } for(let i=0; i<100000; ++i){ fastStringMap.get(i.toString()); }

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
test map
test fast string map

Fastest: N/A

Slowest: N/A

Latest run results:

No previous run results

This benchmark does not have any results yet. Be the first one to run it!

Autogenerated LLM Summary (model llama3.1:latest, generated one year ago):

LLMs can make mistakes. Check important info.

Let's dive into the provided JSON data and explore what's being tested.

**Overview**

The benchmark is testing the performance of two different implementations of a map data structure: the built-in `Map` object (`map`) and a custom implementation called `FastStringMap`.

**What's being compared?**

In this benchmark, we're comparing the execution time per second (EPS) of these two approaches:

1. **test map**: This test case uses the native `Map` object to set and get values for 100 unique keys and then retrieve those values 100,000 times.
2. **test fast string map**: Similarly, this test case employs the custom `FastStringMap` implementation to perform the same operation.

**What are the pros and cons of each approach?**

Here's a brief summary:

*   **Built-in Map (`map`)**:
    *   Pros: Easy to use, widely supported in modern browsers.
    *   Cons: Performance might be slower compared to custom implementations, especially for large datasets.
*   **Custom FastStringMap implementation**:
    *   Pros: Potentially faster execution time, optimized for string-based key-value pairs.
    *   Cons: Custom code requires maintenance and might not be compatible with all browsers or environments.

**Other considerations**

The `FastStringMap` implementation uses a custom hash function (FNV-1a) to index values in an array. This approach can improve lookup performance, especially when dealing with large datasets of string-based key-value pairs.

The test case also demonstrates the use of a custom `fastRemoveElem` function to efficiently remove elements from an array.

**Alternatives**

Other alternatives for storing and retrieving data in JavaScript include:

1.  **Object literals**: Useful for smaller datasets or simple data structures.
2.  **Arrays**: Suitable for ordered collections, especially when working with large datasets.
3.  **Immutable libraries**: Such as Immutable.js, which provides efficient methods for creating and manipulating immutable data structures.

Remember that the best choice depends on your specific use case, performance requirements, and personal preferences.

Related benchmarks:

FastStringMap test1 (version: 0)

Comparing performance of: test map vs test fast string map

Created: 6 years ago by: Guest

Jump to the latest result

test map

test fast string map

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

No previous run results

Autogenerated LLM Summary (model llama3.1:latest, generated one year ago):