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
