GC experiments. Writing my own GC.

[Adam Sakareassen via Digitalmars-d]

Hi all,

As a learning exercise I've just been doing some experimenting with 
rewriting the garbage collection code, and thought I might share some of 
the initial results.  I only program as a hobby these days, and I'm 
certainly no expert, but I thought some people might find it interesting.

My interest started because I wrote a LR1 file parser in D.  I then 
multi threaded the application so multiple files could be parsed 
simultaneously. (Disk IO was all on one thread). To my surprise, the 
through-put dropped significantly.  I could process the files a lot 
faster using only one thread.   It turns out the delays were due to my 
liberal use of the “new” statement.  Rather than block allocate the 
memory I thought I would just hack the GC.  So I cleared out gc.d in the 
runtime and started again.  The basic plan was to make it more 
multi-thread friendly.  Already I have learnt quite a lot. There are a 
number of things I would do differently if I tried another re-write. 
However so far it has been a good learning experience.

Currently, allocations are all working, and the mark phase is running. 
It still will not sweep and free the memory.

All memory allocations are entirely lock free (using CAS instructions). 
  So a pre-empted thread will never block another.   For allocations of 
less than 128 bytes, each thread is allocated memory from it's own 
memory pool to avoid false sharing on the CPU's cache.   The collector 
component runs on a background thread using a mark and sweep algorithm 
which is basically the same as the existing algorithm.  Currently the 
thread will wake up every 100ms and decide if a collection should be 
performed.  An emergency collection will run in the foreground if a 
memory allocation fails during that period.

The mark phase needs to stop the world.  The sweeping portion of the 
collection will run in the background.   This is similar to the current 
implementation as the world is restarted after the mark phase, however 
the thread doing the collection will not allocate the requested memory 
to the calling thread until after the sweep has completed.  This means 
that single threaded applications always wait for the full garbage 
collection cycle.

So far allocation speed seems to have improved.  I can't test collection 
speed as it's not complete.  As a test I wrote a simple function that 
allocates a linked list of 2 million items.  This function is then 
spawned by 20 threads.  This test script is shown below.  Timing for 
allocation (with GC disabled) is as follows.  (Using DMD 2.065)

Existing GC code:  15700ms (average)
My GC code:   500ms (Average)

When performing the same amount of allocations on a single thread, the 
new code is still slightly faster than the old.

What this demonstrates is that the locking mechanisms in the current GC 
code is a huge overhead for multi threaded applications that perform a 
lot of memory allocations.  (ie.  Use the “new” operator or dynamic 
arrays.)

It would be nice to see the default GC and memory allocator improved. 
There is certainly room for improvement on the allocator end which may 
mask some of the performance issues associated with garbage collection.

In the future I think D needs to look at making collection precise.  It 
would not be too hard to adjust the mark and sweep GC to be nearly 
precise.  The language needs to support precise GC before things like 
moving garbage collection become feasible.

Anyway, I just thought I'd share the results of my experimenting.  I 
would be happy to make the code available in a few weeks time.  Perhaps 
someone might find is useful.  I need to get it finished and tested 
first. :-)

Cheers!
Adam

------
//Test script that generated these results:
import std.stdio;
import std.datetime;
import std.concurrency;
import core.memory;

class LinkedList{
	long value =0;
	LinkedList next;
}

shared int threadCount = 0;

void main(){
	core.memory.GC.disable();
	auto start = Clock.currSystemTick();

	foreach(i; 0 .. 20){
		auto tid = spawn(&doSomething, thisTid);
		threadCount++;
	}
		
	while(threadCount >0){};
	
	auto ln = Clock.currSystemTick() - start;
	writeln(ln.msecs, "ms");
}

void doSomething(Tid tid){
	auto top = new LinkedList;
	auto recent = top;

	//Create the linked list
	foreach(i; 1 .. 2_000_000){
		auto newList = new LinkedList;
		newList.value = i;
		recent.next = newList;
		recent = newList;
	}
	
	//Sum the values.  (Just spends some time walking the memory).
	recent = top;
	long total=0;
	while(recent !is null){
		total += recent.value;
		recent = recent.next;
	}
	writeln("Total : ", total );
	threadCount--;
}