Stream: git-wasmtime

Topic: wasmtime / PR #3469 Avoid quadratic behavior in pathologi...

Wasmtime GitHub notifications bot (Oct 21 2021 at 19:17):

cfallin requested alexcrichton for a review on PR #3469.

Wasmtime GitHub notifications bot (Oct 21 2021 at 19:17):

cfallin opened PR #3469 from machbuffer-quadratic-labels to main:

Fixes #3468.

If a program has many instances of the pattern "goto next; next:" in a
row (i.e., no-op branches to the fallthrough address), the branch
simplification in MachBuffer would remove them all, as expected.
However, in order to work correctly, the algorithm needs to track all
labels that alias the current buffer tail, so that they can be adjusted
later if another branch chomp occurs.

When many thousands of this branch-to-next pattern occur, many thousands
of labels will reference the current buffer tail, and this list of
thousands of labels will be shuffled between the branch metadata struct
and the "labels at tail" struct as branches are appended and then
chomped immediately.

It's possible that with smarter data structure design, we could somehow
share the list of labels -- e.g., a single array of all labels, in order
they are bound, with ranges of indices in this array used to represent
lists of labels (actually, that seems like a better design in general);
but let's leave that to future optimization work.

For now, we can avoid the quadratic behavior by just "giving up" if the
list is too long; it's always valid to not optimize a branch. It is very
unlikely that the "normal" case will have more than 100 "goto next"
branches in a row, so this should not have any perf impact; if it does,
we will leave 1 out of every 100 such branches un-optimized in a long
sequence of thousands.

This takes total compilation time down on my machine from ~300ms to
~72ms for the foo.wasm case in #3441. For reference, the old backend
(now removed), built from arbitrarily-chosen-1-year-old commit
c7fcc344, takes 158ms, so we're ~twice as fast, which is what I would
expect.

(This PR also switches a few statics to consts just above where I added
a const, as s drive-by change.)

Wasmtime GitHub notifications bot (Oct 21 2021 at 19:27):

bjorn3 created PR review comment:

Would it be possible to keep the last few declared labels and forget the oldest ones? That should keep branch simplification working for many jmp next;next: in a row I think.

Wasmtime GitHub notifications bot (Oct 21 2021 at 19:27):

bjorn3 submitted PR review.

Wasmtime GitHub notifications bot (Oct 21 2021 at 19:33):

cfallin submitted PR review.

Wasmtime GitHub notifications bot (Oct 21 2021 at 19:33):

cfallin created PR review comment:

Unfortunately, no, the algorithm is built on the invariant that we know all labels that alias the tail; and labels_at_this_branch is also necessarily complete because it is used to refill "labels at tail" when a branch is chomped.

Also, the subtle bit here is that we're not actually forgetting labels directly, we're allowing a branch to be emitted; this means that the branch can no longer be chomped, so we can forget all the labels at the start of the branch, but only as a consequence of the top-level decision.

I think that if we wanted to do better, the data-structure design mentioned in the commit message is probably the way to go, but that's a bit past my risk-vs-reward threshold right now for this (critical to correctness) code :-)

Wasmtime GitHub notifications bot (Oct 21 2021 at 20:15):

alexcrichton submitted PR review.

Wasmtime GitHub notifications bot (Oct 21 2021 at 20:37):

cfallin merged PR #3469.

Last updated: Nov 22 2024 at 16:03 UTC