Patchwork Speedup bitmap iterators

login
register
mail settings
Submitter Jan Hubicka
Date June 9, 2010, 3:07 p.m.
Message ID <20100609150718.GC15770@kam.mff.cuni.cz>
Download mbox | patch
Permalink /patch/55104/
State New
Headers show

Comments

Jan Hubicka - June 9, 2010, 3:07 p.m.
Hi,
here is updated patch addressing the code duplication.  With __builtin_ctzl
I really believe we should fix it at codegen side if it turns out to be slow
on hosts we care about.  It is codegen bug, __builtin_ctzl exists for this
purpose IMO.

On i386 the codegen is good even if the topmost bit is usually set. It is
slower than test+jcc case but not by that big margin.  I might make some
statistics on average amount of bits skipped, but build time testing+oprofiling
definitly didn't found any regression here. 

Honza

	* bitmap.h (bmp_iter_next_bit): New.
	(bmp_iter_set, bmp_iter_and, bmp_iter_and_compl):
	Use it.
Richard Guenther - June 9, 2010, 3:18 p.m.
On Wed, Jun 9, 2010 at 5:07 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
> Hi,
> here is updated patch addressing the code duplication.  With __builtin_ctzl
> I really believe we should fix it at codegen side if it turns out to be slow
> on hosts we care about.  It is codegen bug, __builtin_ctzl exists for this
> purpose IMO.
>
> On i386 the codegen is good even if the topmost bit is usually set. It is
> slower than test+jcc case but not by that big margin.  I might make some
> statistics on average amount of bits skipped, but build time testing+oprofiling
> definitly didn't found any regression here.

This is ok if it bootstraps & regtests.  Please let other maintainers
the chance to complain thouhg.

Thanks,
Richard.

> Honza
>
>        * bitmap.h (bmp_iter_next_bit): New.
>        (bmp_iter_set, bmp_iter_and, bmp_iter_and_compl):
>        Use it.
> Index: bitmap.h
> ===================================================================
> --- bitmap.h    (revision 160447)
> +++ bitmap.h    (working copy)
> @@ -385,6 +385,27 @@ bmp_iter_next (bitmap_iterator *bi, unsi
>   *bit_no += 1;
>  }
>
> +/* Advance to first set bit in BI.  */
> +
> +static inline void
> +bmp_iter_next_bit (bitmap_iterator * bi, unsigned *bit_no)
> +{
> +#if (GCC_VERSION >= 3004)
> +  {
> +    unsigned int n = __builtin_ctzl (bi->bits);
> +    gcc_assert (sizeof (unsigned long) == sizeof (BITMAP_WORD));
> +    bi->bits >>= n;
> +    *bit_no += n;
> +  }
> +#else
> +  while (!(bi->bits & 1))
> +    {
> +      bi->bits >>= 1;
> +      *bit_no += 1;
> +    }
> +#endif
> +}
> +
>  /* Advance to the next nonzero bit of a single bitmap, we will have
>    already advanced past the just iterated bit.  Return true if there
>    is a bit to iterate.  */
> @@ -396,11 +417,7 @@ bmp_iter_set (bitmap_iterator *bi, unsig
>   if (bi->bits)
>     {
>     next_bit:
> -      while (!(bi->bits & 1))
> -       {
> -         bi->bits >>= 1;
> -         *bit_no += 1;
> -       }
> +      bmp_iter_next_bit (bi, bit_no);
>       return true;
>     }
>
> @@ -443,11 +460,7 @@ bmp_iter_and (bitmap_iterator *bi, unsig
>   if (bi->bits)
>     {
>     next_bit:
> -      while (!(bi->bits & 1))
> -       {
> -         bi->bits >>= 1;
> -         *bit_no += 1;
> -       }
> +      bmp_iter_next_bit (bi, bit_no);
>       return true;
>     }
>
> @@ -510,11 +523,7 @@ bmp_iter_and_compl (bitmap_iterator *bi,
>   if (bi->bits)
>     {
>     next_bit:
> -      while (!(bi->bits & 1))
> -       {
> -         bi->bits >>= 1;
> -         *bit_no += 1;
> -       }
> +      bmp_iter_next_bit (bi, bit_no);
>       return true;
>     }
>
>
Joseph S. Myers - June 9, 2010, 8:46 p.m.
On Wed, 9 Jun 2010, Jan Hubicka wrote:

> Hi,
> here is updated patch addressing the code duplication.  With __builtin_ctzl

Not an objection to this patch as there are several existing cases of this 
issue, but I think scattering GCC_VERSION conditionals across the source 
tree (a few places also have __GNUC__ conditionals) is bad style.  It 
would be better to define inline functions, or macros describing if a 
language feature is supported, in one place (with appropriate conditionals 
in their definitions) and use them everywhere.  toplev.h has an example of 
this with definitions of floor_log2 and exact_log2, though on the whole I 
think system.h would be a better place for a central collection of such 
definitions - it has some already.
Paolo Bonzini - June 9, 2010, 10:37 p.m.
On 06/09/2010 10:46 PM, Joseph S. Myers wrote:
> On Wed, 9 Jun 2010, Jan Hubicka wrote:
>
>> Hi,
>> here is updated patch addressing the code duplication.  With __builtin_ctzl
>
> Not an objection to this patch as there are several existing cases of this
> issue, but I think scattering GCC_VERSION conditionals across the source
> tree (a few places also have __GNUC__ conditionals) is bad style.

There are also a number of comparisons GCC_VERSION >= 3400 which, while 
working in practice (only 3.4 is filtered out), are wrong.

Paolo

Patch

Index: bitmap.h
===================================================================
--- bitmap.h	(revision 160447)
+++ bitmap.h	(working copy)
@@ -385,6 +385,27 @@  bmp_iter_next (bitmap_iterator *bi, unsi
   *bit_no += 1;
 }
 
+/* Advance to first set bit in BI.  */
+
+static inline void
+bmp_iter_next_bit (bitmap_iterator * bi, unsigned *bit_no)
+{
+#if (GCC_VERSION >= 3004)
+  {
+    unsigned int n = __builtin_ctzl (bi->bits);
+    gcc_assert (sizeof (unsigned long) == sizeof (BITMAP_WORD));
+    bi->bits >>= n;
+    *bit_no += n;
+  }
+#else
+  while (!(bi->bits & 1))
+    {
+      bi->bits >>= 1;
+      *bit_no += 1;
+    }
+#endif
+}
+
 /* Advance to the next nonzero bit of a single bitmap, we will have
    already advanced past the just iterated bit.  Return true if there
    is a bit to iterate.  */
@@ -396,11 +417,7 @@  bmp_iter_set (bitmap_iterator *bi, unsig
   if (bi->bits)
     {
     next_bit:
-      while (!(bi->bits & 1))
-	{
-	  bi->bits >>= 1;
-	  *bit_no += 1;
-	}
+      bmp_iter_next_bit (bi, bit_no);
       return true;
     }
 
@@ -443,11 +460,7 @@  bmp_iter_and (bitmap_iterator *bi, unsig
   if (bi->bits)
     {
     next_bit:
-      while (!(bi->bits & 1))
-	{
-	  bi->bits >>= 1;
-	  *bit_no += 1;
-	}
+      bmp_iter_next_bit (bi, bit_no);
       return true;
     }
 
@@ -510,11 +523,7 @@  bmp_iter_and_compl (bitmap_iterator *bi,
   if (bi->bits)
     {
     next_bit:
-      while (!(bi->bits & 1))
-	{
-	  bi->bits >>= 1;
-	  *bit_no += 1;
-	}
+      bmp_iter_next_bit (bi, bit_no);
       return true;
     }