Author: Victor Chernyakin Date: 2026-01-04T13:42:02-08:00 New Revision: fd0bf4addec3ac2716dcc6869bcff6bd8bb342c7
URL: https://github.com/llvm/llvm-project/commit/fd0bf4addec3ac2716dcc6869bcff6bd8bb342c7 DIFF: https://github.com/llvm/llvm-project/commit/fd0bf4addec3ac2716dcc6869bcff6bd8bb342c7.diff LOG: [clang-tidy] Speed up deduplicating warnings from alias checks (#174237) Right now, the deduplication algorithm runs in O(n²) time, because it goes warning-by-warning (an O(n) operation), removing duplicates using `std::vector::erase` (another O(n) operation). This starts taking up a noticeable amount of time as you start getting a lot of warnings. For example, running all checks over `clang/lib/Sema/Sema.cpp` and the headers it includes: ```sh time ./build/release/bin/clang-tidy -p build/debug --checks=* clang/lib/Sema/Sema.cpp -header-filter=.* > /dev/null ``` ...takes 2m9s on my system before this change and 1m52s after. Now, this scenario *is* a bit artificial; I imagine runs with so many warnings are uncommon in practice. On the other hand, the change is quite small, so we're not really going out of our way to improve it. Added: Modified: clang-tools-extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp Removed: ################################################################################ diff --git a/clang-tools-extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp b/clang-tools-extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp index 0355eccc397e5..7d6827f0af653 100644 --- a/clang-tools-extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp +++ b/clang-tools-extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp @@ -683,8 +683,6 @@ void ClangTidyDiagnosticConsumer::removeIncompatibleErrors() { std::tuple<unsigned, EventType, int, int, unsigned> Priority; }; - removeDuplicatedDiagnosticsOfAliasCheckers(); - // Compute error sizes. std::vector<int> Sizes; std::vector< @@ -760,9 +758,12 @@ struct LessClangTidyError { const tooling::DiagnosticMessage &M1 = LHS.Message; const tooling::DiagnosticMessage &M2 = RHS.Message; - return std::tie(M1.FilePath, M1.FileOffset, LHS.DiagnosticName, - M1.Message) < - std::tie(M2.FilePath, M2.FileOffset, RHS.DiagnosticName, M2.Message); + // Having DiagnosticName (i.e. the check name) last means sorting + // using this predicate puts duplicate diagnostics into consecutive runs, a + // property which removeDuplicatedDiagnosticsOfAliasCheckers() relies on. + return std::tie(M1.FilePath, M1.FileOffset, M1.Message, + LHS.DiagnosticName) < + std::tie(M2.FilePath, M2.FileOffset, M2.Message, RHS.DiagnosticName); } }; struct EqualClangTidyError { @@ -778,43 +779,38 @@ std::vector<ClangTidyError> ClangTidyDiagnosticConsumer::take() { llvm::stable_sort(Errors, LessClangTidyError()); Errors.erase(llvm::unique(Errors, EqualClangTidyError()), Errors.end()); - if (RemoveIncompatibleErrors) + if (RemoveIncompatibleErrors) { + removeDuplicatedDiagnosticsOfAliasCheckers(); removeIncompatibleErrors(); + } return std::move(Errors); } -namespace { -struct LessClangTidyErrorWithoutDiagnosticName { - bool operator()(const ClangTidyError *LHS, const ClangTidyError *RHS) const { - const tooling::DiagnosticMessage &M1 = LHS->Message; - const tooling::DiagnosticMessage &M2 = RHS->Message; - - return std::tie(M1.FilePath, M1.FileOffset, M1.Message) < - std::tie(M2.FilePath, M2.FileOffset, M2.Message); - } -}; -} // end anonymous namespace - void ClangTidyDiagnosticConsumer::removeDuplicatedDiagnosticsOfAliasCheckers() { - using UniqueErrorSet = - std::set<ClangTidyError *, LessClangTidyErrorWithoutDiagnosticName>; - UniqueErrorSet UniqueErrors; + if (Errors.size() <= 1) + return; - auto IT = Errors.begin(); - while (IT != Errors.end()) { - ClangTidyError &Error = *IT; - const std::pair<UniqueErrorSet::iterator, bool> Inserted = - UniqueErrors.insert(&Error); + static constexpr auto AreDuplicates = [](const ClangTidyError &E1, + const ClangTidyError &E2) { + const tooling::DiagnosticMessage &M1 = E1.Message; + const tooling::DiagnosticMessage &M2 = E2.Message; + return std::tie(M1.FilePath, M1.FileOffset, M1.Message) == + std::tie(M2.FilePath, M2.FileOffset, M2.Message); + }; + auto LastUniqueErrorIt = Errors.begin(); + for (ClangTidyError &Error : llvm::drop_begin(Errors, 1)) { + ClangTidyError &ExistingError = *LastUniqueErrorIt; // Unique error, we keep it and move along. - if (Inserted.second) { - ++IT; + if (!AreDuplicates(Error, ExistingError)) { + ++LastUniqueErrorIt; + if (&*LastUniqueErrorIt != &Error) // Avoid self-moves. + *LastUniqueErrorIt = std::move(Error); } else { - ClangTidyError &ExistingError = **Inserted.first; const llvm::StringMap<tooling::Replacements> &CandidateFix = Error.Message.Fix; const llvm::StringMap<tooling::Replacements> &ExistingFix = - (*Inserted.first)->Message.Fix; + ExistingError.Message.Fix; if (CandidateFix != ExistingFix) { // In case of a conflict, don't suggest any fix-it. @@ -833,7 +829,7 @@ void ClangTidyDiagnosticConsumer::removeDuplicatedDiagnosticsOfAliasCheckers() { // Since it is the same error, we should take it as alias and remove it. ExistingError.EnabledDiagnosticAliases.emplace_back(Error.DiagnosticName); - IT = Errors.erase(IT); } } + Errors.erase(std::next(LastUniqueErrorIt), Errors.end()); } _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
