[Mono-dev] BitVector32 patch

[Debacker]

Hi Scott,

I guess that the objective of your patch is to optimize things, isn't? So,
why did you discard my idea? I have made a simple benchmark:

On my x86 Linux system using 1.9.1, I get the following results:

Benchmark 1

        for(int i = 0 ; i < 2000000000 ; i += 10)
            MostSignificantBit (i);
Loop: 8.097s
Optimized: 1.780s

Thus my code is over 4.5 times faster in average.

Benchmark 2

        for(int i = 0 ; i < 2000000000 ; i += 10)
            MostSignificantBit (i%64);

Loop: 6.088s
Optimized: 3.856s

Still over 1.5 times faster.

Now if there is any technical problem preventing the inclusion of the faster
method, you are welcome to discuss it in this thread.

Laurent.

2008/8/16 Scott Peterson <lunchtimemama at gmail.com>

> OK, this patch just spruces up the HighestSetBit method and fixes the bug.
>
> Index: class/System/System.Collections.Specialized/ChangeLog
> ===================================================================
> --- class/System/System.Collections.Specialized/ChangeLog    (revision
> 109665)
> +++ class/System/System.Collections.Specialized/ChangeLog    (working copy)
> @@ -1,3 +1,10 @@
> +2008-08-06  Scott Peterson  <lunchtimemama at gmail.com>
> +
> +    * BitVector32.cs: Fixed a bug which allowed for invalid sections
> +    to be created with CreateSection. Also simlpified HighestSetBit
> +    algorithm and got rid ofNumberOfSetBits (using HighestSetBit
> +    works just fine).
> +
>  2008-07-31  Jb Evain  <jbevain at novell.com>
>
>      * StringDictionary.cs: remove ComponentModel bits for NET_2_1.
> Index: class/System/System.Collections.Specialized/BitVector32.cs
> ===================================================================
> --- class/System/System.Collections.Specialized/BitVector32.cs    (revision
> 109665)
> +++ class/System/System.Collections.Specialized/BitVector32.cs    (working
> copy)
> @@ -184,11 +184,11 @@
>              if (maxValue < 1)
>                  throw new ArgumentException ("maxValue");
>
> -            int bit = HighestSetBit(maxValue) + 1;
> +            int bit = HighestSetBit(maxValue);
>              int mask = (1 << bit) - 1;
> -            int offset = previous.Offset + NumberOfSetBits
> (previous.Mask);
> +            int offset = previous.Offset + HighestSetBit (previous.Mask);
>
> -            if (offset > 32) {
> +            if (offset + bit > 32) {
>                  throw new ArgumentException ("Sections cannot exceed 32
> bits in total");
>              }
>
> @@ -227,27 +227,12 @@
>          }
>
>          // Private utilities
> -        private static int NumberOfSetBits (int i)
> +        private static int HighestSetBit (int i)
>          {
>              int count = 0;
> -            for (int bit = 0; bit < 32; bit++) {
> -                int mask = 1 << bit;
> -                if ((i & mask) != 0)
> -                    count++;
> -            }
> +            while(i >> count != 0)
> +                count++;
>              return count;
>          }
> -
> -        private static int HighestSetBit (int i)
> -        {
> -            for (int bit = 31; bit >= 0; bit--) {
> -                int mask = 1 << bit;
> -                if ((mask & i) != 0) {
> -                    return bit;
> -                }
> -            }
> -
> -            return -1;
> -        }
>      }
>  }
>
> _______________________________________________
> Mono-devel-list mailing list
> Mono-devel-list at lists.ximian.com
> http://lists.ximian.com/mailman/listinfo/mono-devel-list
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.ximian.com/pipermail/mono-devel-list/attachments/20080816/013ffad6/attachment.html 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ProgramLoop.cs
Type: text/x-csharp
Size: 347 bytes
Desc: not available
Url : http://lists.ximian.com/pipermail/mono-devel-list/attachments/20080816/013ffad6/attachment.bin 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ProgramOptimized.cs
Type: text/x-csharp
Size: 333 bytes
Desc: not available
Url : http://lists.ximian.com/pipermail/mono-devel-list/attachments/20080816/013ffad6/attachment-0001.bin 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ProgramTest.cs
Type: text/x-csharp
Size: 737 bytes
Desc: not available
Url : http://lists.ximian.com/pipermail/mono-devel-list/attachments/20080816/013ffad6/attachment-0002.bin