Huge CPU and RAM usage in redundant_clone/possible_borrower on long functions

[mwkmwkmwk]

Summary

Clippy takes a very large amount of time and RAM to analyze the following code. The time is spent in a single invocation of <rustc_mir_dataflow::framework::engine::Engine<clippy_utils::mir::possible_borrower::PossibleBorrowerAnalysis>>::iterate_to_fixpoint:

[...]
#6  0x00005567f6f1a249 in <rustc_mir_dataflow::framework::engine::Engine<clippy_utils::mir::possible_borrower::PossibleBorrowerAnalysis>>::iterate_to_fixpoint ()
#7  0x00005567f6f79839 in <clippy_utils::mir::possible_borrower::PossibleBorrowerMap>::new ()
#8  0x00005567f6e4d222 in <clippy_lints::redundant_clone::RedundantClone as rustc_lint::passes::LateLintPass>::check_fn ()
[...]

The bug happens with nightly-2022-12-30, while nightly-2022-12-29 is fine (clippy finishes near-instantly).

Reproducer

I tried this code:

fn meow(_s: impl AsRef<str>) {
}

macro_rules! quad {
    ($x:stmt) => {
        $x
        $x
        $x
        $x
    };
}

fn main() {
    let i = 0;
    quad!(quad!(quad!(quad!(quad!(meow(format!("abc{i}")))))));
}

(adjust amount of quad! to taste; the above will reliably OOM my machine)

I expected to see this happen:

Clippy finishes near-instantly.

Instead, this happened:

Clippy crashes with OOM after a while.

Version

rustc 1.68.0-nightly (ad8ae0504 2022-12-29)
binary: rustc
commit-hash: ad8ae0504c54bc2bd8306abfcfe8546c1bb16a49
commit-date: 2022-12-29
host: x86_64-unknown-linux-gnu
release: 1.68.0-nightly
LLVM version: 15.0.6

Additional Labels

No response

[llogiq]

So you have 1024 meow-calls? Sounds like my cat standing in front of the patio door.

[kayabaNerve]

I believe I have this same bug. January 1st nightly clippy is killed after ballooning to 6.1 GB in a few seconds. stable only uses 700 MB. Dec 30th also fails. Dec 29th is fine. While I do have macros, I have no so recursive (AFAIK). Unfortunately, I do not know what in my (rather large) library could serve as MWE.

https://github.com/serai-dex/serai/tree/develop/coins/monero in case it is somehow helpful. cargo +nightly-2022-12-29 clippy (ignoring features and tests) is enough to trigger the monstrous memory usage.

[Jarcho]

Probably due to #9701. Ping @smoelius.

I might have time to look at it in the next couple of days.

[smoelius]

Probably due to #9701.

No doubt.

One thing I noticed is that the meow example involves many singleton sets. So, storing the borrowers in HybridBitSets rather than BitSets helps (see #10144). On my laptop, Clippy gets through the example in a few seconds. But if add another quad, I wind up killing it after 20 seconds or so.

I experimented with a few variants of this idea. For example, using copy-on-write HybridBitSets seems to help a little, but not dramatically.

I am open to ideas.

[llogiq]

Perhaps we need a different approach that calculates the borrowers for a function once and caches that while linting the function to better amortize the work? To me it looks like we may be accidentally quadratic even with a less memory hungry representation.

Btw. I'm curious: How do hybrid bit sets compare to RoaringBitSets?

[amaanq]

Bisected and leaving this log here, still investigating on my end:

git bisect start
# status: waiting for both good and bad commits
# bad: [4fe3727c391ec5bf18019f304d87132a3e3c5211] Auto merge of #9701 - smoelius:improve-possible-borrower, r=Jarcho
git bisect bad 4fe3727c391ec5bf18019f304d87132a3e3c5211
# status: waiting for good commit(s), bad commit known
# bad: [4fe3727c391ec5bf18019f304d87132a3e3c5211] Auto merge of #9701 - smoelius:improve-possible-borrower, r=Jarcho
git bisect bad 4fe3727c391ec5bf18019f304d87132a3e3c5211
# status: waiting for good commit(s), bad commit known
# good: [8a6e6fd623a896a37c1d6defed56b7d98273d4fa] Auto merge of #10056 - koka831:fix/9993, r=Jarcho
git bisect good 8a6e6fd623a896a37c1d6defed56b7d98273d4fa
# bad: [ed519ad746e31f64c4e9255be561785612532d37] Improve `possible_borrower`
git bisect bad ed519ad746e31f64c4e9255be561785612532d37
# bad: [ed519ad746e31f64c4e9255be561785612532d37] Improve `possible_borrower`
git bisect bad ed519ad746e31f64c4e9255be561785612532d37
# good: [1e68973582403f62bf2d55aa2b805b43b4e931cc] Auto merge of #10067 - chansuke:issue-7943, r=giraffate
git bisect good 1e68973582403f62bf2d55aa2b805b43b4e931cc
# good: [c6477eb71188311f01f409da628fab7062697bd7] Add tests
git bisect good c6477eb71188311f01f409da628fab7062697bd7
# first bad commit: [ed519ad746e31f64c4e9255be561785612532d37] Improve `possible_borrower`

ed519ad746e31f64c4e9255be561785612532d37 is the first bad commit
commit ed519ad746e31f64c4e9255be561785612532d37
Author: Samuel Moelius <sam@moeli.us>
Date:   Wed Oct 12 04:34:25 2022 -0400

    Improve `possible_borrower`

 clippy_lints/src/dereference.rs           |   8 +-
 clippy_lints/src/redundant_clone.rs       |   4 +-
 clippy_utils/src/mir/possible_borrower.rs | 265 +++++++++++++++++++-----------
 tests/ui/needless_borrow.fixed            |   2 +-
 tests/ui/needless_borrow.stderr           |   8 +-
 tests/ui/redundant_clone.fixed            |   2 +-
 tests/ui/redundant_clone.stderr           |  14 +-
 7 files changed, 195 insertions(+), 108 deletions(-)

[mwkmwkmwk]

Second testcase that still OOMs even with #10173:

fn meow(_s: impl AsRef<str>) {}

macro_rules! quad {
    ($x:stmt) => {
        $x
        $x
        $x
        $x
    };
}

fn main() {
    quad!(quad!(quad!(for i in 0..4 {
        quad!(quad!(meow(format!("abc{i}"))));
    })));
}

[smoelius]

Oof. Thanks, @mwkmwkmwk.

[digama0]

This is also causing my project's CI to fail. I can minimize if necessary but since there are already a few examples I will wait to see if the fixes for the issues above also solve my problem.

[kayabaNerve]

Should the problem commit in question be reverted until a fixed version is available, since this has broken multiple projects? I understand nightly doesn't have the safety guarantees of stable, it's nightly, yet some targets require nightly and nightly is currently known to be not functioning to standards.

I'm unsure the exact policies here, just wanted to raise it and get the opinion of someone more educated. I've personally just stuck to 12-29 to avoid it, for now.

[Jarcho]

Clippy is normally synced every two weeks with with the main rust repo every two weeks. I believe the next sync is coming up this Thursday, so if it doesn't have a fix before then we can revert it right before the sync.