Data structure and algorithms for garbage collection in C++

Describe the data structures and algorithms that you would use to implement a garbage collector in C++.

My initial thoughts:
Utilize the concept of smart pointer:

template <class T>
class SmartPtr
{
public:
	explicit SmartPtr(T* pointee) : pointee_(pointee);
	SmartPtr& operator=(const SmartPtr& other);
	~SmartPtr();
	
	T& operator*() const {
		..
		return *pointee_;
	}

	T* operator->() const {
		...
		return pointee_;
	}
	
private:
	T* pointee_;
	...
};

Solution:
In C++, garbage collection with reference counting is almost always implemented with smart pointers, which perform reference counting. The main reason for using smart pointers over raw ordinary pointers is the conceptual simplicity of implementation and usage.
With smart pointers, everything related to garbage collection is performed behind the scenes – typically in constructors/destructors/assignment operator/explicit object management functions.
There are two types of functions, both of which are very simple:

RefCountPointer::type1() {
	// implementation depends on reference counting organisation.
	// There can also be no ref. counter at all (see approach #4)
	incrementRefCounter();
}

RefCountPointer::type2() {
	// Implementation depends on reference counting organisation.
	// There can also be no ref. counter at all (see approach #4).
	
	decrementRefCounter();
	if (referenceCounterIsZero()) {
		destructObject();
	}
}

There are several approaches for reference counting implementation in C++:

  1. Simple reference counting:
    struct Object { }; 
    struct RefCount {
    	int count; 
    };
    struct RefCountPtr {
    	Object * pointee;
    	RefCount * refCount; 
    };
    
    • Advantages: performance.
    • Disadvantages: memory overhead because of two pointers.
  2. Alternative reference counting.

    struct Object { ... }; 
    struct RefCountPtrImpl {
    	int count;
    	Object * object; 
    };
    struct RefCountPtr {
    	RefCountPtrImpl * pointee; 
    };
    
    • Advantages: no memory overhead because of two pointers.
    • Disadvantages: performance penalty because of extra level of indirection.
  3. Intrusive reference counting.

    struct Object { ... };
    struct ObjectIntrusiveReferenceCounting {
    	Object object;
    	int count; 
    };
    struct RefCountPtr {
    	ObjectIntrusiveReferenceCounting * pointee; 
    };
    
    • Advantages: no previous disadvantages.
    • Disadvantages: class for intrusive reference counting should be modified.
  4. Ownership list reference counting It is an alternative for approach 1-3. For 1-3 it is only important to determine that counter is zero — its actual value is not important This is the main idea of approach # 4.
    All Smart-Pointers for given objects are stored in doubly-linked lists. The constructor of a smart pointer adds the new node to a list, and the destructor removes a node from the list and checks if the list is empty or not. If it is empty, the object is deleted.

    struct Object {  };
    struct ListNode {
    	Object * pointee;
    	ListNode * next;
    }
    
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: