Benchmark: string map vs. for search with sharded array large N

Script Preparation code:

globalThis.map = []
globalThis.objArr = []

for (let i = 0; i < 10000; i++) {
    const shardKey = String(i).slice(0,2)
  	if (!map[`thing-${shardKey}`]) map[`thing-${shardKey}`] = []
    map[`thing-${shardKey}`][String(i)] = { i }
    objArr.push({ i })
}

Tests:

string map
const v = map['thing-10']['100'] console.log(v) delete map['thing-10']['100']
find
for (let i = objArr.length - 1; i >= 0; i--) { const v = objArr[i] if (v.i === 100) { objArr.splice(i, 1) console.log(v) return v } }

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
string map
find

Fastest: N/A

Slowest: N/A

Latest run results:

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

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

Browser/OS: Chrome 104 on Windows

View result in a separate tab

Test name	Executions per second
string map	176048.8 Ops/sec
find	491.6 Ops/sec

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

LLMs can make mistakes. Check important info.

Let's break down the provided benchmark definition and test cases.

**Benchmark Definition**

The benchmark measures the performance of two different approaches to search and manipulate data in JavaScript:

1. **String Map Search**: This approach uses a string map (similar to an object) with nested keys to store data. The benchmark creates a large array `objArr` containing 10,000 objects, each with an `i` property. It then populates a string map `map` with the same data, but only for a subset of indices (`thing-10` and `thing-20`). Finally, it searches for a specific value in the string map using the key `'thing-10'['100']`.
2. **Find Loop**: This approach uses a simple loop to iterate through an array and find a specific element that matches a certain condition. In this case, the loop iterates through `objArr` in reverse order, checking each element's `i` property until it finds a match.

**Options Compared**

The two approaches are compared in terms of their execution time:

* String Map Search: The benchmark measures how fast the string map search is executed.
* Find Loop: The benchmark measures how fast the find loop is executed.

**Pros and Cons of Each Approach**

1. **String Map Search**
	* Pros:
		+ Fast lookups, especially for large datasets with good key distribution.
		+ Can be more memory-efficient than arrays.
	* Cons:
		+ Requires a well-distributed key set to achieve optimal performance.
		+ May have slower insertion and update times compared to arrays.
2. **Find Loop**
	* Pros:
		+ Simple and easy to implement.
		+ Does not require a pre-allocated array or map.
	* Cons:
		+ Has a higher time complexity due to the linear search.
		+ May be slower for large datasets.

**Library and Special JS Features**

In this benchmark, there is no explicit library used. However, some JavaScript features are used:

1. **Template Literals**: Used in the `const v = map['thing-10']['100']` line to create a string template.
2. **Arrow Functions**: Not explicitly used in this benchmark, but they would be used if you were to rewrite the find loop using an arrow function.

**Other Alternatives**

If you want to explore alternative approaches, here are some options:

1. **Binary Search**: Instead of linear search, you could use binary search to find elements in `objArr`. This would reduce the time complexity to O(log n), but requires a sorted array.
2. **Hash Tables**: You could use a traditional hash table implementation instead of a string map. Hash tables have an average time complexity of O(1) for lookups, but may require more memory and have slower insertion times compared to arrays.
3. **Sorted Arrays**: If you want to search for elements in `objArr` without using a loop, you could sort the array first and then use a binary search algorithm.

Keep in mind that each alternative approach would affect the benchmark's results and interpretation.

Related benchmarks:

string map vs. for search with sharded array large N (version: 0)

Comparing performance of: string map vs find

Created: 2 years ago by: Guest

Jump to the latest result

string map

find

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):