Iterator refactoring

[koute]

This PR simplifies and refactors the iterators in trie-db.

The changes can be summarized as follows:

• Added TrieDBNodeIterator-like TrieDBRawIterator and made it lifetimeless (instead of storing a &TrieDB it now takes it as a parameter during the iteration)
• SuspendedTrieDBKeyIterator was removed since the TrieDBRawIterator is a complete replacement for it (with the added bonus that it can be iterated on)
• TrieDBIterator::next and TrieDBKeyIterator::next were renamed and moved into TrieDBRawIterator with no changes to the logic (except making them use &TrieDB passed as a parameter instead of the one stored in self, and cleaning them up slightly)
• TrieDBIterator and TrieDBKeyIterator now use TrieDBRawIterator under the hood
• A bunch of #[inline]s were added to make recreating a &TrieDB on each iteration into a zero-cost operation
• All of the relevant crate versions were bumped

This makes further refactoring of storage iterators in substrate possible.

[cheme]

TrieDBIterator and TrieDBKeyIterator now use TrieDBRawIterator under the hood

wasn't it the case already?

[cheme]

This makes further refactoring of storage iterators in substrate possible.

Does the suspended approach not work (I remember putting something in place but probably drop it at some point, not sure why)?

[koute]

What are the plans for the substrate optim, I remember planning to use the suspended struct in host function to use it again if the start key used in a following next_key call is the same as the previously return key (but don't find back my branch)? [...] Does the suspended approach not work (I remember putting something in place but probably drop it at some point, not sure why)?

For now I'm mostly just simplifying the way we do iteration; e.g. the Backend trait in state-machine has something like ~8 methods which do iteration, some using an Fn callback and some just collecting into a Vec, and I'm essentially replacing them all with a single method that just returns a raw iterator (plus two extra methods which return dedicated iterators for keys and pairs which are themselves just tiny wrappers around the raw iterator).

So it is essentially the suspend approach, it just needs these changes to make it fully possible (not everything was originally exported the first time I tried it IIRC) and simpler.

In general for now my main objective is to just simplify and remove dangerous methods (those which return a Vec, which make our RPC nodes explode), but I also want to eventually look into speeding up storage iteration/accesses altogether.

Regarding possible substrate optimization, there is one I would find interesting, that would be to switch sp-state-machine backend trait to use &mut on all accesses, thus removing the need for inner mutability (for trie cache and recorder).

Hmm.... is this actually going to affect the performance in a substantial way?

TrieDBIterator and TrieDBKeyIterator now use TrieDBRawIterator under the hood

wasn't it the case already?

Previously they had their dedicated next methods; now those were moved to the raw iterator, so now they're truly just a thin wrappers with no logic of their own.

[cheme]

Hmm.... is this actually going to affect the performance in a substantial way?

Not sure about perf, actually recorder and cache are already behind a refcell in the trie crate. So probably the recorder is already accessed without lock, not sure about the local cache (may still be a useless rwlock there for the local caching, really not sure).

Would still make sense to me to just plain &mut ptr for read access operation and get rid of as much inner mutability as possible, but that is a different question.

[koute]

@cheme Okay, I resurrected the fuzz tests (they didn't compile due to too old version of a dependency in Cargo.toml), renamed the seek_prefix to seek, made next_raw_item return references, and I've simplified the iterator methods a little more (I've reduced the indentation levels, removed unnecessary expects, removed the extra internal enum in next_raw_item).

The logic's unchanged and I didn't touch the extra clones. You're right that we should be able to refactor it so that it appends to the key_nibbles directly, but from what I can see that'd be a more involved change so for now I left it as-is for a future PR.

[cheme]

yes the fuzzer is quite often a bit behind, thanks.

You're right that we should be able to refactor it so that it appends to the key_nibbles directly, but from what I can see that'd be a more involved change so for now I left it as-is for a future PR

I did check a bit, we probably want to return the key_nibbles after the partial (append the partial on descend), which seems fine to do, but at the same time the change will require to modify trie_codec.rs which can be a bit too many changes.

[cheme]

Missed you by a few second, but trie-bench changelog can also be updated (not really important tbh), otherwhise latest changes still looks good.

[koute]

but trie-bench changelog can also be updated

Ah, sorry, I didn't realize that one's also released on crates.io. I'll update it.