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

Closed
#14,210 2 comments 0 reactions 0 assignees View on GitHub
bug cranelift
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.