This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [patch] bitmap.c: Speed up bitmap_find_bit.
- From: Jeffrey A Law <law at redhat dot com>
- To: Kazu Hirata <kazu at cs dot umass dot edu>
- Cc: gcc-patches at gcc dot gnu dot org
- Date: Thu, 25 Nov 2004 23:56:56 -0700
- Subject: Re: [patch] bitmap.c: Speed up bitmap_find_bit.
- Organization: Red Hat, Inc
- References: <20041125.000527.98558816.kazu@cs.umass.edu>
- Reply-to: law at redhat dot com
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