diff options
| author | Jeff Davis <jdavis@postgresql.org> | 2020-07-30 08:44:58 -0700 |
|---|---|---|
| committer | Jeff Davis <jdavis@postgresql.org> | 2020-07-30 09:14:23 -0700 |
| commit | fd734f387d8780d9989d750942d026167de8cf3c (patch) | |
| tree | 07ec4db85bd5c2af6fc4252cb9e1a4549fe8c1fc /src/backend/lib/hyperloglog.c | |
| parent | f1af75c5f2516ec5b20cfe4b3a474071a318ae1e (diff) | |
| download | postgresql-fd734f387d8780d9989d750942d026167de8cf3c.tar.gz postgresql-fd734f387d8780d9989d750942d026167de8cf3c.zip | |
Use pg_bitutils for HyperLogLog.
Using pg_leftmost_one_post32() yields substantial performance benefits.
Backpatching to version 13 because HLL is used for HashAgg
improvements in 9878b643, which was also backpatched to 13.
Reviewed-by: Peter Geoghegan
Discussion: https://postgr.es/m/CAH2-WzkGvDKVDo+0YvfvZ+1CE=iCi88DCOGFF3i1hTGGaxcKPw@mail.gmail.com
Backpatch-through: 13
Diffstat (limited to 'src/backend/lib/hyperloglog.c')
| -rw-r--r-- | src/backend/lib/hyperloglog.c | 13 |
1 files changed, 8 insertions, 5 deletions
diff --git a/src/backend/lib/hyperloglog.c b/src/backend/lib/hyperloglog.c index a5cc1f8b83b..351fed8186f 100644 --- a/src/backend/lib/hyperloglog.c +++ b/src/backend/lib/hyperloglog.c @@ -49,6 +49,7 @@ #include <math.h> #include "lib/hyperloglog.h" +#include "port/pg_bitutils.h" #define POW_2_32 (4294967296.0) #define NEG_POW_2_32 (-4294967296.0) @@ -242,11 +243,13 @@ rho(uint32 x, uint8 b) { uint8 j = 1; - while (j <= b && !(x & 0x80000000)) - { - j++; - x <<= 1; - } + if (x == 0) + return b + 1; + + j = 32 - pg_leftmost_one_pos32(x); + + if (j > b) + return b + 1; return j; } |