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>
5 files changed
tree: 65a44bd9357dd68e4e8b1df6ea7010dc769c5a90
  1. arm/
  2. arm64/
  3. internal/
  4. loong64/
  5. ppc64/
  6. riscv64/
  7. s390x/
  8. x86/
  9. codereview.cfg
  10. CONTRIBUTING.md
  11. go.mod
  12. go.sum
  13. LICENSE
  14. PATENTS
  15. README.md
README.md

arch

Go Reference

This repository holds machine architecture information used by the Go toolchain. The parts needed in the main Go repository are copied in.

Report Issues / Send Patches

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.