Dealing with shared ownership (Rc and Arc)

[SimonSapin]

A central idea behind this crate is that most resources in Rust have one well-defined owner. heap_size_of_children can trace recursively and only consider owned resources. For &T references it can return zero since they usually either point to non-heap memory, or to heap memory owned by something else that will be accounted for there.

This breaks down for types like Rc<T> and Arc<T> that introduce "shared ownership". They do have heap memory that we want to count, but in a fully generic context there is no clear single point where it should be counted.

(In a more specific context there count be a "main" Rc reference for a given resource. For example, following only the "first child" and "next sibling" references in a Kuchiki tree allows traversing the whole tree without duplication.)

In the current version (90dd7e0) this crate has:

impl<T: HeapSizeOf> HeapSizeOf for Arc<T> {
    fn heap_size_of_children(&self) -> usize {
        (**self).heap_size_of_children()
    }
}

This impl is returns an incorrect number for two reasons:

• It’s too low because it only counts the size of resources owned by T, not the size of T itself and the two reference counts that Arc holds internally. This part is easy to fix.

• It’s too high because there could be many Arc references to the same T value, and this impl duplicates by that many times the count of memory owned by T.

  One idea that I’ve heard/read (I don’t remember from who, sorry) was to divide by the strong reference count. If all strong references are traced correctly these fractions should add up to the correct value. But the usize return type would have to be changed to f32 or f64 to get remotely accurate results, which is weird at best. And Arc::strong_count and Rc::strong_count are still #[unstable]: Tracking issue for Arc/Rc extras rust-lang/rust#28356

The current version of this crate has another impl:

impl<T> HeapSizeOf for Vec<Rc<T>> {
    fn heap_size_of_children(&self) -> usize {
        // The fate of measuring Rc<T> is still undecided, but we still want to measure
        // the space used for storing them.
        unsafe {
            heap_size_of(self.as_ptr() as *const c_void)
        }
    }
}

My understanding of it as that, in practice, when we can’t have a correct impl of HeapSizeOf, Servo sometimes implement it (incorrectly) returning zero because an underestimated answer is better(?) than no answer.

This Vec<Rc<T>> follows this idea, just making the error smaller: don’t count Rc’s but count the Vec containing them.

Still, I don’t think there’s a reason to treat Rc<T> and Arc<T> differently.

[jdm]

Yeah, that's an odd inconsistency. I'm surprised we have an implementation for Arc at all.

[asajeffrey]

If heapsize is going to cope with Rc<T> it looks like it would have to implement a graph-marking algorithm. This would mean something like keeping track of a set of pointers, then on reaching an Rc<T>, checking to see if the pointer is in the set: if it is, return a constant, and if it isn't, add it to the set before recursively calculating the size. This makes calculating heap size quite expensive, as it means keeping track of the set of all visited Rcs.

If we could guarantee that only one heapsize calculation at a time was needed, we could try to cram the marker into the Rc, but this would have to be done unsafely since the heap_size_of_children function only has &self, not &mut self. Arc is probably even trickier, since we'd have to ensure thread-safe access to the marker.

[jdm]

@asajeffrey What would be the end goal of maintaining that graph?

[asajeffrey]

Only visiting each Rc<T> once. The pathalogical case is something like:

enum BTree {
    Leaf,
    Node(Rc<BTree>, Rc<BTree>),
}

let tree0 = Rc::new(BTree::Leaf);
let tree1 = Rc::new(BTree::Node(tree0.clone(),tree0.clone()));
let tree2 = Rc::new(BTree::Node(tree1.clone(),tree1.clone()));
...

If you use tree-traversal on treeN, you visit 2^N nodes, with graph-marking you just visit N.

[SimonSapin]

And it’s not (just) about traversal time, it’s to avoid duplicating the count of memory used by T in Arc<T>.

[asajeffrey]

Indeed, we can avoid having to divide by the ref count by only counting each Rc once.

[nnethercote]

Firefox's memory profiling still doesn't handle ref-counted types well. For some of the types we return the full size if the refcount is 1, and 0 otherwise. I've thought about doing the divide-by-the-refcount idea (and using integer division) but never gotten around to it. I think using fractional types would be silly and not worth it.

In general it is indeed better to under-measure than over-measure, because you can get the total heap size (from the allocator) and then subtract the size of all known heap data structures and end up with an "unknown" bucket (called "heap-unclassified" in Firefox's about:memory) and you want that "unknown" bucket to be accurate. If you over-measure it could go negative, which is confusing. (Double-counting any memory can have similarly bad effects.)

In general, ensuring correctness of these measurements is a hard problem. When your code says your memory usage is X, how can you trust that? Firefox has a tool called DMD (https://developer.mozilla.org/en-US/docs/Mozilla/Performance/DMD) that verifies memory reporting by identifying which heap blocks are measure zero times, 1 times, and more than 1 times. It's really important for improving coverage and debugging the measurement code. I was hoping to implement something similar for Rust/Servo but never got around to it, at least partly because it requires (a) wrapping allocations and (b) getting and saving lots of stack traces, both of which are tricky in Rust.

[SimonSapin]

Aww, what’s wrong with reporting 128.00000000000000004 bytes of memory usage? :)

[SimonSapin]

Another "interesting" thing is that Rc and Arc can introduce cycles.

[asajeffrey]

If we're dealing with cyclic structures, then pretty much we have to either do graph marking, or ignore any Rc with refcount > 1. Are we concerned that ignoring Rc with refcount > 1 would cause reported size to change as Rc's are cloned / dropped?

[SimonSapin]

I think I’d prefer not to have a generic impl<T: HeapSizeOf> HeapSizeOf for Arc<T> (which can not assume anything about how Arc/Rc is used) in this crate at all, but rather answer these questions case by case in specific contexts.

[larsbergstrom]

@asajeffrey I assume that there's also a third point there - you can choose not to ignore any Rc with a refcount > 1 if it's instantiated at a type that can't be cyclic, right? Though I suspect that's getting into a level of plugin wizardry that's a bit silly.

[asajeffrey]

@larsbergstrom yes, you could try to be clever and get metadata about the type, like can it introduce cycles, but it seems like it would be tricky to get to fly without over-engineering it.

[larsbergstrom]

@asajeffrey I just thought it might be worth looking at, since a lot of the stuff we Rc in servo is basically a heap-allocated integer, a hash table instantiated at immediate types, etc. There may be very few cases where it's possible to create cycles.