This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [patch] bitmap.c: Speed up bitmap_find_bit.


On Thu, 2004-11-25 at 00:05 -0500, Kazu Hirata wrote:
> Hi,
> 
> Attached is a patch to speed up bitmap_find_bit.
> 
> Currently, bitmap_find_bit always traverses from head->current.  This
> approach tends to be slow if the we are looking for a bit that's
> closer to the beginning of the bitmap than to the "current element" of
> the bitmap.
> 
> The patch adds another way of traversal, namely from head->first.  We
> choose to traverse from head->first when the index of the element that
> contains the bit we are after is less than half of head->indx.
> 
> Here is a timing in seconds on three runs of "./cc1 -quiet -O2
> -fomit-frame-pointer -o /dev/null insn-attrtab.i".
> 
>       original patched
> real:  130.082 128.257 (1.422% down)
> user:  127.122 126.173 (0.752% down)
> 
> Here is a timing in seconds on three runs of "./cc1 -quiet -O2
> -fomit-frame-pointer -o /dev/null fold-const.i".
> 
>       original patched
> real:   27.416  27.013 (1.491% down)
> user:   27.062  26.618 (1.668% down)
> 
> I measured how many times next and prev are followed in
> bitmap_find_bit.  Without this patch, both forward and backward
> following occur about 8 million times each on insn-attrtab.i, so I
> expected my patch to cut down the backward search by half, i.e. the
> total saving of 25%.  It turns out that the forward following from
> head->first and the backward following occur 1.5 million times each,
> the total saving of 45%.  This was rather surprising to me.  Maybe
> elements cluster around the beginning and somewhere else with a "hole"
> in between.
> 
> Nathan kindly looked at this patch and told me on IRC that this patch
> would not interfere with his ongoing work to improve bitmap.
> 
> Tested on i686-pc-linux-gnu.  OK to apply?
> 
> Kazu Hirata
> 
> 2004-11-25  Kazu Hirata  <kazu@cs.umass.edu>
> 
> 	* bitmap.c (bitmap_find_bit): Speed up by traversing from
> 	head->first if that seems profitable.
Approved.
jeff



Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]