Benchmark: log 2 for integers less than 1^^31

Script Preparation code:

function ll(x){
  let b=0, l=16, tmp;
  while (l){
    tmp = b+l;
    if (x & ((-1)<<tmp)) {
      b = tmp;
    }
    l = l>>>1;
  }
  return b;
}
function ll2(x){
  let b=0, l=16, tmp;
  while (l){
    tmp = b+l;
    if (x>>>tmp) {
      b = tmp;
    }
    l = l>>>1;
  }
  return b;
}
function ll3(x){
  let b=0, l=16;
  while (l){
    if (x>>>(b+l)) {
      b += l;
    }
    l = l>>>1;
  }
  return b;
}

var test = [...Array(50)].map(()=>(((-1)>>>1)*Math.random())>>0)

Tests:

standard lib
for (var i=0; i<test.length; i++) Math.log2(test[i])>>0;
dicho integer oriented
for (var i=0; i<test.length; i++) ll(test[i]);
dicho integer oriented 2
for (var i=0; i<test.length; i++) ll2(test[i]);
dicho integer oriented 3
for (var i=0; i<test.length; i++) ll3(test[i]);

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
standard lib
dicho integer oriented
dicho integer oriented 2
dicho integer oriented 3

Fastest: N/A

Slowest: N/A

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

LLMs can make mistakes. Check important info.

Let's dive into the world of JavaScript microbenchmarks!

**Benchmark Overview**

The provided benchmark measures the performance of three different implementations of calculating `Math.log2` for integers less than 1<<31. The tests are run on various browsers, including Chromium 67, which is the current version of Google Chrome.

**Benchmark Definitions**

There are four benchmark definitions:

1. **Standard Library**: This test uses the standard JavaScript library function `Math.log2`.
2. **Dicho Integer Oriented**: This test uses a custom implementation called `ll` (short for "log dichotomous") which is optimized for integers less than 1<<31.
3. **Dicho Integer Oriented 2**: This test uses another custom implementation, `ll2`, which is similar to `ll` but with some minor optimizations.
4. **Dicho Integer Oriented 3**: This test uses a third custom implementation, `ll3`, which is even more optimized than `ll2`.

**Library: None**

There are no external libraries used in this benchmark.

**Special JavaScript Features/Syntax: None**

None of the implementations use any special JavaScript features or syntax.

**Options Comparison**

The three custom implementations (`ll`, `ll2`, and `ll3`) differ in their approach to calculating `Math.log2` for integers less than 1<<31. Here's a brief overview:

* **Dicho Integer Oriented (ll)**: This implementation uses a loop that iterates through the bits of the input integer, keeping track of the number of set bits. The idea is to find the largest power of 2 that can be subtracted from the input without exceeding it.
* **Dicho Integer Oriented 2 (ll2)**: This implementation is similar to `ll` but with some minor optimizations. It uses a more efficient way to iterate through the bits and also uses a lookup table for some common values.
* **Dicho Integer Oriented 3 (ll3)**: This implementation is even more optimized than `ll2`. It uses a combination of bit manipulation and a more sophisticated algorithm to find the largest power of 2 that can be subtracted from the input.

**Pros and Cons**

Each implementation has its pros and cons:

* **Dicho Integer Oriented (ll)**:
	+ Pros: Simple, easy to understand, and maintain.
	+ Cons: May not be as efficient as other implementations for very large inputs.
* **Dicho Integer Oriented 2 (ll2)**:
	+ Pros: More optimized than `ll`, but still relatively simple.
	+ Cons: May have some overhead due to the lookup table.
* **Dicho Integer Oriented 3 (ll3)**:
	+ Pros: Highly optimized, may be faster for large inputs.
	+ Cons: More complex and harder to understand.

**Other Alternatives**

If you were to implement a custom `Math.log2` function from scratch, you might consider using:

* **Bit manipulation**: Using bit shifts and masks to manipulate the bits of the input integer could provide efficient solutions.
* **Exponential search**: Using exponential search algorithms (e.g., binary search) to find the largest power of 2 that can be subtracted from the input without exceeding it could be more efficient than traditional loop-based approaches.

Keep in mind that implementing a custom `Math.log2` function is generally not recommended, as it's part of the standard library and should be used instead.

Latest run results:

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

User agent: Mozilla/5.0 (X11; Linux i686) AppleWebKit/537.36 (KHTML, like Gecko) Ubuntu Chromium/67.0.3396.99 Chrome/67.0.3396.99 Safari/537.36

Browser/OS: Chromium 67 on Ubuntu

View result in a separate tab

Test name	Executions per second
standard lib	45977.2 Ops/sec
dicho integer oriented	59989.2 Ops/sec
dicho integer oriented 2	60515.2 Ops/sec
dicho integer oriented 3	60840.7 Ops/sec

Related benchmarks:

log 2 for integers less than 1^^31 (version: 4)

Comparing performance of: standard lib vs dicho integer oriented vs dicho integer oriented 2 vs dicho integer oriented 3

Created: 6 years ago by: Registered User

Jump to the latest result

standard lib

dicho integer oriented

dicho integer oriented 2

dicho integer oriented 3

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

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