Smart pointers

Templates to implement a super-pointer

C++ templates can be used to create intelligent pointers. Since templates are type factory, why not using this tool to create a new pointer type. The new pointer type is a class template and most of its standard operators are redefined : special operations are performed when assigning an object to the pointer. Such pointers are called smart pointers.

usage counter

To simplest way to know if an object is in used or not is to count objects that are using it. Each object have a counter and this counter is incremented and decremented by smart pointers.

• Smart pointer constructor : +1
• Smart pointer operator = : -1 to previous value, +1 to the new one.
• Smart pointer destructor : -1

When an object's counter reach zero, the object is no more used and can safely be destroyed. Of course, if other kind of pointers or reference are used to handle an object in the same time than our smart pointers, usage count can't be correct. Once an object is assign to a smart pointer, smart pointers must be the only way to access the object.

void foo() {
    NAJA<String> str1=new String("bar"); // bar's use count is 1
    NAJA<String> str2=str1;              // bar's use count is now 2
    NAJA<String> str3=new String("Hello world");
                                               // hello world's count is 1

    str1=str3;                                 // hello world's count is 2
                                               // bar's count is 1
}   // references' destructors are invoked, then hello world's count 
    // reaches successively 1 and 0, bar's count reaches 0.
    // The two Strings can safely be destroyed.

smart pointer lack

All that sounds perfect but smart pointer base on usage counter have a big lack : two objects using each other may be never deleted. Each object counter will never reach 0 since each one is used by the other. So each time there is a cycle in the usage graph, the objects of the cycle may never be deleted, depending of the order of the "usage ends".

Garbage collection

Garbage collection is one of most interesting feature of java. And with java, garbage collection, get really run outside from search labs, and is no more just a strange gadget provided with the quite unused SmallTalk.

It seems magic, no need to worry when freeing memory. No more malicious pointers !

But garbage collection collection is not yet efficient enough. It has a heavy cost. It needs a specific thread to search continuously unused objects. And since java does not let programmer decide himself which object manage automatically or not. Then the garbage collector must spent time to compute if objects are deletable even those are strictly local variable. Dynamic memory management is not always useful and so not necessary.

The NaJA tiny garbage collector

using is a relation

When an object use another, the first set the value of one of its property to the second. Such an association is an asymmetric relation between the two objects. To know at each time if an object is used, we can simply search if a relation to it exists. To do so, each active relation must be stored somewhere, in a list. To this list is append a new relation each time an object sets one of its property to another (may be itself). And each time an object is no more used, the corresponding link is removed from the list.

By reading the list at any time, we get a snapshot of memory usage : by following user/used relations a tree can be built. Its root is the main thread. The recursive use problem exposed before can be resolved. To know if an object is really used, no need to count objects using it, but follow relations to search a path to the root. If not any, object can be safely removed.

Then each time a link is removed, if there is no more path from the root to the used object, this one deleted, then all relation where the deleted object is the user are removed, then the used objects of those relations may be removed, and so on recursivley...

partial automatic memory management

Garbage collection has a heavy cost. Maintaining the relations list, navigate inside to search obsolete object need much processing time. And many cases does not require an automatic memory management. NaJA uses smart pointers to add and remove links to the relation list. So you can use the memory manager only when required simply by assigning an object to a NaJA smart pointer. Furthermore, those pointers will be called NaJA references

the NaJA reference

First the NaJA reference must be assigned with the user address to store the left part of the user/used relation. The default is NULL, and NULL means root inside memory manager. Then a value (the used object) can be set to the reference. At this time, a new link is created and inserted to the relation list.

When setting a new value to the reference, the previous one is removed, i.e. the link is deleted and removed from the relation list and a new one from the same user to the new value is inserted. As the previous link is removed the previous value may be deleted (and its used) as exposed earlier.

When the NaJA reference is destroyed (at end of code section or object - usually the user - destroy), its underlying link is removed from the relation list and then, the used object may be deleted...