2000983 - Speed up Array.indexOf(string)

Status: NEW

(Core :: JavaScript Engine: JIT, task, P2)

Description

[Iain Ireland [:iain]]

On this JSC microbenchmark using indexOf to find a string in an array, we are significantly slower than other engines. We take ~100ms to run the benchmark; V8 takes ~25ms; JSC takes ~15ms.

I've tried increasing the size of the array / using multiple arrays to avoid constant folding / etc to make sure that this isn't a spurious result, but the relative performance between engines stays consistent, so I think it's real. I get similar numbers running the testcase in the browser (at least for Firefox/Chrome; I don't have access to Safari).

V8 implements this with a pre-generated builtin (see here, here, and here) . JSC apparently inlines it in jitcode (see here and here). We call into C++ (here). I don't see any obvious problems in our C++ implementation, but 10x slower based purely on call overhead seems extreme, so possibly there's a problem I'm missing.

I'm pretty sure neither V8 nor JSC is doing anything SIMD-related here.

Comment 1

[André Bargull [:anba]]

JSC is likely only performing pointer comparisons for this specific case:

• https://searchfox.org/wubkat/rev/b4acdd7f48b90951d27f3856d5b1059e59eb7dce/Source/JavaScriptCore/runtime/ArrayPrototype.cpp#1324-1338
• Code added in https://bugs.webkit.org/show_bug.cgi?id=288548.

The atom string code path in JSC can be disabled by performing .map(nonAtom) on the input array with:

function nonAtom(s) {
  return s.split("").join("");
}

Comment 2

[Iain Ireland [:iain]]

Ah, good catch. I checked quickly for atom optimizations, but I was looking at the original JSC patch that added the testcase, and didn't notice that it had been updated later.

JSC gets significantly slower as soon as there's a single non-atom in the array (~40-45ms instead of ~15ms), falling further to ~60ms if the entire array is non-atom. V8 doesn't have the same cliff, but it does slow down slightly per-atom, ending up in the ~55-60ms range if the entire array is non-atom. We don't slow down meaningfully for non-atoms. (We do have a fast path for atoms, but it doesn't help as much; maybe we've already paid the call overhead cost by the time we reach it.)