How to pass objects efficiently?

[sandMan]

fn main() {
    // Just for type signatures.
    let mut adj: Vec<Vec<usize>>;
    let mut vis: Vec<bool>;
    let node: usize;

    dfs(&adj, &mut vis, node);
}

fn dfs(adj: &Vec<Vec<usize>>, vis: &mut Vec<bool>, node: usize) {
    let adj_node: usize;
    dfs(adj, vis, adj_node);
}

The first time I pass the arguments adj, vis and call dfs() from main(), I'm passing references which is efficient and avoids unnecessary deep copy.

• Q1. Are the subsequent recursive calls to dfs() written above fine and efficient (not creating deep copies)?
• Q2. Is there a better way to pass node?

[farnz]

@sandMan

Q1. Are the subsequent recursive calls to dfs() written above fine and efficient (not creating deep copies)?

Yes - they're passing references, not complete objects, because dfs accepts references.

@sandMan

Q2. Is there a better way to pass node?

No; usize is never larger than a reference (but can be smaller - "fat pointers", for example) and thus a reference is going to be more memory use, and less efficient.

Note that passing by reference is not always more efficient - it avoids copying the data structure, but it requires you to indirect through the reference to get to the data structure. Further, the Rust compiler's optimizer makes efforts to remove copies whenever possible - it's not perfect, but there will be cases where it can optimize a function of the form fn do_the_thing(input: T, …) -> T to do the change in-place, rather than creating a copy and destroying the original. You should always measure whether you're getting performance gains when you try to remove copies.

[steffahn]

Rust will never create deep copies implicitly. It’s a IMO (compared to e.g. C++) very valuable thing that deep copies in Rust will always come with an explicit function (or method, operator, macro, …) call, most commonly to the .clone() method of a given type that supports deep copies.

This is always true independent of how anything is passed to any function. The act of passing a &mut Vec<…> reference to a function will not result in a deep copy, but passing an owned Vec<…> value directly would not result in a deep copy either. (However it might force the caller to add an explicit deep copy if they want to hold on to the value for longer.)

The only possibility where this is less explicit than that is when the call to .clone() (or an otherwise directly implemented deep-copying functionality) in turn is hidden in some function or method (or macro, like vec![item; amount]), but typically that should be well documented and thus not very confusing either. In case of generic functions that do this, you’ll also typically see T: Clone bounds indicating the possibility that the function can clone (and thus deep-copy for types where .clone() incurs a deep-copy) the value.

Also note that not every usage of .clone() is expensive, it depends on the type; many types don’t deep-copy even with the .clone() method, either because they don’t even have any deep data to begin with, or because they can use sharing using reference-counting, such as e.g. for the Arc<T> type.

Besides explicit solutions of copying values, as indicated above commonly exposed via the Clone::clone trait method, Rust does have a notion of implicit copying, via the Copy trait; however due to how these copy operations operate, it is guaranteed that these fully implicit copies are never deep, as there’s no customizable logic attached, and it’s always a shallow copy of the "stack data" (types whose values that cannot correctly be copied by copying their shallow data alone cannot implement the Copy trait; which is enforced by the compiler e.g. if the type owns any data via something like a Box<T> in a field, or any non-Copy type for that matter).

[H2CO3]

@sandMan

Are the subsequent recursive calls to dfs() written above fine and efficient (not creating deep copies)?

Would anything else be reasonable behavior? The function's signature and implementation is determined once – it doesn't depend on the caller (whether main calls it or itself). If it did, that would be worrysome.

[steffahn]

Regarding potential improvements: With Vec<T> in particular, it is common practice to avoid immutable references to vectors &Vec<T> and use &[T] slices instead. This is commonly suggested because the &[T] allows for more flexibility for the caller to pass slices derived from other types. But this has some potential performance benefits, too, in that one level of indirection is avoided; the potential downside being that one more word of data is passed to the function, since &[T] slices consist of one pointer and one usize for the length.

Similarly, for &mut Vec<T>, in certain use cases / when possible, &mut [T] would be preferred. These use-cases are whenever the vector isn’t actually mutated in its length (growing and shrinking, e.g. via push/pop)^[1]. As far as I understand your code, the vis vector, presumably tracking which nodes were visited, will not grow or shrink during dfs, so the signature could become

fn dfs(adj: &[Vec<usize>], vis: &mut [bool], node: usize) 

---

1. as a &mut [T] slice reference gives mutable access to its elements, but doesn’t allow resizing the original vector ↩︎

[sandMan]

This was super helpful. Thanks.