Click here to Skip to main content
Click here to Skip to main content

A new approach to memory management that solves the issues with shared_ptrs

, 23 Feb 2009
Rate this:
Please Sign up or sign in to vote.
A new approach to memory management that solves the issues with shared_ptrs

Introduction

This document describes the design and implementation of a new idea for automating memory management that can solve the problem of cyclic references.

Boost contains some nice memory management classes: shared_ptr, weak_ptr, and intrusive_ptr. Memory management using these classes is very nice, but reference counting has one flaw: it can not handle cyclic references.

In order to handle cyclic references with reference counting, the programmer is left with the task to break cycles using weak pointers. Such a task may not scale well in time and space: as a project becomes larger and more complicated, cycles are harder to spot, especially when cycles are introduced via subclasses.

The problem gets worse when a project evolves over a long period of time, with different programmers assigned to a project. During transition from one person to another, knowledge of cycles may be lost.

The code in the file 'main.cpp' implements a solution for automating memory management, borrowing some ideas from true garbage collectors. The solution can handle referential cycles and also delete objects in a good order (finalization order is a well known problem for garbage collectors) when the objects are no longer referenced anywhere from the program.

The presented solution is not a panacea that solves all the aspects of memory management. At best, it can be thought of as complementary to existing methods.

Background

In true garbage collectors, the collector scans the object graph, starting from the root set, marking each visited object as reachable. Objects left untouched at the end of the collection are deemed unreachable and therefore collected. For example, if we have three root references R1, R2, and R3, and objects A, B, and C:

R1 ---> A ---> B 
           |  
R2 --------|
R3 ---> C

If the reference R3 is removed, then the object graph becomes:

R1 ---> A ---> B 
           |  
R2 --------|
R3      C

The collection algorithm execution goes like this:

  1. From R1, A is reachable.
  2. Mark A as reachable.
  3. Scan A.
  4. From A, B is reachable.
  5. Mark B as reachable.
  6. Scan B.
  7. From R2, B is reachable.
  8. B is already marked, do not mark it again.
  9. A, B is reachable; C is not reachable.
  10. Collect C.

Problems of this approach in C++

In order for this to work, we must know the root set. Unfortunately, in C++, the root set is not known (compiler assistance is required for this), so this algorithm can not be applied.

One solution would be to register root pointers to a ptr collection, either explicitly or implicitly in the constructor of a special pointer class. But that does not work with STL containers, because STL containers themselves must use the specified pointer classes. Unfortunately, this is not always true. For example:

ROOT_PTR_COLLECTION
 |
 |--> R1 ---> A ---> B
 |          |
 R2 --------|
 |
 R3 ---> C

But, when we have an STL container:

ROOT_PTR_COLLECTION
 |
 |--> R1 ---> A ---> B
 |    |          |
 |--> R2 --------|
 |    |
 |--> R3 ---> C
 |     
 |--> R4 ----> STL CONTAINER
                | ~~> D
                | ~~> E

In the above diagram, the arrow '~~>' represents a non-garbage collected link (a shared_ptr perhaps). When the collection runs:

  1. From the root ptr collection, the reference R4 is reached.
  2. From R4, the STL CONTAINER is reached.
  3. C and D are not reachable.
  4. Collect C and D.

So, C and D will be collected, even though there is an STL container that refers to these objects.

Solution

In the traditional approach, the collection algorithm can be summarized in the following sentence:

An object is collectable when it is no longer accessible by any path that starts from the root set.

The above sentence can be reversed without altering the essence of the collection algorithm:

An object is collectable when it is no longer accessible by any path that ends at the root set.

Using this reversed approach, a set of smart pointer classes can be created which can be used to check if there is any path to a root pointer. The original example with the three references R1, R2, R3 and objects A, B, and C becomes:

R1 <--- A <--- B
           |
R2 <-------|
R3 <--- C

When a reference is removed, we can check if there is another path that leads to a root reference. If there is no root reference that points to the object, the object can be safely deleted. For example, if the reference R3 is removed, our graph becomes:

R1 <--- A <--- B
           |
R2 <-------|
R3      C

And now, the object C can be safely deleted.

Design and implementation

In the file 'main.cpp', the following classes are defined:

  1. class 'object', as a base class that contains a list of pointers that point to it. This is necessary so that the object graph can be traversed backwards towards the roots. The object class contains a flag 'm_lock' which is used to prevent infinite loops during checking of an object for collectability.
  2. class 'ptr_base', which is a generic pointer class that encapsulates the logic of acquiring and releasing an object:
    1. The operation 'acquire' adds the pointer to the list of pointers of the pointed object.
    2. the operation 'release' removes the pointer from the list of pointers of the previously pointed object. It then calls the object to dispose itself, if it is collectable. This is where the graph is scanned backwards towards the roots.

    The class is a boost::intrusive list node (using boost::intrusive) for performance reasons, since a pointer can only point to a single object at a time.

    The class also contains a pointer to an owner object, set during the construction of a pointer instance. This pointer is used for knowing when a pointer is root: if a pointer is instantiated without an owner, then it is a root pointer.

  3. a class 'ptr<T>', which is a simple derived class that adds type checking to the class 'ptr_base'. The class has normal pointer semantics as well as STL pointer semantics (functions 'get()' and 'reset()').

Destruction order

When an object is disposed, it is checked if it is collectable or not: the graph of objects is traversed backwards to the roots. If the object is collectable, it is deleted.

Deleting the objects causes the member pointers of an object to release their own objects recursively, in natural order (i.e., in C++ destruction order).

Solving the problem of cycles

If there is a cycle, then the dispose() function makes sure that all the pointers pointing to the disposed object are released before the object is deleted, thus resolving the cycle.

Working with STL containers

STL containers contain root references, i.e., instances of ptr<T> that do not have an owner. Therefore, as long as an object is referenced from an STL container, it will not be collected, because it will be accessible from the root set of the STL container.

The STL container itself can be managed via shared pointers. The example provided in 'main.cpp' contains an example with an std::list.

Eager vs. Lazy disposal

Trying to dispose an object each time a pointer changes value may be a very slow operation, if the object graph is too complex. A solution to this problem is to postpone the checking for a later date, i.e., to have lazy disposal.

The classes 'collector' and 'collector_object' work together to provide the functionality for lazy disposal.

Testing

The file 'main.cpp' contains two tests:

  1. a test with trees (nodes pointing to the parent, previous, and next siblings, first, and last children) with eager disposal.
  2. the same test with lazy disposal.

In both cases, all objects are collected as required.

The test has been executed in Visual Studio 2005.

Conclusion

This is a list of previous (and lame Smile | :) ) attempts by this author to make a collector, as well as by other authors:

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

Achilleas Margaritis
Software Developer (Senior)
Greece Greece
No Biography provided

Comments and Discussions

 
QuestionDoes it work in multithreaded programs? PinmemberDmitriy Iassenev9-Mar-09 11:45 
perhaps, you should synchronize m_lock member for this purpose, but then you'd lose performance
AnswerRe: Does it work in multithreaded programs? PinmemberAchilleas Margaritis13-Mar-09 3:52 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web01 | 2.8.140721.1 | Last Updated 23 Feb 2009
Article Copyright 2009 by Achilleas Margaritis
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid