postgres.git / summary / log / commit / refs

commit    07cbcdd00c2465a844513f14b7a96232013d3129
Author:   Jeff Davis <jdavis@postgresql.org>
Date:     Thu Jul 30 15:44:58 2020 +0000
First released in: 14.0, 13.0

    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


 src/backend/lib/hyperloglog.c | 13 ++++++++-----
 1 file 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;
 }


[parent: e710f3b8e7da]