From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 16055 invoked by alias); 6 Mar 2013 18:07:36 -0000 Received: (qmail 16039 invoked by uid 22791); 6 Mar 2013 18:07:35 -0000 X-SWARE-Spam-Status: No, hits=-5.2 required=5.0 tests=AWL,BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,KHOP_RCVD_TRUST,KHOP_THREADED,RCVD_IN_DNSWL_LOW,RCVD_IN_HOSTKARMA_YE X-Spam-Check-By: sourceware.org Received: from mail-ve0-f178.google.com (HELO mail-ve0-f178.google.com) (209.85.128.178) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 06 Mar 2013 18:07:29 +0000 Received: by mail-ve0-f178.google.com with SMTP id db10so7008095veb.9 for ; Wed, 06 Mar 2013 10:07:28 -0800 (PST) X-Received: by 10.52.240.237 with SMTP id wd13mr9926175vdc.18.1362593248245; Wed, 06 Mar 2013 10:07:28 -0800 (PST) MIME-Version: 1.0 Received: by 10.58.237.1 with HTTP; Wed, 6 Mar 2013 10:06:48 -0800 (PST) In-Reply-To: <20130306160622.GC27815@atrey.karlin.mff.cuni.cz> References: <20130306160227.GB27815@atrey.karlin.mff.cuni.cz> <20130306160622.GC27815@atrey.karlin.mff.cuni.cz> From: Steven Bosscher Date: Wed, 06 Mar 2013 18:07:00 -0000 Message-ID: Subject: Re: [patch][RFC] bitmaps as lists *or* trees To: Jan Hubicka Cc: Michael Matz , Richard Biener , GCC Patches , Jeff Law Content-Type: text/plain; charset=ISO-8859-1 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/msg00266.txt.bz2 On Wed, Mar 6, 2013 at 5:06 PM, Jan Hubicka wrote: > And for the RFC, i also find it interesting experiment. I implemented some > time ago splay tree based bitmap with API same as bitmap's but never attempted > to put it to mainline since Danny introduced his ebitmap and there was a lot of > discussion about whether one needs more than one bitmap in the compiler. I Right, I think the ebitmap.c experiment shows that there is *not* room for another bitmap implementation. This is why I developed these splay-tree bitmaps using the same data structures as the existing linked-list sparse bitmaps: Not another bitmap, just another way of looking at the existing bitmap. I required that changing the view of the bitmap from linked-list to splay tree and vv. to be almost free. > never experimented with bitmap.c change itself, just tested that replacing all > bitmaps by tree based ones causes quite some memory consumption on RA side > (with old RA) because bitmaps are pretty good for regsets they were introduced > for. Memory consumption as in higher peak memory? That cannot happen with my splay-tree bitmaps. They take exactly the same amount of memory, independent of whether the current view on the bitmap is linked-list or splay tree. As for cache behavior or number of memory operations (loads, stores) I think this is directly correlated to the lookup success ratio, hence the access pattern, and so if the right view on the bitmap is selected for the right circumstances then the number of memory ops should also be no worse in splay tree view than in linked-list view. Another idea I'm currently (right now on gcc17 ;-) working on, is a trivial speed-up for bitmaps used as regsets. The idea is that bitmap_find_bit should look at head->first if head->current is not the element containing the sought bit, and *not* update head->current if head->first is the right element. This speeds up regsets because a common access pattern is to look at sets containing both pseudos and hardregs, and on most targets all hardregs are in head->first. Not updating head->current preserves a pointer to the latest accessed pseudos. I'll implement this idea and come back with some timings. Ciao! Steven