The iterators of functional-red-black-tree have an update(value) method. For keys that already exist, memdown can use this method to directly update the corresponding node, instead of removing it (for which RBTree itself uses an iterator) and then inserting a new node.
Performance of inserting new keys is the same, overwriting keys is 1.5 to twice as fast.
A benchmark ("remove and insert" is the current implementation, "update or insert" the new):
> matcha put-bench.js
put new key
32 op/s » remove and insert
33 op/s » update or insert
put existing key
270 op/s » remove and insert
486 op/s » update or insert
> matcha batch-bench.js
put new key
36 op/s » remove and insert
36 op/s » update or insert
put new key and delete
27 op/s » remove and insert
27 op/s » update or insert
delete non-existing keys
152 op/s » remove and insert
166 op/s » update or insert
put existing key
342 op/s » remove and insert
590 op/s » update or insert
Build is failing because Saucelabs only runs for contributors... it's a dumb limitation, and I'll get around it by just opening a PR myself with your exact commits. Once that's green, I'm +1.
The iterators of
functional-red-black-tree
have anupdate(value)
method. For keys that already exist, memdown can use this method to directly update the corresponding node, instead of removing it (for which RBTree itself uses an iterator) and then inserting a new node.Performance of inserting new keys is the same, overwriting keys is 1.5 to twice as fast.
A benchmark ("remove and insert" is the current implementation, "update or insert" the new):