Benchmark: array vs hashmap1 vs array-polling

Script Preparation code:

const array = [];

for (let i = 0; i < 100; i++) {
    array.push({
        key: i,
        prop: Math.floor(Math.random() * 10000)
    })
}

function hashmap () { return array.reduce((mapper, next) => ({
    ...mapper,
    [next.key]: next
}), {});}

let hashmap1;

function findInArray (key) {
    const index = bs(array, key, function(element, needle) {
        return element.key - needle;
    });
    return index > 0 ? array[index] : undefined;
}

function findArrayFind (key) {
  return array.find(elem=>elem.key===key);
}

function findInHashMap (key) {
  if (!hashmap1) {
    hashmap1 = hashmap();
  }
    return hashmap1[key] || undefined;
}

function findInArrayByPolling (key) {
    for (let i = 0, len = array.length ; i < len; i++) {
        if (array[i].key === key) {
            return array[i]
        }
    }
}



function bs(haystack, needle, comparator, low, high) {
    var mid, cmp;
  
    if(low === undefined)
      low = 0;
  
    else {
      low = low|0;
      if(low < 0 || low >= haystack.length)
        throw new RangeError("invalid lower bound");
    }
  
    if(high === undefined)
      high = haystack.length - 1;
  
    else {
      high = high|0;
      if(high < low || high >= haystack.length)
        throw new RangeError("invalid upper bound");
    }
  
    while(low <= high) {
      // The naive `low + high >>> 1` could fail for array lengths > 2**31
      // because `>>>` converts its operands to int32. `low + (high - low >>> 1)`
      // works for array lengths <= 2**32-1 which is also Javascript's max array
      // length.
      mid = low + ((high - low) >>> 1);
      cmp = +comparator(haystack[mid], needle, mid, haystack);
  
      // Too low.
      if(cmp < 0.0)
        low  = mid + 1;
  
      // Too high.
      else if(cmp > 0.0)
        high = mid - 1;
  
      // Key found.
      else
        return mid;
    }
  
    // Key not found.
    return ~low;
}

Tests:

find by binary search array
const target = Math.floor(Math.random() * 100); findInArray(target);
find by array polling
const target = Math.floor(Math.random() * 100); findInArrayByPolling(target);
find by hashmap
const target = Math.floor(Math.random() * 100); findInHashMap(target);
find by func find
const target = Math.floor(Math.random() * 100); findArrayFind(target)

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
find by binary search array
find by array polling
find by hashmap
find by func find

Fastest: N/A

Slowest: N/A

Latest run results:

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

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/14.1.1 Safari/605.1.15

Browser/OS: Safari 14 on Mac OS X 10.15.7

View result in a separate tab

Test name	Executions per second
find by binary search array	1066133.8 Ops/sec
find by array polling	2206613.0 Ops/sec
find by hashmap	2759216.0 Ops/sec
find by func find	2088421.6 Ops/sec

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

LLMs can make mistakes. Check important info.

Let's break down the benchmark and its test cases.

**Benchmark Definition**

The benchmark is designed to compare three approaches for finding an element in an array: `findInArrayByPolling`, `findInHashMap`, and `findArrayFind`. The common dataset used in all test cases consists of 100 randomly generated objects with a unique key and a random property value. Each test case uses the `target` variable to find an element by its key.

**Options Compared**

1. **`findInArrayByPolling`**: This approach iterates through the array until it finds the target element or reaches the end of the array.
2. **`findInHashMap`**: This approach uses a hash map (object) to store the data and then searches for the target key in the hash map.
3. **`findArrayFind`**: This approach uses the `find` method, which returns the first element that satisfies the provided condition.

**Pros and Cons**

1. **`findInArrayByPolling`**:
	* Pros: simple to implement, works for small arrays.
	* Cons: inefficient for large arrays (O(n) time complexity), can be slow due to unnecessary iterations.
2. **`findInHashMap`**:
	* Pros: efficient for large datasets (O(1) time complexity on average), can be fast for random key accesses.
	* Cons: requires extra memory for the hash map, can be slower for small arrays.
3. **`findArrayFind`**:
	* Pros: concise and expressive code, works well with modern JavaScript engines.
	* Cons: may not be as efficient as `findInHashMap` for large datasets (O(n) time complexity), may incur overhead due to function call.

**Other Considerations**

* The use of binary search (`bs`) in `findInArrayByPolling` is an interesting optimization. While it's more complex to implement, it can significantly improve performance for large arrays.
* The choice of hash map implementation is crucial. In this case, the hash map is implemented as a simple object, which may not be suitable for large datasets or production environments.

**Library Usage**

The `findInArrayByPolling` function uses a custom `bs` function, but it's not a standard JavaScript library. The other two functions (`findInHashMap` and `findArrayFind`) do not rely on external libraries.

**Benchmark Results**

The latest benchmark results show that the order of performance is:

1. `findInHashMap`
2. `findArrayFind`
3. `findInArrayByPolling`

These results suggest that `findInHashMap` provides the best performance, followed closely by `findArrayFind`. `findInArrayByPolling` is slower due to its O(n) time complexity and unnecessary iterations.

Keep in mind that these results are specific to this benchmark setup and may not generalize to other scenarios or JavaScript engines.

Related benchmarks:

array vs hashmap1 vs array-polling (version: 0)

Comparing performance of: find by binary search array vs find by array polling vs find by hashmap vs find by func find

Created: 3 years ago by: Guest

Jump to the latest result

find by binary search array

find by array polling

find by hashmap

find by func find

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

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