( )⚙ D1396 treedirstate: add vecmap implementation

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D1396

treedirstate: add vecmap implementation
ClosedPublic

Authored by mbthomas on Nov 14 2017, 12:39 PM.
Tags
None
Subscribers
jsgf, durham

Details

Reviewers
jsgf
stash
durham
Group Reviewers
Restricted Project
Commits
rFBHGX3d6ea6138e86: treedirstate: add vecmap implementation
Summary

This adds an implementation of an ordered map that uses a vector pairs, sorted
by the key.

This is largely compatibly with std::collections::BTreeMap, but has performance
characteristics more suited for use in treedirstate.

Diff Detail

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

Event Timeline

mbthomas created this revision.Nov 14 2017, 12:39 PM
Herald added a reviewer: Restricted Project. · View Herald TranscriptNov 14 2017, 12:39 PM
durham added a subscriber: durham.Nov 15 2017, 12:24 PM

Mostly noob questions

rust/treedirstate/src/vecmap.rs
71

Maybe a rust-noob question, but why is '?Sized' needed here?

120

Is this a standard function? If not, maybe a doc comment explaining what 'start' means. Took me a couple reads of the code to realize.

126

Could we have returned if start { 0 } else { self.vec.len() } for this instead? Seems like that would hide the special case from the caller. Or do you intentionally return None because it allows us to detect the special case and do Iter(self.vec.iter()) without slicing later?

127

Since self.vec.binary_search_by(|e| e.0.borrow().cmp(q)) is a common pattern (I see it at least 3 times above), should there be a function to do that for us? I think it'd clean up the one dense line in each of these functions.

184

rust-noob question: What is self.0 here? I thought self was an Iter instance, and I thought self.0 was something used on a tuple instance. So I'm a little confused.

Also, I thought .next() would return the next value. But I thought .map() would only operate on some sort of generator or collection?

mbthomas added inline comments.Nov 15 2017, 12:55 PM
rust/treedirstate/src/vecmap.rs
71

Q is allowed to be a reference to a generic type for which the size is not known (e.g. a trait type). The important thing is that it's a thing that can be compared with a borrowed Key. This allows storing String or Vec[u8] keys, but then accessing/removing the entries using a &str or &[u8] borrowed value from elsewhere.

Rust defaults to assuming Sized for type parameters, so you have to remove it when you don't need it.

120

No, this is a private function to make implementing range and range_mut simpler.

126

That would probably make sense and make the other function simpler. I'll rework it.

127

I'm not sure how easy it will be to extract (there's a lot of type inferencing going on here), but I'll give it a shot.

184

vecmap::Iter is a wrapper around std::slice::Iter (see line 15) that convert its API to one that works in a map-like way. The difference is subtle:

std::slice::Iter for a Vec<Item> yields Option<&Item>, which is Option<&(K, V)> for this module. To be able to iterate over the key/value pairs, we need to convert this to Option<(&K, &V)>. This is more important for IterMut where we want to map Option<&mut (K, V)> to Option<(&K, &mut V)> to prevent the caller mutating the key.

To answer the first question, vecmap::Iter is a 1-tuple containing a std::slice::Iter, so we access the inner iter through self.0. I think this is a common Rust pattern.

For the second question, .next() returns Option<&(K, V)>, which we want to map to Option<(&K, &V)>. The map call here is over the Option type.

mbthomas updated this revision to Diff 3566.Nov 16 2017, 11:42 AM
mbthomas marked 10 inline comments as done.Nov 16 2017, 11:43 AM
mbthomas updated this revision to Diff 3593.Nov 17 2017, 9:44 AM
jsgf requested changes to this revision.Nov 17 2017, 12:30 PM
jsgf added a subscriber: jsgf.

Nits mostly.

rust/treedirstate/src/vecmap.rs
52–53

"that value is >replaced and< returned" for maximum clarity.

54

I prefer to avoid putting mut v: V into signatures, because its a little confusing for readers - it's not obvious that mut has local effect and doesn't affect the function's interface.

Instead:

pub fn insert(&mut self, k: K, v: V) -> Option<V> {
    let mut v = v;
67–69

Is this common enough to just always do as part of insert()?

133–135

How does this look if you just split it into separate range_index_start/range_index_end rather than toggling on start? It would still have some amount of duplication of the overall function and the calls to find_index, but it might be clearer in the end.

Or alternatively take an instance of RangeArgument and handle both at once, returning (usize, usize).

166

RangeArgument? It's already implemented for (Bound<T>, Bound<T>), but also allows using ../..= notation.

198

I prefer:

fn next(&mut self) -> Option<Self::Item> {

to be very explicit.

199

Pattern matching might be a little clearer: .map(|&(ref k, ref v)| (k, v))

207

likewise

208

ditto pattern match

This revision now requires changes to proceed.Nov 17 2017, 12:30 PM
mbthomas added inline comments.Nov 20 2017, 12:19 PM
rust/treedirstate/src/vecmap.rs
166

RangeArgument is nightly-only experimental still. I'm trying to keep to stable rust features.

mbthomas updated this revision to Diff 3648.Nov 20 2017, 12:20 PM
mbthomas marked 9 inline comments as done.Nov 20 2017, 12:22 PM
mbthomas added inline comments.
rust/treedirstate/src/vecmap.rs
67–69

Possibly. I'll see if I can think of a way to measure it.

stash accepted this revision.Nov 21 2017, 5:12 AM
jsgf accepted this revision.Nov 22 2017, 5:47 PM
This revision is now accepted and ready to land.Nov 22 2017, 5:47 PM
mbthomas updated this revision to Diff 3818.Nov 24 2017, 11:52 AM
durham accepted this revision.Nov 27 2017, 12:23 PM
Closed by commit rFBHGX3d6ea6138e86: treedirstate: add vecmap implementation (authored by mbthomas). · Explain WhyNov 28 2017, 6:00 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 3593

rust/treedirstate/Cargo.toml

[package] [package]
name = "rusttreedirstate" name = "rusttreedirstate"
version = "0.1.0" version = "0.1.0"
authors = ["Facebook Source Control Team <sourcecontrol-dev@fb.com>"] authors = ["Facebook Source Control Team <sourcecontrol-dev@fb.com>"]
[profile.release] [profile.release]
lto = true lto = true
[lib] [lib]
name = "rusttreedirstate" name = "rusttreedirstate"
crate-type = ["cdylib"] crate-type = ["cdylib"]
[dev-dependencies]
itertools = "0.7.2"
quickcheck = "*"

rust/treedirstate/src/lib.rs

// Copyright Facebook, Inc. 2017 // Copyright Facebook, Inc. 2017
//! treedirstate - Tree-based Directory State. //! treedirstate - Tree-based Directory State.
//! //!
//! This is a Rust implementation of the dirstate concept for Mercurial, using a tree structure //! This is a Rust implementation of the dirstate concept for Mercurial, using a tree structure
//! in an append-only storage back-end. //! in an append-only storage back-end.
//! //!
//! The directory state stores information for all files in a working copy that are of interest //! The directory state stores information for all files in a working copy that are of interest
//! to Mercurial. In particular, for each file in the working copy it stores the mode flags, //! to Mercurial. In particular, for each file in the working copy it stores the mode flags,
//! size, and modification time of the file. These can be compared with current values to //! size, and modification time of the file. These can be compared with current values to
//! determine if the file has changed. //! determine if the file has changed.
//! //!
//! The directory state also stores files that are in the working copy parent manifest but have //! The directory state also stores files that are in the working copy parent manifest but have
//! been marked as removed. //! been marked as removed.
#[cfg(test)]
extern crate itertools;
#[cfg(test)]
#[macro_use]
extern crate quickcheck;
pub mod vecmap;

rust/treedirstate/src/vecmap.rs

  • This file was added.
// Copyright Facebook, Inc. 2017
//! Ordered map implementation using a sorted vector
use std::mem;
use std::borrow::Borrow;
use std::slice::{Iter as VecIter, IterMut as VecIterMut};
use std::collections::Bound;
use std::collections::Bound::*;
#[derive(Debug)]
pub struct VecMap<K, V> {
vec: Vec<(K, V)>,
}
pub struct Iter<'a, K: 'a, V: 'a>(VecIter<'a, (K, V)>);
pub struct IterMut<'a, K: 'a, V: 'a>(VecIterMut<'a, (K, V)>);
impl<K, V> VecMap<K, V>
where
K: Ord,
{
/// Creates a new, empty VecMap.
pub fn new() -> VecMap<K, V> {
VecMap { vec: Vec::new() }
}
/// Creates a new, empty VecMap, with capacity for `capacity` entries.
pub fn with_capacity(capacity: usize) -> VecMap<K, V> {
VecMap {
vec: Vec::with_capacity(capacity),
}
}
pub fn is_empty(&self) -> bool {
self.vec.is_empty()
}
pub fn len(&self) -> usize {
self.vec.len()
}
/// Utility function to binary search for an index using the key.
fn find_index<Q: ?Sized>(&self, q: &Q) -> Result<usize, usize>
where
K: Borrow<Q>,
Q: Ord,
{
self.vec.binary_search_by(|e| e.0.borrow().cmp(q))
}
/// Inserts a key-value pair into the map. If the key already had a value present in the
/// map, that value is returned. Otherwise, `None` is returned.
jsgfUnsubmitted
Done

"that value is >replaced and< returned" for maximum clarity.

jsgf: "that value is >replaced and< returned" for maximum clarity.
pub fn insert(&mut self, k: K, mut v: V) -> Option<V> {
jsgfUnsubmitted
Done

I prefer to avoid putting mut v: V into signatures, because its a little confusing for readers - it's not obvious that mut has local effect and doesn't affect the function's interface.

Instead:

pub fn insert(&mut self, k: K, v: V) -> Option<V> {
    let mut v = v;
jsgf: I prefer to avoid putting `mut v: V` into signatures, because its a little confusing for…
match self.find_index(&k) {
Ok(index) => {
mem::swap(&mut self.vec[index].1, &mut v);
Some(v)
}
Err(index) => {
self.vec.insert(index, (k, v));
None
}
}
}
/// Inserts a key-value pair into the map. Fast-path for when the key is not already
/// present and is at the end of the map.
pub fn insert_hint_end(&mut self, k: K, v: V) -> Option<V> {
jsgfUnsubmitted
Not Done

Is this common enough to just always do as part of insert()?

jsgf: Is this common enough to just always do as part of `insert()`?
mbthomasAuthorUnsubmitted
Not Done

Possibly. I'll see if I can think of a way to measure it.

mbthomas: Possibly. I'll see if I can think of a way to measure it.
let len = self.vec.len();
if len == 0 || self.vec[len - 1].0 < k {
durhamUnsubmitted
Done

Maybe a rust-noob question, but why is '?Sized' needed here?

durham: Maybe a rust-noob question, but why is '?Sized' needed here?
mbthomasAuthorUnsubmitted
Done

Q is allowed to be a reference to a generic type for which the size is not known (e.g. a trait type). The important thing is that it's a thing that can be compared with a borrowed Key. This allows storing String or Vec[u8] keys, but then accessing/removing the entries using a &str or &[u8] borrowed value from elsewhere.

Rust defaults to assuming Sized for type parameters, so you have to remove it when you don't need it.

mbthomas: `Q` is allowed to be a reference to a generic type for which the size is not known (e.g. a…
self.vec.push((k, v));
None
} else {
self.insert(k, v)
}
}
/// Removes a key-value pair from the map, returning the value if the key was previously in
/// the map.
pub fn remove<Q: ?Sized>(&mut self, q: &Q) -> Option<V>
where
K: Borrow<Q>,
Q: Ord,
{
match self.find_index(q) {
Ok(index) => {
let (_k, v) = self.vec.remove(index);
Some(v)
}
Err(_index) => None,
}
}
/// Returns a reference to the value corresponding to the key.
pub fn get<'a, Q: ?Sized>(&'a self, q: &Q) -> Option<&'a V>
where
K: Borrow<Q>,
Q: Ord,
{
match self.find_index(q) {
Ok(index) => Some(&self.vec[index].1),
Err(_index) => None,
}
}
/// Returns a mutable reference to the value corresponding to the key.
pub fn get_mut<'a, Q: ?Sized>(&'a mut self, q: &Q) -> Option<&'a mut V>
where
K: Borrow<Q>,
Q: Ord,
{
match self.find_index(q) {
Ok(index) => Some(&mut self.vec[index].1),
Err(_index) => None,
}
}
// Returns an iterator over the pairs of entries in the map.
pub fn iter(&self) -> Iter<K, V> {
durhamUnsubmitted
Done

Is this a standard function? If not, maybe a doc comment explaining what 'start' means. Took me a couple reads of the code to realize.

durham: Is this a standard function? If not, maybe a doc comment explaining what 'start' means. Took me…
mbthomasAuthorUnsubmitted
Done

No, this is a private function to make implementing range and range_mut simpler.

mbthomas: No, this is a private function to make implementing `range` and `range_mut` simpler.
Iter(self.vec.iter())
}
/// Returns a mutable iterator over the pairs of entries in the map.
pub fn iter_mut(&mut self) -> IterMut<K, V> {
IterMut(self.vec.iter_mut())
durhamUnsubmitted
Done

Could we have returned if start { 0 } else { self.vec.len() } for this instead? Seems like that would hide the special case from the caller. Or do you intentionally return None because it allows us to detect the special case and do Iter(self.vec.iter()) without slicing later?

durham: Could we have returned `if start { 0 } else { self.vec.len() }` for this instead? Seems like…
mbthomasAuthorUnsubmitted
Done

That would probably make sense and make the other function simpler. I'll rework it.

mbthomas: That would probably make sense and make the other function simpler. I'll rework it.
}
durhamUnsubmitted
Done

Since self.vec.binary_search_by(|e| e.0.borrow().cmp(q)) is a common pattern (I see it at least 3 times above), should there be a function to do that for us? I think it'd clean up the one dense line in each of these functions.

durham: Since `self.vec.binary_search_by(|e| e.0.borrow().cmp(q))` is a common pattern (I see it at…
mbthomasAuthorUnsubmitted
Done

I'm not sure how easy it will be to extract (there's a lot of type inferencing going on here), but I'll give it a shot.

mbthomas: I'm not sure how easy it will be to extract (there's a lot of type inferencing going on here)…
/// Utility function for implementing `range` and `range_mut`. Convert a range boundary to a
/// slice index suitable for use in a range expression.
///
/// * `b` - The boundary to convert.
/// * `start` - Whether this boundary is the start of the range or not.
///
fn range_index<Q: ?Sized>(&self, b: Bound<&Q>, start: bool) -> usize
jsgfUnsubmitted
Done

How does this look if you just split it into separate range_index_start/range_index_end rather than toggling on start? It would still have some amount of duplication of the overall function and the calls to find_index, but it might be clearer in the end.

Or alternatively take an instance of RangeArgument and handle both at once, returning (usize, usize).

jsgf: How does this look if you just split it into separate `range_index_start`/`range_index_end`…
where
K: Borrow<Q>,
Q: Ord,
{
match b {
Unbounded => if start {
0
} else {
self.vec.len()
},
Included(q) => match self.find_index(q) {
Ok(index) => if start {
index
} else {
index + 1
},
Err(index) => index,
},
Excluded(q) => match self.find_index(q) {
Ok(index) => if start {
index + 1
} else {
index
},
Err(index) => index,
},
}
}
/// Returns an iterator over the given range of keys.
pub fn range<Q>(&self, range: (Bound<&Q>, Bound<&Q>)) -> Iter<K, V>
jsgfUnsubmitted
Done

RangeArgument? It's already implemented for (Bound<T>, Bound<T>), but also allows using ../..= notation.

jsgf: `RangeArgument`? It's already implemented for `(Bound<T>, Bound<T>)`, but also allows using `..
mbthomasAuthorUnsubmitted
Done

RangeArgument is nightly-only experimental still. I'm trying to keep to stable rust features.

mbthomas: `RangeArgument` is nightly-only experimental still. I'm trying to keep to stable rust features.
where
K: Borrow<Q>,
Q: Ord + ?Sized,
{
let start = self.range_index(range.0, true);
let end = self.range_index(range.1, false);
Iter(self.vec[start..end].iter())
}
/// Returns a mutuable iterator over the given range of keys.
pub fn range_mut<Q>(&mut self, range: (Bound<&Q>, Bound<&Q>)) -> IterMut<K, V>
where
K: Borrow<Q>,
Q: Ord + ?Sized,
{
let start = self.range_index(range.0, true);
let end = self.range_index(range.1, false);
IterMut(self.vec[start..end].iter_mut())
durhamUnsubmitted
Done

rust-noob question: What is self.0 here? I thought self was an Iter instance, and I thought self.0 was something used on a tuple instance. So I'm a little confused.

Also, I thought .next() would return the next value. But I thought .map() would only operate on some sort of generator or collection?

durham: rust-noob question: What is self.0 here? I thought self was an Iter instance, and I thought…
mbthomasAuthorUnsubmitted
Done

vecmap::Iter is a wrapper around std::slice::Iter (see line 15) that convert its API to one that works in a map-like way. The difference is subtle:

std::slice::Iter for a Vec<Item> yields Option<&Item>, which is Option<&(K, V)> for this module. To be able to iterate over the key/value pairs, we need to convert this to Option<(&K, &V)>. This is more important for IterMut where we want to map Option<&mut (K, V)> to Option<(&K, &mut V)> to prevent the caller mutating the key.

To answer the first question, vecmap::Iter is a 1-tuple containing a std::slice::Iter, so we access the inner iter through self.0. I think this is a common Rust pattern.

For the second question, .next() returns Option<&(K, V)>, which we want to map to Option<(&K, &V)>. The map call here is over the Option type.

mbthomas: `vecmap::Iter` is a wrapper around `std::slice::Iter` (see line 15) that convert its API to one…
}
}
// Wrap `Iter` and `IterMut` for `VecMap` types. These implementations adapt the `next` methods,
// converting their yielded types from `Option<&(K, V)>` to `Option<(&K, &V)>`, and from
// `Option<&mut (K, V)>` to `Option<(&K, &mut V)>`. This allows `VecMap` iterators to be used
// in the same way as other map iterators to iterate over key-value pairs, and prevents callers
// from using the mutable iterator to mutate keys.
impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
type Item = (&'a K, &'a V);
#[inline]
fn next(&mut self) -> Option<(&'a K, &'a V)> {
jsgfUnsubmitted
Done

I prefer:

fn next(&mut self) -> Option<Self::Item> {

to be very explicit.

jsgf: I prefer: ``` fn next(&mut self) -> Option<Self::Item> { ``` to be very explicit.
self.0.next().map(|next| (&next.0, &next.1))
jsgfUnsubmitted
Done

Pattern matching might be a little clearer: .map(|&(ref k, ref v)| (k, v))

jsgf: Pattern matching might be a little clearer: `.map(|&(ref k, ref v)| (k, v))`
}
}
impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> {
type Item = (&'a K, &'a mut V);
#[inline]
fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
jsgfUnsubmitted
Done

likewise

jsgf: likewise
self.0.next().map(|next| (&next.0, &mut next.1))
jsgfUnsubmitted
Done

ditto pattern match

jsgf: ditto pattern match
}
}
#[cfg(test)]
mod tests {
use vecmap::{Iter, VecMap};
use itertools;
use std::collections::Bound::*;
use std::collections::BTreeMap;
#[test]
fn insert_get_remove() {
let mut vm = VecMap::new();
assert_eq!(vm.insert("test1", "value1".to_string()), None);
assert_eq!(vm.insert("test2", "value2".to_string()), None);
assert_eq!(vm.insert_hint_end("test4", "value4".to_string()), None);
assert_eq!(vm.insert_hint_end("test3", "value3".to_string()), None);
assert_eq!(
vm.insert("test1", "value1b".to_string()),
Some("value1".to_string())
);
assert_eq!(vm.get(&"test1"), Some(&"value1b".to_string()));
if let Some(v) = vm.get_mut(&"test1") {
*v = "value1c".to_string();
}
assert_eq!(vm.get(&"test1"), Some(&"value1c".to_string()));
assert_eq!(vm.remove("test2"), Some("value2".to_string()));
assert_eq!(vm.remove("test2"), None);
assert_eq!(vm.get(&"test2"), None);
assert_eq!(vm.get_mut(&"never"), None);
}
#[test]
fn iter() {
let mut vm = VecMap::with_capacity(4);
assert!(vm.is_empty());
vm.insert(2, "value2");
vm.insert(1, "value1");
vm.insert(4, "value4");
vm.insert(3, "value3");
assert!(!vm.is_empty());
assert_eq!(vm.len(), 4);
{
let mut im = vm.iter_mut();
im.next();
let e2 = im.next().unwrap();
*e2.1 = "value2 - modified";
}
let mut i = vm.iter();
assert_eq!(i.next(), Some((&1, &"value1")));
assert_eq!(i.next(), Some((&2, &"value2 - modified")));
assert_eq!(i.next(), Some((&3, &"value3")));
assert_eq!(i.next(), Some((&4, &"value4")));
assert_eq!(i.next(), None);
}
#[test]
fn range() {
let mut vm: VecMap<i32, i32> = VecMap::new();
for n in 0..20 {
vm.insert(n * 2, n * 4);
}
fn check_iter(mut x: Iter<i32, i32>, start: i32, end: i32) {
let mut i = start;
while i < end {
assert_eq!(x.next(), Some((&i, &(i * 2))));
i += 2;
}
assert_eq!(x.next(), None);
}
check_iter(vm.range((Unbounded, Unbounded)), 0, 39);
check_iter(vm.range((Unbounded, Included(&2))), 0, 3);
check_iter(vm.range((Unbounded, Excluded(&2))), 0, 1);
check_iter(vm.range((Unbounded, Excluded(&7))), 0, 7);
check_iter(vm.range((Unbounded, Included(&13))), 0, 13);
check_iter(vm.range((Included(&4), Included(&13))), 4, 13);
check_iter(vm.range((Included(&5), Included(&14))), 6, 15);
check_iter(vm.range((Excluded(&5), Included(&20))), 6, 21);
check_iter(vm.range((Excluded(&6), Included(&60))), 8, 39);
check_iter(vm.range((Excluded(&-30), Unbounded)), 0, 39);
check_iter(vm.range((Included(&-1), Unbounded)), 0, 39);
assert_eq!(vm.get(&16), Some(&32));
{
let mut im = vm.range_mut((Included(&16), Excluded(&18)));
*im.next().unwrap().1 *= 2;
assert_eq!(im.next(), None);
}
assert_eq!(vm.get(&16), Some(&64));
}
fn vecmap_from_btreemap<K: Ord + Clone, V: Clone>(b: &BTreeMap<K, V>) -> VecMap<K, V> {
let mut vm = VecMap::new();
for (k, v) in b.iter() {
vm.insert(k.clone(), v.clone());
}
vm
}
quickcheck! {
fn like_btreemap_is_empty (b: BTreeMap<u32, u32>) -> bool {
let vm = vecmap_from_btreemap(&b);
vm.is_empty() == b.is_empty()
}
fn like_btreemap_len (b: BTreeMap<u32, u32>) -> bool {
let vm = vecmap_from_btreemap(&b);
vm.len() == b.len()
}
fn like_btreemap_iter (b: BTreeMap<u32, u32>) -> bool {
let vm = vecmap_from_btreemap(&b);
itertools::equal(vm.iter(), b.iter())
}
fn like_btreemap_range (b: BTreeMap<u32, u32>, key1: u32, key2: u32) -> bool {
// range requires start key is not after end key.
let (start, end) = if key1 <= key2 { (key1, key2) } else { (key2, key1) };
let vm = vecmap_from_btreemap(&b);
let range = (Included(&start), Excluded(&end));
itertools::equal(vm.range(range), b.range(range))
}
}
}