[PATCH] D126723: [pseudo] GC GSS nodes, reuse them with a freelist
This revision was landed with ongoing or failed builds.
This revision was automatically updated to reflect the committed changes.
Closed by commit rG94b2ca18c10b: [pseudo] GC GSS nodes, reuse them with a
freelist (authored by sammccall).
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D126723/new/
https://reviews.llvm.org/D126723
Files:
clang-tools-extra/pseudo/include/clang-pseudo/GLR.h
clang-tools-extra/pseudo/lib/GLR.cpp
clang-tools-extra/pseudo/tool/ClangPseudo.cpp
clang-tools-extra/pseudo/unittests/GLRTest.cpp
Index: clang-tools-extra/pseudo/unittests/GLRTest.cpp
===
--- clang-tools-extra/pseudo/unittests/GLRTest.cpp
+++ clang-tools-extra/pseudo/unittests/GLRTest.cpp
@@ -393,6 +393,28 @@
"[ 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
Index: clang-tools-extra/pseudo/tool/ClangPseudo.cpp
===
--- clang-tools-extra/pseudo/tool/ClangPseudo.cpp
+++ clang-tools-extra/pseudo/tool/ClangPseudo.cpp
@@ -134,7 +134,7 @@
llvm::outs() << "Forest bytes: " << Arena.bytes()
<< " nodes: " << Arena.nodeCount() << "\n";
llvm::outs() << "GSS bytes: " << GSS.bytes()
- << " nodes: " << GSS.nodeCount() << "\n";
+ << " nodes: " << GSS.nodesCreated() << "\n";
}
}
}
Index: clang-tools-extra/pseudo/lib/GLR.cpp
===
--- clang-tools-extra/pseudo/lib/GLR.cpp
+++ clang-tools-extra/pseudo/lib/GLR.cpp
@@ -12,6 +12,7 @@
#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"
@@ -65,6 +66,18 @@
std::vector NewHeads = {
GSS.addNode(/*State=*/Params.Table.getStartState(StartSymbol),
/*ForestNode=*/nullptr, {})};
+ auto MaybeGC = [&, Roots(std::vector{}), 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 : Terminals) {
LLVM_DEBUG(llvm::dbgs() << llvm::formatv("Next token {0} (id={1})\n",
G.symbolName(Terminal.symbol()),
@@ -80,6 +93,7 @@
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)
@@ -373,5 +387,72 @@
assert(Sequences.empty());
}
+const GSS::Node *GSS::addNode(LRTable::StateID State, const ForestNode *Symbol,
+ llvm::ArrayRef Parents) {
+ Node *Result = new (allocate(Parents.size()))
+ Node({State, GCParity, static_cast(Parents.size())});
+ Alive.push_back(Result);
+ ++NodesCreated;
+ Result->Payload = Symbol;
+ if (!Parents.empty())
+llvm::copy(Parents, reinterpret_cast(Result + 1));
+ return Result;
+}
+
+GSS::Node *GSS::allocate(unsigned Parents) {
+ if (FreeList.size() <= Parents)
+FreeList.resize(Parents + 1);
+ auto = FreeList[Parents];
+ if (!SizedList.empty()) {
+auto *Result = SizedList.back();
+SizedList.pop_back();
+return Result;
+ }
+ return static_cast(
+ 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 &) {
+#ifndef NDEBUG
+ auto ParityMatches = [&](const Node *N) { return N->GCParity ==
[PATCH] D126723: [pseudo] GC GSS nodes, reuse them with a freelist
sammccall added inline comments. Comment at: clang-tools-extra/pseudo/lib/GLR.cpp:78 +// We need to copy the list: Roots is consumed by the GC. +Roots = NewHeads; +GSS.gc(std::move(Roots)); hokein wrote: > 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. 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. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D126723/new/ https://reviews.llvm.org/D126723 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D126723: [pseudo] GC GSS nodes, reuse them with a freelist
hokein accepted this revision. hokein added inline comments. This revision is now accepted and ready to land. Comment at: clang-tools-extra/pseudo/lib/GLR.cpp:78 +// We need to copy the list: Roots is consumed by the GC. +Roots = NewHeads; +GSS.gc(std::move(Roots)); 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. Comment at: clang-tools-extra/pseudo/lib/GLR.cpp:403 + ++NodeCount; + if (FreeList.size() <= Parents) +FreeList.resize(Parents + 1); sammccall wrote: > hokein wrote: > > sammccall wrote: > > > hokein wrote: > > > > 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. > > > 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! > > 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. > 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 **5** mallocs. > > I think you're microoptimizing the wrong places :-) 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. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D126723/new/ https://reviews.llvm.org/D126723 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D126723: [pseudo] GC GSS nodes, reuse them with a freelist
sammccall marked an inline comment as done.
sammccall added inline comments.
Comment at: clang-tools-extra/pseudo/lib/GLR.cpp:391
+ llvm::ArrayRef Parents) {
+ ++NodeCount;
+ Node *Result = new (allocate(Parents.size()))
hokein wrote:
> sammccall wrote:
> > hokein wrote:
> > > The NodeCount becomes vague now, we update in both addNode and allocate
> > > methods, I think we should have two separate counts.
> > - 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.
> > 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.
>
>
OK, I haven't added any new stats APIs for now.
Comment at: clang-tools-extra/pseudo/lib/GLR.cpp:403
+ ++NodeCount;
+ if (FreeList.size() <= Parents)
+FreeList.resize(Parents + 1);
hokein wrote:
> sammccall wrote:
> > hokein wrote:
> > > 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.
> > 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!
> 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.
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 **5** mallocs.
I think you're microoptimizing the wrong places :-)
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D126723/new/
https://reviews.llvm.org/D126723
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D126723: [pseudo] GC GSS nodes, reuse them with a freelist
sammccall updated this revision to Diff 434103.
sammccall marked 6 inline comments as done.
sammccall added a comment.
address comments
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D126723/new/
https://reviews.llvm.org/D126723
Files:
clang-tools-extra/pseudo/include/clang-pseudo/GLR.h
clang-tools-extra/pseudo/lib/GLR.cpp
clang-tools-extra/pseudo/tool/ClangPseudo.cpp
clang-tools-extra/pseudo/unittests/GLRTest.cpp
Index: clang-tools-extra/pseudo/unittests/GLRTest.cpp
===
--- clang-tools-extra/pseudo/unittests/GLRTest.cpp
+++ clang-tools-extra/pseudo/unittests/GLRTest.cpp
@@ -393,6 +393,28 @@
"[ 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
Index: clang-tools-extra/pseudo/tool/ClangPseudo.cpp
===
--- clang-tools-extra/pseudo/tool/ClangPseudo.cpp
+++ clang-tools-extra/pseudo/tool/ClangPseudo.cpp
@@ -132,7 +132,7 @@
llvm::outs() << "Forest bytes: " << Arena.bytes()
<< " nodes: " << Arena.nodeCount() << "\n";
llvm::outs() << "GSS bytes: " << GSS.bytes()
- << " nodes: " << GSS.nodeCount() << "\n";
+ << " nodes: " << GSS.nodesCreated() << "\n";
}
}
}
Index: clang-tools-extra/pseudo/lib/GLR.cpp
===
--- clang-tools-extra/pseudo/lib/GLR.cpp
+++ clang-tools-extra/pseudo/lib/GLR.cpp
@@ -12,6 +12,7 @@
#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"
@@ -65,6 +66,18 @@
std::vector NewHeads = {
GSS.addNode(/*State=*/Params.Table.getStartState(StartSymbol),
/*ForestNode=*/nullptr, {})};
+ auto MaybeGC = [&, Roots(std::vector{}), 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 : Terminals) {
LLVM_DEBUG(llvm::dbgs() << llvm::formatv("Next token {0} (id={1})\n",
G.symbolName(Terminal.symbol()),
@@ -80,6 +93,7 @@
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)
@@ -373,5 +387,72 @@
assert(Sequences.empty());
}
+const GSS::Node *GSS::addNode(LRTable::StateID State, const ForestNode *Symbol,
+ llvm::ArrayRef Parents) {
+ Node *Result = new (allocate(Parents.size()))
+ Node({State, GCParity, static_cast(Parents.size())});
+ Alive.push_back(Result);
+ ++NodesCreated;
+ Result->Payload = Symbol;
+ if (!Parents.empty())
+llvm::copy(Parents, reinterpret_cast(Result + 1));
+ return Result;
+}
+
+GSS::Node *GSS::allocate(unsigned Parents) {
+ if (FreeList.size() <= Parents)
+FreeList.resize(Parents + 1);
+ auto = FreeList[Parents];
+ if (!SizedList.empty()) {
+auto *Result = SizedList.back();
+SizedList.pop_back();
+return Result;
+ }
+ return static_cast(
+ 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 &) {
+#ifndef NDEBUG
+ auto ParityMatches = [&](const Node *N) { return N->GCParity == GCParity; };
+ assert("Before GC" && llvm::all_of(Alive, ParityMatches));
+ auto Deferred =
[PATCH] D126723: [pseudo] GC GSS nodes, reuse them with a freelist
hokein added inline comments.
Comment at: clang-tools-extra/pseudo/lib/GLR.cpp:87
NewHeads.clear();
+MaybeGC();
glrReduce(PendingReduce, Params,
sammccall wrote:
> hokein wrote:
> > 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.
> 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
> 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.
Comment at: clang-tools-extra/pseudo/lib/GLR.cpp:391
+ llvm::ArrayRef Parents) {
+ ++NodeCount;
+ Node *Result = new (allocate(Parents.size()))
sammccall wrote:
> hokein wrote:
> > The NodeCount becomes vague now, we update in both addNode and allocate
> > methods, I think we should have two separate counts.
> - 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.
> 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.
Comment at: clang-tools-extra/pseudo/lib/GLR.cpp:403
+ ++NodeCount;
+ if (FreeList.size() <= Parents)
+FreeList.resize(Parents + 1);
sammccall wrote:
> hokein wrote:
> > 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.
> 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!
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.
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D126723/new/
https://reviews.llvm.org/D126723
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D126723: [pseudo] GC GSS nodes, reuse them with a freelist
sammccall added inline comments.
Comment at: clang-tools-extra/pseudo/lib/GLR.cpp:15
#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/ScopeExit.h"
#include "llvm/ADT/StringExtras.h"
hokein wrote:
> 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.
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.
Comment at: clang-tools-extra/pseudo/lib/GLR.cpp:87
NewHeads.clear();
+MaybeGC();
glrReduce(PendingReduce, Params,
hokein wrote:
> 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.
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
Comment at: clang-tools-extra/pseudo/lib/GLR.cpp:391
+ llvm::ArrayRef Parents) {
+ ++NodeCount;
+ Node *Result = new (allocate(Parents.size()))
hokein wrote:
> The NodeCount becomes vague now, we update in both addNode and allocate
> methods, I think we should have two separate counts.
- 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.
Comment at: clang-tools-extra/pseudo/lib/GLR.cpp:403
+ ++NodeCount;
+ if (FreeList.size() <= Parents)
+FreeList.resize(Parents + 1);
hokein wrote:
> 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.
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!
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D126723/new/
https://reviews.llvm.org/D126723
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D126723: [pseudo] GC GSS nodes, reuse them with a freelist
hokein added a comment.
Nice! I really like the form it goes now.
Comment at: clang-tools-extra/pseudo/include/clang-pseudo/GLR.h:82
// 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
This FIXME is done by this patch :)
Comment at: clang-tools-extra/pseudo/lib/GLR.cpp:15
#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/ScopeExit.h"
#include "llvm/ADT/StringExtras.h"
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.
Comment at: clang-tools-extra/pseudo/lib/GLR.cpp:87
NewHeads.clear();
+MaybeGC();
glrReduce(PendingReduce, Params,
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.
Comment at: clang-tools-extra/pseudo/lib/GLR.cpp:391
+ llvm::ArrayRef Parents) {
+ ++NodeCount;
+ Node *Result = new (allocate(Parents.size()))
The NodeCount becomes vague now, we update in both addNode and allocate
methods, I think we should have two separate counts.
Comment at: clang-tools-extra/pseudo/lib/GLR.cpp:403
+ ++NodeCount;
+ if (FreeList.size() <= Parents)
+FreeList.resize(Parents + 1);
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.
Comment at: clang-tools-extra/pseudo/unittests/GLRTest.cpp:412
+ EXPECT_EQ(0u, GSStack.gc({AB, C})); // D is already gone.
+ auto *E = GSStack.addNode(0, nullptr, {Root});
+ EXPECT_EQ(3u, GSStack.gc({A, E})); // destroys B, AB, C
nit: since we free D, I think here E will reuse the memory free from D, maybe
add pointer comparison with `E` and `D` ?
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D126723/new/
https://reviews.llvm.org/D126723
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D126723: [pseudo] GC GSS nodes, reuse them with a freelist
sammccall updated this revision to Diff 433201.
sammccall added a comment.
remove dead variable
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D126723/new/
https://reviews.llvm.org/D126723
Files:
clang-tools-extra/pseudo/include/clang-pseudo/GLR.h
clang-tools-extra/pseudo/lib/GLR.cpp
clang-tools-extra/pseudo/unittests/GLRTest.cpp
Index: clang-tools-extra/pseudo/unittests/GLRTest.cpp
===
--- clang-tools-extra/pseudo/unittests/GLRTest.cpp
+++ clang-tools-extra/pseudo/unittests/GLRTest.cpp
@@ -393,6 +393,29 @@
"[ 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})); // destroys D
+ EXPECT_EQ(0u, GSStack.gc({AB, C})); // D is already gone.
+ auto *E = GSStack.addNode(0, nullptr, {Root});
+ EXPECT_EQ(3u, GSStack.gc({A, E})); // destroys B, AB, C
+ EXPECT_EQ(1u, GSStack.gc({E}));// destroys A
+
+ (void)D;
+}
+
} // namespace
} // namespace pseudo
} // namespace clang
Index: clang-tools-extra/pseudo/lib/GLR.cpp
===
--- clang-tools-extra/pseudo/lib/GLR.cpp
+++ clang-tools-extra/pseudo/lib/GLR.cpp
@@ -12,6 +12,7 @@
#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"
@@ -65,6 +66,17 @@
std::vector NewHeads = {
GSS.addNode(/*State=*/Params.Table.getStartState(StartSymbol),
/*ForestNode=*/nullptr, {})};
+ auto MaybeGC = [&, Roots(std::vector{}), I(0u)]() mutable {
+assert(NewHeads.empty() && "Running GC at the wrong time!");
+if (++I != 20) // Run periodically to balance CPU and memory usage.
+ return;
+I = 0;
+Roots.clear();
+for (const auto *Pending : {, , })
+ for (const auto : *Pending)
+Roots.push_back(E.Head);
+GSS.gc(std::move(Roots));
+ };
for (const ForestNode : Terminals) {
LLVM_DEBUG(llvm::dbgs() << llvm::formatv("Next token {0} (id={1})\n",
G.symbolName(Terminal.symbol()),
@@ -72,6 +84,7 @@
for (const auto *Head : NewHeads)
AddSteps(Head, Terminal.symbol());
NewHeads.clear();
+MaybeGC();
glrReduce(PendingReduce, Params,
[&](const GSS::Node * NewHead) {
// A reduce will enable more steps.
@@ -373,5 +386,73 @@
assert(Sequences.empty());
}
+const GSS::Node *GSS::addNode(LRTable::StateID State, const ForestNode *Symbol,
+ llvm::ArrayRef Parents) {
+ ++NodeCount;
+ Node *Result = new (allocate(Parents.size()))
+ Node({State, GCParity, static_cast(Parents.size())});
+ Allocated.push_back(Result);
+ Result->Payload = Symbol;
+ if (!Parents.empty())
+llvm::copy(Parents, reinterpret_cast(Result + 1));
+ return Result;
+}
+
+GSS::Node *GSS::allocate(unsigned Parents) {
+ ++NodeCount;
+ if (FreeList.size() <= Parents)
+FreeList.resize(Parents + 1);
+ auto = FreeList[Parents];
+ if (!SizedList.empty()) {
+auto *Result = SizedList.back();
+SizedList.pop_back();
+return Result;
+ }
+ return static_cast(
+ 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 &) {
+#ifndef NDEBUG
+ auto ParityMatches = [&](const Node *N) { return N->GCParity == GCParity; };
+ assert("Before GC" && llvm::all_of(Allocated, ParityMatches));
+ auto Deferred = llvm::make_scope_exit(
+ [&] { assert("After GC" && llvm::all_of(Allocated, ParityMatches)); });
+ assert(llvm::all_of(
+ Queue, [&](const Node *R) { return llvm::is_contained(Allocated, R); }));
+#endif
+ unsigned InitialCount = Allocated.size();
+
+ // Mark
+ GCParity = !GCParity;
+ while (!Queue.empty()) {
+Node *N = const_cast(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(Allocated, [&](Node *N) {
+if (N->GCParity == GCParity) //
[PATCH] D126723: [pseudo] GC GSS nodes, reuse them with a freelist
sammccall created this revision.
sammccall added a reviewer: hokein.
Herald added subscribers: usaxena95, kadircet.
Herald added a project: All.
sammccall requested review of this revision.
Herald added subscribers: cfe-commits, alextsao1999, ilya-biryukov.
Herald added a project: clang-tools-extra.
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.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D126723
Files:
clang-tools-extra/pseudo/include/clang-pseudo/GLR.h
clang-tools-extra/pseudo/lib/GLR.cpp
clang-tools-extra/pseudo/unittests/GLRTest.cpp
Index: clang-tools-extra/pseudo/unittests/GLRTest.cpp
===
--- clang-tools-extra/pseudo/unittests/GLRTest.cpp
+++ clang-tools-extra/pseudo/unittests/GLRTest.cpp
@@ -393,6 +393,29 @@
"[ 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})); // destroys D
+ EXPECT_EQ(0u, GSStack.gc({AB, C})); // D is already gone.
+ auto *E = GSStack.addNode(0, nullptr, {Root});
+ EXPECT_EQ(3u, GSStack.gc({A, E})); // destroys B, AB, C
+ EXPECT_EQ(1u, GSStack.gc({E}));// destroys A
+
+ (void)D;
+}
+
} // namespace
} // namespace pseudo
} // namespace clang
Index: clang-tools-extra/pseudo/lib/GLR.cpp
===
--- clang-tools-extra/pseudo/lib/GLR.cpp
+++ clang-tools-extra/pseudo/lib/GLR.cpp
@@ -12,6 +12,7 @@
#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"
@@ -65,6 +66,18 @@
std::vector NewHeads = {
GSS.addNode(/*State=*/Params.Table.getStartState(StartSymbol),
/*ForestNode=*/nullptr, {})};
+ auto MaybeGC = [&, Roots(std::vector{}), I(0u)]() mutable {
+assert(NewHeads.empty() && "Running GC at the wrong time!");
+if (++I != 20) // Run periodically to balance CPU and memory usage.
+ return;
+I = 0;
+Roots.clear();
+for (const auto *Pending : {, , })
+ for (const auto : *Pending)
+Roots.push_back(E.Head);
+GSS.gc(std::move(Roots));
+ };
+ std::vector GCRoots;
for (const ForestNode : Terminals) {
LLVM_DEBUG(llvm::dbgs() << llvm::formatv("Next token {0} (id={1})\n",
G.symbolName(Terminal.symbol()),
@@ -72,6 +85,7 @@
for (const auto *Head : NewHeads)
AddSteps(Head, Terminal.symbol());
NewHeads.clear();
+MaybeGC();
glrReduce(PendingReduce, Params,
[&](const GSS::Node * NewHead) {
// A reduce will enable more steps.
@@ -373,5 +387,73 @@
assert(Sequences.empty());
}
+const GSS::Node *GSS::addNode(LRTable::StateID State, const ForestNode *Symbol,
+ llvm::ArrayRef Parents) {
+ ++NodeCount;
+ Node *Result = new (allocate(Parents.size()))
+ Node({State, GCParity, static_cast(Parents.size())});
+ Allocated.push_back(Result);
+ Result->Payload = Symbol;
+ if (!Parents.empty())
+llvm::copy(Parents, reinterpret_cast(Result + 1));
+ return Result;
+}
+
+GSS::Node *GSS::allocate(unsigned Parents) {
+ ++NodeCount;
+ if (FreeList.size() <= Parents)
+FreeList.resize(Parents + 1);
+ auto = FreeList[Parents];
+ if (!SizedList.empty()) {
+auto *Result = SizedList.back();
+SizedList.pop_back();
+return Result;
+ }
+ return static_cast(
+ 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 &) {
+#ifndef NDEBUG
+ auto ParityMatches = [&](const Node *N) { return N->GCParity == GCParity; };
+ assert("Before GC"
