3 ms·
It feels to me like this just a kludge added to deal with a lack of a stateful iterator on top of the tree. In this use case, the author indicates that it is ab
by vvern 5y ago
It feels to me like this just a kludge added to deal with a lack of a stateful iterator on top of the tree. In this use case, the author indicates that it is about exploiting locality in a request path. Imagine that the tree offered an iterator that maintained a stack of its path and that thing had a seek method. You can optimize that thing to only go back up to the root if it needs to. Stateful iterators make for a nice pairing with btrees. These other hints are papering over the lack of that abstraction as far as I can tell.
- anderskaseorg 5y agoWith a stateful iterator, you might need to worry about your cached pointers being invalidated by mutations from other callers.
- Ar-Curunir 5y agoNot to sound like a member of the Rust Evangelism StrikeForce, but Rust is able to offer stateful iterators over its `BTree` exactly by preventing mutation during iteration.
- oscardssmith 5y agoDoesn't that mean that iteration requires a write lock? That sounds bad for lots of applications.
- Ar-Curunir 5y agoThe write-lock is checked entirely at compile time, so no performance overhead
- hedora 5y agoIt sounds like that will prevent threads from mutating the tree in the (potential) presence of an iterator in some other part of the tree, which is prohibitively expensive for many applications. Am I missing some clever trick?
- binarybanana 5y agoNo, that is correct. There are ways to avoid locks, but the stdlib implemtation doesn't do it. There are probably a bunch of crates that implemented concurrent BTrees, though.