Benchmark: Include vs Binary search in sorted array vs Map.has()

Script Preparation code:

var array = [];
var map = new Map();

for (var i = 0; i < 2000; i++){
array.push(Math.random());
 map.set(i,true);
}
var sorted = array.sort()

function binaryIndexOf(searchElement) {

 
    var minIndex = 0;
    var maxIndex = this.length - 1;
    var currentIndex;
    var currentElement;
 
    while (minIndex <= maxIndex) {
        currentIndex = (minIndex + maxIndex) / 2 | 0;
        currentElement = this[currentIndex];
 
        if (currentElement < searchElement) {
            minIndex = currentIndex + 1;
        }
        else if (currentElement > searchElement) {
            maxIndex = currentIndex - 1;
        }
        else {
            return currentIndex;
        }
    }
 
    return -1;
}

Tests:

Includes
sorted.includes(5)
binary
binaryIndexOf.call(sorted, 5)
Map.has()
map.has(5);

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Includes
binary
Map.has()

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated 27 days ago):

LLMs can make mistakes. Check important info.

Let's dive into the world of JavaScript microbenchmarks.

The provided JSON represents a benchmark test that measures the performance of three different approaches to find an element in a sorted array:

1. `includes()`: A method of the Array prototype that searches for an element within the array and returns `true` if it is found, or `false` otherwise.
2. Binary search (`binaryIndexOf()`): A custom implementation of binary search to find an element in the sorted array.
3. `has()`: A method of the Map object that checks if a specific key (in this case, a number) exists in the map.

Let's break down each approach:

**1. includes():**

Pros:

* Widely supported and implemented across most JavaScript engines and browsers.
* Simple to understand and implement.

Cons:

* Can be slower than binary search for large arrays due to its linear search algorithm.
* May not perform well on very large arrays since it needs to iterate through the entire array.

**2. Binary search (binaryIndexOf()):**

Pros:

* Efficient for finding an element in a sorted array, especially for larger arrays.
* Can take advantage of the fact that the array is already sorted, reducing the number of comparisons needed.

Cons:

* Requires the array to be sorted, which can be time-consuming to set up initially.
* Custom implementation may not be as widely supported or well-optimized as built-in methods like `includes()`.
* May not perform well on arrays with a large number of duplicate elements.

**3. has():**

Pros:

* Fast and efficient for checking existence in a Map, especially when the map is large.
* Can take advantage of the fact that Map keys are unique, reducing the number of comparisons needed.

Cons:

* Requires a Map object to be created and populated with data before using `has()`.
* May not perform well on arrays without a map implementation (e.g., if only an array is available).

Other alternatives for finding an element in a sorted array include:

* Using `Array.prototype.findIndex()` or `Array.prototype.indexOf()` which are also efficient and widely supported.
* Implementing a more advanced binary search algorithm, such as the "exponential" or "logarithmic" approach.

Now that we've explored each approach, let's look at some additional considerations:

* **Test setup:** The benchmark test creates an array of 2000 random numbers and populates a Map with corresponding keys. This allows for a fair comparison of the three approaches.
* **Script preparation code:** The script preparation code sets up the necessary data structures (array and map) before running the tests.
* **Html preparation code:** There is no HTML preparation code provided, which suggests that this benchmark test focuses solely on the JavaScript implementation.

In terms of special JS features or syntax, none are mentioned in the benchmark definition. However, some notable mentions include:

* The use of `| 0` to perform a bitwise shift and round down to the nearest integer.
* The custom implementation of binary search (`binaryIndexOf()`).

Overall, this benchmark test provides a useful comparison of three different approaches for finding an element in a sorted array, highlighting their pros and cons, and helping developers choose the most efficient solution for their specific use case.

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/101.0.4951.54 Safari/537.36

Browser/OS: Chrome 101 on Windows

View result in a separate tab

Test name	Executions per second
Includes	648520.2 Ops/sec
binary	5712002.5 Ops/sec
Map.has()	12256987.0 Ops/sec

Related benchmarks:

Include vs Binary search in sorted array vs Map.has() (version: 0)

Comparing performance of: Includes vs binary vs Map.has()

Created: 2 years ago by: Guest

Jump to the latest result

Includes

binary

Map.has()

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated 27 days ago):