Re: Garbage collection

Nick Roberts wrote:
> On 23 Aug 2004 12:07:39 -0400, Sebastian <sk@z.pl> wrote:
>>> I find it hard to believe that the designers just gave up on moving
>>> large blocks!
>>
>> Why it is a bad idea? I find it perfectly reasonable. Those objects
>> of course come from another heap, so they don't stand in a way of
>> compaction of smaller stuff.
>
> Yes, but if you don't move large blocks at all, are you not in danger
> of ending up with a lot of (large) unfilled holes?


Well, this holes can be probably filled with somewhat smaller objects. In
typical situations i doubdt that fragmentation is worse than 2x. Copying
collector requires 2x overhead.


>
> I should point out that there are two kinds of problem with holes: (a)
> running out of actual memory; (b) running out of (logical) address
> space. I think it is (b) that is the problem with large holes.


Hmm, unless your system has virtual memory allmost equal in size to logical
address space for applications, then this is prpbably barely a problem. You
can't allocate more memory than swap space + physical mem allows, so even
significant fragmentation in case of such large objects is just
fragmentation of address space. When size of allocatable memory approaches
the size of logical address space compacting is no good either, as you have
no space to copy. Without compacting you can design your app not to cause
too much fragmentation (or at least hope that fragmentation won't be as bad
as 2x) but with compacting you've lost. Compacting system runs out of
memory when half of the address space is filled.


>
>> The main advantage of compacting collector is IMHO extremely fast
>> allocation
>
> Hmmm. Well, that may be an advantage, but isn't the /main/ advantage
> of a compacting collector the fact that it removes holes? Again, the
> problem with these holes may be running out of address space, rather
> than running out of actual memory, but it could be both.


Well, IMHO the hole removal advantage is overestimated. As Hans Boehm points
in the linked article, properly designed non compacting allocator rarely
exhibits fragmentation worse than 2x, while compacting keeps the
fragmentation just at or slightly above (alignment) 2x.


But I have recently profiled C++ application doing a lot of allocations of
rather small objects (the app is an interpreter). To my surpirise the most
significant factor was an allocation.




>> -- but in case of large objects (>=16KB in this case) the more
>> complex allocation from non compactable heap is neglibile in
>> comparison to object initialisation cost. And then moving such large
>> object every time it's generation goes through collection is simply
>> huge and unneded cost.
>
> Well, yes, the cost would be huge if you used REP MOVSD on the data
> itself. I'm suggesting that if you allocate large blocks page aligned,
> you can move them quite quickly by REP MOVSDing in the page tables
> instead.


That requires OS support, I don't know if NT kernel allows for page
movement. As .Net works also on older OS'es (incl. non NT 98 & Millenium)
modifying kernel might not be an option, I guess.
Then unless you have ~2GB of actual virtual memory on 32bit system, logical
address space framgentation is barely an issue and all non allocated pages
are just returned to system.
In case of 64bit enviroments this is not a problem at all.


[snip]
>> http://www.hpl.hp.com/personal/Hans_Boehm/gc/complexity.html
>
> But the criticisms made in this paper (of collection) are based on a
> set of assumptions that Microsoft could not make for all the software
> running under Windows. They could not simply assume that the only
> software requiring garbage collection would be "single-threaded with
> moderately long-lived objects".


Well, but MS didn't take the road describet in the articcle, as they do use
compaction for small objects.




rgds


Sebastian Kaliszewski

Return to the comp.compilers page.
Search the comp.compilers archives again.