Skip site navigation (1) Skip section navigation (2)

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

From: Greg Stark <gsstark(at)mit(dot)edu>
To: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Cc: Stefan Kaltenbrunner <stefan(at)kaltenbrunner(dot)cc>, Jeremy Kerr <jk(at)ozlabs(dot)org>, Robert Haas <robertmhaas(at)gmail(dot)com>, pgsql-hackers(at)postgresql(dot)org
Subject: Re: [PATCH v4] Avoid manual shift-and-test logic in AllocSetFreeIndex
Date: 2009-07-21 01:11:37
Message-ID: 407d949e0907201811i13c73e18x58295566d27aadcc@mail.gmail.com (view raw or flat)
Thread:
Lists: pgsql-hackers
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

Attachment: testit2.c
Description: text/x-csrc (2.4 KB)
Attachment: testit.c
Description: text/x-csrc (3.6 KB)

In response to

Responses

pgsql-hackers by date

Next:From: Tom LaneDate: 2009-07-21 03:07:36
Subject: Re: [PATCH v4] Avoid manual shift-and-test logic in AllocSetFreeIndex
Previous:From: KaiGai KoheiDate: 2009-07-21 00:40:20
Subject: Re: [PATCH] SE-PgSQL/tiny rev.2193

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group