rax
rax copied to clipboard
Add state to the iterator to avoid re-scans for children
This PR:
- Adds a byte stack to
raxIterator
that contains child offsets. - Adds a separate, more complicated and slightly slower
raxLowWalkSeek()
for use byraxSeek()
- this preserves the speed of the simpler originalraxLowWalk()
which is heavily used byraxFind()
etc. - Modifies the
raxSeek()
,raxNext()
andraxPrior()
functions to use the above. - Also incorporates a substantive simplification made to
raxSeek()
taken from Redis 7.0.
The default rax-tests pass, including the fuzz tests.
I merged this in a branch of my fork for testing: https://github.com/jcorporation/rax/tree/michaelplaing-iter_scan_upgrade
I have run the benchmark on master (without this patch) and your patch merged (branch michaelplaing-iter_scan_upgrade) and could see only minor timing changes. Do I miss anything?
There are only minor improvements on the original default tests as they have a pretty sparse keyspaces. Since the spans in each node therefore are short, there is not much room to improve. Tests using binary data can show much more improvement, depending on density. timestamps might be a good example, if they are issued close together. Redis uses millions of them and they are iterated in the event loop. Sequential IDs might be another usage.
How large must be the keyspace to see improvements? A benchmark for illustration would be good.