1803855 - js::SubstringKernel should avoid making small ropes

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect, P2)

Description

[Ted Campbell [:tcampbell]]

When creating substrings of ropes we don't check if the result fits in a linear string in all cases.

https://searchfox.org/mozilla-central/rev/c33879cb4884c08c11980847cd84ccd76f485894/js/src/builtin/String.cpp#609

If we fix this, we can avoid allocating the two extra JSDependentString. It also would let us enforce that all ropes are a minimum length which can rule out some cases like static strings.

Comment 1

[Jan de Mooij [:jandem]]

Good find. Would be nice to add an assertion on minimum rope length to catch this in the future.

(The newRope testing function might make this a little more complicated...)

Comment 2

[Ted Campbell [:tcampbell]]

Performance is actually quite bad for this in a micro-benchmark. https://jsfiddle.net/1yauhpsm/
https://share.firefox.dev/3F7Jg3z

Comment 3

[Matthew Gaudet (he/him) [:mgaudet]]

Attachment: WIP: Bug 1803855 - js::SubstringKernel should avoid making small ropes

Comment 4

[Matthew Gaudet (he/him) [:mgaudet]]

So I attached a WIP patch to this for feedback. I don't love the approach, but it works:

Limitations:

1. Both sides of the rope need to be linear to support using mozilla::PodCopy
2. I'm only 70% sure the templating makes any sense here.

My local testing shows that on a microbenchmark akin to what Ted posted in Comment #2 we improve performance by 10% on Latin1 strings and improve performance on Char16 strings by 20%.

I'm not sure if that's worth it for the extra complexity here, but it would be a step towards being able to assert that ropes are only used for strings longer than the inline string length.

Comment 5

[Matthew Gaudet (he/him) [:mgaudet]]

I'm going to unassign myself here -- I'm not sure when I'll get back to this, and if someone wants to fix my broken patch that'd be cool with me.

Comment 6

[André Bargull [:anba]]

Attachment: Bug 1803855 - Part 1: Add NewInlineString with array parameter. r=jandem!

NewInlineString function where the amount of characters to be copied can be
determined at compile-time. This allows the compiler to inline the memcpy call
using inline assembly, because the number of bytes is a const.

Part 4 will also call this new function.

Comment 7

[André Bargull [:anba]]

Attachment: Bug 1803855 - Part 2: Add StaticStrings::getUnitStringForElement with linear string parameter. r=jandem!

This function is called from CharSplitHelper for two-byte strings where the
input string is guaranteed to be a linear string. We could directly call
StaticStrings::getUnitString(), but testing has shown it doesn't improve
performance, probably because the compiler can't inline this on its own.

Depends on D192189

Comment 8

[André Bargull [:anba]]

Attachment: Bug 1803855 - Part 3: Inline calls to PodCopy. r=jandem!

PodCopy is called directly from other functions in "StringType.cpp" and
"StringType-inl.h", so for consistency call PodCopy everywhere instead of
going through FillChars. The FillChars version which converts from
char16 to Latin-1 is only called in AutoStableStringChars::copyAndInflateLatin1Chars,
directly inline it there. And finally move FillFromCompatible closer to its
callers, so it's next to CanStoreCharsAsLatin1.

Depends on D192190

Comment 9

[André Bargull [:anba]]

Attachment: Bug 1803855 - Part 4: Avoid creating small ropes in SubstringKernel. r=jandem!

The actual change to avoid creating small ropes in SubstringKernel.

The existing calls to NewDependentString on the left and right child nodes
were already linearising the child nodes. Move this linearisation into
SubstringKernel, so we can copy the characters more easily. Then if the final
length fits into inline strings, call SubstringInlineString to create a new
inline string.

Depends on D192191

Comment 10

[André Bargull [:anba]]

Attachment: Bug 1803855 - Part 5: Avoid duplicate code in NewString testing function. r=jandem!

Use a lambda function to avoid duplicating the code for Latin-1 and Two-byte
strings. This is in preparation for the next part, which will add new code to
this function.

Depends on D192192

Comment 11

[André Bargull [:anba]]

Attachment: Bug 1803855 - Part 6: Disallow creating small non-inline or rope strings. r=jandem!

Add assertions to ensure all small strings are created as inline strings. Then
update the testing functions, so they won't trigger the new assertions and fix
tests which created small ropes.

Depends on D192193

Comment 12

[André Bargull [:anba]]

Attachment: Bug 1803855 - Part 7: Prefer std::none_of to search for characters. r=jandem!

Drive-by change noticed while reading through this file. This loop can be
replaced with std::none_of, which Clang is able to optimise more easily to
read multiple characters at once.

Depends on D192194

Comment 13

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/073936638f57
Part 1: Add NewInlineString with array parameter. r=jandem
https://hg.mozilla.org/integration/autoland/rev/12eb211fc288
Part 2: Add StaticStrings::getUnitStringForElement with linear string parameter. r=jandem
https://hg.mozilla.org/integration/autoland/rev/fd0cb08b2b5d
Part 3: Inline calls to PodCopy. r=jandem
https://hg.mozilla.org/integration/autoland/rev/1a6dcbf80a6e
Part 4: Avoid creating small ropes in SubstringKernel. r=jandem
https://hg.mozilla.org/integration/autoland/rev/228e3b2ffba5
Part 5: Avoid duplicate code in NewString testing function. r=jandem
https://hg.mozilla.org/integration/autoland/rev/29cb9f950aab
Part 6: Disallow creating small non-inline or rope strings. r=jandem
https://hg.mozilla.org/integration/autoland/rev/6f44ed5f3e4b
Part 7: Prefer std::none_of to search for characters. r=jandem

Comment 14

[Cristian Tuns]

https://hg.mozilla.org/mozilla-central/rev/073936638f57
https://hg.mozilla.org/mozilla-central/rev/12eb211fc288
https://hg.mozilla.org/mozilla-central/rev/fd0cb08b2b5d
https://hg.mozilla.org/mozilla-central/rev/1a6dcbf80a6e
https://hg.mozilla.org/mozilla-central/rev/228e3b2ffba5
https://hg.mozilla.org/mozilla-central/rev/29cb9f950aab
https://hg.mozilla.org/mozilla-central/rev/6f44ed5f3e4b

Comment 15

[Mayank Bansal]

This bug, or one of bug 1861983 / bug 1861926 led to a 5% improvement on AWFY-JEtstream2-Chai-wtb-Average :
https://treeherder.mozilla.org/perfherder/graphs?highlightAlerts=1&highlightChangelogData=1&highlightCommonAlerts=0&selected=3911337,1787181062&series=mozilla-central,3737950,1,13&series=autoland,3911337,1,13&timerange=5184000&zoom=1698947443590,1699085947600,60.099048311809256,89.42616132162169