MIME-Version: 1.0
References: 
 <CAApHDvq0T=iJ0Sf5TNE9yyWwfOeVjmrBt0wSywDnGD9Y4YJQBA@mail.gmail.com>
 <3190647.1775103768@sss.pgh.pa.us>
 <CAApHDvrvvq_m+nRwjsOpCsFa4EtVtmvJX7zAD=Siria-x6DpbQ@mail.gmail.com>
 <CAApHDvqTUm3Cbgz3ZLV+ad8s_HJHZYrVbrBvGyPQdxCRR-6dvA@mail.gmail.com>
 <59B9EFAF-84DF-40A9-847F-9CF457A798BB@gmail.com>
 <CAApHDvocDY0qvhxRNBaNRjEr46j8TsGFig+=6bHN-NYS_dhSCw@mail.gmail.com>
 <D8422C13-E995-4D0D-B296-5D643DE89399@gmail.com>
In-Reply-To: <D8422C13-E995-4D0D-B296-5D643DE89399@gmail.com>
From: David Rowley <dgrowleyml@gmail.com>
Date: Sat, 4 Apr 2026 16:30:32 +1300
Message-ID: 
 <CAApHDvo+WtKHWbgmPA+H2K24P6h6aUJ_9kAdS__G1L9LDFGwgQ@mail.gmail.com>
Subject: Re: Small and unlikely overflow hazard in bms_next_member()
To: Chao Li <li.evan.chao@gmail.com>
Cc: Tom Lane <tgl@sss.pgh.pa.us>,
	PostgreSQL Developers <pgsql-hackers@lists.postgresql.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: 
 <https://www.postgresql.org/message-id/CAApHDvo%2BWtKHWbgmPA%2BH2K24P6h6aUJ_9kAdS__G1L9LDFGwgQ%40mail.gmail.com>
Precedence: bulk

On Sat, 4 Apr 2026 at 02:28, Chao Li <li.evan.chao@gmail.com> wrote:
> In test_bms_next2.c, you set words_to_alloc =3D 1, which disables the opt=
imization in the unrolled version. If I change words_to_alloc =3D 2, then o=
n my MacBook M4, the unrolled version seems to win:
> ```
> chaol@ChaodeMacBook-Air test % ./test_bms_next2
> Benchmarking 100000000 iterations...
>
> Original:  0.61559 seconds
> David's:          0.61651 seconds
> Chao's version:   1.06033 seconds
> Unrolled loop: 0.60561 seconds
> 2800000000
> ```

Doing the same locally, here's what I get on my Zen2 machine:

drowley@amd3990x:~$ gcc test_bms_next.c -O2 -o test_bms_next && ./test_bms_=
next
Benchmarking 100000000 iterations...

Original:  1.21125 seconds
David's:          1.11997 seconds
Chao's version:   1.72662 seconds
Unrolled loop: 1.63090 seconds
2800000000
drowley@amd3990x:~$ clang test_bms_next.c -O2 -o test_bms_next &&
./test_bms_next
Benchmarking 100000000 iterations...

Original:  1.10780 seconds
David's:          1.05968 seconds
Chao's version:   1.87123 seconds
Unrolled loop: 1.11002 seconds
2800000000

> I guess one-word Bitmapset are probably the most common case in practice.=
 So overall, I agree that your version is the best choice. Please go ahead =
with it as we have already gained both a bug fix and a performance improvem=
ent. If we really want to study the performance more deeply, I think that w=
ould be a separate topic.

Yeah, but it's better to find bottlenecks and focus there than to
optimise blindly without knowing if it'll make any actual difference.
It's still important to test for regressions when modifying code and
try to avoid them, as it's sometimes not obvious if the code being
modified is critical for performance.

I also don't think we should be doing anything to optimise for
multi-word sets at the expense of slowing down single-word sets. Not
that it's very representative of the real world, but I added some
telemetry to bitmapset.c and I see 43 multi-word sets being created
and 1.45 million single-word sets created during make check, or 1 in
33785, if you prefer.

diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 786f343b3c9..21b5053e9a2 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -219,6 +219,10 @@ bms_make_singleton(int x)
        int                     wordnum,
                                bitnum;

+       if (x >=3D 64)
+               elog(NOTICE, "multi-word set bms_make_singleton");
+       else
+               elog(NOTICE, "single-word set bms_make_singleton");
        if (x < 0)
                elog(ERROR, "negative bitmapset member not allowed");
        wordnum =3D WORDNUM(x);
@@ -811,6 +815,9 @@ bms_add_member(Bitmapset *a, int x)
        wordnum =3D WORDNUM(x);
        bitnum =3D BITNUM(x);

+       if (x >=3D 64 && a->nwords =3D=3D 1)
+               elog(NOTICE, "multi-set bms_add_member");
+
        /* enlarge the set if necessary */
        if (wordnum >=3D a->nwords)
        {

Not quite perfect as a set made first as a single word set that later
becomes a multi-word set will be double counted. The number of
operations on the sets is likely more important anyway, not the number
of sets being created. The point is, multi-word sets are rare for most
workloads.

David