Benchmark: array vs hashmap vs array-polling

Script Preparation code:

const array = [];

for (let i = 0; i < 2000; i++) {
    array.push({
        key: i,
        prop: Math.floor(Math.random() * 10000)
    })
}

const hashmap = array.reduce((mapper, next) => ({
    ...mapper,
    [next.key]: next
}), {});

function findInArray (key) {
    const index = bs(array, key, function(element, needle) {
        return element.key - needle;
    });
    return index > 0 ? array[index] : undefined;
}

function findInHashMap (key) {
    return hashmap[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() * 2000); findInArray(target);
find by array polling
const target = Math.floor(Math.random() * 2000); findInArrayByPolling(target);
find by hashmap
const target = Math.floor(Math.random() * 2000); findInHashMap(target);

Historical Performance Data aggregated from 7 community runs

Desktop Results:

Chrome 7 runs

find by hashmap

5.1M/s

find by binary search array

2.1M/s

find by array polling

1.1M/s

Fastest: find by hashmap (4.7x faster)

View exact numbers

✓ find by hashmap: 5,142,536 ops/sec
• find by binary search array: 2,112,464 ops/sec
• find by array polling: 1,099,931 ops/sec

Results show median performance across all community submissions. Run this benchmark yourself to verify on your device.

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

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: one year ago)

User agent: Mozilla/5.0 (iPhone; CPU iPhone OS 18_4 like Mac OS X) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/18.4 Mobile/15E148 Safari/604.1

Browser/OS: Mobile Safari 18 on iOS 18.4

View result in a separate tab

find by hashmap

224.1M/s

find by binary search array

11.7M/s

find by array polling

1.9M/s

View exact numbers

Test name	Executions per second
✓ find by hashmap	224,067,872 Ops/sec
find by binary search array	11,735,196 Ops/sec
find by array polling	1,927,881 Ops/sec

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

LLMs can make mistakes. Check important info.

Let's break down the provided benchmark and explain what's being tested.

**Benchmark Overview**

The benchmark is designed to compare three different approaches for searching an array: binary search, array polling, and using a hashmap (a data structure that maps keys to values).

**Options Being Compared**

1. **Binary Search**: This approach uses a sorting algorithm (in this case, the `Array.prototype.sort()` method) to sort the array and then searches for a target value by finding its middle index and recursively narrowing down the search range.
2. **Array Polling**: This approach iterates through the entire array, checking each element's key until it finds a match with the target value.
3. **Hashmap**: This approach creates an object (the hashmap) from the array and uses the `Object.prototype.hasOwnProperty()` method to find the target value.

**Pros and Cons of Each Approach**

1. **Binary Search**:
	* Pros: Fastest for large datasets, O(log n) time complexity.
	* Cons: Requires sorting the array first, which can be slow for very large arrays.
2. **Array Polling**:
	* Pros: Simple to implement, doesn't require sorting the array.
	* Cons: Slow for large datasets, O(n) time complexity.
3. **Hashmap**:
	* Pros: Fast lookup times, O(1) average time complexity.
	* Cons: Requires creating an object from the array, which can be slow for very large arrays.

**Library and Syntax Used**

The benchmark uses the following libraries:

1. **Array.prototype.sort()**: a built-in JavaScript method that sorts the elements of an array in place.
2. **Object.prototype.hasOwnProperty()**: a built-in JavaScript property that checks if an object has a particular property as its own.

There are no special JavaScript features or syntax used in this benchmark.

**Other Alternatives**

Some other approaches for searching an array include:

1. **Linear Search**: Similar to array polling, but uses a more efficient algorithm.
2. **Ternary Search**: A hybrid approach that combines elements of binary search and linear search.
3. **Interpolation Search**: An optimized version of binary search for uniformly distributed data.

These alternatives may be worth considering in certain situations, but are not part of the current benchmark.

array vs hashmap vs array-polling (version: 0) Benchmark.js

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

Created: 6 years ago by: Registered User

Go to the latest result

find by binary search array

find by array polling

find by hashmap

Historical Performance Data aggregated from 7 community runs

Desktop Results:

Chrome 7 runs

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

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

array vs hashmap vs array-polling (version: 0) Benchmark.js

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

Created: 6 years ago by: Registered User

Go to the latest result

find by binary search array

find by array polling

find by hashmap

Historical Performance Data aggregated from 7 community runs

Desktop Results:

Chrome 7 runs

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

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

Related benchmarks

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