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 gemma2:9b, generated one year ago):

LLMs can make mistakes. Check important info.

This benchmark compares the performance of two different implementations for creating and accessing key-value pairs:

**1. `Map` (built-in JavaScript):** 
   * **Options:** This uses the standard `Map` object provided by JavaScript, which is a powerful and efficient data structure designed for storing key-value pairs.

**2. `FastStringMap` (custom implementation):**
    * **Options:** This is a custom class (`FastStringMap`) created by the benchmark author to implement a similar functionality to a `Map`. The code provided implements core operations like setting, getting, and removing values.

**Pros/Cons Comparison:**

| Feature | `Map` (built-in) | `FastStringMap` (custom) |
|---|---|---|
| **Ease of Use** | Very easy; simply create an instance and use its methods | Requires understanding the code and potentially modifying it |
| **Performance** | Generally very efficient for most common use cases | Potentially faster in specific scenarios due to optimizations or tailored implementation. However, this benchmark shows `Map` outperforming `FastStringMap` significantly. |
| **Maintainability** | Well-tested and maintained by the JavaScript core team | Relies on the author's ongoing maintenance; potential for bugs or inconsistencies |
| **Flexibility** | Supports various data types as keys and values | Limited to strings as keys in this implementation |
| **Features** |  Offers a wider range of built-in methods and features (e.g., iteration, size checks) | May lack some advanced features or functionalities present in `Map` |

**FNV Hashing:** The `FastStringMap` uses a custom hash function based on the FNV hashing algorithm to map keys to indices in its underlying storage.

**Benchmark Results:**
The benchmark results clearly show that the built-in `Map` implementation significantly outperforms the `FastStringMap` in this particular scenario (getting values repeatedly). This suggests that:
   * The `Map` object's internal optimizations and design are very effective for common key-value access patterns.
   * The custom hash function or other optimizations in `FastStringMap` may not be as beneficial in this specific use case.

**Key Takeaways:**

* **Use built-in `Map` whenever possible:** It provides a reliable, performant, and well-supported solution for most key-value storage needs.
* **Carefully evaluate custom implementations:** 
   Before relying on a custom data structure like `FastStringMap`, thoroughly test it against your specific use case and existing solutions to ensure it meets your performance requirements and maintainability expectations.

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 gemma2:9b, generated one year ago):