Rc<Vec<T>> vs ImVec<T>

#1

What are situations where Rc<Vec<T>> works better than Immutable::Vector<T> ?

If we're not modifying, copying either is O(1).

If we are modifying, ImVec is log(n), whereas the Rc<Vec<T>> is O(1) after an O(n) copy.

In practice are there situations where Rc<Vec<T>> makes more sense than ImVec<T> ?

EDIT: (after reading @OptimisticPeach 's comment): This is my fault, I should have been clearer. By ImVec, I'm referring to https://docs.rs/im/14.1.0/im/vector/enum.Vector.html

1 Like
#2

As far as I get it... ImVec sounds like

struct ImVec<T> {
    mine: Vec<T>,
    rest: Rc<Vec<T>>,
    orderings: Vec<(usize, usize)> //what's mine and what's theirs
}

So, if the implementation of your ImVec is like that and you're not modifying, then there's really no point to having it. I'm sure there's a more correct way to write this (this can only modify a preexisting Rc<Vec<T>> and it can't update another ImVec<T>). If you're writing as well and you've got an O(log n) situation vs O(1) & O(n) situation then I'd say it depends on what the specific case is; if you're cloning frequently then Rc makes sense, otherwise ImVec.

#3

Yes. One is when you never need to modify the vector after first creating it. Another is when the operations performed on it are O(n) large anyway.

2 Likes
#4

Sorry, see edit above. By ImVec, I'm referring to https://docs.rs/im/14.1.0/im/vector/enum.Vector.html

1 Like
#5

Is the advantage here being that Rc::new(...) moves the heap alocated Vec, and is O(1), while ImVec::from(...) has to build a new vec, and is O(n) ?

#6

Iteration over im::Vector<T> is amortized O(1), while iteration over Vec<T> is O(1) (without amortization costs). Random lookups are O(log(n)) vs O(1) over the same types.

Rc<Vec<T>> allows immutably sharing Vec<T>, and should generally perform better.

edit: To clarify, iterating either data structure is O(n); I was referring specifically to the time complexity of the individual Iter::next() implementations.

#7

I was going to make the counter argument that assuming the interior nodes are "32 wide", for a vec with 1B elements, log(n) is only ~6.

But then I realized: for a plain Vec, to access v[i], we can jump directly to where the element is located. However, with ImVec[i], we may have to to 6 "sequential, randomish memory lookups" to figure out where to jump to -- and this this can be quite a slowdown.