What kind of memory reclamation algorithm does MRI Ruby 1.8 use?

Question

In other languages you have a number of possibilities usually for memory reclamation:

• Mark objects and then remove them
• Explicit retain and release
• Count references to objects
• Internal heap disposition

How does Ruby work?

Answer 1

Ruby's GC uses the mark-and-sweep strategy.

Answer 2

"conservative mark and sweep"

See this thread which includes Matz' description, which ought to be definitive.

Answer 3

The garbage collector Ruby 1.8 is actually quite awful. Every 7Mb of allocation it will perform a mark phase from all root objects and try to find which can be reached. Those that cannot be reached will be freed.

However, to find out what objects are reachable, it checks the stack, the registers and the allocated object memory. This allows for some false positives but eases writing C extensions: C extensions don't have to reference and deference, since the stack and so on which C extensions used are automatically scanned.

Furthermore, the state of the object (referenced or not) is kept in the state of each object. This is quite bad for cache behavior and copy-on-write behaviour: a lot of cache lines are touched during this process, and ruby interpreters do not share as much memory as they could if you've got more then one (relevant for server deployment like Ruby on Rails). Therefore, other implementations exists (Ruby Enterprise Edition) which do this in a separate part of the memory to speed GC up.

Also a problem are long linked lists. Since mark-and-sweep uses the stack to do the recursion, a long linked lists segfaults ruby.

The GC does also no compaction and this becomes problematic in the long run.

If you run JRuby however, those problems will disappear while keeping Ruby 1.8 compatibility to some extend.