What the developer wrote
Authored by Calvin Kim
treap: return newly created treapNodes in put()
The newly created treapNodes in put() are now returned so that the
caller has access to them. This is done so that the caller can put back
some of the treapNodes to sync.Pool.
For multiple put operations, an immutable treap will allocate many
treapNodes that will immediately be garbage collected. Let's say
there's 3 key-value pairs that are going to be inserted:
key 1: 50
key 2: 10
key 3: 4
Then the insertion is like so:
1: allocate 50.
50
2: clone 50, allocate 10.
50
/ \
10
3: clone 50, clone 10, allocate 4
50
/ \
10
/
4
In this example, only the nodes allocated during insertion of (3) is
going to be used. The rest is going to be garbage collected and they
can be safely be put in the sync.Pool if there's a guarantee that the
previous copies are not being accessed. This is true if the put
operations are going to be called in batches.
By returning the pointers of these allocated treapNodes, we allow the
caller to make such optimizations.
What changed, and why it matters
This commit is a performance optimization for an internal data structure (a treap, a type of tree used in btcd's database). It changes the private put() function to return pointers to newly created nodes so that future callers can recycle them through a sync.Pool, reducing memory allocations. The public Put() method ignores these returned nodes, so behavior is unchanged. There is no security fix or vulnerability patch here.
No security action needed. Treat as a routine performance refactor. If reviewing a larger change that later uses the returned nodes with sync.Pool, verify that recycled nodes are fully reset before reuse to avoid stale-field bugs, but that is outside the scope of this commit.
Security signals we found
No strong security signals were identified.
Evidence from the diff
The change modifies database/internal/treap/immutable.go so that the unexported put() method returns both the updated Immutable treap and an array of newly allocated/cloned treapNode pointers. The exported Put() wrapper discards the array and returns only the Immutable, preserving the existing API. The intent is to allow future batched put operations to return transient node allocations to a sync.Pool, reducing GC pressure. No logic governing key/value insertion, ordering, priorities, or node linking is altered.
Changed components
database/internal/treap/immutable.goprivate put() helperpublic Put() methodInspect captured patch +39 / −7
diff --git a/database/internal/treap/immutable.go b/database/internal/treap/immutable.go
index 16997e9..84ad60b 100644
--- a/database/internal/treap/immutable.go
+++ b/database/internal/treap/immutable.go
@@ -107,11 +107,15 @@ func (t *Immutable) Get(key []byte) []byte {
// Put inserts the passed key/value pair.
func (t *Immutable) Put(key, value []byte) *Immutable {
- return t.put(key, value)
+ immutable, _ := t.put(key, value)
+ return immutable
}
-// put inserts the passed key/value pair.
-func (t *Immutable) put(key, value []byte) *Immutable {
+// put inserts the passed key/value pair and returns all the newly created
+// treapNodes that were created during this put operation. The returned
+// treapNodes can then be put into data structures like sync.Pool to reduce the
+// memory overhead of allocating new treapNodes during multiple put calls.
+func (t *Immutable) put(key, value []byte) (*Immutable, [staticDepth]*treapNode) {
// Use an empty byte slice for the value when none was provided. This
// ultimately allows key existence to be determined from the value since
// an empty byte slice is distinguishable from nil.
@@ -119,10 +123,19 @@ func (t *Immutable) put(key, value []byte) *Immutable {
value = emptySlice
}
+ // recycle is the treapNodes that are created during this put operation.
+ // We keep track of the nodes as the caller may be choose to recycle
+ // them to keep memory allocation low.
+ var (
+ recycle [staticDepth]*treapNode
+ currentRecycleIndex int
+ )
+
// The node is the root of the tree if there isn't already one.
if t.root == nil {
root := newTreapNode(key, value, rand.Int())
- return newImmutable(root, 1, nodeSize(root))
+ recycle[currentRecycleIndex] = root
+ return newImmutable(root, 1, nodeSize(root)), recycle
}
// Find the binary tree insertion point and construct a replaced list of
@@ -138,6 +151,16 @@ func (t *Immutable) put(key, value []byte) *Immutable {
for node := t.root; node != nil; {
// Clone the node and link its parent to it if needed.
nodeCopy := cloneTreapNode(node)
+
+ // Check if we still have space in the recycle for this node.
+ // It's ok if we don't put every single new node to be recycled
+ // as there's no guarantee in the sync.Pool that every recycled
+ // treapNode will be re-utilized.
+ if currentRecycleIndex < staticDepth {
+ recycle[currentRecycleIndex] = nodeCopy
+ currentRecycleIndex++
+ }
+
if oldParent := parents.At(0); oldParent != nil {
if oldParent.left == node {
oldParent.left = nodeCopy
@@ -167,11 +190,20 @@ func (t *Immutable) put(key, value []byte) *Immutable {
newRoot := parents.At(parents.Len() - 1)
newTotalSize := t.totalSize - uint64(len(node.value)) +
uint64(len(value))
- return newImmutable(newRoot, t.count, newTotalSize)
+ return newImmutable(newRoot, t.count, newTotalSize), recycle
}
- // Link the new node into the binary tree in the correct position.
+ // Check if we still have space in the recycle for this node.
+ // It's ok if we don't put every single new node to be recycled
+ // as there's no guarantee in the sync.Pool that every recycled
+ // treapNode will be re-utilized.
node := newTreapNode(key, value, rand.Int())
+ if currentRecycleIndex < staticDepth {
+ recycle[currentRecycleIndex] = node
+ currentRecycleIndex++
+ }
+
+ // Link the new node into the binary tree in the correct position.
parent := parents.At(0)
if compareResult < 0 {
parent.left = node
@@ -211,7 +243,7 @@ func (t *Immutable) put(key, value []byte) *Immutable {
}
}
- return newImmutable(newRoot, t.count+1, t.totalSize+nodeSize(node))
+ return newImmutable(newRoot, t.count+1, t.totalSize+nodeSize(node)), recycle
}
// Delete removes the passed key from the treap and returns the resulting treap
Why this scored 14/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.