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

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