This is an archive of the discontinued Mercurial Phabricator instance.

Differential D1203

radixbuf: implement basic serialization logic
AbandonedPublic

Authored by quark on Oct 20 2017, 8:01 PM.
Tags
None
Subscribers
durin42

Details

Reviewers
None
Group Reviewers
Restricted Project
Summary

This is the first step of a revised radix index implementation in Rust that
was previously implemented in Python and C [1]. The importance of the data
structure is mentioned in the original commit message [1]. And the
performance win is significant when used properly [2].

Choosing Rust for its high level abstractions, type safety, and
compelling-to-C performance.

The radixbuf uses a flat, continuous buffer as the source of truth of the
index. Therefore it needs serialization support. This patch adds basic
serialization interface and implements serialization for common unsigned
integers.

[1]: https://www.mercurial-scm.org/pipermail/mercurial-devel/2017-June/099184.html
[2]: https://www.mercurial-scm.org/pipermail/mercurial-devel/2017-June/099197.html

Test Plan

cargo test

Diff Detail

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

Event Timeline

quark created this revision.Oct 20 2017, 8:01 PM
Herald added a reviewer: Restricted Project. · View Herald TranscriptOct 20 2017, 8:01 PM
quark edited the test plan for this revision. (Show Details)Oct 20 2017, 8:02 PM
quark added a subscriber: durin42.Oct 20 2017, 8:02 PM
quark planned changes to this revision.Oct 21 2017, 4:26 PM

Value types also need part of the serialization interface.

quark edited the summary of this revision. (Show Details)Oct 23 2017, 4:12 PM
quark retitled this revision from keyid: implement a submodule that does Key <-> Id conversion to radixbuf: implement basic serialization logic.
quark added a child revision: D1218: radixbuf: add serialization support for keys (byte arrays).
quark updated this revision to Diff 3067.
quark planned changes to this revision.Oct 24 2017, 3:08 PM

Some types are not used. Could be further simplified.

quark abandoned this revision.Nov 2 2017, 2:48 PM

D1292 does not need serialize

Revision Contents
Changeset List

Diff 3067

rust/radixbuf/Cargo.toml

  • This file was added.
[package]
name = "radixbuf"
version = "0.1.0"
[dependencies]
vlqencoding = { path = "../vlqencoding" }
[dev-dependencies]
quickcheck = "0.4"

rust/radixbuf/README.md

  • This file was added.
# radixbuf
This is a typical [Radix Tree](https://en.wikipedia.org/wiki/Radix_tree) implementation focused on efficient on-disk access.
Namely, it has the following properties:
- Looking up a key is not O(length of the file).
- Making changes to the tree is not O(length of the file).
This is still a work-in-progress.

rust/radixbuf/src/lib.rs

  • This file was added.
#[cfg(test)]
#[macro_use]
extern crate quickcheck;
extern crate vlqencoding;
mod serialize;

rust/radixbuf/src/serialize.rs

  • This file was added.
//! Simple serialization that converts between T and an offset
use std::cell::RefCell;
use std::io::{self, Read, Write, Seek, SeekFrom, ErrorKind};
use std::marker::PhantomData;
use std::mem::transmute;
use std::ops::DerefMut;
use std::rc::Rc;
/// Minimal serializable abstraction.
pub trait Serialize: Sized {
fn write_to<W: Write>(&self, w: &mut W) -> io::Result<()>;
fn read_from<R: Read>(r: &mut R) -> io::Result<Self>;
}
/// Indicates a type will be serialized into fixed number of bytes.
/// This decides whether the type could support rewrite-in-place or not.
pub trait FixedSizedSerialize: Serialize {}
/// Optimized for compact storage.
#[derive(Debug, Eq, PartialEq, Copy, Clone)]
pub struct Offset<T>(u64, PhantomData<T>);
impl<T> Offset<T> {
pub unsafe fn from_raw(offset: u64) -> Self { Offset::<T>(offset, PhantomData) }
}
impl<T> Serialize for Offset<T> {
fn write_to<W: Write>(&self, w: &mut W) -> io::Result<()> { self.0.write_to(w) }
fn read_from<R: Read>(r: &mut R) -> io::Result<Self> {
Ok(unsafe { Offset::from_raw(u64::read_from(r)?) })
}
}
/// Buffer that supports read and write serializable objects.
pub struct Buffer<B>(Rc<RefCell<B>>);
impl<B: Read + Write + Seek> Buffer<B> {
pub fn new(buf: &Rc<RefCell<B>>) -> Self { Buffer(buf.clone()) }
/// Append a Serialize. Returns its offset.
pub fn push<S: Serialize>(&mut self, data: &S) -> io::Result<Offset<S>> {
let mut cur = self.0.try_borrow_mut().or(
Err(ErrorKind::ConnectionRefused),
)?;
let pos = cur.seek(SeekFrom::End(0))?;
data.write_to(cur.deref_mut())?;
Ok(unsafe { Offset::<S>::from_raw(pos) })
}
/// In-place rewrite a FixedSizedSerialize.
pub fn rewrite<S: FixedSizedSerialize>(&mut self, pos: Offset<S>, data: &S) -> io::Result<()> {
let mut cur = self.0.try_borrow_mut().or(
Err(ErrorKind::ConnectionRefused),
)?;
cur.seek(SeekFrom::Start(pos.0 as u64))?;
data.write_to(cur.deref_mut())
}
/// Parse a Serialize from a given offset.
pub fn retrieve<S: Serialize>(&mut self, pos: Offset<S>) -> io::Result<S> {
let mut cur = self.0.try_borrow_mut().or(
Err(ErrorKind::ConnectionRefused),
)?;
cur.seek(SeekFrom::Start(pos.0 as u64))?;
S::read_from(cur.deref_mut())
}
}
macro_rules! impl_serialize_unsigned {
($T: ty, $S: expr) => {
impl Serialize for $T {
fn write_to<W: Write>(&self, w: &mut W) -> io::Result<()> {
let buf: [u8; $S] = unsafe { transmute(self.to_be()) };
w.write_all(&buf)
}
fn read_from<R: Read>(r: &mut R) -> io::Result<Self> {
let mut buf = [0u8; $S];
r.read_exact(&mut buf)?;
let value: $T = unsafe { transmute(buf) };
Ok(value.to_be())
}
}
impl FixedSizedSerialize for $T {}
}
}
impl_serialize_unsigned!(u8, 1);
impl_serialize_unsigned!(u16, 2);
impl_serialize_unsigned!(u32, 4);
impl_serialize_unsigned!(u64, 8);
#[cfg(test)]
mod tests {
use serialize::*;
use std::boxed::Box;
use std::cell::RefCell;
use std::fmt::Debug;
use std::io::Cursor;
use std::rc::Rc;
fn check_round_trip<T: Serialize + Clone + PartialEq + Debug>(keys: Vec<T>) -> bool {
let mut buf = Buffer(Rc::new(RefCell::new(Cursor::new(vec![]))));
let mut offsets: Vec<Offset<T>> = vec![];
// Push keys
for k in keys.iter() {
offsets.push(buf.push(k).unwrap());
}
// Check keys
offsets.iter().enumerate().all(|(i, offset)| {
(buf.retrieve::<T>(offset.clone())).unwrap() == keys[i]
})
}
quickcheck! {
fn test_round_trip_u8(v: Vec<u8>) -> bool {
check_round_trip(v)
}
fn test_round_trip_u16(v: Vec<u16>) -> bool {
check_round_trip(v)
}
fn test_round_trip_u32(v: Vec<u32>) -> bool {
check_round_trip(v)
}
fn test_round_trip_u64(v: Vec<u64>) -> bool {
check_round_trip(v)
}
}
#[test]
fn test_rewrite() {
let mut buf = Buffer(Rc::new(RefCell::new(Cursor::new(vec![]))));
let offsets: Vec<Offset<u32>> = (200..203u32).map(|i| buf.push(&i).unwrap()).collect();
buf.rewrite(offsets[1], &400u32).expect("rewrite");
assert_eq!(buf.retrieve::<u32>(offsets[0]).unwrap(), 200);
assert_eq!(buf.retrieve::<u32>(offsets[1]).unwrap(), 400);
assert_eq!(buf.retrieve::<u32>(offsets[2]).unwrap(), 202);
}
}