Jump to content
  • Advertisement
Sign in to follow this  
Exponent

Confusion about garbage collection and reference counting

This topic is 4812 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello. I've recently come to the decision to change the scripting language in my application from Lua to Squirrel. One of the reasons was because of the supposed performance increase of Squirrel's reference counting techniques used to deallocate unused memory. However, according to this article: http://en.wikipedia.org/wiki/Garbage_collection_(computer_science) reference counting is supposedly much slower then normal garbage collection. So, why is it that the reference counting in Squirrel is better then the garbage collection in Lua?

Share this post


Link to post
Share on other sites
Advertisement
Garbage Collection: unpredictable delays:

Quote:

The primary problems with tracing garbage collection arise from the nature of how it is invoked. A collection cycle can occur at any time and may take an arbitrarily long amount of time. While acceptable in many applications, when timing and quick response are critical, like in real-time computing, it may cause disaster. Incremental garbage collection helps alleviate this problem, but it is still difficult to make hard real-time guarantees.


Reference Counting: predictable (constant) delays:

Quote:

In contrast to garbage collection, reference counting is a form of automatic memory management where each object has a count of the number of references to it, and the object's memory is reclaimed when the count reaches zero.

Reference counting has some advantages: it is easy to implement and its execution time is predictable because there is no need to pause the program to look for unreferenced objects. Whilst in naive implementations a single overwritten reference can cause large numbers of objects to be deallocated, realtime implementations can delay deallocation so that 2 deallocations are made for each allocation, giving realtime performance.

Reference counting is nearly always very much slower than other garbage collection techniques, because of the need to update reference counts whenever a reference is changed, rather than only following references during garbage collection. Reference counting also requires some space in each object. Simple reference counting also fails to reclaim the memory used by data structures that have cycles (such as doubly linked lists), although this is ameliorated somewhat by judicious use of weak pointers.


The "nearly always" comment above probably means net/total time to execute. In a real-time/game application, total-time/net speed is far less important than performance spikes. Even if a GC versioned system was faster than a RC system, it would not be signficant in script code for a game (likewise, although Python is slower than Lua/Squirrel, it does not matter for a game as far more CPU cycles are used elsewhere). Benchmarks would have to be run between GC and RC implementations to find out which method is faster for a particular application. In the case of real-time/games, performance spikes can never be allowed to happen.

When using an RC system and your own custom memory handler, you can free memory N blocks at a time, allowing you to tune performance to your application. Thus RC is better suited for games and can allow more control over performance (and without benchmarks, the "nearly always very much slower" comment is speculation).

Another possible optimization for RC: cache recently freed memory blocks (say N commonly used sizes). New allocations can pull from this cache (which may also be in the CPU cache). This would save more expensive heap alloc/free operations (and may affect performance via the CPU cache).

[Edited by - John Schultz on September 13, 2005 8:58:02 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Exponent
Hello. I've recently come to the decision to change the scripting language in my application from Lua to Squirrel. One of the reasons was because of the supposed performance increase of Squirrel's reference counting techniques used to deallocate unused memory. However, according to this article:
http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)
reference counting is supposedly much slower then normal garbage collection. So, why is it that the reference counting in Squirrel is better then the garbage collection in Lua?


The MS .Net team claimed that *automatic* reference counting was slower than thier garbage collection, which is highly optimized (not 'normal'). And it was only in passing in a newgroup posting IIRC. No hard data to back it up. And the crux of thier problem is that they had to inc/dec *everywere* on every object parameter of every function call.

I wouldn't change your scripting language based on that.

Share this post


Link to post
Share on other sites
Quote:

The MS .Net team claimed that *automatic* reference counting was slower than thier garbage collection, which is highly optimized (not 'normal').

MS .NET uses a generational garbage collector, that reduces spikes compared to a copy collector like Java or mark & sweep like Lua(Lua is switching to a incremental collector in 5.1). A generational collector is far from solving the problem, it has at least as many problems as all the others flavours of GCs.
Generational collectors basically assume that you have many objects that you will keep alive for all the lifetime of you app and certain objects that have a short lifetime. So it keeps different lists of objects(generations) depending for how long they have been in memory. Then scans the younger objects more often than the older objects; If a young objects stays in memory for long enough it gets promoted to an older generation.
The result is better performances in most of the apps and a bounce of annoying artifacts. In our editor that is written in C#, we had to drop the idea of releasing stuff on Finalize() because even if you force the GC to scan the mem 10 times in a row, you cannot be sure that a certain object will be released.
Another GC nightmare is order of deletion, that is completely upredictable. If you have a refcounted C++ system like we have is a major pain in the a%$.

Quote:

reference counting is supposedly much slower then normal garbage collection.

Indeed an RC VM is a bit slower than a GC VM but has the advantage to scale very well with the size of you application.
Squirrel RC is very fast because of the register based architecture(the majority of interepreted languges are stack-machines) and a conservative way to cleanup function's stacks. It also has a backup garbage collector(mosly for debug pouposes) and recently I've added weak references so you can create cycles without locking your mem.

Quote:

So, why is it that the reference counting in Squirrel is better then the garbage collection in Lua?

First Squirrel RC is not better than collection in Lua, in general RC scales better than GC.

ciao
Alberto

Share this post


Link to post
Share on other sites
Reference counting is often used as a form of garbage collection as it has the desired effect. It's main short comings are 1) Inadequate handling of cyclical linkage 2) Continuous run time cost of updating count.

The simple alternative is to store all 'objects' in a big container, start from 'root' objects like globals and locate any reachable object, flag as reachable, then collect all objects that were not flagged. The simple implementation naturally may cause an app to pause as this process occurs.

Incremental garbage collection all but eliminates this pause by spreading the work over time. Incremental collectors can have short comings like unpredictable start and run times, fragmenting memory, and a highly managed (read closed) object model, but most of these things can be avoided with specific implementations. Incremental collectors use a 'read' or 'write barrier' to maintain integrity while pointers are assigned during a collection. This occasionally adds a tiny cost at specific parts of a app run, but only when the collector is running. Most of the time, the collector is idle, waiting for memory limits to be exceeded before restarting. The two reasons a incremental collector could cause a spike are 1) root objects too big and 2) collector mis configured for available memory and work load. Both can be identified and their effect reduced. The reason root objects can be a problem is that they are often traced in one go, whereas the rest of the apps objects may be traced a little at a time.

It is actually possible to make a 'hard' incremental collector, which performs no more than a specific amount of work over a given time (and thus cannot ever cause a performance spike), but these usually need special language or operating system support. (Meaning that retro-fitting into other languages or implementing in closed operating systems is difficult.)

GameMonkey Script and Lua 5.1 both use incremental collectors.

Share this post


Link to post
Share on other sites
Quote:

Reference counting is often used as a form of garbage collection as it has the desired effect. It's main short comings are 1) Inadequate handling of cyclical linkage 2) Continuous run time cost of updating count.

1) really not a biggie(you solve it with weak refs)
2) my profiling on squirrel shows that's very far to be a performance issue(at least in Squirrel).

I did some research in that direction 2 years ago. I actually implemented a incremetal collector in lua 4(three colors). It doesn't really improve things at all, 1) introduces as much work as refcounting; you have to check if you assign an object to a alredy marked one(+ mark&sweep). 2) it needs tweaking based on context(how much mem you got) 3) spikes do not go away because you always have 2 very big objects, A the global object, B the one you use to store C++ references. 4) has all the other artifacts of any other type of collector A random order of deletion, B unpredictable resource deletion, C load dependent performances. 5) debugging it couses permanent brain damage(believe me :) )


ciao
Alberto

[Edited by - fagiano on September 18, 2005 3:33:05 PM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!