From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 19857 invoked by alias); 19 Feb 2008 21:02:16 -0000 Received: (qmail 19842 invoked by uid 22791); 19 Feb 2008 21:02:14 -0000 X-Spam-Check-By: sourceware.org Received: from nikam-dmz.ms.mff.cuni.cz (HELO nikam.ms.mff.cuni.cz) (195.113.20.16) by sourceware.org (qpsmtpd/0.31) with ESMTP; Tue, 19 Feb 2008 21:01:32 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 29025) id 000335BA17; Tue, 19 Feb 2008 22:01:29 +0100 (CET) Date: Tue, 19 Feb 2008 22:30:00 -0000 From: Zdenek Dvorak To: Diego Novillo Cc: gcc-patches@gcc.gnu.org, Aldy Hernandez Subject: Re: [tuples] Remove 'next' and 'prev' fields in gimple_statement_base Message-ID: <20080219210129.GA2793@kam.mff.cuni.cz> References: <20080219201031.GA15913@kam.mff.cuni.cz> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.9i 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: 2008-02/txt/msg00799.txt.bz2 Hi, > On Tue, Feb 19, 2008 at 12:10 PM, Zdenek Dvorak wrote: > > > So although for the moment it is probably better to keep things simple > > and consistent and make the branch work for now, it moving prev & next > > back to gimple_base would probably be an useful future project, > > Yeah, though instead of keeping a double-linked structure I want to > explore the idea of using a variant of arrays. With that we can > totally remove next and prev, keep close to constant time iteration > and have efficient insertion/removal in the middle. One alternative I > looked at are tiered vectors > (http://citeseer.ist.psu.edu/519744.html), which looked half-decent > (but I haven't really tested them). > > If that fails, I guess we can always go back to moving next/prev into > gimple itself. my guess is that basic blocks are so short on average that overhead of anything fancier than linked list or simple array would dominate any possible gains (and simple arrays are not feasible due to quadratic behavior on long basic blocks, making linked lists the best choice). But of course one would need to try some alternatives to be sure, Zdenek