1959310 - String deduplication is complicated and slow

Status: ASSIGNED

(Core :: JavaScript Engine, task, P1)

Description

[Steve Fink [:sfink] [:s:]]

Bug 1895628 was a decent simplification without touching the underlying algorithm. But now that chains of dependent strings are even less likely than they were, and the chains that are possible are constrained in terms of which heap they're in (nursery vs tenured), I think this can all move to a single-pass algorithm.

Comment 1

[Steve Fink [:sfink] [:s:]]

I wasn't able to prove that it is never possible to have a chain ND1 -> TD2 -> NL3, where ND1 is a nursery dependent string, TD2 is a tenured dependent string, and NL3 is a nursery (non-dependent) linear string. But given that I haven't come up with a way to create that situation without cheating with a test function, I decided that it's good enough if that does a fallible allocation (with an oomUnsafe crash) during minor GC in the unlikely or impossible event that it actually happens.

I also added the testing function that allows it to happen anyway, just in case, so that this fallback code path is executed. To hit it, you need a dependent string in the nursery whose chain of bases goes through the tenured heap but ends up back in the nursery. Even then, it won't be a problem if the base string hasn't been promoted yet. These are precisely the cases where a deduplicated (or tenured-to-atom) base string moves its character data, but there's no way for nursery strings that depend on it to know what the original pointer was.

Comment 2

[Steve Fink [:sfink] [:s:]]

Attachment: Bug 1959310 - Single-pass string deduplication r=jonco - Remove order-dependence between dependent strings and their bases by force-promoting their root base strings rather than using separate fixup phases (and different fixups for nursery and...

• Remove order-dependence between dependent strings and their bases by force-promoting their root base strings rather than using separate fixup phases (and different fixups for nursery and tenured strings) to adjust things after everything live is guaranteed to be promoted.
• Force-promotion is a recursive call, but it is guaranteed to bottom out immediately because root bases are never themselves dependent strings.
• Remove the aforementioned fixup phases (the nursery one still exists, but for recursing through ropes only)

This depends on dependent strings and root base strings being disjoint sets: while a dependent string's base can itself be a dependent string, the root base will never be. This is safe; it is the way it has always been.

Note that this patch introduces a theoretical bug that requires the full two-pass machinery to fix, but is at least rare and very possibly impossible to encounter in practice. The following patch will fix it.

Comment 3

[Steve Fink [:sfink] [:s:]]

Attachment: Bug 1959310 - Handle the nursery -> tenured -> nursery case by cloning the original characters (which will not yet have been freed or poisoned) in the event that a promoted nursery string can't recover its original characters pointer r=jonco

Comment 4

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/9c26d4803769
Single-pass string deduplication r=jonco
https://hg.mozilla.org/integration/autoland/rev/1220dffba9a0
Handle the nursery -> tenured -> nursery case by cloning the original characters (which will not yet have been freed or poisoned) in the event that a promoted nursery string can't recover its original characters pointer r=jonco

Comment 5

[Serban Stanca [:SerbanS]]

Backed out for causing spidermonkey bustages in Tenuring.cpp.

• Backout link
• Push with failures
• Failure Log
• Failure line: Assertion failure: nursery_.inCollectedRegion(str), at /builds/worker/checkouts/gecko/js/src/gc/Tenuring.cpp:156

Comment 6

[Narcis Beleuzu [:NarcisB]]

Backed out in addition to another changeset
Backout link: https://hg-edge.mozilla.org/integration/autoland/rev/bdc4e3df9b0b39caa628026d4ff80e16d2124a74

Comment 7

[Steve Fink [:sfink] [:s:]]

I fixed the bug that caused the backout, then merged the two patches together (because the tests will fail with just the first applied), then fought moz-phab because it wouldn't accept the updated patch whether I used jj or git. Finally imported it into mercurial, and Phabricator accepted that. I still have no idea what's going on with that.

Hopefully it will stick now.

Comment 8

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/f47850a3514e
Single-pass string deduplication r=jonco