On Tue, Jul 21, 2009 at 12:07 AM, Tom Lane<tgl@sss.pgh.pa.us> wrote:
> Greg Stark <gsstark@mit.edu> writes:
>> I also wonder if this microbenchmark is actually ok because it's
>> testing the same value over and over so any branch-prediction will
>> shine unrealistically well.
>
> Yeah, that is a good point --- and it would benefit the unrolled loop
> more than the other versions. We should probably revise the test
> harness so it mixes the size requests a bit. I'm not sure of a suitably
> simple way to do that, though.
Well it was a bit of a pain but I filled an array with (1/1000 scaled
down) values and then permuted them. I also went ahead and set the
low-order bits to random values since the lookup table based algorithm
might be affected by it.
The results are a bit disappointing on my machine, only the CLZ and
lookup table come out significantly ahead:
$ ./testit 10
0: 620
1: 4949
2: 5378
3: 3560
4: 4426
5: 4218
6: 1098
7: 387
8: 599
9: 44
10: 52
clz 1.530s
lookup table 1.720s
float hack 4.424s
unrolled 5.280s
normal 5.369s
--
greg
http://mit.edu/~gsstark/resume.pdf