Mailing-List: contact derby-dev-help@db.apache.org; run by ezmlm
Precedence: bulk
Reply-To: <derby-dev@db.apache.org>
Received-SPF: pass (herse.apache.org: local policy)
Date: Tue, 12 Dec 2006 18:44:20 +0100
From: Olav Sandstaa <Olav.Sandstaa@Sun.COM>
Subject: Re: Some questions about FormatableBitSet
In-reply-to: <457D8CDB.1070600@apache.org>
Sender: Olav.Sandstaa@Sun.COM
To: derby-dev@db.apache.org
Message-id: <457EEA74.5050503@sun.com>
Organization: Sun Microsystems - Trondheim, Norway
MIME-version: 1.0
Content-type: text/plain; format=flowed; charset=ISO-8859-1
Content-transfer-encoding: 7BIT
References: <x1o3psaru4w7.fsf@sun.com> <457D8CDB.1070600@apache.org>
User-Agent: Thunderbird 1.5.0.5 (X11/20060730)

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.

Olav