bitreversal program
PATCH 1/2 bitreversal program
include/linux/bitrev.h 2008-05-19 21:49:46.000000000 +0530 renamed from include/linux/bitrev.h 2008-04-17 08:19:44.000000000 +0530 +24 -3
@@ -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);
Signature · 3 lines
This message has been scanned for viruses and dangerous content by MailScanner, and is believed to be clean.
Quoted 10 lines · Soumyadip Das Mahapatra
include/linux/bitrev.h 2008-05-19 21:49:46.000000000 +0530 renamed from include/linux/bitrev.h 2008-04-17 08:19:44.000000000 +0530 +3
-1@@ -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
include/linux/bitrev.h 2008-05-19 21:49:46.000000000 +0530 line 8
Quoted 10 lines
include/linux/bitrev.h 2008-05-19 21:49:46.000000000 +0530 renamed from include/linux/bitrev.h 2008-04-17 08:19:44.000000000 +0530 +8
-1+ * @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?
Quoted 6 lines
include/linux/bitrev.h 2008-05-19 21:49:46.000000000 +0530 renamed from include/linux/bitrev.h 2008-04-17 08:19:44.000000000 +0530 +4
-1+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)
include/linux/bitrev.h 2008-05-19 21:49:46.000000000 +0530 line 32
Quoted 10 lines
include/linux/bitrev.h 2008-05-19 21:49:46.000000000 +0530 renamed from include/linux/bitrev.h 2008-04-17 08:19:44.000000000 +0530 +9
-0+ 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
Quoted 19 lines · Harvey Harrison
Quoted 6 lines
include/linux/bitrev.h 2008-05-19 21:49:46.000000000 +0530 renamed from include/linux/bitrev.h 2008-04-17 08:19:44.000000000 +0530 +4
-1+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)include/linux/bitrev.h 2008-05-19 21:49:46.000000000 +0530 line 32
Quoted 10 lines
include/linux/bitrev.h 2008-05-19 21:49:46.000000000 +0530 renamed from include/linux/bitrev.h 2008-04-17 08:19:44.000000000 +0530 +9
-0+ 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?
Quoted 2 lines
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
Quoted 43 lines · Harvey Harrison
Quoted 10 lines · Soumyadip Das Mahapatra
include/linux/bitrev.h 2008-05-19 21:49:46.000000000 +0530 renamed from include/linux/bitrev.h 2008-04-17 08:19:44.000000000 +0530 +3
-1@@ -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 reversedinclude/linux/bitrev.h 2008-05-19 21:49:46.000000000 +0530 line 8
Quoted 10 lines
include/linux/bitrev.h 2008-05-19 21:49:46.000000000 +0530 renamed from include/linux/bitrev.h 2008-04-17 08:19:44.000000000 +0530 +8
-1+ * @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?
Quoted 6 lines
include/linux/bitrev.h 2008-05-19 21:49:46.000000000 +0530 renamed from include/linux/bitrev.h 2008-04-17 08:19:44.000000000 +0530 +4
-1+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)include/linux/bitrev.h 2008-05-19 21:49:46.000000000 +0530 line 32
Quoted 10 lines
include/linux/bitrev.h 2008-05-19 21:49:46.000000000 +0530 renamed from include/linux/bitrev.h 2008-04-17 08:19:44.000000000 +0530 +9
-0+ 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?
Quoted 9 lines
Harvey
Signature · 3 lines
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
Quoted 1 line
include/linux/bitrev.h 2008-05-19 21:49:46.000000000 +0530 line 8
Quoted 1 line
include/linux/bitrev.h 2008-05-19 21:49:46.000000000 +0530 renamed from include/linux/bitrev.h 2008-04-17 08:19:44.000000000 +0530 +0
-1-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.
Quoted 1 line
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!
Signature · 3 lines
This message has been scanned for viruses and dangerous content by MailScanner, and is believed to be clean.
Quoted 5 lines
Quoted 1 line
Quoted 1 line
-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
...
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---
include/linux/bitrev.h 2008-05-20 20:41:13.000000000 +0530 renamed from include/linux/bitrev.h 2008-04-17 08:19:44.000000000 +0530 +40 -2
@@ -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);
Signature · 3 lines
This message has been scanned for viruses and dangerous content by MailScanner, and is believed to be clean.
Quoted 9 lines · Soumyadip Das Mahapatra
Thanks for giving a reply Akinobu :-)
I forgot thatbitrev8()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 memorycache(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
Quoted 12 lines · Benoit Boissinot
Quoted 9 lines · Soumyadip Das Mahapatra
Thanks for giving a reply Akinobu :-)
I forgot thatbitrev8()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 memorycache(which your bit_rev_table uses).
Quoted 7 lines
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
Signature · 3 lines
This message has been scanned for viruses and dangerous content by MailScanner, and is believed to be clean.
Quoted 15 lines · Soumyadip Das Mahapatra
Quoted 6 lines · Benoit Boissinot
Quoted 3 lines · 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 memorycache(which your bit_rev_table uses).Quoted 7 lines
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.
Quoted 4 lines
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
Signature · 1 line
:wq
Quoted 7 lines · Benoit Boissinot
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
Quoted 6 lines
new:
real 0m5.553s
user 0m5.540s
sys 0m0.004sSo 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
Signature · 3 lines
This message has been scanned for viruses and dangerous content by MailScanner, and is believed to be clean.
Quoted 10 lines · Soumyadip Das Mahapatra
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
Signature · 1 line
:wq
Quoted 3 lines · Soumyadip Das Mahapatra
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.
Am 20.05.2008 17:25 schrieb Soumyadip Das Mahapatra:
Quoted 3 lines
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 memorycache(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
Signature · 4 lines
Tilman Schmidt E-Mail: [email protected] Bonn, Germany Diese Nachricht besteht zu 100% aus wiederverwerteten Bits. Ungeöffnet mindestens haltbar bis: (siehe Rückseite)