[PATCH 1/2] bitreversal program

[PATCH 1/2] bitreversal program

[Soumyadip Das Mahapatra]

--- a/include/linux/bitrev.h    2008-04-17 08:19:44.000000000 +0530
+++ b/include/linux/bitrev.h    2008-05-19 21:49:46.000000000 +0530
@@ -3,11 +3,32 @@

  #include <linux/types.h>

-extern u8 const byte_rev_table[256];
+/**
+ * Here is a generalised bit reversal program
+ * @x: word to get bits reversed
+ * @k: key, explained below
+ * for k = 31, it reverses the bits of word(32 bit)
+ * for k = 24, it reverses the bytes in word
+ * for k = 7, it reverses the bits in every byte without
+ * changing the positions of bytes in a word
+ * and for k = 16 it swaps the left and right halves of a
+ * word
+ */

-static inline u8 bitrev8(u8 byte)
+static inline u32 gen_bit_rev(u32 x, u32 k)
  {
-       return byte_rev_table[byte];
+       if(k & 1)
+               x = (x & 0x55555555) << 1 | (x & 0xaaaaaaaa) >> 1;
+       if(k & 2)
+               x = (x & 0x33333333) << 2 | (x & 0xcccccccc) >> 2;
+       if(k & 4)
+               x = (x & 0x0f0f0f0f) << 4 | (x & 0xf0f0f0f0) >> 4;
+       if(k & 8)
+               x = (x & 0x00ff00ff) << 8 | (x & 0xff00ff00) >> 8;
+       if(k & 16)
+               x = (x & 0x0000ffff) << 16 | (x & 0xffff0000) >> 16;
+
+       return x;
  }

  extern u32 bitrev32(u32 in);

-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.

Re: [PATCH 1/2] bitreversal program

[Harvey Harrison]

On Mon, 2008-05-19 at 19:04 +0200, Soumyadip Das Mahapatra wrote:
> --- a/include/linux/bitrev.h    2008-04-17 08:19:44.000000000 +0530
> +++ b/include/linux/bitrev.h    2008-05-19 21:49:46.000000000 +0530
> @@ -3,11 +3,32 @@
> 
>   #include <linux/types.h>
> 
> -extern u8 const byte_rev_table[256];
> +/**
> + * Here is a generalised bit reversal program
> + * @x: word to get bits reversed
> + * @k: key, explained below
> + * for k = 31, it reverses the bits of word(32 bit)
> + * for k = 24, it reverses the bytes in word
> + * for k = 7, it reverses the bits in every byte without
> + * changing the positions of bytes in a word
> + * and for k = 16 it swaps the left and right halves of a
> + * word
> + */
> 
> -static inline u8 bitrev8(u8 byte)

What about anybody who currently uses bitrev8?

> +static inline u32 gen_bit_rev(u32 x, u32 k)
>   {
> -       return byte_rev_table[byte];
> +       if(k & 1)
> +               x = (x & 0x55555555) << 1 | (x & 0xaaaaaaaa) >> 1;
> +       if(k & 2)
> +               x = (x & 0x33333333) << 2 | (x & 0xcccccccc) >> 2;
> +       if(k & 4)
> +               x = (x & 0x0f0f0f0f) << 4 | (x & 0xf0f0f0f0) >> 4;
> +       if(k & 8)
> +               x = (x & 0x00ff00ff) << 8 | (x & 0xff00ff00) >> 8;
> +       if(k & 16)
> +               x = (x & 0x0000ffff) << 16 | (x & 0xffff0000) >> 16;
> +
> +       return x;
>   }

Why is this better than a single 256 byte table?

Harvey

Re: [PATCH 1/2] bitreversal program

[John Hubbard]

Harvey Harrison wrote:

>> +static inline u32 gen_bit_rev(u32 x, u32 k)
>>   {
>> -       return byte_rev_table[byte];
>> +       if(k & 1)
>> +               x = (x & 0x55555555) << 1 | (x & 0xaaaaaaaa) >> 1;
>> +       if(k & 2)
>> +               x = (x & 0x33333333) << 2 | (x & 0xcccccccc) >> 2;
>> +       if(k & 4)
>> +               x = (x & 0x0f0f0f0f) << 4 | (x & 0xf0f0f0f0) >> 4;
>> +       if(k & 8)
>> +               x = (x & 0x00ff00ff) << 8 | (x & 0xff00ff00) >> 8;
>> +       if(k & 16)
>> +               x = (x & 0x0000ffff) << 16 | (x & 0xffff0000) >> 16;
>> +
>> +       return x;
>>   }
> 
> Why is this better than a single 256 byte table?
> 
> Harvey
> 

One reason it could be better, at least in some situations, is that the 
above is more likely to execute directly from the CPU's instruction 
cache. The table lookup appears more efficient at first, until you 
consider the memory caching hierarchy.

--John Hubbard

Re: [PATCH 1/2] bitreversal program

[Soumyadip Das Mahapatra]

On Mon, 19 May 2008, Harvey Harrison wrote:

> On Mon, 2008-05-19 at 19:04 +0200, Soumyadip Das Mahapatra wrote:
>> --- a/include/linux/bitrev.h    2008-04-17 08:19:44.000000000 +0530
>> +++ b/include/linux/bitrev.h    2008-05-19 21:49:46.000000000 +0530
>> @@ -3,11 +3,32 @@
>>
>>   #include <linux/types.h>
>>
>> -extern u8 const byte_rev_table[256];
>> +/**
>> + * Here is a generalised bit reversal program
>> + * @x: word to get bits reversed
>> + * @k: key, explained below
>> + * for k = 31, it reverses the bits of word(32 bit)
>> + * for k = 24, it reverses the bytes in word
>> + * for k = 7, it reverses the bits in every byte without
>> + * changing the positions of bytes in a word
>> + * and for k = 16 it swaps the left and right halves of a
>> + * word
>> + */
>>
>> -static inline u8 bitrev8(u8 byte)
>
> What about anybody who currently uses bitrev8?
>
>> +static inline u32 gen_bit_rev(u32 x, u32 k)
>>   {
>> -       return byte_rev_table[byte];
>> +       if(k & 1)
>> +               x = (x & 0x55555555) << 1 | (x & 0xaaaaaaaa) >> 1;
>> +       if(k & 2)
>> +               x = (x & 0x33333333) << 2 | (x & 0xcccccccc) >> 2;
>> +       if(k & 4)
>> +               x = (x & 0x0f0f0f0f) << 4 | (x & 0xf0f0f0f0) >> 4;
>> +       if(k & 8)
>> +               x = (x & 0x00ff00ff) << 8 | (x & 0xff00ff00) >> 8;
>> +       if(k & 16)
>> +               x = (x & 0x0000ffff) << 16 | (x & 0xffff0000) >> 16;
>> +
>> +       return x;
>>   }
>
> Why is this better than a single 256 byte table?
>
> Harvey
>
>
> -- 
> This message has been scanned for viruses and
> dangerous content by MailScanner, and is
> believed to be clean.
>
>

Thanks for reviewing Harvey :-)
please look at the line below
>> -static inline u8 bitrev8(u8 byte)
It is a static function, so you cant use it from outside of this
file. So there should not be anyone using this function.

>Why is this better than a single 256 byte table?

Why store those things if stuffs can be done in smoother and cleaner
(using less memeory ofcourse) way!

-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.

Re: [PATCH 1/2] bitreversal program

[Akinobu Mita]

>>> -static inline u8 bitrev8(u8 byte)
>
> It is a static function, so you cant use it from outside of this
> file. So there should not be anyone using this function.
>

bitrev8() is static inline function in header file.
There are several users:

./drivers/isdn/gigaset/asyncdata.c
./drivers/isdn/gigaset/isocdata.c
./drivers/isdn/hisax/st5481_b.c
./drivers/rtc/rtc-s35390a.c
...

Re: [PATCH 1/2] bitreversal program

[Soumyadip Das Mahapatra]

Thanks for giving a reply Akinobu :-)
I forgot that bitrev8() is static in header file. Sorry for that.

Below is my new patch considering this. Cant it be applicable?
Please review it.

I know that my bitrev8() takes more instructions than that
of yours. But we have to think about faster access of cpu cache over that
of memory cache(which your bit_rev_table uses).

Thanks anyway ;-)

---Inline Attachment---
--- a/include/linux/bitrev.h    2008-04-17 08:19:44.000000000 +0530
+++ b/include/linux/bitrev.h    2008-05-20 20:41:13.000000000 +0530
@@ -3,11 +3,49 @@

  #include <linux/types.h>

-extern u8 const byte_rev_table[256];
+/**
+ * Here is a generalised bit reversal program
+ * @x: word to get bits reversed
+ * @k: key, explained below
+ * for k = 31, it reverses the bits of word(32 bit)
+ * for k = 24, it reverses the bytes in word
+ * for k = 7, it reverses the bits in every byte without
+ * changing the positions of bytes in a word
+ * and for k = 16 it swaps the left and right halves of a
+ * word
+ */
+
+static inline u32 gen_bit_rev(u32 x, u32 k)
+{
+       if(k & 1)
+               x = (x & 0x55555555) << 1 | (x & 0xaaaaaaaa) >> 1;
+       if(k & 2)
+               x = (x & 0x33333333) << 2 | (x & 0xcccccccc) >> 2;
+       if(k & 4)
+               x = (x & 0x0f0f0f0f) << 4 | (x & 0xf0f0f0f0) >> 4;
+       if(k & 8)
+               x = (x & 0x00ff00ff) << 8 | (x & 0xff00ff00) >> 8;
+       if(k & 16)
+               x = (x & 0x0000ffff) << 16 | (x & 0xffff0000) >> 16;
+
+       return x;
+}
+
+/**
+ * bitrev8(): function for reversing bits of a byte
+ * @byte: the byte to get its bits reversed
+ */

  static inline u8 bitrev8(u8 byte)
  {
-       return byte_rev_table[byte];
+       u8 k = 7;
+       if(k & 1)
+               byte = (byte & 0x5555) << 1 | (byte & 0xaaaa) >> 1;
+       if(k & 2)
+               byte = (byte & 0x3333) << 2 | (byte & 0xcccc) >> 2;
+       if(k & 4)
+               byte = (byte & 0x0f0f) << 4 | (byte & 0xf0f0) >> 4;
+       return byte;
  }

  extern u32 bitrev32(u32 in);



-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.

Re: [PATCH 1/2] bitreversal program

[Benoit Boissinot]

On Tue, May 20, 2008 at 5:25 PM, Soumyadip Das Mahapatra
<kernelhacker@visualserver.org> wrote:
> Thanks for giving a reply Akinobu :-)
> I forgot that bitrev8() is static in header file. Sorry for that.
>
> Below is my new patch considering this. Cant it be applicable?
> Please review it.
>
> I know that my bitrev8() takes more instructions than that
> of yours. But we have to think about faster access of cpu cache over that
> of memory cache(which your bit_rev_table uses).

I didn't review your patch, sorry.
But I'm pretty sure that your patch won't be considered unless you
provide benchmarks
with numbers for different CPU/architecture.
Ideally you should provide a script to test the correctness and the
performance of your
change that anyone could run on his computer.

regards,

Benoit

Re: [PATCH 1/2] bitreversal program

[Soumyadip Das Mahapatra]

On Tue, 20 May 2008, Benoit Boissinot wrote:

> On Tue, May 20, 2008 at 5:25 PM, Soumyadip Das Mahapatra
> <kernelhacker@visualserver.org> wrote:
>> Thanks for giving a reply Akinobu :-)
>> I forgot that bitrev8() is static in header file. Sorry for that.
>>
>> Below is my new patch considering this. Cant it be applicable?
>> Please review it.
>>
>> I know that my bitrev8() takes more instructions than that
>> of yours. But we have to think about faster access of cpu cache over that
>> of memory cache(which your bit_rev_table uses).
>
> I didn't review your patch, sorry.
> But I'm pretty sure that your patch won't be considered unless you
> provide benchmarks
> with numbers for different CPU/architecture.
> Ideally you should provide a script to test the correctness and the
> performance of your
> change that anyone could run on his computer.

Thanks Benoit for giving me such a precious advice. But sorry, I dont
have any benchmarking system in my hand(how can i have? i am just a
student, not a professional).
So if you do me a favour and kindly do it for me, please :-)

Anyway thanks again.

Soumya

-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.

Re: [PATCH 1/2] bitreversal program

[Benoit Boissinot]

On Tue, May 20, 2008 at 05:57:37PM +0200, Soumyadip Das Mahapatra wrote:
> On Tue, 20 May 2008, Benoit Boissinot wrote:
>> On Tue, May 20, 2008 at 5:25 PM, Soumyadip Das Mahapatra
>> <kernelhacker@visualserver.org> wrote:
>>> I know that my bitrev8() takes more instructions than that
>>> of yours. But we have to think about faster access of cpu cache over that
>>> of memory cache(which your bit_rev_table uses).
>>
>> I didn't review your patch, sorry.
>> But I'm pretty sure that your patch won't be considered unless you
>> provide benchmarks
>> with numbers for different CPU/architecture.
>> Ideally you should provide a script to test the correctness and the
>> performance of your
>> change that anyone could run on his computer.
>
> Thanks Benoit for giving me such a precious advice. But sorry, I dont
> have any benchmarking system in my hand(how can i have? i am just a
> student, not a professional).
> So if you do me a favour and kindly do it for me, please :-)

A quick benchmarking (that you should have done at least one your
computer gives for 100000000 iterations):
old:
real	0m1.631s
user	0m1.628s
sys	0m0.004s

new:
real	0m5.553s
user	0m5.540s
sys	0m0.004s

So I guess there's no need to discuss this further.

regards,

Benoit

-- 
:wq

Re: [PATCH 1/2] bitreversal program

[Soumyadip Das Mahapatra]

On Tue, 20 May 2008, Benoit Boissinot wrote:

> A quick benchmarking (that you should have done at least one your
> computer gives for 100000000 iterations):
> old:
> real	0m1.631s
> user	0m1.628s
> sys	0m0.004s
>
> new:
> real	0m5.553s
> user	0m5.540s
> sys	0m0.004s
>
> So I guess there's no need to discuss this further.

Sorry to disturb you again. But i tested my code against Akinobu's one
and the test result shows my code takes less cpu time than that of
Akinobu's.
Here is the code i used to determine performance
--
#include<stdio.h>
#include<time.h>

int main()
{
 	int i = 100000000;
 	printf("%ld\n", (long)clock());
 	for(; i>0; i--) {
 		bitrev32(0x00face32);
 	}
 	printf("%ld", (long)clock());
}
--
OUTPUT:
[using Akinobu's bitrev32()]
0
6010000

[using my bitrev32()]
0
3990000

And using bitrev8() instead of bitrev32() the result gives the output
like this:
[using Akinobu's bitrev8()]
0
770000

[using my bitrev8()]
0
2360000

My processor is 1.4 GHz one.
I am not forcing you to review my code( or i've no expectation of
inclusion of it ) but its just a curiousity: what is truth behind
the output.

Regards,
Soumya

-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.

Re: [PATCH 1/2] bitreversal program

[Benoit Boissinot]

[-- Attachment #1: Type: text/plain, Size: 718 bytes --]

On Wed, May 21, 2008 at 10:54:15AM +0200, Soumyadip Das Mahapatra wrote:
> On Tue, 20 May 2008, Benoit Boissinot wrote:
>
> Sorry to disturb you again. But i tested my code against Akinobu's one
> and the test result shows my code takes less cpu time than that of
> Akinobu's.
>
> My processor is 1.4 GHz one.
> I am not forcing you to review my code( or i've no expectation of
> inclusion of it ) but its just a curiousity: what is truth behind
> the output.

I'm using a core duo 1.2GHz, if you want to play with the code, I'm
attaching a tarball (it's hackish, just change the #include at the top
of bitrev.h to switch implementation).

I'm using gcc -Wall -O3 to compile with gcc 4.2.3.

regards,

Benoit

-- 
:wq

[-- Attachment #2: bitrev.tar.bz2 --]
[-- Type: application/octet-stream, Size: 1520 bytes --]

Re: [PATCH 1/2] bitreversal program

[Rene Herman]

On 21-05-08 10:54, Soumyadip Das Mahapatra wrote:

> Sorry to disturb you again. But i tested my code against Akinobu's one
> and the test result shows my code takes less cpu time than that of
> Akinobu's.

The unfortunate thing about these kinds of changes is that they're not 
all that easily tested. Straightforwardness would suggest that obviously 
the current table driven method will be faster due to needing fewer code 
cycles. Cache considerations add to that in the sense of instruction 
cache and can (!) detract from it in the sense of data cache; sometimes 
dramaticaly detract due to cache misses basically dwarving most anything 
else.

However, in this case the table is a tiny 256-byte one which isn't even 
going to be pulled in completely in normal usage (just the cache-lines 
needed) while on the other hand the extra i-cache pressure from the 
increased code in your version is always there.

It's unexpected that you would get better results from your new code 
(and I'm not; I took Benoit's posted test and get 15 seconds for your 
version versus 9 for the original table-driven one) and in this case, 
reality wouldn't contradict the micro-benchmark either. It's when the 
table grows and, especially, more of it is needed on a regular basis 
that you'd start to worry.

PS: If you're going to go really micro, there are even going to be 
differences between bitreversing 0x00000000 which is just going to need 
the first byte (hence cacheline) and say 0x004080c0 which is going to 
occupy 4 cachelines. Again not in the isolated test though; the data in 
this case is small enough that you should be having a hard time getting 
your version to perform better -- forking off a competing process that 
does its best to dirty cache might do it, but then you're in a situation 
which is no longer real-world with respect to this "call once" bit of API...

Rene.

Re: [PATCH 1/2] bitreversal program

[Tilman Schmidt]

[-- Attachment #1: Type: text/plain, Size: 854 bytes --]

Am 20.05.2008 17:25 schrieb Soumyadip Das Mahapatra:
> I know that my bitrev8() takes more instructions than that
> of yours. But we have to think about faster access of cpu cache over that
> of memory cache(which your bit_rev_table uses).

bitrev8() is used on every transferred byte for certain types of
ISDN connections, ie. with a steady rate of 8000 bytes/sec.
Depending on the driver, it will be called for individual data
bytes or possibly a small number of bytes at a time, typically
not more than 64, and typically in interrupt context.

I'd expect the table driven version to perform better in those
circumstances.

Thanks,
Tilman

-- 
Tilman Schmidt                    E-Mail: tilman@imap.cc
Bonn, Germany
Diese Nachricht besteht zu 100% aus wiederverwerteten Bits.
Ungeöffnet mindestens haltbar bis: (siehe Rückseite)


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 250 bytes --]