Re: IRHG - GC Memory Fragmentation?

Thnaks for the input !

I have continued to dig inside Ruby GC, which by the way
IS a modified "Bohem/Demers collector".  One thing I have
discovered, and pulling out whats left of hair, is that  that the
GC seems to allocate in two different areas?
----------------------------------------------------
I stopped here because I had a thought "if there was nothing
in the Ruby code to explain it -- What about 'malloc' ?? "

Well, experimentally it  obviously  does put different  SIZES
of allocation in DIFFERENT LOCATIONS in the heap memory!

That of course make sense!  I have never looked at malloc
that close!   I have been programming for 30 years - assembly
and 'C' - and the Ruby Core List keeps me reading tech books.

You would think I would know it all at this point, sigh  :-).

Kurt Stephens wrote:
>
> 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
>
>
>
>
>
>