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.
The doc formatting changes introduced in the recent go version is
increasing the diff for all of the new commits. Formatting it all in
this commit will help the readability of future PRs by reducing the
diff.
The github markdown interpreter has been changed such that it no longer
allows spaces in between the brackets and parenthesis of links and now
requires a newline in between anchors and other formatting. This
updates all of the markdown files accordingly.
While here, it also corrects a couple of inconsistencies in some of the
README.md files.
