[clangd] Make stable_partition on include candidates less slow. NFC

[ioeric]

Summary

stable_partition on objects is slow (due to copies). Do it on pointers
instead.

[sammccall]

clangd/CodeComplete.cpp

325

this seems a bit overly complicated. It does seem like a worry that this code is hot enough to optimize, especially compared to *generating* the list.

But I think we can do something simpler...

415

if this is really hot, you might want to reserve(C.RankedIncludeHeaders.size())

422

What about
(Include.Insertion ? InsertableCandidates : IncludeCandidates).push_back(std::move(Include))

where InsertableCandidates is a vector declared above, and then just move it onto the end of the list after the loop?

[ioeric]

• simplify the code.

[sammccall]

The implementation looks fine, but I believe we concluded that seeing huge lists here was basically a bug.
So you may not want to land it, if you prefer to keep things simple. Up to you.

clangd/CodeComplete.h

struct IncludeCandidate {
     std::string Header;
     // Present if Header should be inserted to use this item.
     llvm::Optional<TextEdit> Insertion;
   };
   // All possible include headers ranked by preference. By default, the first
   // include is used.
   // If we've bundled together overloads that have different sets of includes,
   // thse includes may not be accurate for all of them.
-  llvm::SmallVector<IncludeCandidate, 1> Includes;
+  using IncludeCandidates = llvm::SmallVector<IncludeCandidate, 1>;
+  IncludeCandidates Includes;
 
   /// Holds information about small corrections that needs to be done. Like
   /// converting '->' to '.' on member access.
   std::vector<TextEdit> FixIts;
 
   /// Holds the range of the token we are going to replace with this completion.
   Range CompletionTokenRange;
 

clangd/CodeComplete.cpp

struct ScoredBundleGreater {
   bool operator()(const ScoredBundle &L, const ScoredBundle &R) {
     if (L.second.Total != R.second.Total)
       return L.second.Total > R.second.Total;
     return L.first.front().Name <
            R.first.front().Name; // Earlier name is better.
   }
 };
 
+// Moves includes that do not need edits (i.e. already exist) to the front.
+CodeCompletion::IncludeCandidates
+moveNonInsertingIncludesToFront(CodeCompletion::IncludeCandidates Includes) {
+  if (Includes.size() <= 1)
+    return Includes;
+  // stable_partition on objects is slow. Do it on pointers instead.
+  llvm::SmallVector<CodeCompletion::IncludeCandidate *, 1> Pointers;
+  for (auto &Inc : Includes)
+    Pointers.push_back(&Inc);
+  std::stable_partition(Pointers.begin(), Pointers.end(),
+                        [](const CodeCompletion::IncludeCandidate *I) {
+                          return !I->Insertion.hasValue();
+                        });
+  CodeCompletion::IncludeCandidates Results;
+  for (auto *Inc : Pointers)
+    Results.push_back(std::move(*Inc));
+  return Results;
+}
+
 // Assembles a code completion out of a bundle of >=1 completion candidates.
 // Many of the expensive strings are only computed at this point, once we know
 // the candidate bundle is going to be returned.
 //
 // Many fields are the same for all candidates in a bundle (e.g. name), and are
 // computed from the first candidate, in the constructor.
 // Others vary per candidate, so add() must be called for remaining candidates.
 struct CodeCompletionBuilder {
auto Inserted =
       if (!ResolvedInserted)
         return ResolvedInserted.takeError();
       return std::make_pair(
           Includes.calculateIncludePath(*ResolvedDeclaring, *ResolvedInserted),
           Includes.shouldInsertInclude(*ResolvedDeclaring, *ResolvedInserted));
     };
     bool ShouldInsert = C.headerToInsertIfAllowed().hasValue();
     // Calculate include paths and edits for all possible headers.
+    llvm::SmallVector<CodeCompletion::IncludeCandidate, 1> IncludeCandidates;
     for (const auto &Inc : C.RankedIncludeHeaders) {
       if (auto ToInclude = Inserted(Inc)) {
         CodeCompletion::IncludeCandidate Include;
         Include.Header = ToInclude->first;
         if (ToInclude->second && ShouldInsert)
           Include.Insertion = Includes.insert(ToInclude->first);
-        Completion.Includes.push_back(std::move(Include));
+        IncludeCandidates.push_back(std::move(Include));
       } else
         log("Failed to generate include insertion edits for adding header "
             "(FileURI='{0}', IncludeHeader='{1}') into {2}",
             C.IndexResult->CanonicalDeclaration.FileURI, Inc, FileName);
     }
-    // Prefer includes that do not need edits (i.e. already exist).
-    std::stable_partition(Completion.Includes.begin(),
-                          Completion.Includes.end(),
-                          [](const CodeCompletion::IncludeCandidate &I) {
-                            return !I.Insertion.hasValue();
-                          });
+    Completion.Includes =
+        moveNonInsertingIncludesToFront(std::move(IncludeCandidates));
   }
 
   void add(const CompletionCandidate &C, CodeCompletionString *SemaCCS) {
     assert(bool(C.SemaResult) == bool(SemaCCS));
     Bundled.emplace_back();
     BundledEntry &S = Bundled.back();
     if (C.SemaResult) {
       getSignature(*SemaCCS, &S.Signature, &S.SnippetSuffix,