[pseudo] Store reduction sequences by pointer in heaps, instead of by value.

[sammccall]

Summary

Copying sequences around as the heap resized is significantly expensive.

This speeds up glrParse by ~35% (2.4 => 3.25 MB/s)

[hokein]

clang-tools-extra/pseudo/lib/GLR.cpp

208

I start to have a nervous feeling that we're going to add more and more intermediate data structure, which increases the complexity of the code, but I think the improvement is large enough to justify.

220

nit: add a default value nullptr

269

Just an idea (no action required)

If we want to do further optmization, here if a sequence have multiple Bases, we will have multiple elements in Sequences -- they have the form of (F, PushSpec{N, Seq}) where only N (the base node) is different.

• if we change the PushSpec::Base to store the child node of Base, we could save a bunch of space in Sequences. (The base can be retrieved dynamically from the child->parents()).

317

What's XXX?

[sammccall]

clang-tools-extra/pseudo/lib/GLR.cpp

208

Agree :-(

269

This is interesting! Essentially the reason we do the DFS eagerly (and pay to store its results) is we have to establish the Family via the start token, but this means we have to go only as far as the end of the sequence, rather than one further. (One further feels "cleaner" somehow, but who cares...)

I'll give this a try (not in this patch)

317

Oops, this was left-over from when Sequences stored by pointer and FamilySequences stored by value. Removed.

[sammccall]

clang-tools-extra/pseudo/lib/GLR.cpp

269

This is a ~5% speedup, for almost no extra code (just some comments).
Landed as 466eae6aa3574aea6604d42666f099025718ffa4

clang-tools-extra/pseudo/lib/GLR.cpp

bool operator<(const Family &Other) const {
       if (Symbol != Other.Symbol)
         return Rule > Other.Rule;
       assert(*this == Other);
       return false;
     }
   };
 
   // A sequence is the ForestNode payloads of the GSS nodes we are reducing.
-  // These are the RHS of the rule, the RuleID is stored in the Family.
-  // They specify a sequence ForestNode we may build (but we dedup first).
   using Sequence = llvm::SmallVector<const ForestNode *, Rule::MaxElements>;
+  // Like ArrayRef<const ForestNode*>, but with the missing operator<.
+  // (Sequences are big to move by value as the collections gets rearranged).
+  struct SequenceRef {
+    SequenceRef(const Sequence &S) : S(S) {}
+    llvm::ArrayRef<const ForestNode *> S;
+    friend bool operator==(SequenceRef A, SequenceRef B) { return A.S == B.S; }
+    friend bool operator<(const SequenceRef &A, const SequenceRef &B) {
+      return std::lexicographical_compare(A.S.begin(), A.S.end(), B.S.begin(),
+                                          B.S.end());
+    }
+  };
+  // Underlying storage for sequences pointed to by stored SequenceRefs.
+  std::deque<Sequence> SequenceStorage;
+  // We don't actually destroy the sequences between calls, to reuse storage.
+  // Everything SequenceStorage[ >=SequenceStorageCount ] is reusable scratch.
+  unsigned SequenceStorageCount;
+
+  // Halfway through a reduction (after the pop, before the push), we have
+  // collected nodes for the RHS of a rule, and reached a base node.
+  // They specify a sequence ForestNode we may build (but we dedup first).
+  // (The RuleID is not stored here, but rather in the Family).
   struct PushSpec {
     // A base node is the head after popping the GSS nodes we are reducing.
     const GSS::Node* Base = nullptr;
-    Sequence Seq;
+    Sequence *Seq = nullptr;
   };
   KeyedQueue<Family, PushSpec> Sequences; // FIXME: rename => PendingPushes?
 
   // We treat Heads as a queue of Pop operations still to be performed.
   // PoppedHeads is our position within it.
   std::vector<const GSS::Node *> *Heads;
   unsigned NextPopHead;
   SymbolID Lookahead;
 
   Sequence TempSequence;
 public:
   GLRReduce(const ParseParams &Params) : Params(Params) {}
 
   void operator()(std::vector<const GSS::Node *> &Heads, SymbolID Lookahead) {
     assert(isToken(Lookahead));
 
     NextPopHead = 0;
     this->Heads = &Heads;
     this->Lookahead = Lookahead;
     assert(Sequences.empty());
+    SequenceStorageCount = 0;
 
     popPending();
     while (!Sequences.empty()) {
       pushNext();
       popPending();
     }
   }
 
 private:
   // pop walks up the parent chain(s) for a reduction from Head by to Rule.
   // Once we reach the end, record the bases and sequences.
   void pop(const GSS::Node *Head, RuleID RID) {
     LLVM_DEBUG(llvm::dbgs() << "  Pop " << Params.G.dumpRule(RID) << "\n");
     const auto &Rule = Params.G.lookupRule(RID);
     Family F{/*Start=*/0, /*Symbol=*/Rule.Target, /*Rule=*/RID};
     TempSequence.resize_for_overwrite(Rule.Size);
     auto DFS = [&](const GSS::Node *N, unsigned I, auto &DFS) {
       if (I == Rule.Size) {
         F.Start = TempSequence.front()->startTokenIndex();
         LLVM_DEBUG(llvm::dbgs() << "    --> base at S" << N->State << "\n");
-        Sequences.emplace(F, PushSpec{N, TempSequence});
+
+        // Copy the chain to stable storage so it can be enqueued.
+        if (SequenceStorageCount == SequenceStorage.size())
+          SequenceStorage.emplace_back();
+        SequenceStorage[SequenceStorageCount] = TempSequence;
+        Sequence *Seq = &SequenceStorage[SequenceStorageCount++];
+
+        Sequences.emplace(F, PushSpec{N, Seq});
         return;
       }
       TempSequence[Rule.Size - 1 - I] = N->Payload;
       for (const GSS::Node *Parent : N->parents())
         DFS(Parent, I + 1, DFS);
     };
     DFS(Head, 0, DFS);
   }
for (; NextPopHead < Heads->size(); ++NextPopHead) {
           continue;
         pop((*Heads)[NextPopHead], A.getReduceRule());
       }
     }
   }
 
   // Storage reused by each call to pushNext.
   std::vector<std::pair</*Goto*/ StateID, const GSS::Node *>> FamilyBases;
-  std::vector<std::pair<RuleID, Sequence>> FamilySequences;
+  std::vector<std::pair<RuleID, SequenceRef>> FamilySequences;
   std::vector<const GSS::Node *> Parents;
   std::vector<const ForestNode *> SequenceNodes;
 
   // Process one push family, forming a forest node.
   // This produces new GSS heads which may enable more pops.
   void pushNext() {
     assert(!Sequences.empty());
     Family F = Sequences.top().first;
 
     LLVM_DEBUG(llvm::dbgs() << "  Push " << Params.G.symbolName(F.Symbol)
                             << " from token " << F.Start << "\n");
 
     // Grab the sequences and bases for this family.
     // We don't care which rule yielded each base. If Family.Symbol is S, the
     // base includes an item X := ... • S ... and since the grammar is
     // context-free, *all* parses of S are valid here.
     FamilySequences.clear();
     FamilyBases.clear();
     do {
       FamilySequences.emplace_back(Sequences.top().first.Rule,
-                                   Sequences.top().second.Seq);
+                                   *Sequences.top().second.Seq);
       FamilyBases.emplace_back(
           Params.Table.getGoToState(Sequences.top().second.Base->State,
                                     F.Symbol),
           Sequences.top().second.Base);
 
       Sequences.pop();
     } while (!Sequences.empty() && Sequences.top().first == F);
     // Build a forest node for each unique sequence.
     sortAndUnique(FamilySequences);
     SequenceNodes.clear();
     for (const auto &SequenceSpec : FamilySequences)
       SequenceNodes.push_back(&Params.Forest.createSequence(
-          F.Symbol, SequenceSpec.first, SequenceSpec.second));
+          F.Symbol, SequenceSpec.first, SequenceSpec.second.S));
     // Wrap in an ambiguous node if needed.
     const ForestNode *Parsed =
         SequenceNodes.size() == 1
             ? SequenceNodes.front()
             : &Params.Forest.createAmbiguous(F.Symbol, SequenceNodes);
     LLVM_DEBUG(llvm::dbgs() << "    --> " << Parsed->dump(Params.G) << "\n");
 
     // Bases for this family, deduplicate them, and group by the goTo State.