[patch] bitmap.c: Speed up bitmap_find_bit.

[Kazu Hirata <kazu at cs dot umass dot edu>]

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.

Index: bitmap.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/bitmap.c,v
retrieving revision 1.62
diff -c -d -p -r1.62 bitmap.c
*** bitmap.c	24 Nov 2004 15:26:16 -0000	1.62
--- bitmap.c	24 Nov 2004 15:33:12 -0000
*************** bitmap_find_bit (bitmap head, unsigned i
*** 421,434 ****
        || head->indx == indx)
      return head->current;
  
!   if (head->indx > indx)
      for (element = head->current;
  	 element->prev != 0 && element->indx > indx;
  	 element = element->prev)
        ;
  
    else
!     for (element = head->current;
  	 element->next != 0 && element->indx < indx;
  	 element = element->next)
        ;
--- 421,446 ----
        || head->indx == indx)
      return head->current;
  
!   if (head->indx < indx)
!     /* INDX is beyond head->indx.  Search from head->current
!        forward.  */
!     for (element = head->current;
! 	 element->next != 0 && element->indx < indx;
! 	 element = element->next)
!       ;
! 
!   else if (head->indx / 2 < indx)
!     /* INDX is less than head->indx and closer to head->indx than to
!        0.  Search from head->current backward.  */
      for (element = head->current;
  	 element->prev != 0 && element->indx > indx;
  	 element = element->prev)
        ;
  
    else
!     /* INDX is less than head->indx and closer to 0 than to
!        head->indx.  Search from head->first forward.  */
!     for (element = head->first;
  	 element->next != 0 && element->indx < indx;
  	 element = element->next)
        ;