It would be nice to either use Box or Rc as the underlying smart pointer type. Alas, until we have associated generic types, we can't be polymorphic over this, but perhaps in the interim code generation could be used to create concrete implementations of:

• ArcList
• RcList
• BoxList
• etc.

Then once associated generic types comes we could convert these to type aliases that refer to a common List type.

POC of using Arc::make_mut to avoid allocating new Arcs unnecesarily. Can speedup mutating operations quite significantly on certain workloads.

The same approach could be used on most or all of the other datastructures as well though the difficulty of rewriting may vary.

Before

running 4 tests
test vector_drop_last ... bench: 130,201,140 ns/iter (+/- 36,244,874)
test vector_get       ... bench:   1,184,598 ns/iter (+/- 1,617,973)
test vector_iterate   ... bench:     867,704 ns/iter (+/- 1,049,963)
test vector_push_back ... bench: 144,737,691 ns/iter (+/- 37,627,413)

test result: ok. 0 passed; 0 failed; 0 ignored; 4 measured

After

running 6 tests
test vector_drop_last     ... bench: 121,274,205 ns/iter (+/- 42,464,999)
test vector_drop_last_mut ... bench:   6,236,952 ns/iter (+/- 5,259,908)
test vector_get           ... bench:   1,346,970 ns/iter (+/- 1,673,853)
test vector_iterate       ... bench:     941,329 ns/iter (+/- 1,300,796)
test vector_push_back     ... bench: 166,950,667 ns/iter (+/- 50,590,077)
test vector_push_back_mut ... bench:  12,237,360 ns/iter (+/- 8,773,744)

test result: ok. 0 passed; 0 failed; 0 ignored; 6 measured

$ cargo benchcmp old new
 name              old ns/iter  new ns/iter  diff ns/iter   diff %  speedup
 vector_drop_last  130,201,140  110,503,419   -19,697,721  -15.13%   x 1.18
 vector_get        1,184,598    1,143,228         -41,370   -3.49%   x 1.04
 vector_iterate    867,704      888,491            20,787    2.40%   x 0.98
 vector_push_back  144,737,691  128,403,711   -16,333,980  -11.29%   x 1.13

Hi,

I was reviewing the code in cargo's resolver when I came across this line: "We should switch to persistent hash maps if we can..." and thought didn't I just see a persistent hash map crate.

So if/when this crate is ready, perhaps a pr thare?

Just my 2c.

This patch set adds serde as an optional dependency; serialization/deserialization code isn't compiled if it's not used. Addresses issue #1

You can run tests that include serialization/deserialization code using

cargo test --features serde

or more likely if you want the tests to finish somewhat promptly,

cargo test --release --features serde

In #rust today someone was struggling to serialize rpds::Vector (logs). It would be great to have Serde impls for these data structures that can be enabled by a serde cfg.

I tried using a RedBlackTreeSet inside of another map and was surprised to find it doesn't impl Hash. Considering that you can already hash a RedBlackTreeMap<T, ()>, I think it makes sense to expose that functionality on the Set type here too.

Speedup HashTrie Iterator by:

• avoid pushing single bucket leafs into the stack
• avoid recursion
• avoid iterator peeking

Before: rpds hash trie map sync iterate time: [301.18 us 304.05 us 307.06 us]

After (this PR, non inlined next) rpds hash trie map sync iterate time: [120.29 us 120.96 us 121.72 us]

After (when next is inlined, not in this PR) rpds hash trie map sync iterate time: [103.74 us 104.39 us 105.03 us]

This implementation is based on the suggestion in #23, but I ended up diverging a bit from that. In particular, I'm not implementing IterArc in terms of RangeIter, because the termination logic ended up being different and so there wasn't much code-sharing to be had. Also, the logic in RangeIter is much nicer if I don't include the lazy-initialization optimization for the stacks.

I did, however, attempt to reuse some code between IterArc and RangeIter by factoring out some utilities for managing the stacks.

Vectors seem promising but the RedBlackTree regresses in get and iterate which is rather odd... Need to investigate further.

 name                  old ns/iter  new ns/iter  diff ns/iter   diff %  speedup 
 vector_drop_last      120,354,099  95,403,062    -24,951,037  -20.73%   x 1.26 
 vector_drop_last_mut  7,469,591    5,451,750      -2,017,841  -27.01%   x 1.37 
 vector_get            2,969,756    2,909,477         -60,279   -2.03%   x 1.02 
 vector_iterate        1,411,878    1,269,607        -142,271  -10.08%   x 1.11 
 vector_push_back      131,497,470  103,677,766   -27,819,704  -21.16%   x 1.27 
 vector_push_back_mut  14,291,589   9,912,382      -4,379,207  -30.64%   x 1.44 

(10k elements)

 name                        old_tree ns/iter  new_tree ns/iter  diff ns/iter   diff %  speedup 
 red_black_tree_map_get      624,572           667,942                 43,370    6.94%   x 0.94 
 red_black_tree_map_insert   17,937,010        15,219,633          -2,717,377  -15.15%   x 1.18 
 red_black_tree_map_iterate  172,588           197,880                 25,292   14.65%   x 0.87 
 red_black_tree_map_remove   22,687,565        18,574,023          -4,113,542  -18.13%   x 1.22 

As #41 suggests, when dropping a large List, rust recursively calls Arc's drop function, which leads to stackoverflow. We can implement our custom Drop trait for List to prevent this, the following code seems to solve this problem:

impl<T, P> Drop for List<T, P>
where
    P: SharedPointerKind,
{
    fn drop(&mut self) {
        let mut head = self.head.take();
        while let Some(node) = head {
            if let Ok(mut node) = SharedPointer::try_unwrap(node) {
                head = node.next.take();
            }
            else {
                break;
            }
        }
    }
}

Attempting to implement a wrapper for HashTrieMap and got the following error:

SIGSEGV: invalid memory reference

Most of the relevant code is below. It compiles but fails when running the test. Any idea what a fix would be for this?

type ContainedHval = Box<HVal>;

#[derive(Clone,Debug)]
pub struct HDict(HashTrieMap<String, ContainedHval>);

//pub type HDict<'b> = HashTrieMap<String, Box<HVal<'b>>>;

impl HVal for HDict {
    fn to_zinc(&self) -> String {
        "Not implemented!".to_string()
    }
}

impl Eq for HDict {}

impl PartialEq for HDict {
    fn eq(&self, other: &Self) -> bool {
        if self.0.size() != other.0.size() {
            return false;
        }

        for (k,v) in self.0.iter() {
            let tmp = match other.0.get(k) {
                Some(ov) => **v == **ov,
                None => false
            };

            if !tmp {
                return false;
            }
        }

        true
    }
}

impl HDict {
    pub fn new() -> HDict {
        HDict(HashTrieMap::new())
    }

    fn has(&self, name: &String) -> HBool {
        self.0.contains_key(name)
    }

    fn is_empty(&self) -> HBool {
        self.0.is_empty()
    }

    fn missing(&self, name: &String) -> HBool {
        !self.0.contains_key(name)
    }

    pub fn iter(&self) -> Iter<String, ContainedHval> {
        self.0.iter()
    }

    fn insert(&mut self, name: &String, value: ContainedHval) -> Self {
        HDict(self.0.insert(name.clone(),value))
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn create() {
        let a = HDict::new();
        let b = HDict::new().insert(&"Hello".to_owned(),Box::new(true));

        //assert_ne!(a,a.clone().insert(&"Hello".to_owned(),Box::new(true)));
        //assert_eq!(a,HDict::new());
        ///*
        assert_eq!(
            b.clone(),
            HDict::new().insert(&"Hello".to_owned(),Box::new(true))
        );
        //*/
    }
}

I find myself doing this a lot:

match foo.peek() {
  Some(head) => {
    foo = foo.pop().unwrap();
  }
}

As far as I can see, there isn't a single API for popping an item and returning it. Would it make sense to add one?

(I'm sure you can think of a better name if you do add this.)

I would like to make rpds an optional dependency while at the same time implementing some traits in a generic manner (i.e. impl<T, P: archery::SharedPointerKind> for rpds::Vector<T, P>).

I can't find a way to make this work without adding archery as an optional dependency and then requiring users to enable both features.

I was using im and recently moving to rpds. im as methods like skip take drop_first...which create slices from existing vectors. I can't find these methods in rpds so I have to use for... .iter() and then copy elements into new vectors, and that would be slow due to lack of structural sharing.

Is there suggesting ways to make slices?

updated,

probably just https://github.com/orium/rpds/issues/61 .

Any chance for adding a Finger Tree data-structure to rpds? 😃🙏

(there are references for this being done—at least in partially persistent ways—as early as '86)

What is a good way to get the current memory usage of a rpds structure? I'm looking for something like Servo's malloc_size_of. I can get the size of leaves but I'm missing the size of branches. Or is it trivial to calculate it? Any recommendation would be appreciated.