This is an archive of the discontinued Mercurial Phabricator instance.

Differential D1328

radix204: add memvec support
AbandonedPublic

Authored by quark on Nov 7 2017, 12:40 PM.
Tags
None
Subscribers
None

Details

Reviewers
None
Group Reviewers
Restricted Project
Summary

As planned, the radix buffer could also be backed by mmap-based vectors.
This diff implements that.

Performance-wise, the mmap version running on a tmpfs is very similar to the
vec version:

test radix::tests::bench_50k_insert       ... bench:   4,691,703 ns/iter (+/- 678,029)
test radix::tests::bench_50k_insert_mmap  ... bench:   4,557,263 ns/iter (+/- 822,600)

Diff Detail

Repository
rFBHGX Facebook Mercurial Extensions
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

quark created this revision.Nov 7 2017, 12:40 PM
Herald added a reviewer: Restricted Project. · View Herald TranscriptNov 7 2017, 12:40 PM
quark abandoned this revision.Nov 11 2017, 1:34 AM

No longer needed after refactoring.

Revision Contents
Changeset List

PathPackages
Mrust/radix204/src/lib.rs (2 lines)
Mrust/radix204/src/radix.rs (159 lines)

Diff 3313

rust/radix204/src/lib.rs

extern crate tempdir; extern crate tempdir;
pub mod types; pub mod types;
pub mod errors; pub mod errors;
pub mod base16; pub mod base16;
pub mod radix; pub mod radix;
pub mod mmapvec; pub mod mmapvec;
pub type RadixBuffer = radix::RadixBuffer; pub type RadixBuffer<KB, RB> = radix::RadixBuffer<KB, RB>;

rust/radix204/src/radix.rs

// Copyright 2017 Facebook, Inc. // Copyright 2017 Facebook, Inc.
// //
// This software may be used and distributed according to the terms of the // This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version. // GNU General Public License version 2 or any later version.
//! Main radix buffer implementation that maintains `Key` to `KeyId` mapping. //! Main radix buffer implementation that maintains `Key` to `KeyId` mapping.
use std::ops::DerefMut; use std::ops::{DerefMut, Index, IndexMut, Range};
use std::marker::PhantomData;
use base16::ToBase16Iter; use base16::ToBase16Iter;
use errors::{Result, ErrorKind}; use errors::{Result, ErrorKind};
use mmapvec::MmapVec;
use types::{Key, KeyId, Offset, Shared}; use types::{Key, KeyId, Offset, Shared};
// KeyBuffer and RadixBuffer.
// They might be changed to type parameters. ex. they might be backed by mmap.
type KB = Vec<u8>;
type RB = Vec<u32>;
/// Represents pointer to 16 offsets that are rewritable in-place. /// Represents pointer to 16 offsets that are rewritable in-place.
struct RadixNode(Offset); struct RadixNode<KB, RB>(Offset, PhantomData<(KB, RB)>);
/// The return value of `RadixNode::follow`. /// The return value of `RadixNode::follow`.
enum FollowResult { enum FollowResult<KB, RB> {
Radix(RadixNode), Radix(RadixNode<KB, RB>),
KeyId(KeyId), KeyId(KeyId),
Missing, Missing,
} }
impl RadixNode { impl<KB, RB> RadixNode<KB, RB>
where
KB: VecLike<u8>,
RB: VecLike<u32>,
{
#[inline] #[inline]
pub fn new(offset: Offset) -> Self { RadixNode(offset) } pub fn new(offset: Offset) -> Self { RadixNode(offset, PhantomData) }
#[inline] #[inline]
pub fn create(vec: &mut RB) -> Result<Self> { pub fn create(vec: &mut RB) -> Result<Self> {
let mut pos = vec.len(); let mut pos = vec.len();
// The LSB is reserved for marking leaf. So align pos by 2. // The LSB is reserved for marking leaf. So align pos by 2.
if pos & 1 == 1 { if pos & 1 == 1 {
pos += 1; pos += 1;
} }
if pos > ::std::u32::MAX as usize { if pos > ::std::u32::MAX as usize {
return Err(ErrorKind::OffsetOverflow(pos).into()); return Err(ErrorKind::OffsetOverflow(pos).into());
} }
vec.resize(pos + 16, 0); vec.resize(pos + 16, 0);
Ok(RadixNode(Offset::from(pos as u32))) Ok(RadixNode(Offset::from(pos as u32), PhantomData))
} }
/// Follow index by one step. /// Follow index by one step.
#[inline] #[inline]
pub fn follow(&self, vec: &RB, index: u8) -> Result<FollowResult> { pub fn follow(&self, vec: &RB, index: u8) -> Result<FollowResult<KB, RB>> {
debug_assert!(index < 16); debug_assert!(index < 16);
let pos = self.0.to_usize() + usize::from(index); let pos = self.0.to_usize() + usize::from(index);
let o = vec.get(pos); if pos >= vec.len() {
match o { return Err(ErrorKind::OffsetOverflow(pos).into());
None => Err(ErrorKind::OffsetOverflow(pos).into()), }
Some(v) => { let v = vec[pos].to_le();
let v = v.to_le();
if v == 0 { if v == 0 {
Ok(FollowResult::Missing) Ok(FollowResult::Missing)
} else if v & 1 != 0 { } else if v & 1 != 0 {
Ok(FollowResult::KeyId((v >> 1).into())) Ok(FollowResult::KeyId((v >> 1).into()))
} else { } else {
Ok(FollowResult::Radix(RadixNode::new(v.into()))) Ok(FollowResult::Radix(RadixNode::<KB, RB>::new(v.into())))
}
}
} }
} }
/// Return an iterator of non-none (not 0) indexes. /// Return an iterator of non-none (not 0) indexes.
#[inline] #[inline]
pub fn keys(&self, vec: &mut RB) -> Result<Vec<u8>> { pub fn keys(&self, vec: &mut RB) -> Result<Vec<u8>> {
let pos = self.0.to_usize(); let pos = self.0.to_usize();
let end = pos + 16; let end = pos + 16;
if end > vec.len() { if end > vec.len() {
return Err(ErrorKind::OffsetOverflow(pos).into()); return Err(ErrorKind::OffsetOverflow(pos).into());
} }
Ok( Ok(
vec[pos..end] vec[pos..end]
.iter() .iter()
.enumerate() .enumerate()
.filter(|&(_, v)| *v != 0) .filter(|&(_, v)| *v != 0)
.map(|(i, _)| i as u8) .map(|(i, _)| i as u8)
.collect(), .collect(),
) )
} }
/// Rewrite an index entry to point to another `RadixNode`. /// Rewrite an index entry to point to another `RadixNode`.
#[inline] #[inline]
pub fn write_radix(&self, vec: &mut RB, index: u8, node: &RadixNode) -> Result<()> { pub fn write_radix(&self, vec: &mut RB, index: u8, node: &RadixNode<KB, RB>) -> Result<()> {
self.write_raw_offset(vec, index, node.0) self.write_raw_offset(vec, index, node.0)
} }
/// Rewrite an index entry to point to a `KeyId`. /// Rewrite an index entry to point to a `KeyId`.
#[inline] #[inline]
pub fn write_key_id(&self, vec: &mut RB, index: u8, key_id: KeyId) -> Result<()> { pub fn write_key_id(&self, vec: &mut RB, index: u8, key_id: KeyId) -> Result<()> {
self.write_raw_offset(vec, index, key_id.to_encoded_offset()?) self.write_raw_offset(vec, index, key_id.to_encoded_offset()?)
} }
vec[pos] = v.to_le(); vec[pos] = v.to_le();
Ok(()) Ok(())
} }
} }
/// `RadixBuffer` provides efficient `Key` to `KeyId` lookups. It maintains two buffers: /// `RadixBuffer` provides efficient `Key` to `KeyId` lookups. It maintains two buffers:
/// - A key buffer for `Key` lookups. Caller is responsible for appending new keys there. /// - A key buffer for `Key` lookups. Caller is responsible for appending new keys there.
/// - A radix buffer for storing radix tree offsets. /// - A radix buffer for storing radix tree offsets.
pub struct RadixBuffer(Shared<KB>, Shared<RB>, Offset); pub struct RadixBuffer<KB, RB>(Shared<KB>, Shared<RB>, Offset);
impl RadixBuffer { impl<KB, RB> RadixBuffer<KB, RB>
where
KB: VecLike<u8>,
RB: VecLike<u32>,
{
pub fn new(key_buf: Shared<KB>, radix_buf: Shared<RB>, root: Offset) -> Self { pub fn new(key_buf: Shared<KB>, radix_buf: Shared<RB>, root: Offset) -> Self {
RadixBuffer(key_buf, radix_buf, root) RadixBuffer(key_buf, radix_buf, root)
} }
/// Lookup a `Key` /// Lookup a `Key`
pub fn lookup(&self, key: &Key) -> Result<Option<KeyId>> { pub fn lookup(&self, key: &Key) -> Result<Option<KeyId>> {
let result = self.lookup_unchecked(key); let result = self.lookup_unchecked(key);
if let Ok(Some(key_id)) = result { if let Ok(Some(key_id)) = result {
// Double check if key_id matches // Double check if key_id matches
let key_to_check = self.read_key(key_id)?; let key_to_check = self.read_key(key_id)?;
if key_to_check != *key { if key_to_check != *key {
return Ok(None); return Ok(None);
} }
} }
result result
} }
/// Find `KeyId` from a `Key`. Do not check if `KeyId` and `Key` matches. /// Find `KeyId` from a `Key`. Do not check if `KeyId` and `Key` matches.
pub fn lookup_unchecked(&self, key: &Key) -> Result<Option<KeyId>> { pub fn lookup_unchecked(&self, key: &Key) -> Result<Option<KeyId>> {
borrow_shared(&self.1, |rbuf| { borrow_shared(&self.1, |rbuf| {
let mut radix = RadixNode::new(self.2); let mut radix = RadixNode::<KB, RB>::new(self.2);
for b in key.to_base16iter() { for b in key.to_base16iter() {
match radix.follow(rbuf, b)? { match radix.follow(rbuf, b)? {
FollowResult::Radix(next_radix) => { FollowResult::Radix(next_radix) => {
radix = next_radix; radix = next_radix;
} }
FollowResult::Missing => { FollowResult::Missing => {
return Ok(None); return Ok(None);
} }
FollowResult::KeyId(id) => return Ok(Some(id)), FollowResult::KeyId(id) => return Ok(Some(id)),
} }
} }
Err(ErrorKind::KeyConflict.into()) Err(ErrorKind::KeyConflict.into())
}) })
} }
pub fn lookup_prefix(&self, base16seq: &[u8]) -> Result<Option<KeyId>> { pub fn lookup_prefix(&self, base16seq: &[u8]) -> Result<Option<KeyId>> {
borrow_shared(&self.1, |rbuf| { borrow_shared(&self.1, |rbuf| {
let mut radix = RadixNode::new(self.2); let mut radix = RadixNode::<KB, RB>::new(self.2);
for &b in base16seq { for &b in base16seq {
debug_assert!(b < 16); debug_assert!(b < 16);
match radix.follow(rbuf, b)? { match radix.follow(rbuf, b)? {
FollowResult::Radix(next_radix) => { FollowResult::Radix(next_radix) => {
radix = next_radix; radix = next_radix;
} }
FollowResult::Missing => { FollowResult::Missing => {
return Ok(None); return Ok(None);
pub fn insert(&self, new_key_id: KeyId) -> Result<()> { pub fn insert(&self, new_key_id: KeyId) -> Result<()> {
let new_key = self.read_key(new_key_id)?; let new_key = self.read_key(new_key_id)?;
self.insert_with_key(new_key_id, &new_key) self.insert_with_key(new_key_id, &new_key)
} }
/// Insert when both `KeyId` and `Key` are known /// Insert when both `KeyId` and `Key` are known
pub fn insert_with_key(&self, new_key_id: KeyId, new_key: &Key) -> Result<()> { pub fn insert_with_key(&self, new_key_id: KeyId, new_key: &Key) -> Result<()> {
borrow_shared(&self.1, |rbuf| { borrow_shared(&self.1, |rbuf| {
let mut radix = RadixNode::new(self.2); let mut radix = RadixNode::<KB, RB>::new(self.2);
for (i, b) in new_key.to_base16iter().enumerate() { for (i, b) in new_key.to_base16iter().enumerate() {
match radix.follow(rbuf, b)? { match radix.follow(rbuf, b)? {
FollowResult::Radix(next_radix) => { FollowResult::Radix(next_radix) => {
radix = next_radix; radix = next_radix;
} }
FollowResult::Missing => { FollowResult::Missing => {
return radix.write_key_id(rbuf, b, new_key_id); return radix.write_key_id(rbuf, b, new_key_id);
} }
pub fn borrow_shared<B, F, R>(shared: &Shared<B>, func: F) -> Result<R> pub fn borrow_shared<B, F, R>(shared: &Shared<B>, func: F) -> Result<R>
where where
F: FnOnce(&mut B) -> Result<R>, F: FnOnce(&mut B) -> Result<R>,
{ {
let mut borrowed = shared.try_borrow_mut()?; let mut borrowed = shared.try_borrow_mut()?;
func(borrowed.deref_mut()) func(borrowed.deref_mut())
} }
/// Vec-like interface
pub trait VecLike<T>
: IndexMut<usize>
+ Index<usize, Output = T>
+ IndexMut<Range<usize>>
+ Index<Range<usize>, Output = [T]> {
fn extend_from_slice(&mut self, other: &[T]);
fn resize(&mut self, new_len: usize, value: T);
fn len(&self) -> usize;
}
macro_rules! impl_vec_like {
($T: ident) => {
impl<T: Copy> VecLike<T> for $T<T> {
#[inline]
fn extend_from_slice(&mut self, other: &[T]) { $T::extend_from_slice(self, other) }
#[inline]
fn resize(&mut self, new_len: usize, value: T) { $T::resize(self, new_len, value) }
#[inline]
fn len(&self) -> usize { $T::len(self) }
}
}
}
impl_vec_like!(Vec);
impl_vec_like!(MmapVec);
#[cfg(test)] #[cfg(test)]
mod tests { mod tests {
use super::*; use super::*;
use std::collections::HashSet; use std::collections::HashSet;
use std::ops::Deref; use std::ops::Deref;
use std::rc::Rc; use std::rc::Rc;
use std::cell::RefCell; use std::cell::RefCell;
use rand::{ChaChaRng, Rng}; use rand::{ChaChaRng, thread_rng, Rng};
use test::Bencher; use test::Bencher;
use quickcheck::{Arbitrary, Gen}; use quickcheck::{Arbitrary, Gen};
use tempdir::TempDir;
type KB = Vec<u8>; type KB = Vec<u8>;
type RB = Vec<u32>; type RB = Vec<u32>;
fn prepare_kbuf_radix() -> (Shared<KB>, Shared<RB>, RadixBuffer) { fn prepare_kbuf_radix() -> (Shared<KB>, Shared<RB>, RadixBuffer<KB, RB>) {
let kbuf = Rc::new(RefCell::new(vec![])); let kbuf = Rc::new(RefCell::new(vec![]));
let rbuf = Rc::new(RefCell::new(vec![0u32; 17])); let rbuf = Rc::new(RefCell::new(vec![0u32; 17]));
let radix = RadixBuffer::new(Rc::clone(&kbuf), Rc::clone(&rbuf), 1.into()); let radix = RadixBuffer::new(Rc::clone(&kbuf), Rc::clone(&rbuf), 1.into());
(kbuf, rbuf, radix) (kbuf, rbuf, radix)
} }
fn append_key(kbuf: &Shared<KB>, key: &Key) -> KeyId { type MKB = MmapVec<u8>;
type MRB = MmapVec<u32>;
fn prepare_mmap_kbuf_radix(tempdir: TempDir)
-> (Shared<MKB>, Shared<MRB>, RadixBuffer<MKB, MRB>) {
let kbuf = Rc::new(RefCell::new(
MKB::from_path(tempdir.path().join("kbuf")).unwrap(),
));
let mut rvec = MRB::from_path(tempdir.path().join("rbuf")).unwrap();
rvec.extend_from_slice(&[0u32; 17]);
let rbuf = Rc::new(RefCell::new(rvec));
let radix = RadixBuffer::new(Rc::clone(&kbuf), Rc::clone(&rbuf), 1.into());
(kbuf, rbuf, radix)
}
fn append_key<T: VecLike<u8>>(kbuf: &Shared<T>, key: &Key) -> KeyId {
borrow_shared(&kbuf, |kvec| { borrow_shared(&kbuf, |kvec| {
let pos = kvec.len(); let pos = kvec.len();
kvec.extend_from_slice(key.deref()); kvec.extend_from_slice(key.deref());
Ok(KeyId::from(pos as u32)) Ok(KeyId::from(pos as u32))
}).unwrap() }).unwrap()
} }
fn check_duplicated_key_ids(key: Key) -> bool { fn check_duplicated_key_ids(key: Key) -> bool {
let (kbuf, _rbuf, radix) = prepare_kbuf_radix(); let (kbuf, _rbuf, radix) = prepare_kbuf_radix();
let key_id1 = append_key(&kbuf, &key); let key_id1 = append_key(&kbuf, &key);
let key_id2 = append_key(&kbuf, &key); let key_id2 = append_key(&kbuf, &key);
radix.insert(key_id1).expect("insert"); radix.insert(key_id1).expect("insert");
radix.insert(key_id2).unwrap_err().description() == "same key with different IDs" radix.insert(key_id2).unwrap_err().description() == "same key with different IDs"
} }
fn check_with_stdset(std_set: HashSet<Key>) -> bool { fn check_with_stdset(std_set: HashSet<Key>) -> bool {
let (kbuf, _rbuf, radix) = prepare_kbuf_radix(); let (kbuf, rbuf, radix) = prepare_kbuf_radix();
let tempdir = TempDir::new("mradix").unwrap();
let (mkbuf, mrbuf, mradix) = prepare_mmap_kbuf_radix(tempdir);
for &key in &std_set { for &key in &std_set {
if radix.lookup(&key).unwrap().is_some() { if radix.lookup(&key).unwrap().is_some() {
return false; return false;
} }
if mradix.lookup(&key).unwrap().is_some() {
return false;
}
let key_id = append_key(&kbuf, &key); let key_id = append_key(&kbuf, &key);
radix.insert(key_id).expect("insert"); radix.insert(key_id).expect("insert");
radix.insert_with_key(key_id, &key).expect("insert"); radix.insert_with_key(key_id, &key).expect("insert");
let key_id = append_key(&mkbuf, &key);
mradix.insert(key_id).expect("insert");
mradix.insert_with_key(key_id, &key).expect("insert");
} }
for &orig in &std_set { for &orig in &std_set {
for bit in 0..161 { for bit in 0..161 {
let mut key = orig; let mut key = orig;
if bit > 0 { if bit > 0 {
let mut buf: [u8; 20] = *orig; let mut buf: [u8; 20] = *orig;
buf[(bit - 1) / 8] ^= 1u8 << ((bit - 1) % 8); buf[(bit - 1) / 8] ^= 1u8 << ((bit - 1) % 8);
key = buf.into(); key = buf.into();
} }
if std_set.contains(&key) ^ radix.lookup(&key).unwrap().is_some() { let expected = std_set.contains(&key);
if expected != radix.lookup(&key).unwrap().is_some() ||
expected != mradix.lookup(&key).unwrap().is_some()
{
return false; return false;
} }
} }
} }
assert_eq!(mkbuf.borrow()[..], kbuf.borrow()[..]);
assert_eq!(mrbuf.borrow()[..], rbuf.borrow()[..]);
true true
} }
#[test] #[test]
fn test_errors() { fn test_errors() {
let (_kbuf, _rbuf, radix) = prepare_kbuf_radix(); let (_kbuf, _rbuf, radix) = prepare_kbuf_radix();
let key = Key::default(); let key = Key::default();
let r = radix.insert_with_key((1 << 31).into(), &key); let r = radix.insert_with_key((1 << 31).into(), &key);
let radix = RadixBuffer::new(Rc::clone(&kbuf), Rc::clone(&rbuf), 0.into()); let radix = RadixBuffer::new(Rc::clone(&kbuf), Rc::clone(&rbuf), 0.into());
for key_id in 0..COUNT { for key_id in 0..COUNT {
let v = key_id * Key::fixed_len() as u32; let v = key_id * Key::fixed_len() as u32;
radix.insert(v.into()).expect("insert"); radix.insert(v.into()).expect("insert");
} }
}) })
} }
fn prepare_radix_keys(count: usize) -> (RadixBuffer, Vec<Key>) { #[bench]
fn bench_50k_insert_mmap(b: &mut Bencher) {
let tempdir = TempDir::new("mradix").unwrap();
const COUNT: u32 = 51200;
let key_buf: Vec<u8> = ChaChaRng::new_unseeded()
.gen_iter()
.take(COUNT as usize * Key::fixed_len())
.collect();
let mut kvec = MKB::from_path(tempdir.path().join("kbuf")).unwrap();
kvec.extend_from_slice(&key_buf);
let kbuf = Rc::new(RefCell::new(kvec));
b.iter(|| {
let mut rvec = MRB::from_path(tempdir.path().join(
format!("rbuf-{}", thread_rng().next_u64()),
)).unwrap();
rvec.extend_from_slice(&[0u32; 17]);
let rbuf = Rc::new(RefCell::new(rvec));
let radix = RadixBuffer::new(Rc::clone(&kbuf), Rc::clone(&rbuf), 1.into());
for key_id in 0..COUNT {
let v = key_id * Key::fixed_len() as u32;
radix.insert(v.into()).expect("insert");
}
})
}
fn prepare_radix_keys(count: usize) -> (RadixBuffer<KB, RB>, Vec<Key>) {
let mut rng = ChaChaRng::new_unseeded(); let mut rng = ChaChaRng::new_unseeded();
let (kbuf, _rbuf, radix) = prepare_kbuf_radix(); let (kbuf, _rbuf, radix) = prepare_kbuf_radix();
let mut keys = vec![]; let mut keys = vec![];
for _ in 0..count { for _ in 0..count {
let key = rng.gen(); let key = rng.gen();
let key_id = append_key(&kbuf, &key); let key_id = append_key(&kbuf, &key);
radix.insert_with_key(key_id, &key).expect("insert"); radix.insert_with_key(key_id, &key).expect("insert");
keys.push(key); keys.push(key);