* [patch] sbitmap.h: Speed up EXECUTE_IF_SET_IN_SBITMAP.
@ 2004-10-18 21:35 Kazu Hirata
2004-10-18 22:36 ` Jeffrey A Law
2004-10-19 23:21 ` Richard Henderson
0 siblings, 2 replies; 7+ messages in thread
From: Kazu Hirata @ 2004-10-18 21:35 UTC (permalink / raw)
To: gcc-patches
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 <kazu@cs.umass.edu>
* sbitmap.h (EXECUTE_IF_SET_IN_SBITMAP): Speed up by shifting
the currently visited word to right.
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)
^ permalink raw reply [flat|nested] 7+ messages in thread* Re: [patch] sbitmap.h: Speed up EXECUTE_IF_SET_IN_SBITMAP.
2004-10-18 21:35 [patch] sbitmap.h: Speed up EXECUTE_IF_SET_IN_SBITMAP Kazu Hirata
@ 2004-10-18 22:36 ` Jeffrey A Law
2004-10-18 22:45 ` Zdenek Dvorak
2004-10-19 23:21 ` Richard Henderson
1 sibling, 1 reply; 7+ messages in thread
From: Jeffrey A Law @ 2004-10-18 22:36 UTC (permalink / raw)
To: Kazu Hirata; +Cc: gcc-patches
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 <kazu@cs.umass.edu>
>
> * 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)
>
^ permalink raw reply [flat|nested] 7+ messages in thread* Re: [patch] sbitmap.h: Speed up EXECUTE_IF_SET_IN_SBITMAP.
2004-10-18 22:36 ` Jeffrey A Law
@ 2004-10-18 22:45 ` Zdenek Dvorak
0 siblings, 0 replies; 7+ messages in thread
From: Zdenek Dvorak @ 2004-10-18 22:45 UTC (permalink / raw)
To: Jeffrey A Law; +Cc: Kazu Hirata, gcc-patches
Hello,
> > 2004-10-18 Kazu Hirata <kazu@cs.umass.edu>
> >
> > * 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.
not so straightforwardly (I made similar change there already when I
rewrote EXECUTE_IF_SET_IN_BITMAP to iterator style). However some
functions in bitmap.c could definitely be improved (somewhere deep in
history of gcc-patches probably still lives my patch that made them
some 40% or so faster, IIRC).
Zdenek
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [patch] sbitmap.h: Speed up EXECUTE_IF_SET_IN_SBITMAP.
2004-10-18 21:35 [patch] sbitmap.h: Speed up EXECUTE_IF_SET_IN_SBITMAP Kazu Hirata
2004-10-18 22:36 ` Jeffrey A Law
@ 2004-10-19 23:21 ` Richard Henderson
2004-10-20 2:26 ` Kazu Hirata
1 sibling, 1 reply; 7+ messages in thread
From: Richard Henderson @ 2004-10-19 23:21 UTC (permalink / raw)
To: Kazu Hirata; +Cc: gcc-patches
On Mon, Oct 18, 2004 at 05:22:13PM -0400, Kazu Hirata wrote:
> 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_]; \
[...]
> + SBITMAP_ELT_TYPE word_ = ptr_[word_num_] >> bit_num_; \
Previously, setting MIN arbitrarily large would not read from PTR;
now it does. I think this is a faulty translation of this function.
r~
^ permalink raw reply [flat|nested] 7+ messages in thread* Re: [patch] sbitmap.h: Speed up EXECUTE_IF_SET_IN_SBITMAP.
2004-10-19 23:21 ` Richard Henderson
@ 2004-10-20 2:26 ` Kazu Hirata
2004-10-21 1:33 ` Kazu Hirata
2004-10-22 19:51 ` Jeffrey A Law
0 siblings, 2 replies; 7+ messages in thread
From: Kazu Hirata @ 2004-10-20 2:26 UTC (permalink / raw)
To: rth; +Cc: gcc-patches
Hi Richard,
> > 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_]; \
> [...]
> > + SBITMAP_ELT_TYPE word_ = ptr_[word_num_] >> bit_num_; \
>
> Previously, setting MIN arbitrarily large would not read from PTR;
> now it does. I think this is a faulty translation of this function.
oops. I found another problem of accessing PTR beyond its end. Note
that I check for the end condition *after* I increment word_num and
get a new word_ like so.
for (; \
word_num_ < size_; \
word_num_++, bit_num_ = 0, word_ = ptr_[word_num_]) \
I'll be testing the patch below shortly. The end result is a bit
ugly, but there shouldn't be any performance loss. OK to apply if
testing passes?
Kazu Hirata
2004-10-19 Kazu Hirata <kazu@cs.umass.edu>
* sbitmap.h (EXECUTE_IF_SET_IN_SBITMAP): Don't access PTR
beyond its end.
Index: sbitmap.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/sbitmap.h,v
retrieving revision 1.24
diff -c -r1.24 sbitmap.h
*** sbitmap.h 18 Oct 2004 23:56:18 -0000 1.24
--- sbitmap.h 20 Oct 2004 02:06:38 -0000
***************
*** 62,80 ****
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)
--- 62,87 ----
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_; \
\
! if (word_num_ < size_) \
{ \
! word_ = ptr_[word_num_] >> bit_num_; \
! \
! while (1) \
{ \
! for (; word_ != 0; word_ >>= 1, bit_num_++) \
{ \
! if ((word_ & 1) != 0) \
! { \
! (N) = word_num_ * SBITMAP_ELT_BITS + bit_num_; \
! CODE; \
! } \
} \
+ word_num_++; \
+ if (word_num_ >= size_) \
+ break; \
+ bit_num_ = 0, word_ = ptr_[word_num_]; \
} \
} \
} while (0)
^ permalink raw reply [flat|nested] 7+ messages in thread* Re: [patch] sbitmap.h: Speed up EXECUTE_IF_SET_IN_SBITMAP.
2004-10-20 2:26 ` Kazu Hirata
@ 2004-10-21 1:33 ` Kazu Hirata
2004-10-22 19:51 ` Jeffrey A Law
1 sibling, 0 replies; 7+ messages in thread
From: Kazu Hirata @ 2004-10-21 1:33 UTC (permalink / raw)
To: rth; +Cc: gcc-patches
Hi Richard,
> * sbitmap.h (EXECUTE_IF_SET_IN_SBITMAP): Don't access PTR
> beyond its end.
I tested this on i686-pc-linux-gnu. OK to apply?
Kazu Hirata
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [patch] sbitmap.h: Speed up EXECUTE_IF_SET_IN_SBITMAP.
2004-10-20 2:26 ` Kazu Hirata
2004-10-21 1:33 ` Kazu Hirata
@ 2004-10-22 19:51 ` Jeffrey A Law
1 sibling, 0 replies; 7+ messages in thread
From: Jeffrey A Law @ 2004-10-22 19:51 UTC (permalink / raw)
To: Kazu Hirata; +Cc: rth, gcc-patches
On Tue, 2004-10-19 at 20:10, Kazu Hirata wrote:
> Hi Richard,
>
> > > 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_]; \
> > [...]
> > > + SBITMAP_ELT_TYPE word_ = ptr_[word_num_] >> bit_num_; \
> >
> > Previously, setting MIN arbitrarily large would not read from PTR;
> > now it does. I think this is a faulty translation of this function.
>
> oops. I found another problem of accessing PTR beyond its end. Note
> that I check for the end condition *after* I increment word_num and
> get a new word_ like so.
>
> for (; \
> word_num_ < size_; \
> word_num_++, bit_num_ = 0, word_ = ptr_[word_num_]) \
>
> I'll be testing the patch below shortly. The end result is a bit
> ugly, but there shouldn't be any performance loss. OK to apply if
> testing passes?
>
> Kazu Hirata
>
> 2004-10-19 Kazu Hirata <kazu@cs.umass.edu>
>
> * sbitmap.h (EXECUTE_IF_SET_IN_SBITMAP): Don't access PTR
> beyond its end.
This is OK assuming it passed regression testing.
jeff
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2004-10-22 19:33 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2004-10-18 21:35 [patch] sbitmap.h: Speed up EXECUTE_IF_SET_IN_SBITMAP Kazu Hirata
2004-10-18 22:36 ` Jeffrey A Law
2004-10-18 22:45 ` Zdenek Dvorak
2004-10-19 23:21 ` Richard Henderson
2004-10-20 2:26 ` Kazu Hirata
2004-10-21 1:33 ` Kazu Hirata
2004-10-22 19:51 ` Jeffrey A Law
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).