Olav Sandstaa <[EMAIL PROTECTED]> writes:
> Daniel John Debrunner wrote:
>> [EMAIL PROTECTED] 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
