[clang-tidy] misc-confusable-identifiers checker is very slow

[zygoloid]

We're seeing the misc-confusable-identifiers checker be easily 10x slower than any other clang-tidy check. I think this check becomes slow in the presence of an identifier declared many times -- such as a large overload set.

The current implementation appears to be quadratic in the number of redeclarations of a given identifier.

[llvmbot]

@llvm/issue-subscribers-clang-tidy

Author: Richard Smith (zygoloid)

We're seeing the misc-confusable-identifiers checker be easily 10x slower than any other clang-tidy check. I think this check becomes slow in the presence of an identifier declared many times -- such as a large overload set.

The current implementation appears to be quadratic in the number of redeclarations of a given identifier.

[denzor200]

Please provide additional information about clang-tools-extra version you using.
It's known that "misc-confusable-identifiers" was seriously optimized in this change, does your tool include that change?

Otherwise it would be nice to provide cpp which were the described performance issue reproduces.
Or at least let us know the minumum number of redeclarations of a given identifier to see the problem.

[zygoloid]

It looks like I was using clang-tidy version 16, which I think does not have that change. I've tried again with clang-tidy 18, and this check is indeed a lot faster.

It's still much slower than it should be, but it's taking less than 2% of the overall clang-tidy time, so I suppose a lot of these checks are a lot slower than they should be. I note that the new implementation is still (unnecessarily) quadratic in the number of redeclarations of an identifier, and does a lot more work than is necessary repeatedly computing skeletons for the same identifier.

[zygoloid]

Sent #130369 to improve the performance (and fix some bugs in the implementation).