Re: [PATCH v4] Avoid manual shift-and-test logic in AllocSetFreeIndex

On Tue, Jul 21, 2009 at 12:07 AM, Tom Lane<tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Greg Stark <gsstark(at)mit(dot)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