Benchmark: Sparse array vs Map for random access and iteration

Script Preparation code:

window.indexes = [];
window.arr = [];
window.map = new Map();
for (let i = 0; i < 1000; i++) {
	if (Math.random() > 0.7) {
		window.indexes.push(i);
		window.arr[i] = true;
		window.map.set(i, true);
	}
}

Tests:

Get from array (all hits)
for (const idx of window.indexes) { const a = window.arr[idx]; }
Get from array (with misses)
for (let i = 0; i < 1000; i++) { const a = window.arr[i]; }
Get from map (all hits)
for (const idx of window.indexes) { const a = window.map.get(idx); }
Get from map (with misses)
for (let i = 0; i < 1000; i++) { const a = window.map.get(i); }
Iterate array
for (const val of window.arr) { const a = val; }
Iterate map
for (const val of window.map) { const a = val; }

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Get from array (all hits)
Get from array (with misses)
Get from map (all hits)
Get from map (with misses)
Iterate array
Iterate map

Fastest: N/A

Slowest: N/A

Latest run results:

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

User agent: Mozilla/5.0 (Linux; Android 10; K) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/138.0.0.0 Mobile Safari/537.36

Browser/OS: Chrome Mobile 138 on Android

View result in a separate tab

Test name	Executions per second
Get from array (all hits)	710399.1 Ops/sec
Get from array (with misses)	404.2 Ops/sec
Get from map (all hits)	34145.6 Ops/sec
Get from map (with misses)	769762.8 Ops/sec
Iterate array	1720927.6 Ops/sec
Iterate map	1165826.1 Ops/sec

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

LLMs can make mistakes. Check important info.

Let's dive into the world of JavaScript microbenchmarks on MeasureThat.net.

**Benchmark Overview**

The benchmark measures performance differences between three data structures: an array, a Map, and sparse arrays with iteration. The test creates a large dataset of 1000 random indices, where some indices are used to store a boolean value (true or false). The benchmark then compares the execution times of accessing these values using different methods.

**Options Compared**

1. **Array Iteration**: Directly iterating over the array using `for...of` loop.
2. **Array Indexing**: Accessing an element at a specific index (`arr[idx]`) to retrieve its value.
3. **Map Iteration**: Iterating over the Map using `for...of` loop.
4. **Map Indexing**: Accessing a value associated with a key (`map.get(idx)`) to retrieve its value.

**Pros and Cons**

* **Array Iteration**: Pros: simple, efficient for sparse arrays; Cons: may be slower than indexing or map operations due to the overhead of iteration.
* **Array Indexing**: Pros: fast, direct access to elements; Cons: can be slow if indices are random or out of bounds.
* **Map Iteration**: Pros: efficient for large datasets, as it only iterates over keys; Cons: may not be suitable for sparse arrays or small datasets.
* **Map Indexing**: Pros: similar performance to array indexing for sparse arrays; Cons: can be slower than iteration due to the overhead of hash table lookups.

**Library Usage**

None of the test cases use any external libraries. The data structures (array and Map) are part of the JavaScript standard library.

**Special JS Features**

The benchmark uses `const` declarations, arrow functions (`=>`), and template literals (`\r\n`) to simplify the script preparation code. No special JavaScript features or syntax are used in the individual test cases.

**Other Alternatives**

If you wanted to explore alternative approaches:

* **Linked Hash Tables**: Instead of using a sparse array, you could use a linked hash table data structure, which would provide faster lookup times for sparse arrays.
* **Trie Data Structure**: A trie (prefix tree) data structure can be used to efficiently store and retrieve values associated with keys.
* **Custom Implementation**: You could implement your own optimized data structures, such as a custom array or Map implementation, to compare their performance against the standard library implementations.

Keep in mind that these alternatives might require significant changes to the benchmarking code and are not directly comparable to the standard library implementations.

Related benchmarks:

Sparse array vs Map for random access and iteration (version: 1)

Comparing performance of: Get from array (all hits) vs Get from array (with misses) vs Get from map (all hits) vs Get from map (with misses) vs Iterate array vs Iterate map

Created: 3 years ago by: Registered User

Jump to the latest result

Get from array (all hits)

Get from array (with misses)

Get from map (all hits)

Get from map (with misses)

Iterate array

Iterate map

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

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