internal/unify: use arbitrary expressions for environment sets
Currently, nonDetEnv, which represents a set of environments, uses a
restricted algebraic form consisting of a cross-product of sets of
environments. Unfortunately, this restriction means that if we want to
union two environment sets, we may need to multiply factors out in
order to normalize the result into this restricted representation. In
some cases, this can result in exponential blowup. For example, if
there are nested sums, then the environment will contain bindings of
variables that don't matter for whole branches of the value
expression, but that still participate when constructing the union of
environment sets. These dead variables wind up expanding the
environment representation exponentially, even though they have no
effect.
To fix this, we lift this restriction. Now, a nonDetEnv is an
arbitrary algebraic expression of unions and cross-products. This is
actually much simpler, implementation-wise, and addresses this
exponential blowup problem.
We add a stress test demonstrated nested sums that prior to this
change required 12 GB of RAM and took 20 seconds to unify. With this
change, it takes 90 MB of RAM and a fraction of a second.
We're about to add "import" support to YAML, which will tend to create
these nested sums. Thus we have to fix this first.
This has no effect on the output of simdgen. Curiously, it also has no
effect on the time of simdgen, but it does reduce its memory by almost
10x:
│ /tmp/before.bench │ /tmp/after.bench │
│ sec/op │ sec/op vs base │
Simdgen 26.40 ± 3% 26.49 ± 26% ~ (p=1.000 n=10)
│ /tmp/before.bench │ /tmp/after.bench │
│ peak-RSS-bytes │ peak-RSS-bytes vs base │
Simdgen 1443.4Mi ± 1% 178.4Mi ± 1% -87.64% (p=0.000 n=10)
Change-Id: Idaecb8693065c61d5d63afbc1014d3300886def8
Reviewed-on: https://go-review.googlesource.com/c/arch/+/693338
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Junyang Shao <shaojunyang@google.com>
Auto-Submit: Austin Clements <austin@google.com>
This repository holds machine architecture information used by the Go toolchain. The parts needed in the main Go repository are copied in.
This repository uses Gerrit for code changes. To learn how to submit changes to this repository, see https://go.dev/doc/contribute.
The git repository is https://go.googlesource.com/arch.
The main issue tracker for the arch repository is located at https://go.dev/issues. Prefix your issue with “x/arch:” in the subject line, so it is easy to find.