Sunday, November 26, 2006

When profiling MonoTorrent (under MS.NET, i haven't managed to get profiling under mono working yet. That should lead to a nice comparison), i noticed that about 85% (or more) of my ongoing allocations are due to the 100's of asynchronous sending and receiving methods that i fire every second. For example, if i set my download rate to 400kB/sec, there would be ~200 socket.BeginReceive calls every second. Add in a few BeginSend's and that's quite a lot of calls being fired.

Now, the thing is that when each of those operations finishes there is a bit of managed overhead to allow my callback to be executed (such as System.Net.Sockets.OverlappedAsyncResult, System.Threading.ExecutionContext etc). Now, these allocations are all pretty short term, 95% of them will be cleared up during the next garbage collection. The only ones that won't be cleared up are ones for connections that are running at that moment in time.

Now, it struck me then that wouldn't it be nice if there was a way of detecting "temporary" variables and being able to deallocate them immediately when they go out of scope. This way some items could be destroyed practically immediately after a method ends which reduces the work the GC has to do and reduces the memory overhead of having objects hanging around that arent going to be used more than once.

Take this method for an example:
public void Example()
{
MyObject a = new MyObject(15);
a.DoACalculation();
Console.WriteLine(a.ResultFromCalculation);
return;
}

Now, it should be possible to do a scan and see that an object 'a' is instantiated, then it is only used to calculate a value (for example 15*15+15) and then print that result to the console. A reference to the object never leaves the scope of the method, therefore the object could be classified as a "Fast GC Object" and could be deallocated as soon as the "return" statement is hit.

Also, take a look at this.
public void Example2()
{
using(MainForm form = new MainForm())
form.ShowModal();
return;
}

In this case, *everything* to do with that form could be GC'ed as soon as the return statement is hit. These "Fast GC" objects would never need to be tracked by the GC as such as it is known at the JIT stage when each object will be allocated and when each object will be destroyed.

Now, i've been told that this idea is nothing new (and i'm not surprised). The art of deciding what objects can be GC'ed fast is known as Escape Analysis. The question is, what is the real world benefit for this kind of Garbage Collection. Does it provide an appreciable difference to overall memory usage? Does it reduce time spent in Garbage Collection? Is it exceptionally difficult to implement? Can the JIT be modified to generate this kind of code?

It should be possible to do a mockup to test the theory without changing anything in the Mono runtime. It should be possible to take the bytecode for any .NET application and run a program on it which will check which methods have objects which can be fast GC'ed. Once this data has been stored, the application being tested can be run with a profiler attached which just monitors how many times each method is hit during normal use.

With the knowledge of how many times each method is being hit and which objects are able to be fast GC'ed it should be possible to calculate what the benefit would be to use this new method of garbage collection. A statistic like 50% of all object allocations could be changed to be "Fast GC Objects" would be nice. Then again, if the realworld statistics said that 95% of applications would have less than 5% of their objects suitable for "Fast GC" would mean this method is near useless.

7 comments:

Anonymous said...

Mmmmm, wait a moment:

public void Example()
{
MyObject a = new MyObject(15);
a.DoACalculation();
Console.WriteLine(a.ResultFromCalculation);
return;
}

What happens if DoACalculation function creates a new thread that launches and passes it the reference to the a variable? Then we would be in the case where reaching the return statement, the a object should not be collected.

Is it really possible to fast-collect an object?

Alan said...

Well, that's why you need an algorithm to test what objects can actually be fast collected. If DoACalculation passed a reference outside the scope of the method, then that object would definately *not* be fast collectable.

However if the object were defined like this:

public MyObject()
{
private int number;

public MyObject(int number)
{
this.number = number;
}

public int DoACalculation()
{
return this.number*this.number;
}
}

then this object would definitely be fast collectable.


Another scenario: Assume MethodA creates the object above and passes it to MethodB which performs the calculation there. This object would still be fast collectable at the end of MethodA (assuming that MethodB doesn't pass the object completely out of its scope).

Anonymous said...

Well I guess you know the saying: Never try to outsmart the GC ;)
I doubt that you would get a lot from it. A more simple method for improvement would be making some of the classes structs (for some it should be possible without much hassle). Structs don't put pressure on the GC...

Unknown said...

You don't know if MyObject (now or at some point in the future is modified to) save a reference to it self in some class variable or give a reference of itself away. Think singleton pattern, object cache or pool. Therefor you probably need to go to a full GC algorithm to check if the object is truly free and short lived.

I think your observation is addressed by the new GC that is being developed. It is (among other things) a Generational Collector and treat short lived objects differently than long lived objects (defined as objects that have survived a single collection). Here the assumption is that objects are either very short lived or they are quite long lived and most objects are very short lived. Therefore, if an object isn't very short lived, there is no need to try to GC it as often. http://www.mono-project.com/Compacting_GC

Barry Kelly said...

When doing something similar on the .NET platform with BeginReceive & other sundry long-running IO routines that take byte buffers, I allocate slices of buffers out of manually managed heaps, where the byte buffers are large enough to force allocation from the LOH (large object heap, anything >80000 bytes in .NET).

That way, there's no GC needed since GC allocations aren't being made.

Anonymous said...

There is another optimization where potentially long lived objects are promoted straight into the mature part of the heap (generations 2 and 3 in the MS collector). This is called pretenuring; check out Pretenuring for Java.

Alan said...

Well, i've been giving this a lot of thought and i've come to realise that what i really want is a real-time garbage collector. One that collects as soon as all references to an object are dropped.

Of course, i have no idea of the logistics involved in that, so i wont even pretend to know how hard it'd be to do right. Still, it would be nice... :p

Hit Counter