From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 11507 invoked by alias); 23 Oct 2011 17:31:50 -0000 Received: (qmail 11491 invoked by uid 22791); 23 Oct 2011 17:31:48 -0000 X-SWARE-Spam-Status: No, hits=-2.3 required=5.0 tests=AWL,BAYES_00,RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from one.firstfloor.org (HELO one.firstfloor.org) (213.235.205.2) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Sun, 23 Oct 2011 17:31:29 +0000 Received: by one.firstfloor.org (Postfix, from userid 503) id 155411A9803E; Sun, 23 Oct 2011 19:31:27 +0200 (CEST) Date: Sun, 23 Oct 2011 20:03:00 -0000 From: Andi Kleen To: Richard Guenther Cc: Andi Kleen , gcc-patches@gcc.gnu.org, Andi Kleen Subject: Re: [PATCH 2/3] Free large chunks in ggc Message-ID: <20111023173127.GC1980@one.firstfloor.org> References: <1319176370-26071-1-git-send-email-andi@firstfloor.org> <1319176370-26071-3-git-send-email-andi@firstfloor.org> <20111021183058.GC22535@one.firstfloor.org> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: User-Agent: Mutt/1.4.2.2i Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org X-SW-Source: 2011-10/txt/msg02103.txt.bz2 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