Re: IRHG - GC Memory Fragmentation?

Charles Thornton wrote:
> While working on Chapter 05  and referencing various works
> on Garbage Collection, I keep seeing that Mark & Sweep are
> considered to have a problem with memory fragmentation.
>
> Since I have not seen any complaints on this subject on the core
> list, I am wondering if there is something inherent about Ruby
> that prevents major fragmentation.
>
> For example, since all basic ruby objects are the same size, does
> this help reduce fragmentation of the GC space?
>
>                 Chuck
>                 [e-mail]
>
My $0.03:

Ruby objects, like Strings and Vectors, explicitly allocate
dynamically-sized regions, well as the hash tables underneath all the
basic object structures.  Mark and sweep collectors always suffer from
fragmentation because order of allocation and reclamation does not imply
locality; page utilization can become sparser overtime, esp if page
allocations are not segmented by object size and free regions are not
aggressively scanned for best-fit during reallocation or scavenging.

Ruby (appears to) allocate its memory from the OS via malloc(), which
can lead to two levels of fragmentation, depending on the implementation
of malloc();  power-of-two allocators have notoriously poor actual
memory utilization.  Given the lack of comments in Ruby's gc.c, its hard
to tell if Ruby's GC does anything special about the fragmentation
issues with mark-sweep.

I recommend reading the proceedings from the ISMM
(http://www.cs.kent.ac.uk/people/staff/rej/ismm2008/) over the last ten
years and other papers on Lisp system design over the last 20 years.
http://www.memorymanagement.org/ has some helpful information.

There's a great book called "Topics in Advanced Language Implementation"
MIT Press, 1991 that provides a good overview of different automatic
memory managers and their context in programming languages.

My money is on the developments of efficient write barriers that allow
the allocate, mark, scan, reclaim phases to occur concurrently with very
minimal stopping of the world .

http://kurtstephens.com/pub/tredmill/current/src/tredmill/ is a
prototype implementation of a Treadmill allocator that uses color- and
size-segmented lists to concurrently allocate, mark, scan and reclaim
objects in the same thread.  It requires compiler-generated (or
hand-written) calls to a write-barrier to recolor mutated objects that
have been previous marked or scanned.  OS pages are segmented by
allocation size,  making the write-barrier computation reasonably simple.

Unfortunately, it would be difficult to use with Ruby due to Ruby's C
foreign-function interface.  FFIs to C greatly complicate modern memory
management techniques.  SUN's first Java implementations used mark-sweep
until it was clear that it does not perform well for long-running server
processes.  I believe Sun's Java now uses indirection handles to hide a
generational, copying collector from FFI C code. (I could be wrong on
this, I dislike Java too much to care about it :)

I'd like to see how well Ruby would perform using the Bohem/Demers
collector.  Don't get me started about Ruby using a 0x01 type tag for
Fixnums. :)

Kurt Stephens
http://kurtstephens.com