Horton

Thread

Commits

  1. Micro-optimize AllocSetFreeIndex() by reference to pg_bitutils code.

  2. Speed up AllocSetFreeIndex, which is a significant cost in palloc and pfree,

  1. use CLZ instruction in AllocSetFreeIndex()

    John Naylor <john.naylor@2ndquadrant.com> — 2019-12-26T23:49:46Z

    Hi all,

In commit ab5b4e2f9ed, we optimized AllocSetFreeIndex() using a lookup
table. At the time, using CLZ was rejected because compiler/platform
support was not widespread enough to justify it. For other reasons, we
recently added bitutils.h which uses __builtin_clz() where available,
so it makes sense to revisit this. I modified the test in [1] (C files
attached), using two separate functions to test CLZ versus the
open-coded algorithm of pg_leftmost_one_pos32().

These are typical results on a recent Intel platform:

HEAD        5.55s
clz         4.51s
open-coded  9.67s

CLZ gives a nearly 20% speed boost on this microbenchmark. I suspect
that this micro-benchmark is actually biased towards the lookup table
more than real-world workloads, because it can monopolize the L1
cache. Sparing cache is possibly the more interesting reason to use
CLZ. The open-coded version is nearly twice as slow, so it makes sense
to keep the current implementation as the default one, and not use
pg_leftmost_one_pos32() directly. However, with a small tweak, we can
reuse the lookup table in bitutils.c instead of the bespoke one used
solely by AllocSetFreeIndex(), saving a couple cache lines here also.
This is done in the attached patch.

[1] https://www.postgresql.org/message-id/407d949e0907201811i13c73e18x58295566d27aadcc%40mail.gmail.com

--
John Naylor                https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

  2. Re: use CLZ instruction in AllocSetFreeIndex()

    Alvaro Herrera <alvherre@2ndquadrant.com> — 2019-12-27T13:21:50Z

    On 2019-Dec-26, John Naylor wrote:

> In commit ab5b4e2f9ed, we optimized AllocSetFreeIndex() using a lookup
> table. At the time, using CLZ was rejected because compiler/platform
> support was not widespread enough to justify it. For other reasons, we
> recently added bitutils.h which uses __builtin_clz() where available,
> so it makes sense to revisit this. I modified the test in [1] (C files
> attached), using two separate functions to test CLZ versus the
> open-coded algorithm of pg_leftmost_one_pos32().
> 
> These are typical results on a recent Intel platform:
> 
> HEAD        5.55s
> clz         4.51s
> open-coded  9.67s

I can confirm these results on my Intel laptop.  I ran it with a
repetition of 20, averages of 4 runs:

clz		1,614
bitutils	3,714
current		2,088
(stddevs are under 0,031).


-- 
Álvaro Herrera                https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

  3. Re: use CLZ instruction in AllocSetFreeIndex()

    Tom Lane <tgl@sss.pgh.pa.us> — 2019-12-27T14:54:35Z

    Alvaro Herrera <alvherre@2ndquadrant.com> writes:
> On 2019-Dec-26, John Naylor wrote:
>> In commit ab5b4e2f9ed, we optimized AllocSetFreeIndex() using a lookup
>> table. At the time, using CLZ was rejected because compiler/platform
>> support was not widespread enough to justify it. For other reasons, we
>> recently added bitutils.h which uses __builtin_clz() where available,
>> so it makes sense to revisit this. I modified the test in [1] (C files
>> attached), using two separate functions to test CLZ versus the
>> open-coded algorithm of pg_leftmost_one_pos32().

> I can confirm these results on my Intel laptop.  I ran it with a
> repetition of 20, averages of 4 runs:

I tried this on a few other architectures --- ppc32, aarch64, and x86
(not 64).  The general contours of the result are the same on all,
eg here's the results on aarch64 (Fedora 28):

$ ./a.out 100
...
                 clz 22.713s
       bitutils func 59.462s
             current 30.630s

This kind of leads me to wonder if we don't need to expend more
effort on the non-CLZ version of pg_leftmost_one_pos32; it seems
like it shouldn't be losing this badly to the only-slightly-
improved logic that's currently in AllocSetFreeIndex.  On the
other hand, the buildfarm thinks that __builtin_clz is essentially
universal these days --- the only active non-MSVC critter that
reports not having it is anole.  So maybe it's not worth sweating
over that.  Perhaps what we really ought to be working on is
finding MSVC equivalents for __builtin_clz and friends.

Anyway, getting back to the presented patch, I find myself a bit
dissatisfied with it because it seems like it's leaving something
on the table.  Specifically, looking at the generated assembly
code on a couple of architectures, the setup logic generated by

		tsize = (size - 1) >> ALLOC_MINBITS;

looks like it costs as much or more as the clz proper.  I'm not
sure we can get rid of the subtract-one step, but couldn't the
right shift be elided in favor of changing the constant we
subtract clz's result from?  Shifting off those bits separately
made sense in the old implementation, but assuming that CLZ is
more or less constant-time, it doesn't with CLZ.

			regards, tom lane

  4. Re: use CLZ instruction in AllocSetFreeIndex()

    John Naylor <john.naylor@2ndquadrant.com> — 2019-12-27T15:47:01Z

    On Fri, Dec 27, 2019 at 9:54 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> Anyway, getting back to the presented patch, I find myself a bit
> dissatisfied with it because it seems like it's leaving something
> on the table.  Specifically, looking at the generated assembly
> code on a couple of architectures, the setup logic generated by
>
>                 tsize = (size - 1) >> ALLOC_MINBITS;
>
> looks like it costs as much or more as the clz proper.  I'm not
> sure we can get rid of the subtract-one step,

As I understand it, the desired outcome is ceil(log2(size)), which can
be computed by clz(size - 1) + 1.

> but couldn't the
> right shift be elided in favor of changing the constant we
> subtract clz's result from?  Shifting off those bits separately
> made sense in the old implementation, but assuming that CLZ is
> more or less constant-time, it doesn't with CLZ.

That makes sense -- I'll look into doing that.

-- 
John Naylor                https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

  5. Re: use CLZ instruction in AllocSetFreeIndex()

    Tom Lane <tgl@sss.pgh.pa.us> — 2019-12-27T16:05:22Z

    John Naylor <john.naylor@2ndquadrant.com> writes:
> On Fri, Dec 27, 2019 at 9:54 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> ... but couldn't the
>> right shift be elided in favor of changing the constant we
>> subtract clz's result from?  Shifting off those bits separately
>> made sense in the old implementation, but assuming that CLZ is
>> more or less constant-time, it doesn't with CLZ.

> That makes sense -- I'll look into doing that.

Actually, we could apply that insight to both code paths.
In the existing path, that requires assuming 
ALLOCSET_NUM_FREELISTS+ALLOC_MINBITS <= 17, but that's OK.
(Nowadays I'd probably add a StaticAssert about that.)

			regards, tom lane

  6. Re: use CLZ instruction in AllocSetFreeIndex()

    Alvaro Herrera <alvherre@2ndquadrant.com> — 2019-12-27T16:29:47Z

    On 2019-Dec-27, Tom Lane wrote:

> This kind of leads me to wonder if we don't need to expend more
> effort on the non-CLZ version of pg_leftmost_one_pos32; it seems
> like it shouldn't be losing this badly to the only-slightly-
> improved logic that's currently in AllocSetFreeIndex.  On the
> other hand, the buildfarm thinks that __builtin_clz is essentially
> universal these days --- the only active non-MSVC critter that
> reports not having it is anole.  So maybe it's not worth sweating
> over that.  Perhaps what we really ought to be working on is
> finding MSVC equivalents for __builtin_clz and friends.

Apparently clz() can be written using _BitScanReverse(), per
https://stackoverflow.com/a/20468180
https://docs.microsoft.com/en-us/cpp/intrinsics/bitscanreverse-bitscanreverse64?view=vs-2015

-- 
Álvaro Herrera                https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

  7. Re: use CLZ instruction in AllocSetFreeIndex()

    David Fetter <david@fetter.org> — 2019-12-27T16:37:28Z

    On Fri, Dec 27, 2019 at 01:29:47PM -0300, Alvaro Herrera wrote:
> On 2019-Dec-27, Tom Lane wrote:
> 
> > This kind of leads me to wonder if we don't need to expend more
> > effort on the non-CLZ version of pg_leftmost_one_pos32; it seems
> > like it shouldn't be losing this badly to the only-slightly-
> > improved logic that's currently in AllocSetFreeIndex.  On the
> > other hand, the buildfarm thinks that __builtin_clz is essentially
> > universal these days --- the only active non-MSVC critter that
> > reports not having it is anole.  So maybe it's not worth sweating
> > over that.  Perhaps what we really ought to be working on is
> > finding MSVC equivalents for __builtin_clz and friends.
> 
> Apparently clz() can be written using _BitScanReverse(), per
> https://stackoverflow.com/a/20468180
> https://docs.microsoft.com/en-us/cpp/intrinsics/bitscanreverse-bitscanreverse64?view=vs-2015

There's also various flavors of lczntN for N in (16,32,64) on
(relatively) modern architectures.

https://docs.microsoft.com/en-us/cpp/intrinsics/lzcnt16-lzcnt-lzcnt64?redirectedfrom=MSDN&view=vs-2019

Best,
David.
-- 
David Fetter <david(at)fetter(dot)org> http://fetter.org/
Phone: +1 415 235 3778

Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate

  8. Re: use CLZ instruction in AllocSetFreeIndex()

    Tom Lane <tgl@sss.pgh.pa.us> — 2019-12-27T16:43:18Z

    Alvaro Herrera <alvherre@2ndquadrant.com> writes:
> On 2019-Dec-27, Tom Lane wrote:
>> ... Perhaps what we really ought to be working on is
>> finding MSVC equivalents for __builtin_clz and friends.

> Apparently clz() can be written using _BitScanReverse(), per
> https://stackoverflow.com/a/20468180
> https://docs.microsoft.com/en-us/cpp/intrinsics/bitscanreverse-bitscanreverse64?view=vs-2015

Yeah, I found that too.  It looks promising, but we need to look into
* portability to different MSVC versions? (I guess the buildfarm would
  tell us)
* performance, does it actually generate comparable code?
* intrinsics for the other bit instructions we use?

			regards, tom lane

  9. Re: use CLZ instruction in AllocSetFreeIndex()

    John Naylor <john.naylor@2ndquadrant.com> — 2019-12-28T00:02:02Z

    On Fri, Dec 27, 2019 at 11:05 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> John Naylor <john.naylor@2ndquadrant.com> writes:
> > On Fri, Dec 27, 2019 at 9:54 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> >> ... but couldn't the
> >> right shift be elided in favor of changing the constant we
> >> subtract clz's result from?  Shifting off those bits separately
> >> made sense in the old implementation, but assuming that CLZ is
> >> more or less constant-time, it doesn't with CLZ.
>
> > That makes sense -- I'll look into doing that.
>
> Actually, we could apply that insight to both code paths.
> In the existing path, that requires assuming
> ALLOCSET_NUM_FREELISTS+ALLOC_MINBITS <= 17, but that's OK.
> (Nowadays I'd probably add a StaticAssert about that.)

I tried that in the attached files and got these results:

             current 6.14s
                 clz 4.52s
  clz no right shift 3.15s
        lookup table 5.56s
lookup table no right shift 7.34s

Here, "lookup table" refers to using the pg_leftmost_one_pos[] array
and incrementing the result. Removing the shift operation from the CLZ
case is clearly an improvement, and the main body goes from

movabsq $34359738367, %rax
addq %rax, %rdi
shrq $3, %rdi
bsrl %edi, %eax
xorl $-32, %eax
addl $33, %eax

to

decl %edi
bsrl %edi, %eax
xorl $-32, %eax
addl $30, %eax

The lookup table case is less clear. Removing the shift results in
assembly that looks more like the C code and is slower for me. The
standard lookup table code uses some magic constants and does its own
constant folding by shifting 11 (8 + 3). In the absence of testing on
platforms that will actually exercise this path, it seems the
open-coded path should keep the shift for now. Thoughts?

-- 
John Naylor                https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

  10. Re: use CLZ instruction in AllocSetFreeIndex()

    David Fetter <david@fetter.org> — 2019-12-28T02:16:48Z

    On Fri, Dec 27, 2019 at 07:02:02PM -0500, John Naylor wrote:
> On Fri, Dec 27, 2019 at 11:05 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> >
> > John Naylor <john.naylor@2ndquadrant.com> writes:
> > > On Fri, Dec 27, 2019 at 9:54 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> > >> ... but couldn't the
> > >> right shift be elided in favor of changing the constant we
> > >> subtract clz's result from?  Shifting off those bits separately
> > >> made sense in the old implementation, but assuming that CLZ is
> > >> more or less constant-time, it doesn't with CLZ.
> >
> > > That makes sense -- I'll look into doing that.
> >
> > Actually, we could apply that insight to both code paths.
> > In the existing path, that requires assuming
> > ALLOCSET_NUM_FREELISTS+ALLOC_MINBITS <= 17, but that's OK.
> > (Nowadays I'd probably add a StaticAssert about that.)
> 
> I tried that in the attached files and got these results:
> 
>              current 6.14s
>                  clz 4.52s
>   clz no right shift 3.15s
>         lookup table 5.56s
> lookup table no right shift 7.34s
> 
> Here, "lookup table" refers to using the pg_leftmost_one_pos[] array
> and incrementing the result. Removing the shift operation from the CLZ
> case is clearly an improvement, and the main body goes from
> 
> movabsq $34359738367, %rax
> addq %rax, %rdi
> shrq $3, %rdi
> bsrl %edi, %eax
> xorl $-32, %eax
> addl $33, %eax
> 
> to
> 
> decl %edi
> bsrl %edi, %eax
> xorl $-32, %eax
> addl $30, %eax
> 
> The lookup table case is less clear. Removing the shift results in
> assembly that looks more like the C code and is slower for me. The
> standard lookup table code uses some magic constants and does its own
> constant folding by shifting 11 (8 + 3). In the absence of testing on
> platforms that will actually exercise this path, it seems the
> open-coded path should keep the shift for now. Thoughts?

It's probably worth doing the things you've found unambiguous gains
for as a patch, putting it on the next commitfest, and seeing what the
commitfest.cputube.org machinery has to say about it.

Maybe it'd be worth trying out a patch that enables CLZ for Windows,
but that seems like a separate issue.

Best,
David.
-- 
David Fetter <david(at)fetter(dot)org> http://fetter.org/
Phone: +1 415 235 3778

Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate

  11. Re: use CLZ instruction in AllocSetFreeIndex()

    John Naylor <john.naylor@2ndquadrant.com> — 2019-12-28T03:44:14Z

    On Fri, Dec 27, 2019 at 9:16 PM David Fetter <david@fetter.org> wrote:
> On Fri, Dec 27, 2019 at 07:02:02PM -0500, John Naylor wrote:
> > The lookup table case is less clear. Removing the shift results in
> > assembly that looks more like the C code and is slower for me. The
> > standard lookup table code uses some magic constants and does its own
> > constant folding by shifting 11 (8 + 3). In the absence of testing on
> > platforms that will actually exercise this path, it seems the
> > open-coded path should keep the shift for now. Thoughts?
>
> It's probably worth doing the things you've found unambiguous gains
> for as a patch, putting it on the next commitfest, and seeing what the
> commitfest.cputube.org machinery has to say about it.

Done in the attached.

> Maybe it'd be worth trying out a patch that enables CLZ for Windows,
> but that seems like a separate issue.

Agreed.

-- 
John Naylor                https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

  12. Re: use CLZ instruction in AllocSetFreeIndex()

    John Naylor <john.naylor@2ndquadrant.com> — 2019-12-28T14:50:24Z

    v2 had an Assert that was only correct while experimenting with
eliding right shift. Fixed in v3.

-- 
John Naylor                https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

  13. Re: use CLZ instruction in AllocSetFreeIndex()

    Tom Lane <tgl@sss.pgh.pa.us> — 2019-12-28T22:33:18Z

    John Naylor <john.naylor@2ndquadrant.com> writes:
> v2 had an Assert that was only correct while experimenting with
> eliding right shift. Fixed in v3.

I think there must have been something wrong with your test that
said that eliminating the right shift from the non-CLZ code made
it slower.  It should be an unconditional win, just as it is for
the CLZ code path.  (Maybe some odd cache-line-boundary effect?)

Also, I think it's just weird to account for ALLOC_MINBITS one
way in the CLZ path and the other way in the other path.

I decided that it might be a good idea to do performance testing
in-place rather than in a standalone test program.  I whipped up
the attached that just does a bunch of palloc/pfree cycles.
I got the following results on a non-cassert build (medians of
a number of tests; the times are repeatable to ~ 0.1% for me):

HEAD:		2429.431 ms
v3 CLZ:		2131.735 ms
v3 non-CLZ:	2477.835 ms
remove shift:	2266.755 ms

I didn't bother to try this on non-x86_64 architectures, as
previous testing convinces me the outcome should be about the
same.

Hence, pushed that way, with a bit of additional cosmetic foolery:
the static assertion made more sense to me in relation to the
documented assumption that size <= ALLOC_CHUNK_LIMIT, and I
thought the comment could use some work.

			regards, tom lane