pg.ddx.io pgsql-hackers@postgresql.org mailing list archive help / color / mirror / Atom feed From: David Fetter <david@fetter.org>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Peter Eisentraut <peter.eisentraut@enterprisedb.com>
Cc: Daniel Verite <daniel@manitou-mail.org>
Cc: PostgreSQL Development <pgsql-hackers@postgresql.org>
Cc: Vik Fearing <vik@postgresfriends.org>
Subject: Re: popcount
Date: Tue, 19 Jan 2021 01:15:35 +0100
Message-ID: <20210119001535.GD8721@fetter.org> (raw )
In-Reply-To: <338981.1610984050@sss.pgh.pa.us >
References: <20201230105535.GJ13234@fetter.org >
<5ea2932e-50f5-4a74-9550-5e3291b6652b@manitou-mail.org >
<20201230164108.GK13234@fetter.org >
<eb416bd3-9ee2-8a81-8cd4-d61baaf93ec2@enterprisedb.com >
<20210111161354.GA8721@fetter.org >
<e48355d3-efaf-e762-fffa-4b2191680292@enterprisedb.com >
<338981.1610984050@sss.pgh.pa.us >
On Mon, Jan 18, 2021 at 10:34:10AM -0500, Tom Lane wrote:
> Peter Eisentraut <peter.eisentraut@enterprisedb.com> writes:
> > [ assorted nits ]
fixed, I think.
> At the level of bikeshedding ... I quite dislike using the name "popcount"
> for these functions. I'm aware that some C compilers provide primitives
> of that name, but I wouldn't expect a SQL programmer to know that;
> without that context the name seems pretty random and unintuitive.
> Moreover, it invites confusion with SQL's use of "pop" to abbreviate
> "population" in the statistical aggregates, such as var_pop().
>
> Perhaps something along the lines of count_ones() or count_set_bits()
> would be more apropos.
Done that way.
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
Attachments:
[text/x-diff] v4-0001-popcount.patch (7.3K, ../20210119001535.GD8721@fetter.org/2-v4-0001-popcount.patch)
download | inline diff:
From 92f3d5bf1718b1b52a5a4d792f5c75e0bcc7fb74 Mon Sep 17 00:00:00 2001
From: David Fetter <david@fetter.org>
Date: Wed, 30 Dec 2020 02:51:46 -0800
Subject: [PATCH v4] popcount
To: hackers
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="------------2.29.2"
This is a multi-part message in MIME format.
--------------2.29.2
Content-Type: text/plain; charset=UTF-8; format=fixed
Content-Transfer-Encoding: 8bit
Now it's accessible to SQL for the BIT VARYING and BYTEA types.
diff --git doc/src/sgml/func.sgml doc/src/sgml/func.sgml
index aa99665e2e..7626edeee7 100644
--- doc/src/sgml/func.sgml
+++ doc/src/sgml/func.sgml
@@ -4030,6 +4030,23 @@ SELECT format('Testing %3$s, %2$s, %s', 'one', 'two', 'three');
</para></entry>
</row>
+ <row>
+ <entry role="func_table_entry"><para role="func_signature">
+ <indexterm>
+ <primary>count_set_bits</primary>
+ </indexterm>
+ <function>count_set_bits</function> ( <parameter>bytes</parameter> <type>bytea</type> )
+ <returnvalue>bigint</returnvalue>
+ </para>
+ <para>
+ Counts the number of bits set in a binary string.
+ </para>
+ <para>
+ <literal>count_set_bits('\xdeadbeef'::bytea)</literal>
+ <returnvalue>24</returnvalue>
+ </para></entry>
+ </row>
+
<row>
<entry role="func_table_entry"><para role="func_signature">
<indexterm>
@@ -4830,6 +4847,23 @@ SELECT format('Testing %3$s, %2$s, %s', 'one', 'two', 'three');
</para></entry>
</row>
+ <row>
+ <entry role="func_table_entry"><para role="func_signature">
+ <indexterm>
+ <primary>count_set_bits</primary>
+ </indexterm>
+ <function>count_set_bits</function> ( <parameter>bits</parameter> <type>bit</type> )
+ <returnvalue>bigint</returnvalue>
+ </para>
+ <para>
+ Counts the bits set in a bit string.
+ </para>
+ <para>
+ <literal>count_set_bits(B'101010101010101010')</literal>
+ <returnvalue>9</returnvalue>
+ </para></entry>
+ </row>
+
<row>
<entry role="func_table_entry"><para role="func_signature">
<indexterm>
@@ -4869,6 +4903,7 @@ SELECT format('Testing %3$s, %2$s, %s', 'one', 'two', 'three');
<returnvalue>101010001010101010</returnvalue>
</para></entry>
</row>
+
</tbody>
</tgroup>
</table>
diff --git src/include/catalog/pg_proc.dat src/include/catalog/pg_proc.dat
index b5f52d4e4a..416ee0c2fb 100644
--- src/include/catalog/pg_proc.dat
+++ src/include/catalog/pg_proc.dat
@@ -1446,6 +1446,9 @@
{ oid => '752', descr => 'substitute portion of string',
proname => 'overlay', prorettype => 'bytea',
proargtypes => 'bytea bytea int4', prosrc => 'byteaoverlay_no_len' },
+{ oid => '8436', descr => 'count set bits',
+ proname => 'count_set_bits', prorettype => 'int8', proargtypes => 'bytea',
+ prosrc => 'byteapopcount'},
{ oid => '725',
proname => 'dist_pl', prorettype => 'float8', proargtypes => 'point line',
@@ -3865,6 +3868,9 @@
{ oid => '3033', descr => 'set bit',
proname => 'set_bit', prorettype => 'bit', proargtypes => 'bit int4 int4',
prosrc => 'bitsetbit' },
+{ oid => '8435', descr => 'count set bits',
+ proname => 'count_set_bits', prorettype => 'int8', proargtypes => 'bit',
+ prosrc => 'bitpopcount'},
# for macaddr type support
{ oid => '436', descr => 'I/O',
diff --git src/backend/utils/adt/varbit.c src/backend/utils/adt/varbit.c
index 2235866244..c9c6c73422 100644
--- src/backend/utils/adt/varbit.c
+++ src/backend/utils/adt/varbit.c
@@ -36,6 +36,7 @@
#include "libpq/pqformat.h"
#include "nodes/nodeFuncs.h"
#include "nodes/supportnodes.h"
+#include "port/pg_bitutils.h"
#include "utils/array.h"
#include "utils/builtins.h"
#include "utils/varbit.h"
@@ -1878,3 +1879,30 @@ bitgetbit(PG_FUNCTION_ARGS)
else
PG_RETURN_INT32(0);
}
+
+/*
+ * bitpopcount
+ *
+ * Returns the number of bits set in a bit string.
+ *
+ */
+Datum
+bitpopcount(PG_FUNCTION_ARGS)
+{
+ /* There's really no chance of an overflow here because
+ * to get to INT64_MAX set bits, an object would have to be
+ * an exbibyte long, exceeding what PostgreSQL can currently
+ * store by a factor of 2^28
+ */
+ int64 popcount;
+ VarBit *arg1 = PG_GETARG_VARBIT_P(0);
+ bits8 *p;
+ int len;
+
+ p = VARBITS(arg1);
+ len = (VARBITLEN(arg1) + BITS_PER_BYTE - 1) / BITS_PER_BYTE;
+
+ popcount = pg_popcount((char *)p, len);
+
+ PG_RETURN_INT64(popcount);
+}
diff --git src/backend/utils/adt/varlena.c src/backend/utils/adt/varlena.c
index 479ed9ae54..3f1179a0e8 100644
--- src/backend/utils/adt/varlena.c
+++ src/backend/utils/adt/varlena.c
@@ -3439,6 +3439,22 @@ bytea_overlay(bytea *t1, bytea *t2, int sp, int sl)
return result;
}
+/*
+ * popcount
+ */
+Datum
+byteapopcount(PG_FUNCTION_ARGS)
+{
+ bytea *t1 = PG_GETARG_BYTEA_PP(0);
+ int len;
+ int64 result;
+
+ len = VARSIZE_ANY_EXHDR(t1);
+ result = pg_popcount(VARDATA_ANY(t1), len);
+
+ PG_RETURN_INT64(result);
+}
+
/*
* byteapos -
* Return the position of the specified substring.
diff --git src/test/regress/expected/bit.out src/test/regress/expected/bit.out
index a7f95b846d..1187076a8d 100644
--- src/test/regress/expected/bit.out
+++ src/test/regress/expected/bit.out
@@ -710,6 +710,19 @@ SELECT overlay(B'0101011100' placing '001' from 20);
0101011100001
(1 row)
+-- Popcount
+SELECT count_set_bits(B'0101011100'::bit(10));
+ count_set_bits
+----------------
+ 5
+(1 row)
+
+SELECT count_set_bits(B'1111111111'::bit(10));
+ count_set_bits
+----------------
+ 10
+(1 row)
+
-- This table is intentionally left around to exercise pg_dump/pg_upgrade
CREATE TABLE bit_defaults(
b1 bit(4) DEFAULT '1001',
diff --git src/test/regress/expected/strings.out src/test/regress/expected/strings.out
index 7c91afa6e4..e94e76000b 100644
--- src/test/regress/expected/strings.out
+++ src/test/regress/expected/strings.out
@@ -2179,3 +2179,10 @@ SELECT encode(overlay(E'Th\\000omas'::bytea placing E'\\002\\003'::bytea from 5
Th\000o\x02\x03
(1 row)
+SET bytea_output TO hex;
+SELECT count_set_bits(E'\\xdeadbeef'::bytea);
+ count_set_bits
+----------------
+ 24
+(1 row)
+
diff --git src/test/regress/sql/bit.sql src/test/regress/sql/bit.sql
index ea01742c4a..8893d38b0d 100644
--- src/test/regress/sql/bit.sql
+++ src/test/regress/sql/bit.sql
@@ -215,6 +215,10 @@ SELECT overlay(B'0101011100' placing '101' from 6);
SELECT overlay(B'0101011100' placing '001' from 11);
SELECT overlay(B'0101011100' placing '001' from 20);
+-- Popcount
+SELECT count_set_bits(B'0101011100'::bit(10));
+SELECT count_set_bits(B'1111111111'::bit(10));
+
-- This table is intentionally left around to exercise pg_dump/pg_upgrade
CREATE TABLE bit_defaults(
b1 bit(4) DEFAULT '1001',
diff --git src/test/regress/sql/strings.sql src/test/regress/sql/strings.sql
index ef4bfb008a..a4f7879b16 100644
--- src/test/regress/sql/strings.sql
+++ src/test/regress/sql/strings.sql
@@ -730,3 +730,6 @@ SELECT btrim(E'\\000trim\\000'::bytea, ''::bytea);
SELECT encode(overlay(E'Th\\000omas'::bytea placing E'Th\\001omas'::bytea from 2),'escape');
SELECT encode(overlay(E'Th\\000omas'::bytea placing E'\\002\\003'::bytea from 8),'escape');
SELECT encode(overlay(E'Th\\000omas'::bytea placing E'\\002\\003'::bytea from 5 for 3),'escape');
+
+SET bytea_output TO hex;
+SELECT count_set_bits(E'\\xdeadbeef'::bytea);
--------------2.29.2--
view thread (20+ messages) latest in thread
Message-ID: <20210119001535.GD8721@fetter.org>
Permalink: ../20210119001535.GD8721@fetter.org/
Also on: postgresql.org/message-id/20210119001535.GD8721@fetter.org
copy link · copy postgr.es · copy git am
reply Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: david@fetter.org, tgl@sss.pgh.pa.us, peter.eisentraut@enterprisedb.com, daniel@manitou-mail.org, vik@postgresfriends.org
Subject: Re: popcount
In-Reply-To: <20210119001535.GD8721@fetter.org>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox