[clang-tidy][NFC] Reduce map lookups in IncludeSorter

[njames93]

Summary

Because StringMapEntrys have stable addresses, The IncludeBuckets can be changed to store pointers to entrys instead of the key used for accessing IncludeLocations.
This saves having to lookup the IncludeLocations map as well as creating unnecessary strings.

[alexfh]

I wonder what motivated the patch. Is this a performance optimization? If so, do you have any measurements?

[njames93]

In D117460#3248613, @alexfh wrote:

I wonder what motivated the patch. Is this a performance optimization? If so, do you have any measurements?

I was doing some work on IncludeInserter and just thought, this seems unnecessary. It'd be hard to microbenchmark this, but I'll see what I can rustle up.

[LegalizeAdulthood]

Are we waiting on some sort of benchmark before accepting/rejecting this change?

[PiotrZSL]

This change is dangerous, it depends that elements/iterators won't be re-allocated/invalidated during insertion process.
Part with removing double lookup in IncludeSorter::addInclude looks fine, but part that involve IncludeBucket is problematic.
I will try to push part that involve IncludeLocations optimizations.

clang-tools-extra/clang-tidy/utils/IncludeSorter.h

 //===------------ IncludeSorter.h - clang-tidy ----------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_INCLUDESORTER_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_INCLUDESORTER_H
 
 #include "../ClangTidyCheck.h"
-#include <string>
 
 namespace clang {
 namespace tidy {
 namespace utils {
 
 /// Class used by ``IncludeInserterCallback`` to record the names of the
 /// inclusions in a given source file being processed and generate the necessary
 /// commands to sort the inclusions according to the precedence encoded in
private:
   FileID CurrentFileID;
   /// The file name stripped of common suffixes.
   StringRef CanonicalFile;
   /// Locations of visited include directives.
   SourceRangeVector SourceLocations;
   /// Mapping from file name to #include locations.
   llvm::StringMap<SourceRangeVector> IncludeLocations;
   /// Includes sorted into buckets.
-  SmallVector<std::string, 1> IncludeBucket[IK_InvalidInclude];
+  SmallVector<llvm::StringMapEntry<SourceRangeVector> *, 1>
+      IncludeBucket[IK_InvalidInclude];
 };
 
 } // namespace utils
 
 template <> struct OptionEnumMapping<utils::IncludeSorter::IncludeStyle> {
   static ArrayRef<std::pair<utils::IncludeSorter::IncludeStyle, StringRef>>
   getEnumMapping();
 };
 } // namespace tidy
 } // namespace clang
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_INCLUDESORTER_H

clang-tools-extra/clang-tidy/utils/IncludeSorter.cpp

IncludeSorter::IncludeSorter(const SourceManager *SourceMgr,
     : SourceMgr(SourceMgr), Style(Style), CurrentFileID(FileID),
       CanonicalFile(makeCanonicalName(FileName, Style)) {}
 
 void IncludeSorter::addInclude(StringRef FileName, bool IsAngled,
                                SourceLocation HashLocation,
                                SourceLocation EndLocation) {
   int Offset = findNextLine(SourceMgr->getCharacterData(EndLocation));
 
+  auto &MapEntry = *IncludeLocations.try_emplace(FileName).first;
   // Record the relevant location information for this inclusion directive.
-  IncludeLocations[FileName].push_back(
+  MapEntry.getValue().push_back(
       SourceRange(HashLocation, EndLocation.getLocWithOffset(Offset)));
-  SourceLocations.push_back(IncludeLocations[FileName].back());
+  SourceLocations.push_back(MapEntry.getValue().back());
 
   // Stop if this inclusion is a duplicate.
-  if (IncludeLocations[FileName].size() > 1)
+  if (MapEntry.getValue().size() > 1)
     return;
 
   // Add the included file's name to the appropriate bucket.
   IncludeKinds Kind =
       determineIncludeKind(CanonicalFile, FileName, IsAngled, Style);
   if (Kind != IK_InvalidInclude)
-    IncludeBucket[Kind].push_back(FileName.str());
+    IncludeBucket[Kind].push_back(&MapEntry);
 }
 
 Optional<FixItHint> IncludeSorter::createIncludeInsertion(StringRef FileName,
                                                           bool IsAngled) {
   std::string IncludeStmt;
   if (Style == IncludeStyle::IS_Google_ObjC) {
     IncludeStmt = IsAngled
                       ? llvm::Twine("#import <" + FileName + ">\n").str()
if (SourceLocations.empty()) {
     return FixItHint::CreateInsertion(
         SourceMgr->getLocForStartOfFile(CurrentFileID), IncludeStmt);
   }
 
   auto IncludeKind =
       determineIncludeKind(CanonicalFile, FileName, IsAngled, Style);
 
   if (!IncludeBucket[IncludeKind].empty()) {
-    for (const std::string &IncludeEntry : IncludeBucket[IncludeKind]) {
+    for (auto *IncludeMapEntry : IncludeBucket[IncludeKind]) {
+      StringRef IncludeEntry = IncludeMapEntry->getKey();
       if (compareHeaders(FileName, IncludeEntry, Style) < 0) {
-        const auto &Location = IncludeLocations[IncludeEntry][0];
+
+        const auto &Location = IncludeMapEntry->getValue().front();
         return FixItHint::CreateInsertion(Location.getBegin(), IncludeStmt);
       }
       if (FileName == IncludeEntry) {
         return llvm::None;
       }
     }
     // FileName comes after all include entries in bucket, insert it after
     // last.
-    const std::string &LastInclude = IncludeBucket[IncludeKind].back();
-    SourceRange LastIncludeLocation = IncludeLocations[LastInclude].back();
+    SourceRange LastIncludeLocation =
+        IncludeBucket[IncludeKind].back()->getValue().back();
     return FixItHint::CreateInsertion(LastIncludeLocation.getEnd(),
                                       IncludeStmt);
   }
   // Find the non-empty include bucket to be sorted directly above
   // 'IncludeKind'. If such a bucket exists, we'll want to sort the include
   // after that bucket. If no such bucket exists, find the first non-empty
   // include bucket in the file. In that case, we'll want to sort the include
   // before that bucket.
   IncludeKinds NonEmptyKind = IK_InvalidInclude;
   for (int I = IK_InvalidInclude - 1; I >= 0; --I) {
     if (!IncludeBucket[I].empty()) {
       NonEmptyKind = static_cast<IncludeKinds>(I);
       if (NonEmptyKind < IncludeKind)
         break;
     }
   }
   if (NonEmptyKind == IK_InvalidInclude) {
     return llvm::None;
   }
 
   if (NonEmptyKind < IncludeKind) {
     // Create a block after.
-    const std::string &LastInclude = IncludeBucket[NonEmptyKind].back();
-    SourceRange LastIncludeLocation = IncludeLocations[LastInclude].back();
+    SourceRange LastIncludeLocation =
+        IncludeBucket[NonEmptyKind].back()->getValue().back();
     IncludeStmt = '\n' + IncludeStmt;
     return FixItHint::CreateInsertion(LastIncludeLocation.getEnd(),
                                       IncludeStmt);
   }
   // Create a block before.
-  const std::string &FirstInclude = IncludeBucket[NonEmptyKind][0];
-  SourceRange FirstIncludeLocation = IncludeLocations[FirstInclude].back();
+  SourceRange FirstIncludeLocation =
+      IncludeBucket[NonEmptyKind][0]->getValue().back();
   IncludeStmt.append("\n");
   return FixItHint::CreateInsertion(FirstIncludeLocation.getBegin(),
                                     IncludeStmt);
 }
 
 } // namespace utils
 
 llvm::ArrayRef<std::pair<utils::IncludeSorter::IncludeStyle, StringRef>>