Attaching allocation ICs in a very large function takes quadratic time (seen on YouTube page load)
Categories
(Core :: JavaScript Engine: JIT, defect)
Tracking
()
| Tracking | Status | |
|---|---|---|
| firefox162 | --- | fixed |
People
(Reporter: plawless, Assigned: plawless)
References
Details
Attachments
(1 external file)
Filed in Performance: General for a perf review first. Recommended component once reviewed: Core :: JavaScript Engine: JIT.
ICScript::getOrCreateAllocSite finds an existing site by scanning allocSites_ linearly for a matching pcOffset, then appends a new site if none matches:
https://searchfox.org/firefox-main/rev/d9bd6be9a67efb1c2667ef91a89856f35eb7cf5e/js/src/jit/JitScript.cpp#903
Each NewArray, NewObject or Lambda IC that attaches in a function that already has a baseline script goes through this lookup (IRGenerator::maybeCreateAllocSite). The lookup cost grows with the list, and once the per-minor-GC creation cap is reached (MaxAllocSitesPerMinorGC, 600) a miss doesn't add an entry: it scans the whole list, then returns the zone's unknownAllocSite. Nothing records that miss, so the next attach at a new pc scans the whole list again. A large function that runs many distinct allocation sites once pays (number of attaches) × (list length).
Measured on youtube.com with temporary counters in getOrCreateAllocSite (local opt build, 7 loads). The largest list belongs to the top-level function of YouTube's main bundle, which reaches 2,940–3,549 sites when YouTube serves base_module_set, and 4,096–8,191 in an earlier run where it served kevlar_base. Over the whole content process, each load does 37,000–41,000 lookups that miss after the cap and scans 76–84 million list entries. None of those lookups find an existing site. (Counts are sampled at power-of-two call counts, so they are lower bounds.)
In profiles this shows up in the top-level function of YouTube's main bundle (kevlar_base or base_module_set; YouTube served different bundles across runs), inside the single long task (215–233 ms) that runs just before DOMContentLoaded. Of that task's samples, 18–26% are in getOrCreateAllocSite and AllocSite::pcOffset, called from DoNewArrayFallback → tryAttachArrayObject, DoLambdaFallback → tryAttachFunctionClone and DoNewObjectFallback → tryAttachPlainObject. That held on Firefox Nightly (macOS, M4 Pro) and on a local opt build at d9bd6be9a67e, across the different bundles YouTube served.
Profile (Nightly, warm load of youtube.com): https://share.firefox.dev/3WuicI1
Shell reproduction (xpcshell from an opt build, best of 3). Each test function warms up until it gets a baseline script, then runs N distinct [], ({}) and (() => 0) sites once each. The control spreads the same N across separate functions of 100 sites each:
| Sites | One function | 100 sites per function |
|---|---|---|
| 16k | 9 ms | 7 ms |
| 32k | 36 ms | 11 ms |
| 64k | 143 ms | 23 ms |
| 128k | 556 ms | 45 ms |
Generator (writes v2-one-<N>.js / v2-split-<N>.js; run with python3 gen2.py <N> one|split):
import sys
n, mode = int(sys.argv[1]), sys.argv[2]
kinds = ["[]", "({})", "(() => 0)"]
warm = "for (let w = 0; w < 2000; w++) {}"
def body(lo, hi): return "\n".join(f" s = {kinds[k % 3]};" for k in range(lo, hi))
out = ["var t0 = Date.now(); var s;"]
if mode == "one":
out.append(f"(function root() {{ var s;\n{warm}\n{body(0, n)}\n}})();")
else:
for f in range(0, n, 100):
out.append(f"(function r{f}() {{ var s;\n{warm}\n{body(f, min(f + 100, n))}\n}})();")
out.append('dump("ms=" + (Date.now() - t0) + "\\n");')
open(f"v2-{mode}-{n}.js", "w").write("\n".join(out))
Possible fixes: key the sites by pcOffset (a hash map, or a binary search since sites are mostly appended in increasing pc order), and avoid the full scan on the capped path, which on YouTube is almost all of the calls.
Related: bug 1969328 (moving alloc-site creation to trial inlining) and bug 1996989 (memory used by alloc-site storage in ICScript) touch the same code.
| Assignee | ||
Comment 1•6 days ago
|
||
Local patch: keep allocSites_ sorted by pcOffset and look sites up with mozilla::BinarySearchIf, inserting at the found index. This also makes the lookup on the capped path, which on YouTube is almost every call, logarithmic.
Shell reproduction from comment 0, one function:
| Sites | Before | After |
|---|---|---|
| 16k | 9 ms | 3 ms |
| 32k | 36 ms | 6 ms |
| 64k | 143 ms | 12 ms |
| 128k | 556 ms | 25 ms |
Try, tp6 YouTube, 6 jobs per side: https://perf.compare/compare-lando-results?landoInstance=lando-prod-2025&baseLando=117027&newLando=117028&baseRepo=try&newRepo=try&framework=13
Recorded page, median per job, base → patched:
| Linux | Windows | macOS 14.7 | |
|---|---|---|---|
| loadtime, cold | 1204 → 1095 ms (−9.0%) | 780 → 730 ms (−6.3%) | 1628 → 1392 ms (−14.5%) |
| LCP, cold | −7.9% | −5.3% | −16.4% |
| SpeedIndex, cold | −11.9% | −6.9% | −16.1% |
| loadtime, warm | −4.2% | −1.3% | +2.2% (low confidence) |
Live YouTube shows loadtime and LCP improvements of 2–13% on all three platforms. Warm cpuTime on the recorded page went up 2.3% on Linux and 7.8% on macOS (medium confidence) with no matching loadtime regression; that is the one result I'd like a second look at.
Try auto with the patch has no failures: https://treeherder.mozilla.org/jobs?repo=try&landoInstance=lando-prod-2025&landoCommitID=117025
| Assignee | ||
Comment 2•5 days ago
|
||
Large run-once functions attach thousands of allocation ICs, and each attach
scanned the whole list, including after the per-GC creation cap was hit.
Updated•5 days ago
|
Comment 4•2 days ago
|
||
| bugherder | ||
Comment 5•2 days ago
|
||
| bugherder | ||
Updated•2 days ago
|
Description
•