forego caching cycles leads to a severe perf regression

[ipetkov]

#60444 has introduced a severe perf regression when building/testing the conch-runtime crate.

Previously a test run would take ~5 mins, and with the latest nightly (rustc 1.36.0-nightly (372be4f36 2019-05-14)) it now takes ~82(!!) mins.

$ git clone https://github.com/ipetkov/conch-runtime.git
$ cd conch-runtime
$ cargo test --lib
   # snip
    Finished dev [unoptimized + debuginfo] target(s) in 4m 16s
$ cargo clean
$ cargo +nightly test --lib
   # snip
    Finished dev [unoptimized + debuginfo] target(s) in 82m 54s

Crate info

The crate offers the functionality to execute shell programs. Each piece of the grammar is represented as a node which can hold generic sub-nodes. The reasoning for this is so that the crate consumer could customize their AST with different/custom nodes, while reusing existing implementations.

The shell grammar is deeply recursive. Basically each command can vary in complexity (compound commands such as case, for, or simple commands like echo foo), but is ultimately made up of a list of shell words (literals, interpolations, etc.). Because each word can contain a command substitution, the AST type is recursive (a Command<W> has a Word<C> type, which gives us Command<Word<Command<...>>).

There are two "top-level" type definitions which seek to unify the entire AST tree concretely which are basically TopLevelCommand(Command<TopLevelWord>) TopLevelWord(Word<TopLevelCommand>).

The crate also heavily uses generics and trait bounds (perhaps overly so), however, there's hopefully some low hanging fruits that can reduce the 16x slow down in performance.

cc @nikomatsakis @pnkfelix

[pnkfelix]

a 16x compile-time regression does sound pretty bad indeed.

[pnkfelix]

triage: P-high. Leaving nomination tag, as I would like to discuss strategies for addressing this at the meeting, if possible.

[cramertj]

@matklad also thinks this might have caused this failure in rust-analyzer: rust-lang/rust-analyzer#1283

[pnkfelix]

"discussed" at T-compiler meeting. Assigning to self to investigate. Removing nomination tag.

[nikomatsakis]

Well, it was known that this could cause problems in performance. I don't know that there is a simple fix. (I suspect the errors in rust-analyzer are legit, as well)

[nikomatsakis]

But I was contemplating starting on a more complete re-write of the trait solver (kind of an intermediate step towards switching to chalk). I think that might be what is ultimately needed. (Note that chalk actually has a variant of this same bug...)

[nikomatsakis]

I have a potential fix for this.

UPDATE: But I may have just realized a flaw in the caching scheme I was planning on.

[nikomatsakis]

OK, #61754 is up, though still doing final tests. 🤞 When I ran it locally, it seemed to resolve the perf slowdown.