Benchmark: Integer key lookup, sparse array vs object vs map

Script Preparation code:

var sparse_array = [];
var object = {};
var map = new Map();

var known_keys = [];

for(i=0; i<10000; i++) {
	const index = Math.floor(Math.random()*Number.MAX_SAFE_INTEGER);
    const val = {id:index};
    // Insert the val into all the containers
    known_keys.push(index);
    sparse_array[index] = val;
    object[index] = val;
    map.set(index, val);
}

Tests:

Sparse Array
for(const key of known_keys) { const val = sparse_array[key]; }
Object
for(const key of known_keys) { const val = object[key]; }
Map
for(const key of known_keys) { const val = map.get(key); }

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Sparse Array
Object
Map

Fastest: N/A

Slowest: N/A

Latest run results:

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

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:109.0) Gecko/20100101 Firefox/113.0

Browser/OS: Firefox 113 on Mac OS X 10.15

View result in a separate tab

Test name	Executions per second
Sparse Array	648.2 Ops/sec
Object	653.6 Ops/sec
Map	5304.3 Ops/sec

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

LLMs can make mistakes. Check important info.

The provided JSON represents a JavaScript benchmark test case, specifically designed to compare the performance of three data structures: sparse arrays, objects, and Maps.

**What is tested:**

* The benchmark tests how fast each data structure can find a value associated with a given key. In this case, the keys are randomly generated integers between 0 (inclusive) and `Number.MAX_SAFE_INTEGER` (exclusive). Only hits (i.e., when a key is present in the data structure) are considered.

**Options compared:**

* **Sparse Array**: A sparse array is an array where some elements are missing. In this benchmark, we insert the values into the sparse array using the generated random keys.
* **Object**: An object is a collection of key-value pairs stored in a single unit. We create an object and insert its values using the same random keys as the sparse array.
* **Map**: A Map is a data structure that stores key-value pairs, with the key being unique. We create a new Map instance and insert its values using the generated random keys.

**Pros and Cons of each approach:**

* **Sparse Array**: The sparse array approach has an advantage when there are many missing elements, as it only needs to allocate space for the present elements. However, in this benchmark, we're dealing with a large range of integers, so the sparse array's performance is likely to be similar to the object's.
	+ Pros: efficient use of memory
	+ Cons: may require more memory allocation and deallocation
* **Object**: Objects are simple and widely supported, making them a good choice for many applications. In this benchmark, objects perform well because we're using a sparse array-like approach with some elements missing.
	+ Pros: easy to implement, fast lookup times
	+ Cons: may not be the most efficient data structure in memory usage
* **Map**: Maps are designed for fast lookups and can handle large amounts of data efficiently. In this benchmark, we see that the Map performs well because it uses its built-in `get()` method to retrieve values by key.
	+ Pros: fast lookups, efficient use of memory
	+ Cons: may require additional imports if not native to all browsers

**Library usage:**

* None in this specific benchmark.

**Special JS features or syntax:**

None mentioned. However, note that the `Map` data structure is a modern JavaScript feature introduced in ECMAScript 2015 (ES6). If you're using an older browser or environment, you might need to polyfill it or use a library like jQuery Map.

**Alternatives:**

* Other data structures that could be used for this benchmark include:
	+ **Array**: While arrays are not suitable for sparse data structures, they can still provide fast lookups when the values are stored at specific indices.
	+ **Set**: Sets are unordered collections of unique elements. They might be a good choice if we're only interested in checking membership or finding unique keys.
	+ **WeakMap**: WeakMaps are similar to Maps but are designed for use with weak references, which can help prevent memory leaks.

Keep in mind that the specific results may depend on the chosen data structure and the browser environment used.

Related benchmarks:

Integer key lookup, sparse array vs object vs map (version: 0)

Given an integer key with a large range, find the object associated with that key. Only hits are considered.

Comparing performance of: Sparse Array vs Object vs Map

Created: one year ago by: Guest

Jump to the latest result

Sparse Array

Object

Map

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

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