Previously, the Put() function took in a single key-value pair,
resulting in memory allocation overhead as the intermediary treapNodes
got allocated and immediately garbage collected, resulting in
performance loss due to the garbage collection overhead.
We're able to recycle the intermediary treapNodes allocated by taking in
multiple key-value pairs. This results in better performance of the
node especially during UTXO cache flushes.
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.
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.
