Rc<T> - A smart pointer supporting multiple ownership in Rust
Rust has a neat type called Rc<T>, which is similar to Box<T> but supports multiple owners at the same time. Compared to Box<T>, Rc<T> can be cloned without having to do a deep copy. All clones of an Rc<T> still point to the same object, which is exactly what we want. Even better, once the last Rc<T> goes out of scope, it automatically cleans up the heap allocation, just as Box<T> would. Since the final owner typically cannot be determined at compile-time, Rc<T> requires some form of runtime tracking of the number of owners. As a consequence, Rc<T> has a larger runtime overhead than Box<T>For most practical purposes, we can consider both Box<T> and std::unique_ptr<T> to have no runtime overhead compared to a hand-written version that does the same. There are some rare situations though where the generated code is not as optimal..
A first try at implementing a multiple ownership smart pointer (using C++)
How can we implement something that behaves like Rc<T>? We will try first in C++, because it has less strict rules, and then look at how we could do it in Rust.
struct RefCount {
size_t count;
};
template<typename T>
struct Rc {
Rc() : obj(nullptr), ref_count(nullptr) {}
~Rc() {
if(!ref_count) return;
ref_count->count--;
if(ref_count->count == 0) {
delete obj;
delete ref_count;
}
}
explicit Rc(T obj) {
this->obj = new T{std::move(obj)};
ref_count = new RefCount{};
ref_count->count = 1;
}
Rc(const Rc& other) {}
Rc(Rc&& other) {}
Rc& operator=(const Rc& other) {}
Rc& operator=(Rc&& other) {}
const T& get() const {
return *obj;
}
private:
T* obj;
RefCount* ref_count;
};
Our Rc type consists of two pieces of heap-allocated memory: The actual instance of type T and a reference count, which stores the number of references that exist to that instance. This already resolves the mystery of the name Rc, which is a shorthand for reference-counted. The constructor takes an instance of T and moves it onto the heap, creating a new RefCount on the heap and initializing its reference count with 1. In the destructor, the reference count is decremented by one and if it is zero then, we know that we just destroyed the last reference to the instance of T, so we delete both the instance and the RefCount. We also specify a default constructor which sets everything to nullptr.
Now to implement the copy and move constructors and assignment operators:
Rc(const Rc& other) : obj(other.obj), ref_count(other.ref_count) {
if(ref_count) {
ref_count->count++;
}
}
Rc(Rc&& other) : obj(other.obj), ref_count(other.ref_count) {
other.obj = nullptr;
other.ref_count = nullptr;
}
The copy constructor copies just the raw pointers of the instance and the reference count block, and if the reference count is not nullptr increments the reference count by one. This is a shallow copy because we just copied the pointers! The move constructor is even simpler: It moves the pointers from the old Rc to the new one. The reference count is not changed, because no new reference has been created.
Rc& operator=(const Rc& other) {
if(ref_count) {
ref_count->count--;
if(ref_count->count == 0) {
delete obj;
delete ref_count;
}
}
obj = other.obj;
ref_count = other.ref_count;
if(ref_count) {
ref_count->count++;
}
return *this;
}
Rc& operator=(Rc&& other) {
if(ref_count) {
ref_count->count--;
if(ref_count->count == 0) {
delete obj;
delete ref_count;
}
}
obj = other.obj;
ref_count = other.ref_count;
other.obj = nullptr;
other.ref_count = nullptr;
return *this;
}
The copy constructor is a bit more involved. It decrements the reference count of the current object and potentially deletes it if this was the last reference. Then, it copies the pointers of the other Rc and potentially increases the reference count, which now refers to the instance of the other Rc. The move constructor is similar, but instead of incrementing the new reference count, it just steals the pointers from the other Rc. The following example shows how to use this Rc type:
int main() {
Rc<int> rc1{42};
std::cout << rc1.get() << std::endl;
Rc<int> rc2 = rc1;
rc1 = {};
std::cout << rc2.get() << std::endl;
return 0;
}
The whole process that we implemented here is called reference counting, because that is exactly what it does: We count the number of active references to a piece of memory, and when this count goes to zero, we automatically release the memory. To do so requires two memory allocations, one for the object to track and one for the reference count. The reference count has to live on the heap as well, because it is also shared between all instances of the Rc type which point to the same instance of T. Since this reference count gets updated at runtime, reference counting has a larger performance overhead than using the single-ownership containers. It also means we lose a bit of determinism regarding when exactly the object gets destroyed. With Box<T>/std::unique_ptr<T>, we knew at compile-time where the object gets destroyed. With Rc, this depends on the runtime situation. If our type T does some non-trivial work in its destructor that takes some time, with Rc it is harder to figure out when exactly this work happens.
Reference counting details
One thing that is a little bothersome is that reference counting requires two memory allocations instead of one. The problem is that the type T and the type that stores the reference count (RefCount in our code) are two distinct types. We could make the type T should store its own reference count and then change our code to something like this:
template<typename T>
struct IntrusiveRc {
IntrusiveRc() : obj(nullptr) {}
~IntrusiveRc() {
if(!obj) return;
obj->dec_ref_count();
if(obj->get_ref_count() == 0) {
delete obj;
}
}
explicit IntrusiveRc(T obj) {
this->obj = new T{std::move(obj)};
this->obj->set_ref_count(1);
}
/* Other methods... */
private:
T* obj;
};
We call this process intrusive reference counting, because the information about the reference count intrudes the type T. As a consequence, our IntrusiveRc<T> type can only be used with specific types T which support the necessary operations (set_ref_count(), get_ref_count() etc.). The benefit is that we only require a single dynamic memory allocation, and the code can actually be faster, because the reference count will typically be stored inside the memory of the managed instance! This makes intrusive reference counting potentially faster than non-intrusive reference counting (which is what we used for our Rc<T> type).
There is a third option: We can store the reference count and the instance of T next to each other in memory, without one knowing about the other! Let's try this:
template<typename T>
struct RefCountAndT {
RefCountAndT(T obj) : ref_count(1), obj(std::move(obj)) {}
size_t ref_count;
T obj;
};
template<typename T>
struct PackedRc {
PackedRc() : ref_count_and_obj(nullptr) {}
~PackedRc() {
if(!ref_count_and_obj) return;
ref_count_and_obj->ref_count--;
if(ref_count_and_obj->ref_count == 0) {
delete ref_count_and_obj;
}
}
explicit PackedRc(T obj) {
ref_count_and_obj = new RefCountAndT{std::move(obj)};
}
/* Other methods... */
private:
RefCountAndT<T>* ref_count_and_obj;
};
Here we introduce a new type RefCountAndT, which packs the reference count and an instance of T into the same memory region. This way, we can allocate both the reference count and the instance of T next to each other in memory using a single allocation. This is a 'best-of-both-worlds' approach to reference counting, and it is basically what the standard library implementations of Rc<T> in Rust and its C++-equivalent std::shared_ptr<T> use internally. The following image visualizes the three types of reference counting:
