Implementing reference counting or life without GC (almost)
Good day, Habr!
Many people think that the system language and the garbage collector are incompatible concepts. In some situations, indeed, the collector may cause some problems.
As you most likely know , in D the garbage collector is partly optional. But manual memory management is the last century.
Therefore, today I will show how you can implement garbage collection yourself through a “semi-automatic” reference counting, as well as at the same time minimize calls to the built-in garbage collection runtime based on memory scanning.
')
We will solve the problem of counting references to pointers, classes and arrays.
Two things should be discussed right away: why we will not completely reject GC in this article and why reference counting is “semi-automatic”.
A complete rejection of GC implies the use of the @nogc attribute for the entire code, but there is one BUT. The
Reference counting will be “semi-automatic”, since at this stage of language development it is impossible to automatically execute some code when transferring or assigning reference types (classes and arrays), therefore we will call this code ourselves, but we will try to make it as hidden as possible.
Let's start with the implementation of allocator.
At the core of our allocator is the
Such an approach allows using existing classes without modification, since information on the number of links is stored outside the object.
Now we can create and destroy class objects and pointers using our allocator.
Already something, but for the time being it is not interesting: only make increments the counter for us, then increment and decriminalize it ourselves.
Add a wrapper that will do some things for us.
Now we have scope-dependent reference counting and we can do this:
This is already something! But what about the arrays? Add work with arrays to our allocator:
And we implement a wrapper for arrays.
but there are some fundamental points:
Also in the destructor there is a small logical hack: let's say we only have a cut of the array, and the wrapper on the original array has sunk into oblivion. Then it turns out that the reference counter for
All this together allows us to do these things:
Although the code is not marked asdon’t touch and don’t smell, don’t excrete through GC and it will not collect.
That's all, I hope you have something new podcherpnuli)
The code is designed as a dub package.
Sorts on github .
This is not a finished library, but for now just a sketch, it requires many more improvements.
I would be very happy to help, if not by deed, so by advice.
Many people think that the system language and the garbage collector are incompatible concepts. In some situations, indeed, the collector may cause some problems.
As you most likely know , in D the garbage collector is partly optional. But manual memory management is the last century.
Therefore, today I will show how you can implement garbage collection yourself through a “semi-automatic” reference counting, as well as at the same time minimize calls to the built-in garbage collection runtime based on memory scanning.
')
We will solve the problem of counting references to pointers, classes and arrays.
Two things should be discussed right away: why we will not completely reject GC in this article and why reference counting is “semi-automatic”.
A complete rejection of GC implies the use of the @nogc attribute for the entire code, but there is one BUT. The
IAllocator interface, which we will use, allows us to create and destroy class instances correctly with a single command (correctly, calling all constructors and all destructors of the class hierarchy), but the functions that do this are not marked as @nogc and not to inflate the article implement them independently (partly in the last article it was considered).Reference counting will be “semi-automatic”, since at this stage of language development it is impossible to automatically execute some code when transferring or assigning reference types (classes and arrays), therefore we will call this code ourselves, but we will try to make it as hidden as possible.
Let's start with the implementation of allocator.
static this() { RC.affixObj = allocatorObject(RC.affix); } // struct RC { static: alias affix = AffixAllocator!(Mallocator,size_t,size_t).instance; // IAllocator affixObj; // auto make(T,A...)( auto ref A args ) { return incRef( affixObj.make!T(args) ); } // , private void dispose(T)( T* p ) { affixObj.dispose(p); } private void dispose(T)( T p ) if( is(T == class) || is(T == interface) ) { affixObj.dispose(p); } // affix.prefix( void[] p ), p -- , // , ref size_t refCount(T)( T p ) if( is(T == class) || is(T == interface) ) { return affix.prefix( (cast(void*)p)[0..__traits(classInstanceSize,T)] ); } ref size_t refCount(T)( T* p ) { return affix.prefix( (cast(void*)p)[0..T.sizeof] ); } // , auto incRef(T)( auto ref T p ) { if( p is null ) return null; refCount(p)++; return p; } // , , null 0 auto decRef(T)( T p ) { if( p is null ) return null; if( refCount(p) > 0 ) { refCount(p)--; if( refCount(p) == 0 ) { dispose(p); return null; } } return p; } } At the core of our allocator is the
Mallocator , an allocator that works through C-shny malloc and free . We wrapped it in AffixAllocator . It is parameterized by the present real allocator and 2 data types. When allocating AffixAllocator allocate a little more: the size of the Prefix and Suffix types (respectively, the second and third template parameters). As you can guess, the prefix is ​​located before the memory allocated for the object, and the suffix after. In our case, Prefix and Suffix are size_t , and just the prefix will impersonate the reference count.Such an approach allows using existing classes without modification, since information on the number of links is stored outside the object.
Now we can create and destroy class objects and pointers using our allocator.
auto p = RC.make!int( 10 ); assert( is( typeof(p) == int* ) ); assert( *p == 10 ); assert( RC.refCount(p) == 1 ); p = RC.decRef(p); assert( p is null ); Already something, but for the time being it is not interesting: only make increments the counter for us, then increment and decriminalize it ourselves.
Add a wrapper that will do some things for us.
struct RCObject(T) { T obj; alias obj this; // , obj RCObject this(this) { incRef(); } // -- this( T o ) { obj = o; incRef(); } // -- // ( RC.make) package static auto make( T o ) { RCObject!T ret; ret.obj = o; return ret; } // nothrow std.experimental.allocator ~this() nothrow { if( obj is null ) return; try decRef(); catch(Exception e) { import std.experimental.logger; try errorf( "ERROR: ", e ); catch(Exception e) {} } } void incRef() { if( obj is null ) return; RC.incRef(obj); } /// obj void decRef() { if( obj is null ) return; assert( refCount > 0, "not null object have 0 refs" ); obj = RC.decRef(obj); } size_t refCount() @property const { if( obj is null ) return 0; return RC.refCount(obj); } // , void opAssign(X=this)( auto ref RCObject!T r ) { decRef(); obj = r.obj; incRef(); } /// T, void opAssign(X=this)( auto ref T r ) { decRef(); obj = r; incRef(); } } // auto rcMake(T,A...)( A args ){ return RCObject!(T).make( RC.make!T(args) ); } Now we have scope-dependent reference counting and we can do this:
static class Ch { } { RCObject!Ch c; { auto a = rcMake!Ch(); assert( a.refCount == 1 ); auto b = a; assert( a.refCount == 2 ); assert( b.refCount == 2 ); c = a; assert( a.refCount == 3 ); assert( b.refCount == 3 ); assert( c.refCount == 3 ); b = rcMake!Ch(); assert( a.refCount == 2 ); assert( b.refCount == 1 ); assert( c.refCount == 2 ); b = rcMake!Ch(); // , assert( a.refCount == 2 ); assert( b.refCount == 1 ); assert( c.refCount == 2 ); } assert( c.refCount == 1 ); } This is already something! But what about the arrays? Add work with arrays to our allocator:
... T[] makeArray(T,A...)( size_t length ) { return incRef( affixObj.makeArray!T(length) ); } T[] makeArray(T,A...)( size_t length, auto ref T init ) { return incRef( affixObj.makeArray!T(length,init) ); } private void dispose(T)( T[] arr ) { affixObj.dispose(arr); } ref size_t refCount(T)( T[] arr ) { return affix.prefix( cast(void[])arr ); } ... And we implement a wrapper for arrays.
It is not much different from object wrapping.
struct RCArray(T) { // , private T[] orig; // T[] work; private void init( T[] origin, T[] slice ) { if( slice !is null ) assert( slice.ptr >= origin.ptr && slice.ptr < origin.ptr + origin.length, "slice is not in original" ); orig = origin; incRef(); work = slice is null ? orig : slice; static if( isRCType!T ) // foreach( ref w; work ) w.incRef; // } /// alias work this; this(this) { incRef(); } this( T[] orig, T[] slice=null ) { init( orig, slice ); } /// no increment ref package static auto make( T[] o ) { RCArray!T ret; ret.orig = o; ret.work = o; return ret; } // auto opSlice( size_t i, size_t j ) { return RCArray!T( orig, work[i..j] ); } void opAssign(X=this)( auto ref RCArray!T arr ) { decRef(); init( arr.orig, arr.work ); } void incRef() { if( orig is null ) return; RC.incRef(orig); } void decRef() { if( orig is null ) return; assert( refCount > 0, "not null object have 0 refs" ); orig = RC.decRef(orig); } size_t refCount() @property const { if( orig is null ) return 0; return RC.refCount(orig); } ~this() { if( refCount ) { // if( refCount == 1 ) { static if( isRCType!T ) foreach( ref w; orig ) if( w.refCount ) w.incRef; } static if( isRCType!T ) // foreach( ref w; work ) w.decRef; decRef; } } } template isRCType(T) { static if( is( TE == RCObject!X, X ) || is( TE == RCArray!X, X ) ) enum isRCType = true; else enum isRCType = false; } but there are some fundamental points:
- in a wrapper for arrays we store an array of allocated memory and a working slice
- in the constructor, if the elements are wrappers, increase the reference count for the elements of the working slice
- in the destructor in the same situation we reduce
Also in the destructor there is a small logical hack: let's say we only have a cut of the array, and the wrapper on the original array has sunk into oblivion. Then it turns out that the reference counter for
orig is 1, which means that if the serse is also deleted, then dispose will be called for the original ( orig ) array, this will result in objects taken from the original array but not falling into will reduce the number of references and can be deleted. To prevent this from happening, we add +1 to each element that already has more than 1. Then there will be a decrease in the working set, this will allow to leave 1 more for the elements of the original array that were not included in the working set and when the original array was deleted, their counter will not reach zero.All this together allows us to do these things:
class A { int no; this( int i ) { no=i; } } alias RCA = RCObject!A; { RCA obj; { RCArray!RCA tmp1; { RCArray!RCA tmp2; { auto arr = rcMakeArray!RCA(6); foreach( int i, ref a; arr ) a = rcMake!A(i); assert( arr[0].refCount == 1 ); assert( arr[1].refCount == 1 ); assert( arr[2].refCount == 1 ); assert( arr[3].refCount == 1 ); assert( arr[4].refCount == 1 ); assert( arr[5].refCount == 1 ); tmp1 = arr[1..4]; assert( arr[0].refCount == 1 ); assert( arr[1].refCount == 2 ); assert( arr[2].refCount == 2 ); assert( arr[3].refCount == 2 ); assert( arr[4].refCount == 1 ); assert( arr[5].refCount == 1 ); tmp2 = arr[3..5]; assert( arr[0].refCount == 1 ); assert( arr[1].refCount == 2 ); assert( arr[2].refCount == 2 ); assert( arr[3].refCount == 3 ); assert( arr[4].refCount == 2 ); assert( arr[5].refCount == 1 ); obj = tmp2[0]; assert( arr[0].refCount == 1 ); assert( arr[1].refCount == 2 ); assert( arr[2].refCount == 2 ); assert( arr[3].refCount == 4 ); assert( arr[4].refCount == 2 ); assert( arr[5].refCount == 1 ); } assert( tmp1[0].refCount == 1 ); assert( tmp1[1].refCount == 1 ); assert( tmp1[2].refCount == 3 ); assert( obj.refCount == 3 ); assert( tmp2[0].refCount == 3 ); assert( tmp2[0].obj.no == 3 ); assert( tmp2[1].refCount == 1 ); assert( tmp2[1].obj.no == 4 ); } assert( tmp1[0].refCount == 1 ); assert( tmp1[1].refCount == 1 ); assert( tmp1[2].refCount == 2 ); assert( obj.refCount == 2 ); } assert( obj.refCount == 1 ); } // 3 Although the code is not marked as
@nogc , it does not refer to the embedded GC. And as we know, That's all, I hope you have something new podcherpnuli)
The code is designed as a dub package.
Sorts on github .
This is not a finished library, but for now just a sketch, it requires many more improvements.
I would be very happy to help, if not by deed, so by advice.
Source: https://habr.com/ru/post/304074/
All Articles