Benchmark: Array.find vs. Map.get by array

Array.find vs. Map.get by array (version: 1)

Test the performance of Array.find vs. Map.get, with various array sizes, and with/without conversion from array to map

Comparing performance of: Array.find, 100 elements vs Map.get, 100 elements vs Array.find, 1 000 000 elements vs Map.get, 1 000 000 elements vs Array to Map + Map.get, 1 lookup vs Array to Map + Map.get, 10 lookups vs Array to Map + Map.get, 100 lookups vs Array.find, 10 lookups vs Array.find, 100 lookups

Created: 3 months ago by: Guest

Jump to the latest result

Script Preparation code:

function getRandomElement(id) {
    return {
        id,
        a: Math.random(),
        b: Math.random(),
        c: Math.random(),
    }
}

function getArray(length) {
    const result = [];
    for (let i = 0; i < length; i++) {
        result.push(getRandomElement(i))
    }

    return result;
}

function getArrays(length) {
    const result = new Array(length).fill(0);;
    for (let i = 0; i < length; i++) {
        result[i] = (getRandomElement(i))
    }

    return result;
}

function arrayToMap(array) {
    return new Map(array.map(el => [el.id, el]));
}

function getRandomInt(max) {
    return Math.floor(Math.random() * max);
}

array_small = getArrays(100);
array_large = getArrays(10000);

map_small = arrayToMap(array_small);
map_large = arrayToMap(array_large);

​x
 
function getRandomElement(id) {    return {        id,        a: Math.random(),        b: Math.random(),        c: Math.random(),    }}​function getArray(length) {    const result = [];    for (let i = 0; i < length; i++) {        result.push(getRandomElement(i))    }​    return result;}​function getArrays(length) {    const result = new Array(length).fill(0);;    for (let i = 0; i < length; i++) {        result[i] = (getRandomElement(i))    }​    return result;}​function arrayToMap(array) {    return new Map(array.map(el => [el.id, el]));}​function getRandomInt(max) {    return Math.floor(Math.random() * max);}​array_small = getArrays(100);array_large = getArrays(10000);​map_small = arrayToMap(array_small);map_large = arrayToMap(array_large);

Tests:

Array.find, 100 elements
const target = getRandomInt(99); array_small.find(el => el.id === target);
const target = getRandomInt(99);
array_small.find(el => el.id === target);
Map.get, 100 elements
const target = getRandomInt(99); map_small.get(target);
const target = getRandomInt(99);
map_small.get(target);
Array.find, 1 000 000 elements
const target = getRandomInt(999999); array_large.find(el => el.id === target);
const target = getRandomInt(999999);
array_large.find(el => el.id === target);
Map.get, 1 000 000 elements
const target = getRandomInt(999999); map_large.get(target)
const target = getRandomInt(999999);
map_large.get(target)
Array to Map + Map.get, 1 lookup
const map = arrayToMap(array_small); const target = getRandomInt(9999); map.get(target);
const map = arrayToMap(array_small);
const target = getRandomInt(9999);
map.get(target);
Array to Map + Map.get, 10 lookups
const map = arrayToMap(array_small); for (let i = 0; i < 10; i++) { const target = getRandomInt(9999); map.get(target); }
const map = arrayToMap(array_small);

for (let i = 0; i < 10; i++) {
const target = getRandomInt(9999);
map.get(target);
}
Array to Map + Map.get, 100 lookups
const map = arrayToMap(array_small); for (let i = 0; i < 100; i++) { const target = getRandomInt(9999); map.get(target); }
const map = arrayToMap(array_small);

for (let i = 0; i < 100; i++) {
const target = getRandomInt(9999);
map.get(target);
}
Array.find, 10 lookups
for (let i = 0; i < 10; i++) { const target = getRandomInt(9999); array_small.find(el => el.id === target) }
for (let i = 0; i < 10; i++) {
const target = getRandomInt(9999);
array_small.find(el => el.id === target)
}
Array.find, 100 lookups
for (let i = 0; i < 100; i++) { const target = getRandomInt(9999); array_small.find(el => el.id === target) }
for (let i = 0; i < 100; i++) {
const target = getRandomInt(9999);
array_small.find(el => el.id === target)
}

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Experimental features:

Memory measurements supported only in Chrome.
For precise memory measurements Chrome must be launched with --enable-precise-memory-info flag.
More information: Monitoring JavaScript Memory

Test case name	Result
Array.find, 100 elements
Map.get, 100 elements
Array.find, 1 000 000 elements
Map.get, 1 000 000 elements
Array to Map + Map.get, 1 lookup
Array to Map + Map.get, 10 lookups
Array to Map + Map.get, 100 lookups
Array.find, 10 lookups
Array.find, 100 lookups

Fastest: N/A

Slowest: N/A

Latest run results:

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

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/128.0.0.0 Safari/537.36 OPR/114.0.0.0

Browser/OS: Opera 114 on Windows

View result in a separate tab

Test name	Executions per second
Array.find, 100 elements	10705738.0 Ops/sec
Map.get, 100 elements	58079804.0 Ops/sec
Array.find, 1 000 000 elements	29872.3 Ops/sec
Map.get, 1 000 000 elements	60034052.0 Ops/sec
Array to Map + Map.get, 1 lookup	299120.8 Ops/sec
Array to Map + Map.get, 10 lookups	294243.6 Ops/sec
Array to Map + Map.get, 100 lookups	234919.8 Ops/sec
Array.find, 10 lookups	683254.4 Ops/sec
Array.find, 100 lookups	67373.5 Ops/sec

Autogenerated LLM Summary (model gpt-4o-mini, generated 3 months ago):

This benchmark evaluates the performance of two different methods used for searching or retrieving values from a collection in JavaScript: Array.find and Map.get. It compares these methods when applied to arrays of varying sizes and when using intermediate data structures.

Description of the Benchmark

Options Compared

Array.find
- This method is used to search through an array for an element that satisfies a given predicate (in this case, finding an object with a specific id).
- It performs a linear search, iterating through each element until it either finds a match or reaches the end of the array.
Map.get
- This method retrieves a value from a map (a collection of key-value pairs) using a specified key.
- Maps use hash tables under the hood, allowing for average-case O(1) time complexity for lookups, which is faster than the linear search used by Array.find, particularly for larger collections.

Test Cases

The benchmark includes multiple test cases to illustrate performance under different conditions:

Searching an array of 100 elements using Array.find and Map.get.
Searching an array of 1,000,000 elements using both methods.
Comparing the performance of Map.get after converting a small array to a map, for scenarios with varying numbers of lookups (1, 10, and 100 lookups).

Pros and Cons

Array.find

Pros:

Simple to implement and read.
Can be used with any iterable collection.

Cons:

Performance degrades dramatically as the size of the array increases due to linear search.
Not suitable for scenarios where frequent lookups are needed.

Map.get

Pros:

Provides faster access times for lookups, especially with larger datasets due to its average-case O(1) performance.
Efficient for frequent updates and lookups.

Cons:

Requires initial overhead to construct the map from an array.
Slightly more complex to implement compared to a direct array lookup for singular operations.

Other Considerations

The benchmark also tests the impact of converting an array to a map before performing lookups, which can have notable performance benefits for repeated lookups.
The arrayToMap function transforms an array of objects into a Map format, making retrieval operations faster.

Latest Benchmark Results

The benchmark results show that Map.get significantly outperforms Array.find in nearly all scenarios, especially with larger arrays:

For 1,000,000 elements, Map.get executed approximately 60 million times per second, while Array.find struggled around 29,000 times per second.
Performing 10 lookups using Map.get shows the efficacy of the map structure in enabling quick retrievals, while Array.find shows increasingly slower results as the number of lookups increases.

Other Alternatives

Other potential alternatives for optimized lookups might include:

Binary search: Applicable if the array is sorted.
Set: If uniqueness of elements is important and membership tests are frequent.
Objects: If you are storing key-value pair data rather than complex objects, regular JavaScript objects can sometimes suffice, though they do not enforce key order and have their own limitations regarding keys.

The choice between these data structures heavily relies on the specific needs of the application and the nature of the data being managed. Each structure offers unique trade-offs between complexity, performance, and ease of use.

LLMs can make mistakes. Check important info.

This benchmark evaluates the performance of two different methods used for searching or retrieving values from a collection in JavaScript: `Array.find` and `Map.get`. It compares these methods when applied to arrays of varying sizes and when using intermediate data structures.

### Description of the Benchmark

#### Options Compared
1. **Array.find**
   - This method is used to search through an array for an element that satisfies a given predicate (in this case, finding an object with a specific `id`).
   - It performs a linear search, iterating through each element until it either finds a match or reaches the end of the array.

2. **Map.get**
   - This method retrieves a value from a map (a collection of key-value pairs) using a specified key.
   - Maps use hash tables under the hood, allowing for average-case O(1) time complexity for lookups, which is faster than the linear search used by `Array.find`, particularly for larger collections.

#### Test Cases
The benchmark includes multiple test cases to illustrate performance under different conditions:
- Searching an array of 100 elements using `Array.find` and `Map.get`.
- Searching an array of 1,000,000 elements using both methods.
- Comparing the performance of `Map.get` after converting a small array to a map, for scenarios with varying numbers of lookups (1, 10, and 100 lookups).

### Pros and Cons

#### Array.find
**Pros:**
- Simple to implement and read.
- Can be used with any iterable collection.

**Cons:**
- Performance degrades dramatically as the size of the array increases due to linear search.
- Not suitable for scenarios where frequent lookups are needed.

#### Map.get
**Pros:**
- Provides faster access times for lookups, especially with larger datasets due to its average-case O(1) performance.
- Efficient for frequent updates and lookups.

**Cons:**
- Requires initial overhead to construct the map from an array.
- Slightly more complex to implement compared to a direct array lookup for singular operations.

### Other Considerations
- The benchmark also tests the impact of converting an array to a map before performing lookups, which can have notable performance benefits for repeated lookups.
- The `arrayToMap` function transforms an array of objects into a Map format, making retrieval operations faster.

### Latest Benchmark Results
The benchmark results show that `Map.get` significantly outperforms `Array.find` in nearly all scenarios, especially with larger arrays:
- For 1,000,000 elements, `Map.get` executed approximately 60 million times per second, while `Array.find` struggled around 29,000 times per second.
- Performing 10 lookups using `Map.get` shows the efficacy of the map structure in enabling quick retrievals, while `Array.find` shows increasingly slower results as the number of lookups increases.

### Other Alternatives
Other potential alternatives for optimized lookups might include:
- **Binary search**: Applicable if the array is sorted.
- **Set**: If uniqueness of elements is important and membership tests are frequent.
- **Objects**: If you are storing key-value pair data rather than complex objects, regular JavaScript objects can sometimes suffice, though they do not enforce key order and have their own limitations regarding keys.

Related benchmarks: