From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 20055 invoked by alias); 5 Mar 2013 14:48:24 -0000 Received: (qmail 20033 invoked by uid 22791); 5 Mar 2013 14:48:22 -0000 X-SWARE-Spam-Status: No, hits=-6.4 required=5.0 tests=AWL,BAYES_00,KHOP_RCVD_UNTRUST,KHOP_THREADED,RCVD_IN_DNSWL_HI,RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from cantor2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 05 Mar 2013 14:48:13 +0000 Received: from relay1.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id D8EF8A525A; Tue, 5 Mar 2013 15:48:11 +0100 (CET) Date: Tue, 05 Mar 2013 14:48:00 -0000 From: Michael Matz To: Richard Biener Cc: Steven Bosscher , GCC Patches , Jeff Law Subject: Re: [patch][RFC] bitmaps as lists *or* trees In-Reply-To: Message-ID: References: User-Agent: Alpine 2.00 (LNX 1167 2008-08-23) MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-IsSubscribed: yes 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: 2013-03/txt/msg00182.txt.bz2 Hi, On Tue, 5 Mar 2013, Richard Biener wrote: > > I haven't tested this patch at all, except making sure that it > > compiles. Just posting this for discussion, and for feedback on the > > idea. I know there have been many others before me who've tried > > different data structures for bitmaps, perhaps someone has already > > tried this before. > > Definitely a nice idea. Iteration should be easy to implement (without > actually splaying for each visited bit), the bit operations can use the > iteration as building block as well then. Iteration isn't easy on trees without a pointer to the parent (i.e. enlarging each node), you need to remember variably sized context in the iterator (e.g. the current stack of nodes). I do like the idea of reusing the same internal data structure to implement the tree. And I'm wondering about performance impact, I wouldn't be surprised either way (i.e. that it brings about a large improvement, or none at all), most bitmap membership tests in GCC are surprisingly clustered so that the bitmaps cache of last accessed element can work its magic (not all of them, as the testcase shows of course :) ). Ciao, Michael.