From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 3331 invoked by alias); 5 Mar 2013 12:32:37 -0000 Received: (qmail 3319 invoked by uid 22791); 5 Mar 2013 12:32:35 -0000 X-SWARE-Spam-Status: No, hits=-5.0 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-we0-f182.google.com (HELO mail-we0-f182.google.com) (74.125.82.182) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 05 Mar 2013 12:32:29 +0000 Received: by mail-we0-f182.google.com with SMTP id t57so6057966wey.41 for ; Tue, 05 Mar 2013 04:32:28 -0800 (PST) MIME-Version: 1.0 X-Received: by 10.180.84.162 with SMTP id a2mr18168781wiz.14.1362486748576; Tue, 05 Mar 2013 04:32:28 -0800 (PST) Received: by 10.194.56.100 with HTTP; Tue, 5 Mar 2013 04:32:28 -0800 (PST) In-Reply-To: References: Date: Tue, 05 Mar 2013 12:32:00 -0000 Message-ID: Subject: Re: [patch][RFC] bitmaps as lists *or* trees From: Richard Biener To: Steven Bosscher Cc: GCC Patches , Michael Matz , 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/msg00175.txt.bz2 On Tue, Mar 5, 2013 at 1:00 PM, Steven Bosscher wrote: > Hello, > > A recurring problem with GCC's sparse bitmap data structure is that it > performs poorly for random access patterns. Such patterns result in > linked-list walks, and can trigger behavior quadratic in the number of > linked-list member elements in the set. > > The attached patch is a first stab at an idea I've had for a while: > Implement a "change of view" for bitmaps, such that a bitmap can be > either a linked list, or a binary tree. I've implemented this idea > with top-down splay trees because splay tree nodes do not need > meta-data on (unlike e.g. color for RB-trees, rank for AVL trees, > etc.) and top-down splay tree operations are very simple to implement > (less than 200 lines of code). As far as I'm aware, this is the first > attempt at allowing different views on bitmaps. The idea came from > Andrew Macleod's tree-ssa-live implementation. > > The idea is to convert the bitmap to a tree view if the set > represented by the bitmap is mostly used for membership testing, and > not for iterations over the items (as e.g. for bitmap dataflow). A > typical example of this is e.g. invalid_mode_changes, which just > explodes for the test case of PR55135 at -O0. > > 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. Now, an instrumented bitmap to identify bitmaps that would benefit from the tree view would be nice ;) [points-to sets are never modified after being computed, but they are both random-tested and intersected] What I missed often as well is a reference counted shared bitmap implementation (we have various special case implementations). I wonder if that could even use shared sub-trees/lists of bitmap_elts. Richard. > Ciao! > Steven