1932624 - Have a less expensive book-keeping for mRunsAvail

Status: RESOLVED FIXED

(Core :: Memory Allocator, enhancement)

Description

[Jens Stutte [:jstutte]]

mRunsAvail's primary use seems to be "find a run of at least size X". That means the sort criteria "size" could be enough if then we had just a plain list of runs behind each size, getting us a potentially much smaller and much more stable tree. The difficulty here is that we cannot easily use hash maps or other standard implementations, as we must avoid normal allocations during these operations.

This would reduce the cost of adding, removing and finding those runs (under the assumption that we have many runs of the same size) and also get us for free a "most recently made available" policy for those runs on re-use.

Note that operations on mRunsAvail show up in profiles and potentially contribute to keeping arena_t::mLock blocked.

Comment 1

[Paul Bone [:pbone]]

Attachment: Bug 1932624 - p1. Fix an incorrect variable name in a comment r=glandium

Comment 2

[Paul Bone [:pbone]]

Attachment: Bug 1932624 - p2. Replace the mRunsAvail RedBlackTree with an array of lists r=glandium

Replace the mRunsAvail RedBlackTree with a new class that uses an array
of linked lists. Inserting and removing runs are now constant time.
Searching for a run is linear with respect to the number of possible
sizes. The next patch will amortise that cost.

Comment 3

[Paul Bone [:pbone]]

Attachment: Bug 1932624 - p3. Use a hint to avoid a linear scan r=glandium

Comment 4

[Paul Bone [:pbone]]

Here is a prefhearder link for these changes: https://perf.compare/compare-results?baseRev=ab1aa584a75dd4d5054ed8a03405daa8c2d61f8f&baseRepo=try&newRev=52da6d23edc91dc72046025d9ca19b81533409f5&newRepo=try&framework=13 This is an improvment everywhere except MacOS 14, but it makes fragmentation worse.

Comment 5

[Jens Stutte [:jstutte]]

(In reply to Paul Bone [:pbone] from comment #4)

Here is a prefhearder link for these changes: https://perf.compare/compare-results?baseRev=ab1aa584a75dd4d5054ed8a03405daa8c2d61f8f&baseRepo=try&newRev=52da6d23edc91dc72046025d9ca19b81533409f5&newRepo=try&framework=13 This is an improvment everywhere except MacOS 14, but it makes fragmentation worse.

Nice! There seem to be improvements across the board (looking at the details) except for old macOS (regression) and windows11-64-24h2-shippable (unchanged, but hw-ref Windows improved). In particular Android seems to like it.

Comment 6

[Paul Bone [:pbone]]

(In reply to Paul Bone [:pbone] from comment #4)

Here is a prefhearder link for these changes: https://perf.compare/compare-results?baseRev=ab1aa584a75dd4d5054ed8a03405daa8c2d61f8f&baseRepo=try&newRev=52da6d23edc91dc72046025d9ca19b81533409f5&newRepo=try&framework=13 This is an improvment everywhere except MacOS 14, but it makes fragmentation worse.

Here's the direct link to the AWSY change: https://perf.compare/compare-results?baseRev=ab1aa584a75dd4d5054ed8a03405daa8c2d61f8f&baseRepo=try&newRev=52da6d23edc91dc72046025d9ca19b81533409f5&newRepo=try&framework=4&search=resident

The base resident memory is affected more than the general resident memory. So the general difference should be small.

Comment 7

[Pulsebot]

Pushed by [e-mail]:
https://github.com/mozilla-firefox/firefox/commit/beb98e529cb6
https://hg.mozilla.org/integration/autoland/rev/88012802497e
p1. Fix an incorrect variable name in a comment r=glandium
https://github.com/mozilla-firefox/firefox/commit/e6ea5591fce8
https://hg.mozilla.org/integration/autoland/rev/725af738b4c7
p2. Replace the mRunsAvail RedBlackTree with an array of lists r=glandium
https://github.com/mozilla-firefox/firefox/commit/7dcfcde206e9
https://hg.mozilla.org/integration/autoland/rev/9e3acd6857df
p3. Use a hint to avoid a linear scan r=glandium

Comment 8

[amarc]

https://hg.mozilla.org/mozilla-central/rev/88012802497e
https://hg.mozilla.org/mozilla-central/rev/725af738b4c7
https://hg.mozilla.org/mozilla-central/rev/9e3acd6857df

Comment 9

[Florin Bilt]

(In reply to amarc from comment #8)

https://hg.mozilla.org/mozilla-central/rev/88012802497e
https://hg.mozilla.org/mozilla-central/rev/725af738b4c7
https://hg.mozilla.org/mozilla-central/rev/9e3acd6857df

Perfherder has detected a devtools performance change from push 9e3acd6857df9064c79755e846a59ad63c0076f2.

No action is required from the author; this comment is provided for informational purposes only.

Improvement	Test	Platform	Options	Absolute values [old vs new]
15%	damp source-map-loader.init.DAMP (doc)	linux2404-64-shippable	e10s fission stylo webrender	41.05 ms -> 35.02 ms
3%	damp server.protocoljs.DAMP (doc)	linux2404-64-shippable	e10s fission stylo webrender	798.46 ms -> 774.00 ms

Need Help or Information?

If you have any questions, please reach out to [e-mail]. Alternatively, you can find help on Slack by joining #perf-help, and on Matrix you can find help by joining #perftest.

Details of the alert can be found in the alert summary, including links to graphs and comparisons for each of the affected tests.

Comment 10

[Florin Bilt]

(In reply to amarc from comment #8)

https://hg.mozilla.org/mozilla-central/rev/88012802497e
https://hg.mozilla.org/mozilla-central/rev/725af738b4c7
https://hg.mozilla.org/mozilla-central/rev/9e3acd6857df

Perfherder has detected a browsertime performance change from push 9e3acd6857df9064c79755e846a59ad63c0076f2.

No action is required from the author; this comment is provided for informational purposes only.

Improvement	Test	Platform	Options	Absolute values [old vs new]
6%	jetstream3 bomb-workers-Average (doc)	android-hw-a55-14-0-aarch64-shippable	fission webrender	157.75 ms -> 148.32 ms
6%	jetstream3 bomb-workers-Average (doc)	android-hw-a55-14-0-aarch64-shippable	webrender	158.34 ms -> 149.38 ms
5%	speedometer3 cpuTime (doc)	android-hw-a55-14-0-aarch64-shippable	fission webrender	116,940.74 ms -> 110,912.50 ms
4%	speedometer3 wallclock-for-tracking-only (doc)	android-hw-a55-14-0-aarch64-shippable	fission webrender	73,306.74 ms -> 70,291.05 ms
4%	speedometer3 Editor-TipTap/total (doc)	android-hw-a55-14-0-aarch64-shippable	fission webrender	132.84 ms -> 127.93 ms
2%	speedometer3 total (doc)	android-hw-a55-14-0-aarch64-shippable	fission webrender	3,265.75 ms -> 3,191.94 ms

Need Help or Information?

If you have any questions, please reach out to [e-mail]. Alternatively, you can find help on Slack by joining #perf-help, and on Matrix you can find help by joining #perftest.

Details of the alert can be found in the alert summary, including links to graphs and comparisons for each of the affected tests.