Fix stack overflow during btree iteration

[i1i1]

Migrating from rocksdb to paritydb (here) I discovered that stack randomly overflows during BTreeIterator::{next, prev} calls.

Seems like rust compiler failed to optimize some recursive functions with no state with TCO (even in release mode). Looks like as all optimizations, TCO is also eventual and is not guaranteed in any way. More on the history of it in the compiler here.

So this pr basically rewrites recursive functions using loops so that we would guarantee that we will reuse memory and won't allocate stack frame.

Better to review pr commit by commit, and for the first one it would be helpful to ignore indentations.

[cheme]

I had a branch which implements prev iterator differently (but forgot to do a PR for it), I wonder if tail recursion work on it master...cheme:parity-db:last_state_iterator (the branch avoid seek when changing direction and remove some code redundancy).

But regarding this PR, looks good to me, except the missing line in comment (I did not check code logic, just ensure the code path is the same).

More generally, I prefer not having the rec call, but I'll be interested to know under which condition the stack overflow happen, certainly not the depth of the btree, there may be something else here.

[nazar-pc]

@i1i1 can you run it under gdb to catch backtrace when stack overflow happens?

[i1i1]

@cheme Here is the backtrace.
You can reproduce it on this commit with following command:

$ cargo run --release -p subspace-farmer -- \
    --base-path some-path-with-empty-3G-of-space \
    bench \
      --plot-size 3G \
      --write-pieces-size 6G

CC: @nazar-pc

[cheme]

what I think may have happen is that we touch a removed value in commit overlay, and we did change direction, so even if on recursive call (former line 156) there is a self.from_seek = false it is set again here due to direction switch and then we loop more than 3 thousand time on next function, probably exit the loop when commit value get flushed.
So before recursive call direction would need to be updated.
With current PR, we will be having some very long call to next in this case.
So this needs fixing.

An alternative to fixing these direction would be to try to use my branch I did mention, but that is more review work.

[i1i1]

Didn't review code, but feel free to open pr with it and adding me as a reviewer!

Tested that branch, and it also exits with stack overflow

[cheme]

Tested that branch, and it also exits with stack overflow

By any chance, do you have the stack trace? (I did not read the same issue).

Realize I am wrong in my earlier statement since direction should have been updated in call to next_backend.

[cheme]

Ok got it, your process did probably remove something like more than 3000 values, and then the iterator goes over the commit map in a recursive way.
So fixing the way you did is correct.

[cheme]

@i1i1 thanks for the stacktrace and the PR. Small question what is the size (in number for keys) of your column ? (One of my first implementation for the btree index did use a dedicated file for nodes which we replace by just using table values entry to simplify a bit as perf was not the first concern, but maybe I should try to resurrect the branch IIRC it is an easy perf gain and not that much code in fact).

[i1i1]

Small question what is the size (in number for keys) of your column?

In that case, it was around 3000 keys. Scenario was as follows:

1. At first, we insert 3000 key values in batches of 256 I believe
2. Then we do those things in a loop:
3. 1. try to find N keys starting from the beginning of the db and N keys from the end
4. 2. remove those keys and add some new ones

So everything blows at iterating over db as we hit some case when we need to recur after removing key in commit overlay

[i1i1]

@cheme can you merge it please? Or are we waiting for something?

[cheme]

I think it's good. @arkpar I am merging let me know if anything off.