One issue with garbage collection is that the points when the garbage collector are invoked are usually not under the control of the programmer. While the garbage collector is running, the program will be either halted (in the case of a sequential GC algorithm) or at the very least slowed down (in the case of a concurrent GC algorithm). This makes garbage collected languages often unusable for applications that need to satisfy strict timing guarantees (e.g. real-time applications such as multi-media apps, video games, embedded controllers, etc.).
An alternative approach to automated memory management is reference counting. Here, the idea is to keep track of how many references point to an object and free it when there are no more. That is:
-
Set reference count to 1 for newly created objects.
-
Increment reference count whenever we copy the pointer to the object.
-
Decrement count when a point to the object goes out of scope or stops pointing to the object.
-
When the count gets to 0, we can deallocate the object
Advantages:
-
More predictable performance: Memory can be reclaimed as soon as no longer needed. Rather than spending a lot of time on executing individual GC cycles, the time spent on memory management is more evenly distributed throughout program execution, which increases responsiveness.
-
Simplicity: Can be done by the programmer for languages not supporting GC.
Disadvantages:
-
Additional space is needed for keeping track of the reference count.
-
We still have some run-time overhead to perform the necessary bookkeeping for creating/deleting/updating the counters.
-
Will not reclaim circular reference structures (e.g. a cyclic list on the heap).
A common way to implement reference counting is in the form of a smart pointer library. We demonstrate how to do this in C++, which allows us to implement smart pointers in a way that mimics a regular pointer in syntax and semantics, making it convenient to use for clients.
-
With smart pointers we can do some of what a garbage collector does for us (i.e. automatically deallocate heap memory that is no longer needed).
-
Our smart pointer will do reference counting, as discussed above.
-
An implementation of this is included in this repository. The library is implemented as a template class
Ptr<T>
that represents a smart pointer to some value of typeT
. -
One core question, though: if we want to track the reference count of every object, where in memory do we store that information?
-
Do we store the count as a field inside each
Ptr
instance (internal containment)? -
That has problems...
-
When two instances of
Ptr
point to the same underlying object and one of them goes out of the scope, both counters in the twoPtr
s need to be decremented. -
Clunky and difficult to access internal state of separate instance.
-
-
How about inside the data layout of the referenced values
T
.- We don't want to implement this either because we want our code
to support pointers to values of primitive types like
int
and also null pointers, neither of which have a data layout.
- We don't want to implement this either because we want our code
to support pointers to values of primitive types like
-
How about we store the counter as a separate object on the heap with a reference to it in each
Ptr
? (external containment)-
With this approach the counter can be shared across all
Ptr
s that reference the same object. -
Whenever we do an assignment or a copy of a
Ptr
we increment the shared counter (respectively, decrement the counter to the previously referenced object).
-
-
Here is the basic skeleton of our smart pointer class:
template<typename T>
class Ptr {
T* addr; // pointer to referenced object
size_t* counter; // pointer to counter shared by all Ptrs that point to addr.
public:
...
};
The notation, template<typename T>
is C++'s way of defining a
generic class or function. Here, we define a generic class Ptr
that
is parameterized by a type T
(the type of values to which we
point)`.
Each instance of Ptr<T>
have two fields:
-
a pointer
addr
to a value of typeT
. This is the raw pointer that is managed by the smart pointer. -
a pointer
counter
that points to the counter (of typesize_t
) used to keep track of how many references we have to the value pointed to byaddr
.
Before we go into the details of the implementation, we need to briefly discuss how memory management works in C++.
In C++, heap allocated objects need to be managed explicitly. When a heap allocated object is no longer needed, it must be deallocated explicitly by the program. Otherwise, the program leaks memory.
There are three important methods related to memory management that
every C++ class A
needs to implement:
Copy constructor: this constructor is used whenever the compiler
automatically creates a copy of an A
instance. This happens e.g.
when an instance is passed by value to a function or when one instance
is used to initialize another:
A x; // allocate an A instance on the stack (calls default constructor of A)
A y = x; // calls copy constructor of A with x as argument to initialize y
Assignment operator: this method is called whenever we assign another instance of the class to the current instance of the class:
A x;
A y;
y = x; // calls assignment operator of `A` on y with x as argument.
Destructor: intuitively, you can think of a destructor as the
opposite of a constructor. A destructor is a method which is
automatically invoked when the object is destroyed, i.e., when the
memory of the instance is to be freed. Its main purpose is to free the
resources (memory allocations, open files etc.) which were acquired by
the instance along its life cycle. Destructors are necessary because
C++ does not have fully automatic memory management. The destructor of
a class A
is denoted by ~A
.
-
If an instance of a class
A
is allocated on the stack, the destructor~A
is called automatically when the instance goes out of scope. -
If an instance of a class
A
is allocated on the heap (vianew A(...);
), the destructor~A
is called when the instance is explicitly deallocated with adelete
statement.Unlike Scala, C++ does not automatically reclaim heap-allocated memory when it is no longer reachable from any global or stack variable. It is the program's responsibility to delete heap-allocated instances via explicit
delete
calls.
If the programmer does not define these three methods explicitly, then the C++ compiler will add them automatically. The semantics of the default implementations are:
-
Destructor - Call the destructors of all the object's class-type members (note that for pointer-typed members, the destructors of the referenced external objects are not called by the default destructors).
-
Copy constructor - Construct all the object's members from the corresponding members of the copy constructor's argument (shallow copy).
-
Assignment operator - Assign all the object's members from the corresponding members of the assignment operator's argument (shallow copy).
If one of the three methods has to be defined with a different semantics than the compiler-generated version, it means that the compiler-generated versions of the other two methods also likely do not fit the needs of the class. This is known as the Rule of Three.
Typically, the way to go about memory management in C++ is that the references to heap allocated objects are encapsulated in other objects which are stored as values on the stack. The copy constructors, assignment operators, and destructors of the stack-allocated objects take care of managing the heap allocated objects and freeing them when they are no longer needed. Since destructors of stack-allocated objects are called automatically when the objects are popped from the stack, this approach yields a semi-automatic memory management strategy.
Where things get more complicated is when heap allocated objects are shared between several stack allocated objects. So in this case, it is in general unclear which object is responsible for cleaning up. This is where smart pointers come into play.
We discuss the methods of our smart pointer class Ptr
in turn:
-
Standard constructor
Ptr(T* _addr = 0) : addr(_addr), counter(new size_t(1)) {}
This constructor is called when we create a
Ptr
to wrap around a raw pointer_addr
to a new heap allocated object of typeT
. We use_addr
to initialize the fieldaddr
of thePtr
instance and create a new counter on the heap. The counter is initialized to 1 since thisPtr
holds the only pointer to*addr
. -
Copy constructor
Ptr(const Ptr<T>& other) : addr(other.addr), counter(other.counter) { ++(*counter); }
When copying a
Ptr
instanceother
, we initialize the copy with a pointer to the same counter on the heap and increment the counter. -
Destructor
~Ptr() { if (0 == --(*counter)) { delete addr; delete counter; } }
When the current
Ptr
is destroyed, its destructor is called. The destructor first decrements the reference counter, since we now have one fewer reference toaddr
. When the counter becomes 0, i.e., we are destructing the last reference toaddr
. In this case, both the counter value on the heap, as well as the referenced object are deleted.Note that we do not need to safeguard against deleting
addr
when it is aNULL
pointer becausedelete
has no effect when its operand isNULL
. -
Assignment Operator
Ptr& operator=(const Ptr& right) { if (addr != right.addr) { if (0 == --(*counter)) { delete addr; delete counter; } addr = right.addr; counter = right.counter; ++(*counter); } return *this; }
Whenever we do an assignment between two
Ptr
instances, we first do a self-assignment check: if we try to assign aPtr
instance to itself, then there is nothing to be done and we simply return.Otherwise, we decrement the counter for the object that
addr
currently points to. If that counter becomes 0, the currentPtr
was the last one pointing to it. So we can delete both the counter and the object.Then we copy over the values of
addr
andcounter
from the other instanceright
and increment the new counter since we now hold one more reference to the object pointed to byright
.Note that the self-assignment check is critical for the correctness of the implementation. If the current instance is the only instance holding a reference to
addr
when the assignment operator is called, then without the self-assignment check we would delete the object and counter, which would lead to use after free error when we subsequently try to increment the deleted counter.
Let's see this in action:
1: {
2: Ptr<int> p = new int(3);
3: Ptr<int> q = p;
4: cout << *q << endl;
5: }
-
In line 2, we allocate an
int
on the heap which is initialized to 3. Then we call the constructorPtr(int*)
to createp
on the stack, passing to the constructor the address of theint
value 3 on the heap. -
In line 3, we call the copy constructor
Ptr(const &Ptr<int>)
withp
as argument to createq
on the stack. -
In line 4, we call
Ptr::operator*
which returns the value pointed to by the fieldaddr
ofp
, which is 3, and then pass it tocout
which prints 3. -
In line 5, both
p
andq
go out of scope. Hence, they are popped from the stack and the destructor~Ptr
is called for each of them. The first destructor call will decrement the value of the counter associated with theint
value on the heap to 1. The second destructor call will decrement it to 0 and then delete both the counter as well as theint
value.
Here is another example
1: struct Node {
2: Ptr<Node> next;
3: };
4:
5: {
6: Ptr<Node> p = new Node();
7: p->next = p;
8: }
When line 8 is executed, we set the smart pointer inside of the Node
object on the heap that is pointed to by p
back to itself, creating
a cyclic pointer structure. I.e. at this point, we have one counter
associated with the Node
object created on line 6 and its value is 2
because we have two references to the object: one from p
and one
from p->next
.
When p
goes out of scope on line 8
, then p
is popped from the
stack and its destructor is called. The destructor will decrement the
counter associated with the Node
object to 1. Since the counter is
not 0 (we still have the cyclic reference from p->next
back to p
),
the Node
object and its counter are not deleted. That is, here we
leak memory despite the usage of the smart pointers. Thus, when using
smart pointers, you have to be careful not to create cylic structures
with them.
You can find the smart pointer implementation in the file
src/ptr.h
and a test program in
src/ptr_test.cpp
.
To compile the test program you can use the cmake
build tool. If you
have cmake
installed, then run the following command once at the
root of the repo:
cmake .
Then you can run
make
./ptr_test
whenever you want to compile and run the test program.