treap: add treapNodePool and fetch from it for cloneTreapNode and newTreapNode
What the developer wrote
Authored by Calvin Kim
treap: add treapNodePool and fetch from it for cloneTreapNode and
newTreapNode
The treapNodePool will allow for less memory allocations during
immutable treap operations. We first change the cloneTreapNode and
newTreapNode to allocate a treapNode from the sync.Pool.
The allocated treapNodes will be put back into the sync.Pool in later
commits.
What changed, and why it matters
This commit is a routine performance optimization for an internal data structure used in the btcd Bitcoin node. It introduces a memory pool (sync.Pool) to reuse small treapNode objects instead of repeatedly allocating new ones from the garbage collector. There is no security-relevant change here; it only reduces memory pressure and allocation overhead during database operations.
No security action required. Treat as a normal performance refactor. If reviewing the broader series, verify that later commits correctly reset all treapNode fields before returning objects to the pool to avoid stale-state bugs.
Security signals we found
No strong security signals were identified.
Evidence from the diff
The change modifies database/internal/treap/common.go and database/internal/treap/immutable.go so that newTreapNode and cloneTreapNode fetch a treapNode from a package-level sync.Pool rather than constructing one with the &treapNode{} literal. The fields are then explicitly assigned. The commit message notes that returning nodes to the pool will happen in later commits, so this patch is only the first half of the optimization. No logic, validation, or concurrency behavior changes are introduced.
Changed components
database/internal/treap/common.godatabase/internal/treap/immutable.goInspect captured patch +25 / −8
diff --git a/database/internal/treap/common.go b/database/internal/treap/common.go
index 090a7bd..1eaf6bc 100644
--- a/database/internal/treap/common.go
+++ b/database/internal/treap/common.go
@@ -6,6 +6,7 @@ package treap
import (
"math/rand"
+ "sync"
"time"
)
@@ -33,6 +34,14 @@ var (
emptySlice = make([]byte, 0)
)
+// treapNodePool defines a concurrent safe free list of treapNode used to
+// provide temporary buffers.
+var treapNodePool = sync.Pool{
+ New: func() any {
+ return &treapNode{}
+ },
+}
+
// treapNode represents a node in the treap.
type treapNode struct {
key []byte
@@ -51,7 +60,14 @@ func nodeSize(node *treapNode) uint64 {
// newTreapNode returns a new node from the given key, value, and priority. The
// node is not initially linked to any others.
func newTreapNode(key, value []byte, priority int) *treapNode {
- return &treapNode{key: key, value: value, priority: priority}
+ n := treapNodePool.Get().(*treapNode)
+ n.key = key
+ n.value = value
+ n.priority = priority
+ n.left = nil
+ n.right = nil
+
+ return n
}
// parentStack represents a stack of parent treap nodes that are used during
diff --git a/database/internal/treap/immutable.go b/database/internal/treap/immutable.go
index 0a05d13..16997e9 100644
--- a/database/internal/treap/immutable.go
+++ b/database/internal/treap/immutable.go
@@ -11,13 +11,14 @@ import (
// cloneTreapNode returns a shallow copy of the passed node.
func cloneTreapNode(node *treapNode) *treapNode {
- return &treapNode{
- key: node.key,
- value: node.value,
- priority: node.priority,
- left: node.left,
- right: node.right,
- }
+ n := treapNodePool.Get().(*treapNode)
+ n.key = node.key
+ n.value = node.value
+ n.priority = node.priority
+ n.left = node.left
+ n.right = node.right
+
+ return n
}
// Immutable represents a treap data structure which is used to hold ordered
Why this scored 12/100
Community notes
Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.
The AI analysis stands alone for now. Submit a note if you can add evidence or important context.