Re: [PATCH 2/3] Free large chunks in ggc

[Andi Kleen <andi@firstfloor.org>]

On Sun, Oct 23, 2011 at 12:24:46PM +0200, Richard Guenther wrote:
> >> space in the free list afterward we free it back on the next GC cycle.
> >> Then if there's a malloc or other allocator later it can grab
> >> the address space we freed.
> >>
> >> That was done to address your earlier concern.
> >>
> >> This will only happen on ggc_collect of course.
> >>
> >> So one difference from before the madvise patch is that different
> >> generations of free pages can accumulate in the freelist. Before madvise
> >> the freelist would never contain more than one generation.
> >> Normally it's sorted by address due to the way GC works, but there's no
> >> attempt to keep the sort order over multiple generations.
> >>
> >> The "free in batch" heuristic requires sorting, so it will only
> >> work if all the pages are freed in a single gc cycle.
> >>
> >> I considered sorting, but it seemed to be too slow.
> >>
> >> I can expand the comment on that.
> >
> > Ah, now I see ... but that's of course bad - I expect large regions to be
> > free only after multiple collections.  Can you measure what sorting would
> > make for a difference?
> 
> I wonder if the free list that falls out of a single collection is sorted

The original author seemed to have assumed it is usually. The 
allocation part tries hard to insert sorted. So I thought it 
was ok to assume.

I stuck in an assert now nd it triggers in a bootstrap on the large
files, so it's not always true (so my earlier assumption was not fully correct)

I suppose it's just another heuristic which is often enough true.

So madvise may not may have it made that much worse.

> (considering also ggc_free) - if it is, building a new one at each collection

ggc_free does not put into the freelist I believe.

> and then merging the two sorted lists should be reasonably fast.

It's definitely not O(1). Ok one could assume it's usually sorted
and do a merge sort with max one pass only. But I'm sceptical 
it's worth the effort, at least without anyone having a test case.
At least for 64bit it's not needed anyways.

-Andi