Author: Gerd Isenberg
Date: 15:58:31 07/08/03
Go up one level in this thread
On July 08, 2003 at 18:10:28, Dieter Buerssner wrote:
>Out of curiosity, I added the code generated by the following program just
>before your main:
>
>#include <stdio.h>
>
>int main(void)
>{
> unsigned i,j;
> for (i=0; i<256; i++)
> {
> printf("void func%d(void)\n{\n", i);
> for (j=0; j<8; j++)
> if (i & (1<<j))
> printf(" handleBit%d();\n", j);
> printf("}\n\n");
> }
> printf("typedef void (*FUNC)(void);\n\nFUNC funcs[256]={\n");
> for (i=0; i<256; i++)
> printf(" func%d%s\n", i, i<255?",":"");
> printf("};\n");
>}
>
>And added
>
>
>void funcp(int uptoNbits)
>{
> int i;
> clock_t start, stop;
>
> mySeedRand(0);
> n = n1 = n2 = n3 = n4 = n5 = n6 = n7 = n8 = 0;
> start = clock();
>
> for (i = 0 ; i < MAX_ITERATIONS; i++)
> {
> unsigned long bits = randbits(uptoNbits);
> funcs[bits]();
> }
> stop = clock();
> n = n1 + n2 + n3 + n4 + n5 + n6 + n7 + n8;
> printf("funcp 0x%08lx, time = %.3f\n", n, (float)(stop - start) /
>CLOCKS_PER_SEC);
>}
>
One drawback here with functions pointers is, that you need 256 different
functions with a lot of same instructions - and there is no room for "jump"
optimization. In the switch approach you find a lot of jumps to common case code
- minimum code saving about 50% or better. So with larger bithandler a code
cache misshit may occure more often.
Reinhards approach looks huge due to the cases - but there is only a jump-table
and minimal code. That's probably more cache friendly - but this is of course
even true for Tim's, Andrew's and Heiner's approach.
Gerd
>Note, that you used %x for unsigned long (no prob with MSVC, but will fail with
>some other compilers).
>
>Also added funcp(i) to the loop in main() (I changed it to int main(void), some
>compilers will refuse to translate void main()). I translated it as cpp (because
>of some for loops that are not valid in "old" ISO C).
>
>My results (P4, 2.53 GHz, MSVC 6 -Ox2 -Ob2 -G6 -Gf -Gr):
>
>lonesome one bit:
>Simple 0x20e17a76, time = 1.962
>Andrew 0x20e17a76, time = 2.284
>Tim 0x20e17a76, time = 1.722
>Heiner 0x20e17a76, time = 1.642
>Reinhard 0x20e17a76, time = 1.613
>switch 0x20e17a76, time = 1.672
>funcp 0x20e17a76, time = 1.853
>
>up to two one bits:
>Simple 0x226c8b78, time = 2.443
>Andrew 0x226c8b78, time = 2.824
>Tim 0x226c8b78, time = 2.254
>Heiner 0x226c8b78, time = 2.213
>Reinhard 0x226c8b78, time = 2.093
>switch 0x226c8b78, time = 2.353
>funcp 0x226c8b78, time = 2.123
>
>up to three one bits:
>Simple 0x23f27d79, time = 2.934
>Andrew 0x23f27d79, time = 3.415
>Tim 0x23f27d79, time = 2.714
>Heiner 0x23f27d79, time = 2.654
>Reinhard 0x23f27d79, time = 2.564
>switch 0x23f27d79, time = 2.974
>funcp 0x23f27d79, time = 2.363
>
>eight random bits:
>Simple 0x83001752, time = 4.847
>Andrew 0x83001752, time = 4.767
>Tim 0x83001752, time = 5.388
>Heiner 0x83001752, time = 4.436
>Reinhard 0x83001752, time = 4.247
>switch 0x83001752, time = 1.782
>funcp 0x83001752, time = 2.053
>
>eight random bits high one probability:
>Simple 0xb78285c8, time = 4.597
>Andrew 0xb78285c8, time = 4.476
>Tim 0xb78285c8, time = 6.469
>Heiner 0xb78285c8, time = 4.517
>Reinhard 0xb78285c8, time = 5.097
>switch 0xb78285c8, time = 2.404
>funcp 0xb78285c8, time = 2.573
>
>eight one bits 0xff:
>Simple 0x0642ac00, time = 0.922
>Andrew 0x0642ac00, time = 1.041
>Tim 0x0642ac00, time = 3.215
>Heiner 0x0642ac00, time = 1.422
>Reinhard 0x0642ac00, time = 2.193
>switch 0x0642ac00, time = 0.701
>funcp 0x0642ac00, time = 1.001
>
>Regards,
>Dieter
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.