bytecodealliance / bytecodealliance/wasmtime
Cranelift: compiling a module with many allocating global initializers is superlinear under the copying collector, and v48 makes it several times worse
- Dominant language
- Rust
- Stars
- 18.6k
- Forks
- 1.8k
- Avg merge
- 1d 19h
- Merged PRs (30d)
- 121
Description
### Test Case (with a WAT generator)
A module that is nothing but `N` globals whose initializers allocate a GC struct. No functions, no imports, no data segments.
```js
// gen.mjs — node gen.mjs > repro.wat
const n = Number(process.argv[2] ?? 500);
const out = ['(module', ' (type $node (struct (field $val i32) (field $tag i32)))'];
for (let i = 0; i < n; i++) {
out.push(` (global $g${i} (ref $node) (struct.new $node (i32.const ${i}) (i32.const 0)))`);
}
out.push(')');
process.stdout.write(out.join('\n') + '\n');
```
### Steps to Reproduce
* `node gen.mjs 1000 > repro.wat`
* `wasmtime compile -o /dev/null repro.wat` — all defaults; since #13756 the default collector is copying, so nothing needs to be turned on.
* Repeat for `N` = 250, 500, 1000, 2000, and compare against `-C collector=drc`.
### Expected Results
Compile time grows linearly in `N`, as it does with `-C collector=drc`.
### Actual Results
Compile time is superlinear in `N`. Wall time of `wasmtime compile`, aarch64 macOS, release build of `main` (`0ac37df998`):
| N | copying | drc | copying, per doubling |
| ---: | ---: | ---: | ---: |
| 250 | 0.17 s | 0.01 s | — |
| 500 | 1.01 s | 0.01 s | 5.9x |
| 1000 | 8.6 s | 0.04 s | 8.5x |
| 2000 | 67.0 s | 0.12 s | 7.8x |
`Module::new` on x86_64 Linux, `OptLevel::Speed`, comparing releases:
| N | 47.0.3 copying | 48.0.1 copying | 48.0.1 drc | 48 / 47 |
| ---: | ---: | ---: | ---: | ---: |
| 250 | 0.082 s | 0.244 s | 0.015 s | 3.0x |
| 500 | 0.424 s | 1.63 s | 0.031 s | 3.8x |
| 1000 | 2.65 s | 12.5 s | 0.065 s | 4.7x |
| 2000 | 21.96 s | 96.4 s | 0.134 s | 4.4x |
drc is linear; copying is superlinear on both 47 and 48 — the superlinearity is not new in 48, but 48 raises both the constant and the exponent, and that is what takes [a real module](https://github.com/wado-lang/wado/pull/1902) from "slow" to "does not finish":
| Real 1.8 MB component | `Component::new` |
| --- | --- |
| 47.0.3 copying | 5.2 s |
| 48.0.1 copying | not finished after 14 min (killed) |
| 48.0.1 drc | 8.0 s |
That component is a generated SQLite-grammar parser whose constant data is globalized into ~2500 `struct.new` and ~2500 `array.new` global initializers. Stubbing every function body in it to `unreachable` leaves the blowup intact, which is what pointed at the globals.
### Versions and Environment
Wasmtime version or commit: 48.0.1 (cranelift-codegen 0.135.1) and `main` at `0ac37df998`, compared against 47.0.3 (0.134.3)
Operating system: Linux (48.0.1 / 47.0.3 numbers), macOS 26 (`main` numbers)
Architecture: x86_64 and aarch64
### Extra Info
**Where the time goes.** Effectively every sample of the compiling thread lands in the alias-analysis fixpoint. `sample` on `main` at N=2000, top of stack:
```
cranelift_codegen::alias_analysis::observe 1803
cranelift_codegen::alias_analysis::LastStores::meet_from 880
cranelift_codegen::alias_analysis::LastStores::update 718
cranelift_codegen::alias_analysis::AliasAnalysis::new 72
```
all under `AliasAnalysis::new` ← `Context::optimize`. On the real component the time is in `LastStores::update` rather than `meet_from` — same pass, same caller. `-O opt-level=0` skips `optimize`, and the blowup with it; `-C collector=null` does not show it either.
**Reading of the cause.** `LastStores.regions` is a `SecondaryMap>`, and both consumers walk every region:
- `LastStores::observe_others` (`cranelift/codegen/src/alias_analysis.rs`) iterates `self.regions` for each trapping store.
- `LastStores::meet_from` (`cranelift/codegen/src/alias_analysis.rs`) iterates `0..max(regions.keys().len(), rhs.regions.keys().len())` for each CFG edge.
`AliasRegion` is an unbounded `u32` entity, and since #14115 Wasmtime gives each statically-known entity its own region — `AliasRegionKey::DefinedGlobal { module, index }` in `crates/cranelift/src/alias_region.rs` — so `N` globals means `N` regions. All of the initializers land in one synthesized function (`FuncEnvironment::module_initialize_global`, `crates/cranelift/src/func_environ.rs`), giving `N` stores × `N` regions before the block fixpoint multiplies it again.
That also fits the copying/drc split: the copying collector's allocation sequence stores through a trapping path, so each one takes the full `observe_others` walk, while drc's barriers stay out of it.
The 48-specific part is presumably the dead-store elimination landed in #13806 / #13947 (closing #4167): the pass grew a whole-function `observed_stores` map that `observe` now writes on every one of those walks. #13806 measured a small compile-time cost on some Sightglass benchmarks and #13947 reports that recovered; a module with thousands of globals is far outside what those benchmarks cover.
Contributor guide
Assessment
This issue has not been assessed yet.