summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2021-11-18 19:19:30 -0800
committerGravatar dinord <dino.radakovich@gmail.com>2021-11-19 10:33:56 -0500
commit8a4e6b8cc9baa26ebdc87fd813dc808d77e0640c (patch)
treeafc4a692db8fff7966e52e86366d5ed912058bdc
parent299f59cadda78dfaf71b2a35049b63911e8eff47 (diff)
Export of internal Abseil changes
-- e400e8c3dc7190b83dec57be9d858ee44e146a42 by Martijn Vels <mvels@google.com>: Optimize Cord destructor through CordRepBtree::Destroy This change inlines tree destruction 2 levels at a time, special casing leaf and leaf + 1 levels. Benchmarks shows this provides up to 8% speed up PiperOrigin-RevId: 410953099 GitOrigin-RevId: e400e8c3dc7190b83dec57be9d858ee44e146a42 Change-Id: Ic1c123fa0fa2b13cb141ee7a6be155d9e57a0466
-rw-r--r--absl/strings/internal/cord_rep_btree.cc71
-rw-r--r--absl/strings/internal/cord_rep_btree.h22
2 files changed, 51 insertions, 42 deletions
diff --git a/absl/strings/internal/cord_rep_btree.cc b/absl/strings/internal/cord_rep_btree.cc
index 7cefcc52..83cdd5f4 100644
--- a/absl/strings/internal/cord_rep_btree.cc
+++ b/absl/strings/internal/cord_rep_btree.cc
@@ -190,24 +190,29 @@ inline void FastUnref(R* r, Fn&& fn) {
}
}
-// Deletes a leaf node data edge. Requires `rep` to be an EXTERNAL or FLAT
-// node, or a SUBSTRING of an EXTERNAL or FLAT node.
-void DeleteLeafEdge(CordRep* rep) {
- for (;;) {
+
+void DeleteSubstring(CordRepSubstring* substring) {
+ CordRep* rep = substring->child;
+ if (!rep->refcount.Decrement()) {
if (rep->tag >= FLAT) {
CordRepFlat::Delete(rep->flat());
- return;
- }
- if (rep->tag == EXTERNAL) {
+ } else {
+ assert(rep->tag == EXTERNAL);
CordRepExternal::Delete(rep->external());
- return;
}
- assert(rep->tag == SUBSTRING);
- CordRepSubstring* substring = rep->substring();
- rep = substring->child;
- assert(rep->tag == EXTERNAL || rep->tag >= FLAT);
- delete substring;
- if (rep->refcount.Decrement()) return;
+ }
+ delete substring;
+}
+
+// Deletes a leaf node data edge. Requires `IsDataEdge(rep)`.
+void DeleteLeafEdge(CordRep* rep) {
+ assert(CordRepBtree::IsDataEdge(rep));
+ if (rep->tag >= FLAT) {
+ CordRepFlat::Delete(rep->flat());
+ } else if (rep->tag == EXTERNAL) {
+ CordRepExternal::Delete(rep->external());
+ } else {
+ DeleteSubstring(rep->substring());
}
}
@@ -372,19 +377,39 @@ void CordRepBtree::Dump(const CordRep* rep, std::ostream& stream) {
Dump(rep, absl::string_view(), false, stream);
}
-void CordRepBtree::DestroyLeaf(CordRepBtree* tree, size_t begin, size_t end) {
- for (CordRep* edge : tree->Edges(begin, end)) {
- FastUnref(edge, DeleteLeafEdge);
+template <size_t size>
+static void DestroyTree(CordRepBtree* tree) {
+ for (CordRep* node : tree->Edges()) {
+ if (!node->refcount.Decrement()) {
+ for (CordRep* edge : node->btree()->Edges()) {
+ if (!edge->refcount.Decrement()) {
+ if (size == 1) {
+ DeleteLeafEdge(edge);
+ } else {
+ CordRepBtree::Destroy(edge->btree());
+ }
+ }
+ }
+ CordRepBtree::Delete(node->btree());
+ }
}
- Delete(tree);
+ CordRepBtree::Delete(tree);
}
-void CordRepBtree::DestroyNonLeaf(CordRepBtree* tree, size_t begin,
- size_t end) {
- for (CordRep* edge : tree->Edges(begin, end)) {
- FastUnref(edge->btree(), Destroy);
+void CordRepBtree::Destroy(CordRepBtree* tree) {
+ switch (tree->height()) {
+ case 0:
+ for (CordRep* edge : tree->Edges()) {
+ if (!edge->refcount.Decrement()) {
+ DeleteLeafEdge(edge);
+ }
+ }
+ return CordRepBtree::Delete(tree);
+ case 1:
+ return DestroyTree<1>(tree);
+ default:
+ return DestroyTree<2>(tree);
}
- Delete(tree);
}
bool CordRepBtree::IsValid(const CordRepBtree* tree, bool shallow) {
diff --git a/absl/strings/internal/cord_rep_btree.h b/absl/strings/internal/cord_rep_btree.h
index 0b44509e..df5c994c 100644
--- a/absl/strings/internal/cord_rep_btree.h
+++ b/absl/strings/internal/cord_rep_btree.h
@@ -163,6 +163,9 @@ class CordRepBtree : public CordRep {
// typically after a ref_count.Decrement() on the last reference count.
static void Destroy(CordRepBtree* tree);
+ // Destruction
+ static void Delete(CordRepBtree* tree) { delete tree; }
+
// Use CordRep::Unref() as we overload for absl::Span<CordRep* const>.
using CordRep::Unref;
@@ -440,12 +443,6 @@ class CordRepBtree : public CordRep {
// Requires `offset` < length.
Position IndexBeyond(size_t offset) const;
- // Destruction
- static void DestroyLeaf(CordRepBtree* tree, size_t begin, size_t end);
- static void DestroyNonLeaf(CordRepBtree* tree, size_t begin, size_t end);
- static void DestroyTree(CordRepBtree* tree, size_t begin, size_t end);
- static void Delete(CordRepBtree* tree) { delete tree; }
-
// Creates a new leaf node containing as much data as possible from `data`.
// The data is added either forwards or reversed depending on `edge_type`.
// Callers must check the length of the returned node to determine if all data
@@ -689,19 +686,6 @@ inline CordRepBtree* CordRepBtree::New(CordRepBtree* front,
return tree;
}
-inline void CordRepBtree::DestroyTree(CordRepBtree* tree, size_t begin,
- size_t end) {
- if (tree->height() == 0) {
- DestroyLeaf(tree, begin, end);
- } else {
- DestroyNonLeaf(tree, begin, end);
- }
-}
-
-inline void CordRepBtree::Destroy(CordRepBtree* tree) {
- DestroyTree(tree, tree->begin(), tree->end());
-}
-
inline void CordRepBtree::Unref(absl::Span<CordRep* const> edges) {
for (CordRep* edge : edges) {
if (ABSL_PREDICT_FALSE(!edge->refcount.Decrement())) {