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

​x
 
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']
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
    }
  }

 
  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

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
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 6 months ago):

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:

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'].
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

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

Template Literals: Used in the const v = map['thing-10']['100'] line to create a string template.
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:

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.
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.
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.

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