From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 5716 invoked by alias); 18 Oct 2004 22:25:52 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 5671 invoked from network); 18 Oct 2004 22:25:50 -0000 Received: from unknown (HELO mx1.redhat.com) (66.187.233.31) by sourceware.org with SMTP; 18 Oct 2004 22:25:50 -0000 Received: from int-mx1.corp.redhat.com (int-mx1.corp.redhat.com [172.16.52.254]) by mx1.redhat.com (8.12.11/8.12.10) with ESMTP id i9IMPnaF002794; Mon, 18 Oct 2004 18:25:49 -0400 Received: from [172.16.83.144] (vpn83-144.boston.redhat.com [172.16.83.144]) by int-mx1.corp.redhat.com (8.11.6/8.11.6) with ESMTP id i9IMPmr04018; Mon, 18 Oct 2004 18:25:48 -0400 Subject: Re: [patch] sbitmap.h: Speed up EXECUTE_IF_SET_IN_SBITMAP. From: Jeffrey A Law Reply-To: law@redhat.com To: Kazu Hirata Cc: gcc-patches@gcc.gnu.org In-Reply-To: <20041018.172213.59683982.kazu@cs.umass.edu> References: <20041018.172213.59683982.kazu@cs.umass.edu> Content-Type: text/plain Organization: Red Hat, Inc Message-Id: <1098138347.2915.95.camel@localhost.localdomain> Mime-Version: 1.0 Date: Mon, 18 Oct 2004 22:36:00 -0000 Content-Transfer-Encoding: 7bit X-SW-Source: 2004-10/txt/msg01568.txt.bz2 On Mon, 2004-10-18 at 15:22, Kazu Hirata wrote: > Hi, > > Attached is a patch to speed up EXECUTE_IF_SET_IN_SBITMAP. > > Currently, EXECUTE_IF_SET_IN_SBITMAP tests if a bit is set by using a > construct of the form: > > mask = 1 << bit_num; > if ((word & mask) != 0) > CODE; > > We can improve this by shifting the currently visited word to right in > every iteration like so: > > word >>= 1; > if ((word & 1) != 0) > CODE; > > The patch precisely implements the above improvement. Here are some > advantages over the current version. > > o Two "if"s are gone, namely "if (word_ != 0)" and "if (word_ == 0)" > > o "bit_num_ < SBITMAP_ELT_BITS" is replaced with "word_ != 0" > - equality comparison with 0 is often cheaper. > > o no masking off like "word_ &= ~ _mask;" > - a right shift will take care of killing bits that are behind us. > > o no loading of constant 1 arising from the left shift > - x86 cannot shift 1 without loading it first. > > o 6 lines shorter :-) > > There is no functional change. > > Here is a timing for compiling preprocessed GCC sources with > cc1 -O2 -fomit-frame-pointer -march=athlon-xp -o /dev/null. > > original patched > real: 521.159s 519.647s (0.290% down) > user: 485.607s 484.922s (0.141% down) > > Tested on i686-pc-linux-gnu. OK to apply? > > Kazu Hirata > > 2004-10-18 Kazu Hirata > > * sbitmap.h (EXECUTE_IF_SET_IN_SBITMAP): Speed up by shifting > the currently visited word to right. Approved. Please install. Note you may be able to do similar stuff in bitmap.h as well. THanks, jeff > > Index: sbitmap.h > =================================================================== > RCS file: /cvs/gcc/gcc/gcc/sbitmap.h,v > retrieving revision 1.23 > diff -c -r1.23 sbitmap.h > *** sbitmap.h 15 Oct 2004 14:47:11 -0000 1.23 > --- sbitmap.h 18 Oct 2004 14:21:55 -0000 > *************** > *** 58,87 **** > /* Loop over all elements of SBITSET, starting with MIN. */ > #define EXECUTE_IF_SET_IN_SBITMAP(SBITMAP, MIN, N, CODE) \ > do { \ > ! unsigned int word_num_; \ > unsigned int bit_num_ = (MIN) % (unsigned int) SBITMAP_ELT_BITS; \ > unsigned int size_ = (SBITMAP)->size; \ > SBITMAP_ELT_TYPE *ptr_ = (SBITMAP)->elms; \ > \ > ! for (word_num_ = (MIN) / (unsigned int) SBITMAP_ELT_BITS; \ > ! word_num_ < size_; word_num_++, bit_num_ = 0) \ > { \ > ! SBITMAP_ELT_TYPE word_ = ptr_[word_num_]; \ > ! \ > ! if (word_ != 0) \ > ! for (; bit_num_ < SBITMAP_ELT_BITS; bit_num_++) \ > ! { \ > ! SBITMAP_ELT_TYPE _mask = (SBITMAP_ELT_TYPE) 1 << bit_num_; \ > ! \ > ! if ((word_ & _mask) != 0) \ > ! { \ > ! word_ &= ~ _mask; \ > ! (N) = word_num_ * SBITMAP_ELT_BITS + bit_num_; \ > ! CODE; \ > ! if (word_ == 0) \ > ! break; \ > ! } \ > ! } \ > } \ > } while (0) > > --- 58,81 ---- > /* Loop over all elements of SBITSET, starting with MIN. */ > #define EXECUTE_IF_SET_IN_SBITMAP(SBITMAP, MIN, N, CODE) \ > do { \ > ! unsigned int word_num_ = (MIN) / (unsigned int) SBITMAP_ELT_BITS; \ > unsigned int bit_num_ = (MIN) % (unsigned int) SBITMAP_ELT_BITS; \ > unsigned int size_ = (SBITMAP)->size; \ > SBITMAP_ELT_TYPE *ptr_ = (SBITMAP)->elms; \ > + SBITMAP_ELT_TYPE word_ = ptr_[word_num_] >> bit_num_; \ > \ > ! for (; \ > ! word_num_ < size_; \ > ! word_num_++, bit_num_ = 0, word_ = ptr_[word_num_]) \ > { \ > ! for (; word_ != 0; word_ >>= 1, bit_num_++) \ > ! { \ > ! if ((word_ & 1) != 0) \ > ! { \ > ! (N) = word_num_ * SBITMAP_ELT_BITS + bit_num_; \ > ! CODE; \ > ! } \ > ! } \ > } \ > } while (0) >