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

[Sam McCall via Phabricator via cfe-commits]

sammccall accepted this revision.
sammccall added a comment.
This revision is now accepted and ready to land.

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.


Repository:
  rCTE Clang Tools Extra

https://reviews.llvm.org/D52617



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Eric Liu via Phabricator via cfe-commits]

ioeric updated this revision to Diff 167361.
ioeric marked 3 inline comments as done.
ioeric added a comment.

- simplify the code.


Repository:
  rCTE Clang Tools Extra

https://reviews.llvm.org/D52617

Files:
  clangd/CodeComplete.cpp


Index: clangd/CodeComplete.cpp
===
--- clangd/CodeComplete.cpp
+++ clangd/CodeComplete.cpp
@@ -406,25 +406,27 @@
   Includes.shouldInsertInclude(*ResolvedDeclaring, *ResolvedInserted));
 };
 bool ShouldInsert = C.headerToInsertIfAllowed().hasValue();
-// Calculate include paths and edits for all possible headers.
+// Put includes with insertions after those without.
+llvm::SmallVector 
InsertableCandidates;
+Completion.Includes.reserve(C.RankedIncludeHeaders.size());
+InsertableCandidates.reserve(C.RankedIncludeHeaders.size());
 for (const auto  : 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));
+(Include.Insertion ? InsertableCandidates : Completion.Includes)
+.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 ) {
-return !I.Insertion.hasValue();
-  });
+if (!InsertableCandidates.empty())
+  std::move(InsertableCandidates.begin(), InsertableCandidates.end(),
+std::back_inserter(Completion.Includes));
   }
 
   void add(const CompletionCandidate , CodeCompletionString *SemaCCS) {


Index: clangd/CodeComplete.cpp
===
--- clangd/CodeComplete.cpp
+++ clangd/CodeComplete.cpp
@@ -406,25 +406,27 @@
   Includes.shouldInsertInclude(*ResolvedDeclaring, *ResolvedInserted));
 };
 bool ShouldInsert = C.headerToInsertIfAllowed().hasValue();
-// Calculate include paths and edits for all possible headers.
+// Put includes with insertions after those without.
+llvm::SmallVector InsertableCandidates;
+Completion.Includes.reserve(C.RankedIncludeHeaders.size());
+InsertableCandidates.reserve(C.RankedIncludeHeaders.size());
 for (const auto  : 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));
+(Include.Insertion ? InsertableCandidates : Completion.Includes)
+.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 ) {
-return !I.Insertion.hasValue();
-  });
+if (!InsertableCandidates.empty())
+  std::move(InsertableCandidates.begin(), InsertableCandidates.end(),
+std::back_inserter(Completion.Includes));
   }
 
   void add(const CompletionCandidate , CodeCompletionString *SemaCCS) {
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Sam McCall via Phabricator via cfe-commits]

sammccall added inline comments.



Comment at: clangd/CodeComplete.cpp:325
+CodeCompletion::IncludeCandidates
+moveNonInsertingIncludesToFront(CodeCompletion::IncludeCandidates Includes) {
+  if (Includes.size() <= 1)

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...



Comment at: clangd/CodeComplete.cpp:415
 // Calculate include paths and edits for all possible headers.
+llvm::SmallVector IncludeCandidates;
 for (const auto  : C.RankedIncludeHeaders) {

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



Comment at: clangd/CodeComplete.cpp:422
   Include.Insertion = Includes.insert(ToInclude->first);
-Completion.Includes.push_back(std::move(Include));
+IncludeCandidates.push_back(std::move(Include));
   } else

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?


Repository:
  rCTE Clang Tools Extra

https://reviews.llvm.org/D52617



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Eric Liu via Phabricator via cfe-commits]

ioeric created this revision.
ioeric added a reviewer: sammccall.
Herald added subscribers: cfe-commits, kadircet, arphaman, jkorous, MaskRay, 
ilya-biryukov.

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


Repository:
  rCTE Clang Tools Extra

https://reviews.llvm.org/D52617

Files:
  clangd/CodeComplete.cpp
  clangd/CodeComplete.h


Index: clangd/CodeComplete.h
===
--- clangd/CodeComplete.h
+++ clangd/CodeComplete.h
@@ -145,7 +145,8 @@
   // 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 Includes;
+  using IncludeCandidates = llvm::SmallVector;
+  IncludeCandidates Includes;
 
   /// Holds information about small corrections that needs to be done. Like
   /// converting '->' to '.' on member access.
Index: clangd/CodeComplete.cpp
===
--- clangd/CodeComplete.cpp
+++ clangd/CodeComplete.cpp
@@ -320,6 +320,25 @@
   }
 };
 
+// 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 Pointers;
+  for (auto  : Includes)
+Pointers.push_back();
+  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.
@@ -393,24 +412,21 @@
 };
 bool ShouldInsert = C.headerToInsertIfAllowed().hasValue();
 // Calculate include paths and edits for all possible headers.
+llvm::SmallVector IncludeCandidates;
 for (const auto  : 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 ) {
-return !I.Insertion.hasValue();
-  });
+Completion.Includes =
+moveNonInsertingIncludesToFront(std::move(IncludeCandidates));
   }
 
   void add(const CompletionCandidate , CodeCompletionString *SemaCCS) {


Index: clangd/CodeComplete.h
===
--- clangd/CodeComplete.h
+++ clangd/CodeComplete.h
@@ -145,7 +145,8 @@
   // 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 Includes;
+  using IncludeCandidates = llvm::SmallVector;
+  IncludeCandidates Includes;
 
   /// Holds information about small corrections that needs to be done. Like
   /// converting '->' to '.' on member access.
Index: clangd/CodeComplete.cpp
===
--- clangd/CodeComplete.cpp
+++ clangd/CodeComplete.cpp
@@ -320,6 +320,25 @@
   }
 };
 
+// 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 Pointers;
+  for (auto  : Includes)
+Pointers.push_back();
+  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;
+}
+
 //