[pseudo] GC GSS nodes, reuse them with a freelist

[sammccall]

Summary

Most GSS nodes have short effective lifetimes, keeping them around until the
end of the parse is wasteful. Mark and sweep them every 20 tokens.

When parsing clangd/AST.cpp, this reduces the GSS memory from 1MB to 20kB.
We pay ~5% performance for this according to the glrParse benchmark.
(Parsing more tokens between GCs doesn't seem to improve this further).

Compared to the refcounting approach in https://reviews.llvm.org/D126337, this
is simpler (at least the complexity is better isolated) and has >2x less
overhead. It doesn't provide death handlers (for error-handling) but we have
an alternative solution in mind.

[sammccall]

remove dead variable

[hokein]

Nice! I really like the form it goes now.

clang-tools-extra/pseudo/include/clang-pseudo/GLR.h

81–82

This FIXME is done by this patch :)

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

15

an off-topic comment: we only use the function in debug branch code, this will trigger the include-cleaner warning in release mode :)

we could warp it with #ifndef NDEBUG as well.

88

I would just call it before the NewHeads.clear(), and run the gc on the NewHeads directly.

It simplifies the implementation (no need to traverse three pending actions, and no duplicated elements in Roots). The downside is that some dead heads (heads with no available actions on Terminal.symbol()) will not be GCed in this run, but I think it is negligible, as those will be GCed in next run.

392

The NodeCount becomes vague now, we update in both addNode and allocate methods, I think we should have two separate counts.

404

What's the practical size of the FreeList? I think we can just find one, and use it as initial default size, to save some cost of resize.

clang-tools-extra/pseudo/unittests/GLRTest.cpp

412

nit: since we free D, I think here E will reuse the memory free from D, maybe add pointer comparison with E and D ?

[sammccall]

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

15

conditional including is ugly and can cause subtle opt-only compile failures.
I'm tempted to add a "keep" pragma but want to think about how to handle this case a bit more.

88

Oops, I forgot that Pending* are all empty at the beginning of this loop. I should probably add an assertion for that.

We can call it right at the top of the loop, yes? It doesn't need to be between AddSsteps and NewHeads.clear().

run the gc on the NewHeads directly

Unfortunately not: the GC naturally consumes the argument (it becomes the stack for the DFS) so we need a copy.
We could move the copy into gc() but:

• this way we can reuse the same vector every time and don't have to allocate
• soon we'll have error-recovery candidates as additional roots we want to pass in

392

• Oops, that duplicated ++NodeCount is just a mistake.
• names are vague now, both "NodeCount" and "Allocated" are dubious. Maybe I'll rename to NodesCreated and Alive, WDYT?
• are there actually more metrics we want to record? we have nodes-created, currently-live-nodes (Allocated.size()), nodes-destroyed (NodeCount - Allocated.size()). We could track max-live-node but I think Arena.bytes() is fine for our purposes.
• do we want to expose any of those numbers through APIs? I couldn't work out what I'd actually do with them.

404

It's whatever the max #parents is - maybe 10 or something?
I don't think it's worth adding a hard-coded guess to save ~1 resize of a single vector per parse!

[hokein]

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

88

Oops, I forgot that Pending* are all empty at the beginning of this loop. I should probably add an assertion for that.

Yes. I would probably do it after glrReduce and glrShift calls.

We can call it right at the top of the loop, yes? It doesn't need to be between AddSsteps and NewHeads.clear().

Yes, exactly. We could also do that at the end of the loop.

run the gc on the NewHeads directly

Unfortunately not: the GC naturally consumes the argument (it becomes the stack for the DFS) so we need a copy.
We could move the copy into gc() but:

• this way we can reuse the same vector every time and don't have to allocate
• soon we'll have error-recovery candidates as additional roots we want to pass in

oh, I didn't notice that. I think making a copy is fine.

392

names are vague now, both "NodeCount" and "Allocated" are dubious. Maybe I'll rename to NodesCreated and Alive, WDYT?

Sounds good to me.

are there actually more metrics we want to record? we have nodes-created, currently-live-nodes (Allocated.size()), nodes-destroyed (NodeCount - Allocated.size()). We could track max-live-node but I think Arena.bytes() is fine for our purposes.

I think these are sufficient, should provide enough details about GSS-memory-related information. The other things I will like to record is the max-active-heads, but that's a different bit.

do we want to expose any of those numbers through APIs? I couldn't work out what I'd actually do with them.

I think we should avoid to expose an API per field, we probably just need a single API which returns a Stats struct containing all these things. We can do it later.

404

I would image there will be multiple resize calls, if the path like allocate(1), allocate(3), ..., allocate(max), which I think it is practical? unless the first call is allocate(max) which is unlikely I think.

[sammccall]

address comments

[sammccall]

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

392

OK, I haven't added any new stats APIs for now.

404

So for parsing clangd/AST.cpp, we have 4 small allocations for the whole file, which we could reduce by 3.

size increased to 1
capacity grew from 0 to 1
size increased to 2
capacity grew from 1 to 2
size increased to 3
capacity grew from 2 to 4
size increased to 4
size increased to 6
capacity grew from 4 to 8
size increased to 7

By comparison, each call to glrReduce creates 5 vectors and 2 priority queues, each of which can have multiple allocations as it grows. There are 4000 tokens, for a total of probably 50000 mallocs.

I think you're microoptimizing the wrong places :-)

[hokein]

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

78

nit: I'd rather pass the NewHeads as a vector parameter, and get rid of the Roots variable in the lambda, but up to you.

404

that's fair enough (and there are some opportunities to optimize the glrReduce). But I think adding a single FreeList.revese(10); statement seems trivial. Up to you.

[sammccall]

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

78

That would result in reallocating the array every time: we would allocate a new vector to copy NewHeads into, copy it, gc() would own it and destroy (deallocate) it at the end.

As the code is now, Roots stays alive. Each time we GC we fill it up with elements, and then gc() clears them out again, but we never actually deallocate the buffer.

clang-tools-extra/pseudo/include/clang-pseudo/GLR.h

struct GSS {
   // Unlike a regular LR stack frame, it may have multiple parents.
   //
   // Nodes are not exactly pushed and popped on the stack: pushing is just
   // allocating a new head node with a parent pointer to the old head. Popping
   // is just forgetting about a node and remembering its parent instead.
   struct alignas(struct Node *) Node {
     // LR state describing how parsing should continue from this head.
     LRTable::StateID State;
+    // Used internally to track reachability during garbage collection.
+    bool GCParity;
     // Number of the parents of this node.
     // The parents hold previous parsed symbols, and may resume control after
     // this node is reduced.
     unsigned ParentCount;
     // The parse node for the last parsed symbol.
     // This symbol appears on the left of the dot in the parse state's items.
     // (In the literature, the node is attached to the *edge* to the parent).
     const ForestNode *Payload = nullptr;
 
-    // FIXME: Most nodes live a fairly short time, and are simply discarded.
-    // Is it worth refcounting them (we have empty padding) and returning to a
-    // freelist, to keep the working set small?
-
     llvm::ArrayRef<const Node *> parents() const {
       return llvm::makeArrayRef(reinterpret_cast<const Node *const *>(this + 1),
                                 ParentCount);
     };
     // Parents are stored as a trailing array of Node*.
   };
 
   // Allocates a new node in the graph.
   const Node *addNode(LRTable::StateID State, const ForestNode *Symbol,
-                      llvm::ArrayRef<const Node *> Parents) {
-    ++NodeCount;
-    Node *Result = new (Arena.Allocate(
-        sizeof(Node) + Parents.size() * sizeof(Node *), alignof(Node)))
-        Node({State, static_cast<unsigned>(Parents.size())});
-    Result->Payload = Symbol;
-    if (!Parents.empty())
-      llvm::copy(Parents, reinterpret_cast<const Node **>(Result + 1));
-    return Result;
-  }
+                      llvm::ArrayRef<const Node *> Parents);
+  // Frees all nodes not reachable as ancestors of Roots, and returns the count.
+  // Calling this periodically prevents steady memory growth of the GSS.
+  unsigned gc(std::vector<const Node *> &&Roots);
 
   size_t bytes() const { return Arena.getTotalMemory() + sizeof(*this); }
-  size_t nodeCount() const { return NodeCount; }
+  size_t nodesCreated() const { return NodesCreated; }
 
 private:
+  // Nodes are recycled using freelists.
+  // They are variable size, so use one free-list per distinct #parents.
+  std::vector<std::vector<Node *>> FreeList;
+  Node *allocate(unsigned Parents);
+  void destroy(Node *N);
+  // The list of nodes created and not destroyed - our candidates for gc().
+  std::vector<Node *> Alive;
+  bool GCParity = false; // All nodes should match this, except during GC.
+
   llvm::BumpPtrAllocator Arena;
-  unsigned NodeCount = 0;
+  unsigned NodesCreated = 0;
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const GSS::Node &);
 
 // Parameters for the GLR parsing.
 struct ParseParams {
   // The grammar of the language we're going to parse.
   const Grammar &G;
   // The LR table which GLR uses to parse the input, should correspond to the

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

 //===--- GLR.cpp   -----------------------------------------------*- C++-*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang-pseudo/GLR.h"
 #include "clang-pseudo/Grammar.h"
 #include "clang-pseudo/LRTable.h"
 #include "clang/Basic/TokenKinds.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/FormatVariadic.h"
 #include <algorithm>
 #include <memory>
 #include <queue>
 
for (const auto &Action : Params.Table.getActions(Head->State, NextTok)) {
       default:
         llvm_unreachable("unexpected action kind!");
       }
     }
   };
   std::vector<const GSS::Node *> NewHeads = {
       GSS.addNode(/*State=*/Params.Table.getStartState(StartSymbol),
                   /*ForestNode=*/nullptr, {})};
+  auto MaybeGC = [&, Roots(std::vector<const GSS::Node *>{}), I(0u)]() mutable {
+    assert(PendingShift.empty() && PendingReduce.empty() &&
+           PendingAccept.empty() && "Running GC at the wrong time!");
+
+    if (++I != 20) // Run periodically to balance CPU and memory usage.
+      return;
+    I = 0;
+
+    // We need to copy the list: Roots is consumed by the GC.
+    Roots = NewHeads;
+    GSS.gc(std::move(Roots));
+  };
   for (const ForestNode &Terminal : Terminals) {
     LLVM_DEBUG(llvm::dbgs() << llvm::formatv("Next token {0} (id={1})\n",
                                              G.symbolName(Terminal.symbol()),
                                              Terminal.symbol()));
     for (const auto *Head : NewHeads)
       AddSteps(Head, Terminal.symbol());
     NewHeads.clear();
     glrReduce(PendingReduce, Params,
               [&](const GSS::Node * NewHead) {
                 // A reduce will enable more steps.
                 AddSteps(NewHead, Terminal.symbol());
               });
 
     glrShift(PendingShift, Terminal, Params,
              [&](const GSS::Node *NewHead) { NewHeads.push_back(NewHead); });
+    MaybeGC();
   }
   LLVM_DEBUG(llvm::dbgs() << llvm::formatv("Next is eof\n"));
   for (const auto *Heads : NewHeads)
     AddSteps(Heads, tokenSymbol(tok::eof));
   glrReduce(PendingReduce, Params,
             [&](const GSS::Node * NewHead) {
               // A reduce will enable more steps.
               AddSteps(NewHead, tokenSymbol(tok::eof));
while (!BasesLeft.empty()) {
       // reduces to the PendingReduce queue!
       NewHeadCB(Params.GSStack.addNode(NextState, Parsed, Parents));
     }
     PopPending();
   }
   assert(Sequences.empty());
 }
 
+const GSS::Node *GSS::addNode(LRTable::StateID State, const ForestNode *Symbol,
+                              llvm::ArrayRef<const Node *> Parents) {
+  Node *Result = new (allocate(Parents.size()))
+      Node({State, GCParity, static_cast<unsigned>(Parents.size())});
+  Alive.push_back(Result);
+  ++NodesCreated;
+  Result->Payload = Symbol;
+  if (!Parents.empty())
+    llvm::copy(Parents, reinterpret_cast<const Node **>(Result + 1));
+  return Result;
+}
+
+GSS::Node *GSS::allocate(unsigned Parents) {
+  if (FreeList.size() <= Parents)
+    FreeList.resize(Parents + 1);
+  auto &SizedList = FreeList[Parents];
+  if (!SizedList.empty()) {
+    auto *Result = SizedList.back();
+    SizedList.pop_back();
+    return Result;
+  }
+  return static_cast<Node *>(
+      Arena.Allocate(sizeof(Node) + Parents * sizeof(Node *), alignof(Node)));
+}
+
+void GSS::destroy(Node *N) {
+  unsigned ParentCount = N->ParentCount;
+  N->~Node();
+  assert(FreeList.size() > ParentCount && "established on construction!");
+  FreeList[ParentCount].push_back(N);
+}
+
+unsigned GSS::gc(std::vector<const Node *> &&Queue) {
+#ifndef NDEBUG
+  auto ParityMatches = [&](const Node *N) { return N->GCParity == GCParity; };
+  assert("Before GC" && llvm::all_of(Alive, ParityMatches));
+  auto Deferred = llvm::make_scope_exit(
+      [&] { assert("After GC" && llvm::all_of(Alive, ParityMatches)); });
+  assert(llvm::all_of(
+      Queue, [&](const Node *R) { return llvm::is_contained(Alive, R); }));
+#endif
+  unsigned InitialCount = Alive.size();
+
+  // Mark
+  GCParity = !GCParity;
+  while (!Queue.empty()) {
+    Node *N = const_cast<Node *>(Queue.back()); // Safe: we created these nodes.
+    Queue.pop_back();
+    if (N->GCParity != GCParity) { // Not seen yet
+      N->GCParity = GCParity;      // Mark as seen
+      for (const Node *P : N->parents()) // And walk parents
+        Queue.push_back(P);
+    }
+  }
+  // Sweep
+  llvm::erase_if(Alive, [&](Node *N) {
+    if (N->GCParity == GCParity) // Walk reached this node.
+      return false;
+    destroy(N);
+    return true;
+  });
+
+  LLVM_DEBUG(llvm::dbgs() << "GC pruned " << (InitialCount - Alive.size())
+                          << "/" << InitialCount << " GSS nodes\n");
+  return InitialCount - Alive.size();
+}
+
 } // namespace pseudo
 } // namespace clang

clang-tools-extra/pseudo/tool/ClangPseudo.cpp

if (ParseableStream) {
                             *StartSymID);
       if (PrintForest)
         llvm::outs() << Root.dumpRecursive(*G, /*Abbreviated=*/true);
 
       if (PrintStatistics) {
         llvm::outs() << "Forest bytes: " << Arena.bytes()
                      << " nodes: " << Arena.nodeCount() << "\n";
         llvm::outs() << "GSS bytes: " << GSS.bytes()
-                     << " nodes: " << GSS.nodeCount() << "\n";
+                     << " nodes: " << GSS.nodesCreated() << "\n";
       }
     }
   }
 
   return 0;
 }

clang-tools-extra/pseudo/unittests/GLRTest.cpp

EXPECT_EQ(Parsed.dumpRecursive(*G),
             "[  0, end) test := <ambiguous>\n"
             "[  0, end) ├─test := IDENTIFIER\n"
             "[  0, end) │ └─IDENTIFIER := tok[0]\n"
             "[  0, end) └─test := foo\n"
             "[  0, end)   └─foo := IDENTIFIER\n"
             "[  0, end)     └─IDENTIFIER := tok[0]\n");
 }
 
+TEST(GSSTest, GC) {
+  //      ┌-A-┬-AB
+  //      ├-B-┘
+  // Root-+-C
+  //      ├-D
+  //      └-E
+  GSS GSStack;
+  auto *Root = GSStack.addNode(0, nullptr, {});
+  auto *A = GSStack.addNode(0, nullptr, {Root});
+  auto *B = GSStack.addNode(0, nullptr, {Root});
+  auto *C = GSStack.addNode(0, nullptr, {Root});
+  auto *D = GSStack.addNode(0, nullptr, {Root});
+  auto *AB = GSStack.addNode(0, nullptr, {A, B});
+
+  EXPECT_EQ(1u, GSStack.gc({AB, C})) << "D is destroyed";
+  EXPECT_EQ(0u, GSStack.gc({AB, C})) << "D is already gone";
+  auto *E = GSStack.addNode(0, nullptr, {Root});
+  EXPECT_EQ(D, E) << "Storage of GCed node D is reused for E";
+  EXPECT_EQ(3u, GSStack.gc({A, E})) << "Destroys B, AB, C";
+  EXPECT_EQ(1u, GSStack.gc({E})) << "Destroys A";
+}
+
 } // namespace
 } // namespace pseudo
 } // namespace clang