db-derby-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Dyre.Tjeldv...@Sun.COM
Subject Re: Some questions about FormatableBitSet
Date Wed, 13 Dec 2006 10:04:54 GMT
Olav Sandstaa <Olav.Sandstaa@Sun.COM> writes:

> Daniel John Debrunner wrote:
>> Dyre.Tjeldvoll@Sun.COM wrote:
>>> - A minor nit: This class appears to do a lot of division and
>>>   remainder calculations with powers of 2 (frequently 8). Is it not
>>>   generally preferably to do this with shifts and  bitwise ANDs?
>>
>> I prefer the approach that leads to code that is easy to understand.
>> If the purpose of the code is to divide by two I prefer clear code like:
>>
>>   a = b / 2;
>>
>> to
>>
>>   a = b >> 1;
>>
>> Good compilers typically compile multiplication down to shift
>> instructions, why have the human do it?
>
> I too prefer code that is easy to read. Still, you are more likely to
> get the compiler to produce more efficient code when you use language
> constructs that you know are easy to map to efficient instructions on
> the underlying hardware.
>
> As a small experiment I took the two code pieces above and ran them in
> a tight loop to see if the compiler was able to optimize these to the
> same set of machine instructions. The test code looked like this:
>
>   static int divtest(int a)
>   {
>      int i;
>      for (i=0; i<1000000; ++i) {
>          a = a / 2;
>          /*a = a >> 1;*/
>      }
>      return a;
>   }
>
> Running this code compiled with two C-compilers and three Java
> compilers/VMs gave the following results:
>
>                       a = a / 2      a = a >> 1
> GCC                      1.94           0.77
> Sun Studio 11            1.54           0.51
> Sun JDK 5                1.55           0.38
> Sun JDK 6                1.55           0.38
> IBM SDK 5                1.26           0.38
>
>
> All numbers are in milliseconds and is the amount if time it took to
> run the above function once (in the test I measured amount if time it
> took to run the function 10.000 times).
>
> Basically, with these compilers and this example code doing the
> division by two is about 3-4 times as costly as using a shift
> operator. (And since these measurments also account for the code for
> the for-loop, the real difference between the division and the shift
> operation is probably closer to 10x).
>
> So in this example none of the compilers were able to map the division
> by two to as efficient code as produces by the >> 1 operation. Why?
> Because the compiler did not know what I knew: The number to do the
> operation on was always a positive integer.
>
> And given that this is code that Dyre refers to is an implementation
> for an operations on bit sets I do not see it as a problem that the
> code is implemented by utilizing "bit manipulation operations",
> particularly if the optimizations are well commented.

Wow, thank you for the thorough investigation! I stand corrected, it is not
a _nit_ it is actually rather important... :)

-- 
dt


Mime
View raw message