search

zandaqo / structurae

Data structures for high-performance JavaScript applications.
MIT License
694 stars 21 forks source link

getLSBIndex: Replace PoT lookup table with Math.clz32 #42

Open liamdon opened 8 months ago

liamdon commented 8 months ago

The lookup table approach is really neat, but after running some benchmarks it looks like we can get a ~10-15x speedup by using the built-in Math.clz32()

Benchmark

let n = 2;
for (let i = 0; i < 16; i++) {
    getLSBIndex(n);
    n *= 2;
}

Chrome 119

Approach Second Header
Math.clz32 145M ops/s ± 0.48%
Lookup table 9.8M ops/s ± 0.24% (93.21% slower)

Safari 17.9

Approach Second Header
Math.clz32 120M ops/s ± 0.24%
Lookup table 12M ops/s ± 0.51%. (89.76% slower)

Math.clz32() Browser support