| durham |
| Restricted Project |
The radix tree would be using base16 to save space and support hex-string
prefix queries. Therefore a base16 iterator is needed.
DoubleEndedIterator, ExactSizeIterator and fast paths of skip and
take are implemented so certain patterns (ex. skip.take.rev, used in a
future patch) could work without a temporary Vec.
cargo test --lib
| Automatic diff as part of commit; lint not applicable. |
| Automatic diff as part of commit; unit tests not applicable. |
| rust/radix204/src/base16.rs | ||
|---|---|---|
| 10–17 ↗ | (On Diff #3210) | This seems a bit over-complex. You basically want an iterator that can take anything that's AsRef<[u8]> and then emit those bytes nibble-by-nibble. It may also end up being awkward for it to always borrow the value rather than taking ownership of it. It's always more flexible to have a trait take something by ownership, because then you can either make it own something outright (ie, have 'static lifetime), or implement it for a &'a T type, and it's subject to 'a lifetime. Whereas if you specify the trait as having a lifetime, then you're stuck with that, and its hard to make it own something if that what you need to do. |
| rust/radix204/src/base16.rs | ||
|---|---|---|
| 10–17 ↗ | (On Diff #3210) | I had another flexible version that takes an iterator: pub struct IterIter(Box<Iterator<Item = u8>>, u8, u8);
impl IntoBase16Iter<IterIter> for Vec<u8> {
fn into_base16iter(self) -> IterIter { IterIter(Box::new(self.into_iter()), 0, 0) }
}
impl Iterator for IterIter {
type Item = u8;
fn next(&mut self) -> Option<Self::Item> {
match self.2 {
0 => {
match self.0.next() {
Some(x) => {
self.1 = x & 0xf;
self.2 = 1;
Some(x >> 4)
}
None => None,
}
}
1 => {
self.2 = 0;
Some(self.1)
}
_ => None,
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
let (lower, higher) = self.0.size_hint();
(lower * 2 + 1, higher.map(|x| x * 2 + 2))
}
fn count(self) -> usize { self.0.count() * 2 + 1 }
}But it was slower. I was using into_base16iter(self) but found it enforced copies and that did hurt perf. So I changed it to to_ version. I agree the iterator type here is tricky. The current code is after some aggressive simplification. Previously I wanted to make things very flexible and had ended up like: impl<K, KC, KI, KB, RB, V> RadixTree<K, KC, KI, KB, RB, V>
where
for<'a> K: ToBase16Iter<'a, KI>,
KC: KeyConverter<K>,
KI: Iterator<Item = u8>,
KB: Read + Write + Seek,
RB: Read + Write + Seek,
V: Serialize,It actually worked thanks for the for<'a> syntax. But the API is not that easy to use. It was also slower (io::Cursor adds 50% overhead). So I decided to trade flexibility for performance. |
For the "take the ownership": The &[u8] comes from a slice owned by a mmap-ed buffer. We cannot own the entire mmap buffer here in the iterator. By copying the slice to heap the radix tree is about ~50% slower. So taking reference to achieve zero-copy here seems to be a reasonable choice.
The ToBase16Iter trait can be replaced by a function to reduce type complexity. That'll be a codemoding replacing all x.to_base16iter() to to_base16iter(x). I'll do that.
| rust/radixbuf/src/base16.rs | ||
|---|---|---|
| 97 | There are too many combinations. I think these are complex enough to reasonably cover interesting cases. | |
| 109 | Will remove u8 after 0x56. Elements in a Rust array must have a same type. So one explicit type is enough. | |
Why test these particular access patterns? Why not others?