1864323 - There might be room for improving String.prototype.includes() performance

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement, P3)

Description

[vlakoff]

Steps to reproduce:

String.prototype.indexOf() and String.prototype.includes() are quite similar methods, and both are very fast.

I benchmarked these methods on Chrome and Pale Moon, and both methods have basically the same performance.

However, on Firefox I noticed includes() is about 40x slower than indexOf()!
(measured on Firefox 119 x64, Windows 10)

This let me guess there might be some room for improvement that has been missed.

Actual results:

includes() is about 40x slower than indexOf()!

Expected results:

includes() should be as fast as indexOf().

Comment 1

[vlakoff]

Now I suspect there is really a performance issue.

When testing with longer haystacks (and needle not occurring in it), includes() gets worse and worse as I'm increasing the haystack length. Seems to be O(n).
Whereas indexOf() (and includes() too, on other browsers) also gets slower, but only marginally.

For instance, I quickly reached an includes() 300x slower than indexOf().

I guess there is some optimization in indexOf() to avoid being O(n) complexity, but that optimization is missing from includes().

Comment 2

[Mayank Bansal]

Can you post the benchmark you were using to test performance, and the numbers you were getting on it?

Comment 3

[vlakoff]

(function () {
    let i, nb = 10000000;

    let haystack = 'A'.repeat(10);
    let needle = 'B';

    let t1 = new Date();
    for (i = nb; i--; ) {
        haystack.includes(needle);
    }
    let t2 = new Date();
    for (i = nb; i--; ) {
        haystack.indexOf(needle) !== -1;
    }
    let t3 = new Date();

    console.log(t2 - t1);
    console.log(t3 - t2);
})();

Results with nb = 10000000 (thankfully, these methods are fast), less is better:

With haystack = 'A'.repeat(10):

includes: 315
indexOf:  12

With haystack = 'A'.repeat(10000):

includes: 2376
indexOf:  19

includes() is clearly slower and – though it's not as bad as O(n) actually – less scalable.

Comment 4

[Mayank Bansal]

haystack = 'A'.repeat(10):
Nightly - 143, 6
Chrome - 6, 5

haystack = 'A'.repeat(10000):
Nightly - 665,6
Chrome - 7, 6

Comment 5

[Mayank Bansal]

Attachment: OPs testcase.html

Comment 6

[Mayank Bansal]

FWIW, there was a huge improvement (188ms ->6ms) in the String.prototype.indexOf in this changeset : https://hg.mozilla.org/mozilla-central/pushloghtml?fromchange=17df1e9794687c0d56a85bc975e6b650c911b69f&tochange=fbae7216fa061be5b7521010f78bb51dade2a5a9 , which points to bug 1784023 / bug 1784090

Comment 7

[Jan de Mooij [:jandem]]

I think what's happening is that indexOf is optimized by the JITs and in this case the call can be optimized away. The JIT doesn't know as much about includes at this point so it can't optimize that yet.

Comment 8

[André Bargull [:anba]]

Attachment: Bug 1864323 - Part 1: Inline String.p.{includes,lastIndexOf} with a VM-call. r=jandem!

This is still a simple VM-call, but the alias-set information will allow Ion
to optimise out unused MStringIncludes and MStringLastIndexOf calls, similar to
how MStringIndexOf can already be optimised out.

Comment 9

[André Bargull [:anba]]

Attachment: Bug 1864323 - Part 2: Directly call into the SIMD code. r=jandem!

For one and two character search strings we can directly call into mozilla::SIMD.
This gives a noticeable performance improvement when compared to using a VM-call
and our performance for one element search strings now matches or even surpasses
JSC and V8.

Depends on D197683

Comment 10

[André Bargull [:anba]]

Attachment: Bug 1864323 - Part 3: Inline String trim functions. r=jandem!

Inline String.p.trim{,Start,End} so all non-selfhosted String functions
can be inlined. (Except for String.p.normalize where we have to call into ICU.)

For CacheIR we simply call into the VM. For Warp reuse MSubstr to create the
result string, because this allows to inline the String allocation code.

Depends on D197684

Comment 11

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/31b2d4376671
Part 1: Inline String.p.{includes,lastIndexOf} with a VM-call. r=jandem
https://hg.mozilla.org/integration/autoland/rev/a43b1a957eb7
Part 2: Directly call into the SIMD code. r=jandem
https://hg.mozilla.org/integration/autoland/rev/af1367f14f14
Part 3: Inline String trim functions. r=jandem

Comment 12

[Natalia Csoregi [:nataliaCs]]

https://hg.mozilla.org/mozilla-central/rev/31b2d4376671
https://hg.mozilla.org/mozilla-central/rev/a43b1a957eb7
https://hg.mozilla.org/mozilla-central/rev/af1367f14f14

Comment 13

[vlakoff]

Thanks André Bargull for this amazing work!

Refs #1873042 in which you brought even more optimizations to the string functions :)