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>
In-Reply-To: <59B9EFAF-84DF-40A9-847F-9CF457A798BB@gmail.com>
From: David Rowley <dgrowleyml@gmail.com>
Date: Sat, 4 Apr 2026 00:42:17 +1300
Message-ID: 
 <CAApHDvocDY0qvhxRNBaNRjEr46j8TsGFig+=6bHN-NYS_dhSCw@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: multipart/mixed; boundary="000000000000f02158064e8ccf54"
Archived-At: 
 <https://www.postgresql.org/message-id/CAApHDvocDY0qvhxRNBaNRjEr46j8TsGFig%2B%3D6bHN-NYS_dhSCw%40mail.gmail.com>
Precedence: bulk

--000000000000f02158064e8ccf54
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Fri, 3 Apr 2026 at 16:24, Chao Li <li.evan.chao@gmail.com> wrote:
> I also did a load test with a standalone c program with 4 versions:

I think you'd be better off picking a more realistic Bitmapset. The
code is doing:

    int words_to_alloc =3D 20000; // Large set to bypass CPU cache slightly
    Bitmapset *bms =3D malloc(sizeof(Bitmapset) + words_to_alloc *
sizeof(bitmapword));
    bms->nwords =3D words_to_alloc;
    memset(bms->words, 0, words_to_alloc * sizeof(bitmapword));

    /* Set a bit far into the set to force a long scan */
    int target_bit =3D (words_to_alloc - 1) * 64 + 10;
    bms->words[words_to_alloc - 1] |=3D (1ULL << 10);

A set with 20k words! Then you're doing:

    for (int i =3D 0; i < iterations; i++) sink =3D bms_next_member(bms, 0)=
;

So you're not looping correctly over the set, as looping over a set
with 1 member requires 2 calls to the function.

I'd say this unrealistically favours the unrolled loop version, as
most of the effort is in the loop looping over empty words and you can
do that without the extra bit-wise AND that the other versions have.
That version also seems to apply both the 64-bit fix and the INT_MAX
fix. Why both?  Because you're only calling the function once per
iteration, it also means your || INT_MAX is only executed once, rather
than n_members + 1 as it would normally be executed. That'll make your
version seem better than it is.

I fixed all that and changed the Bitmapset to something more realistic
with how it's more likely to be seen in PostgreSQL and ran the
benchmark with a proper bms_next_member loop. File attached and
results below:

Zen2 Linux

$ gcc test_bms_next.c -O2 -o test_bms_next && ./test_bms_next
Benchmarking 100000000 iterations...

Original:  0.62113 seconds
David's:          0.70257 seconds
Chao's version:   1.70691 seconds
Unrolled loop: 1.56239 seconds
2800000000

$ clang test_bms_next.c -O2 -o test_bms_next && ./test_bms_next
Benchmarking 100000000 iterations...

Original:  1.11263 seconds
David's:          0.87399 seconds
Chao's version:   0.52962 seconds
Unrolled loop: 1.07799 seconds
2800000000

Apple M2:

Benchmarking 100000000 iterations...

Original:  0.64023 seconds
David's:          0.41087 seconds
Chao's version:   1.21113 seconds
Unrolled loop: 0.55924 seconds
2800000000

> I=E2=80=99m curious that, when something performs differently across plat=
forms, which platform should take priority?

I don't think it matters too much for this case. If we were actually
working on a function that was a bottleneck, then it would be worth
looking deeper and seeing if the compilers are producing suboptimal
code and then try to coax them into making better code. As a last
resort, have two versions and some preprocessor to decide which one.
However, this just isn't performance-critical enough to warrant such
an effort. I think we're already going far too far with this. I just
want to fix the bug. If performance increases in some way as a result
of that, then good.

If I sum up the times from each version of the above results, I get:

Original: 2.37399
David's: 1.98743
Chao's: 3.44766
Unrolled: 3.19962

I'm happy to go with the fastest one. I expect the one with the fewest
instructions is likely more important when running it in the planner,
as that's less to decode. I didn't look, but I expect your loop
unrolled version and your || INT_MAX version to have more
instructions.

David

--000000000000f02158064e8ccf54
Content-Type: text/plain; charset="US-ASCII"; name="test_bms_next2.c"
Content-Disposition: attachment; filename="test_bms_next2.c"
Content-Transfer-Encoding: base64
Content-ID: <f_mnitaoci0>
X-Attachment-Id: f_mnitaoci0

I2luY2x1ZGUgPHN0ZGlvLmg+DQojaW5jbHVkZSA8c3RkbGliLmg+DQojaW5jbHVkZSA8c3RkaW50
Lmg+DQojaW5jbHVkZSA8c3RyaW5nLmg+DQojaW5jbHVkZSA8dGltZS5oPg0KI2luY2x1ZGUgPGxp
bWl0cy5oPg0KDQovLyNkZWZpbmUgTlVMTCAoKHZvaWQgKikgMCkNCnR5cGVkZWYgdWludDY0X3Qg
dWludDY0Ow0KdHlwZWRlZiBpbnQ2NF90IGludDY0Ow0KI2RlZmluZSBCSVRTX1BFUl9CSVRNQVBX
T1JEIDY0DQp0eXBlZGVmIHVpbnQ2NCBiaXRtYXB3b3JkOwkgIC8qIG11c3QgYmUgYW4gdW5zaWdu
ZWQgdHlwZSAqLw0KdHlwZWRlZiBpbnQ2NCBzaWduZWRiaXRtYXB3b3JkOyAvKiBtdXN0IGJlIHRo
ZSBtYXRjaGluZyBzaWduZWQgdHlwZSAqLw0KDQojZGVmaW5lIFdPUkROVU0oeCkgICgoeCkgLyBC
SVRTX1BFUl9CSVRNQVBXT1JEKQ0KI2RlZmluZSBCSVROVU0oeCkgICAoKHgpICUgQklUU19QRVJf
QklUTUFQV09SRCkNCg0KdHlwZWRlZiBzdHJ1Y3QgQml0bWFwc2V0DQp7DQoJaW50CQkgbndvcmRz
OwkJLyogbnVtYmVyIG9mIHdvcmRzIGluIGFycmF5ICovDQoJYml0bWFwd29yZCAgd29yZHNbXTsJ
LyogcmVhbGx5IFtud29yZHNdICovDQp9IEJpdG1hcHNldDsNCg0Kc3RhdGljIGlubGluZSBpbnQN
CmJtd19yaWdodG1vc3Rfb25lX3Bvcyh1aW50NjQgd29yZCkNCnsNCglyZXR1cm4gX19idWlsdGlu
X2N0emxsKHdvcmQpOw0KfQ0KDQovLyAxLiBPcmlnaW5hbCB2ZXJzaW9uDQppbnQNCmJtc19uZXh0
X21lbWJlcihjb25zdCBCaXRtYXBzZXQgKmEsIGludCBwcmV2Yml0KQ0Kew0KCWludAkJIG53b3Jk
czsNCgliaXRtYXB3b3JkICBtYXNrOw0KDQoJaWYgKGEgPT0gTlVMTCkNCgkJcmV0dXJuIC0yOw0K
DQoJbndvcmRzID0gYS0+bndvcmRzOw0KCXByZXZiaXQrKzsNCgltYXNrID0gKH4oYml0bWFwd29y
ZCkgMCkgPDwgQklUTlVNKHByZXZiaXQpOw0KCWZvciAoaW50IHdvcmRudW0gPSBXT1JETlVNKHBy
ZXZiaXQpOyB3b3JkbnVtIDwgbndvcmRzOyB3b3JkbnVtKyspDQoJew0KCQliaXRtYXB3b3JkICB3
ID0gYS0+d29yZHNbd29yZG51bV07DQoNCgkJLyogaWdub3JlIGJpdHMgYmVmb3JlIHByZXZiaXQg
Ki8NCgkJdyAmPSBtYXNrOw0KDQoJCWlmICh3ICE9IDApDQoJCXsNCgkJCWludAkJIHJlc3VsdDsN
Cg0KCQkJcmVzdWx0ID0gd29yZG51bSAqIEJJVFNfUEVSX0JJVE1BUFdPUkQ7DQoJCQlyZXN1bHQg
Kz0gYm13X3JpZ2h0bW9zdF9vbmVfcG9zKHcpOw0KCQkJcmV0dXJuIHJlc3VsdDsNCgkJfQ0KDQoJ
CS8qIGluIHN1YnNlcXVlbnQgd29yZHMsIGNvbnNpZGVyIGFsbCBiaXRzICovDQoJCW1hc2sgPSAo
fihiaXRtYXB3b3JkKSAwKTsNCgl9DQoJcmV0dXJuIC0yOw0KfQ0KDQovLyAyLiBEYXZpZCdzIHZl
cnNpb24NCmludA0KYm1zX25leHRfbWVtYmVyX2RhdmlkKGNvbnN0IEJpdG1hcHNldCAqYSwgaW50
IHByZXZiaXQpDQp7DQoJaW50NjQJCWN1cnJiaXQ7DQoJc2l6ZV90CQlud29yZHM7DQoJYml0bWFw
d29yZAltYXNrOw0KDQoJaWYgKGEgPT0gTlVMTCkNCgkJcmV0dXJuLTI7DQoJbndvcmRzID0gYS0+
bndvcmRzOw0KCWN1cnJiaXQgPSAoaW50NjQpIHByZXZiaXQgKyAxOw0KCW1hc2sgPSAofihiaXRt
YXB3b3JkKSAwKSA8PCBCSVROVU0oY3VycmJpdCk7DQoJZm9yIChzaXplX3Qgd29yZG51bSA9IFdP
UkROVU0oY3VycmJpdCk7IHdvcmRudW0gPCBud29yZHM7IHdvcmRudW0rKykNCgl7DQoJCWJpdG1h
cHdvcmQgIHcgPSBhLT53b3Jkc1t3b3JkbnVtXTsNCg0KCQkvKiBpZ25vcmUgYml0cyBiZWZvcmUg
Y3VycmJpdCAqLw0KCQl3ICY9IG1hc2s7DQoNCgkJaWYgKHcgIT0gMCkNCgkJew0KCQkJaW50CQkg
cmVzdWx0Ow0KDQoJCQlyZXN1bHQgPSAoaW50KSB3b3JkbnVtICogQklUU19QRVJfQklUTUFQV09S
RDsNCgkJCXJlc3VsdCArPSBibXdfcmlnaHRtb3N0X29uZV9wb3Modyk7DQoJCQlyZXR1cm4gcmVz
dWx0Ow0KCQl9DQoNCgkJLyogaW4gc3Vic2VxdWVudCB3b3JkcywgY29uc2lkZXIgYWxsIGJpdHMg
Ki8NCgkJbWFzayA9ICh+KGJpdG1hcHdvcmQpIDApOw0KCX0NCglyZXR1cm4gLTI7DQp9DQoNCi8v
IDMuIE9yaWdpbmFsIHZlcnNpb24gKyBJTlQzMl9NQVggY2hlY2sgKyA2NGJpdA0KaW50DQpibXNf
bmV4dF9tZW1iZXJfY2hhbyhjb25zdCBCaXRtYXBzZXQgKmEsIGludCBwcmV2Yml0KQ0Kew0KCXNp
emVfdAkJIG53b3JkczsNCgliaXRtYXB3b3JkICBtYXNrOw0KDQoJaWYgKGEgPT0gTlVMTCB8fCBw
cmV2Yml0ID09IElOVDMyX01BWCkNCgkJcmV0dXJuIC0yOw0KCW53b3JkcyA9IChzaXplX3QpIGEt
Pm53b3JkczsNCglwcmV2Yml0Kys7DQoJbWFzayA9ICh+KGJpdG1hcHdvcmQpIDApIDw8IEJJVE5V
TShwcmV2Yml0KTsNCglmb3IgKHNpemVfdCB3b3JkbnVtID0gV09SRE5VTShwcmV2Yml0KTsgd29y
ZG51bSA8IG53b3Jkczsgd29yZG51bSsrKQ0KCXsNCgkJYml0bWFwd29yZCAgdyA9IGEtPndvcmRz
W3dvcmRudW1dOw0KDQoJCS8qIGlnbm9yZSBiaXRzIGJlZm9yZSBwcmV2Yml0ICovDQoJCXcgJj0g
bWFzazsNCg0KCQlpZiAodyAhPSAwKQ0KCQl7DQoJCQlpbnQJCSByZXN1bHQ7DQoNCgkJCXJlc3Vs
dCA9IChpbnQpd29yZG51bSAqIEJJVFNfUEVSX0JJVE1BUFdPUkQ7DQoJCQlyZXN1bHQgKz0gYm13
X3JpZ2h0bW9zdF9vbmVfcG9zKHcpOw0KCQkJcmV0dXJuIHJlc3VsdDsNCgkJfQ0KDQoJCS8qIGlu
IHN1YnNlcXVlbnQgd29yZHMsIGNvbnNpZGVyIGFsbCBiaXRzICovDQoJCW1hc2sgPSAofihiaXRt
YXB3b3JkKSAwKTsNCgl9DQoJcmV0dXJuIC0yOw0KfQ0KDQovLyA0LiBQdWxsIHVwIGZpcnN0IGl0
ZXJhdGlvbg0KaW50IGJtc19uZXh0X21lbWJlcl91bnJvbGxfZmlyc3QoY29uc3QgQml0bWFwc2V0
ICphLCBpbnQgcHJldmJpdCkNCnsNCgl1aW50NjQJCWN1cnJiaXQ7DQoJaW50CQkJd29yZG51bTsN
CglpbnQJCQlud29yZHM7DQoNCglpZiAoYSA9PSBOVUxMKQ0KCQlyZXR1cm4gLTI7DQoNCgljdXJy
Yml0ID0gKGludDY0KSBwcmV2Yml0ICsgMTsNCgl3b3JkbnVtID0gV09SRE5VTShjdXJyYml0KTsN
Cglud29yZHMgPSBhLT5ud29yZHM7DQoNCglpZiAod29yZG51bSA+PSBud29yZHMpDQoJCXJldHVy
biAtMjsNCg0KCS8qIEhhbmRsZSBmaXJzdCB3b3JkIHdpdGggbWFzayAqLw0KCWNvbnN0IGJpdG1h
cHdvcmQgKnAgPSAmYS0+d29yZHNbd29yZG51bV07DQoJYml0bWFwd29yZCAgdyA9ICgqcCkgJiAo
KH4oYml0bWFwd29yZCkgMCkgPDwgQklUTlVNKGN1cnJiaXQpKTsNCg0KCWlmICh3ICE9IDApDQoJ
CXJldHVybiAod29yZG51bSAqIEJJVFNfUEVSX0JJVE1BUFdPUkQpICsgYm13X3JpZ2h0bW9zdF9v
bmVfcG9zKHcpOw0KDQoJLyogVGhlICJUaWdodCIgUG9pbnRlciBTY2FuICovDQoJY29uc3QgYml0
bWFwd29yZCAqZW5kID0gJmEtPndvcmRzW253b3Jkc107DQoJZm9yIChwKys7IHAgPCBlbmQ7IHAr
KykNCgl7DQoJCWlmICgqcCAhPSAwKQ0KCQl7DQoJCQl3b3JkbnVtID0gcCAtIGEtPndvcmRzOyAv
LyBQb2ludGVyIGFyaXRobWV0aWMgdG8gZ2V0IGluZGV4DQoJCQlyZXR1cm4gKHdvcmRudW0gKiBC
SVRTX1BFUl9CSVRNQVBXT1JEKSArIGJtd19yaWdodG1vc3Rfb25lX3BvcygqcCk7DQoJCX0NCgl9
DQoNCglyZXR1cm4gLTI7DQp9DQoNCmRvdWJsZSBnZXRfdGltZSgpIHsNCglzdHJ1Y3QgdGltZXNw
ZWMgdHM7DQoJY2xvY2tfZ2V0dGltZShDTE9DS19QUk9DRVNTX0NQVVRJTUVfSUQsICZ0cyk7DQoJ
cmV0dXJuIHRzLnR2X3NlYyArIHRzLnR2X25zZWMgKiAxZS05Ow0KfQ0KDQppbnQgbWFpbigpIHsN
CglpbnQgd29yZHNfdG9fYWxsb2MgPSAxOyAvLyBMYXJnZSBzZXQgdG8gYnlwYXNzIENQVSBjYWNo
ZSBzbGlnaHRseQ0KCUJpdG1hcHNldCAqYm1zID0gbWFsbG9jKHNpemVvZihCaXRtYXBzZXQpICsg
d29yZHNfdG9fYWxsb2MgKiBzaXplb2YoYml0bWFwd29yZCkpOw0KCWJtcy0+bndvcmRzID0gd29y
ZHNfdG9fYWxsb2M7DQoJbWVtc2V0KGJtcy0+d29yZHMsIDAsIHdvcmRzX3RvX2FsbG9jICogc2l6
ZW9mKGJpdG1hcHdvcmQpKTsNCglkb3VibGUgZW5kOw0KCWludDY0IGNvdW50ID0gMDsNCg0KCS8q
IFNldCBhIGJpdCBmYXIgaW50byB0aGUgc2V0IHRvIGZvcmNlIGEgbG9uZyBzY2FuICovDQoJYm1z
LT53b3Jkc1t3b3Jkc190b19hbGxvYyAtIDFdIHw9IDB4YWY0Ow0KDQoJaW50IGl0ZXJhdGlvbnMg
PSAxMDAwMDAwMDA7DQoNCg0KCXByaW50ZigiQmVuY2htYXJraW5nICVkIGl0ZXJhdGlvbnMuLi5c
blxuIiwgaXRlcmF0aW9ucyk7DQoNCgkvLyBUZXN0IE9yaWdpbmFsDQoJZG91YmxlIHN0YXJ0ID0g
Z2V0X3RpbWUoKTsNCglmb3IgKGludCBpID0gMDsgaSA8IGl0ZXJhdGlvbnM7IGkrKykNCgl7DQoJ
CWludCBqID0gLTE7DQoJCXdoaWxlICgoaiA9IGJtc19uZXh0X21lbWJlcihibXMsIGopKSA+PSAw
KQ0KCQkJY291bnQrKzsNCgl9DQoJZW5kID0gZ2V0X3RpbWUoKTsNCglwcmludGYoIk9yaWdpbmFs
OiAgJS41ZiBzZWNvbmRzXG4iLCBlbmQgLSBzdGFydCk7DQoNCgkvLyBUZXN0IEZhc3QNCglzdGFy
dCA9IGdldF90aW1lKCk7DQoJZm9yIChpbnQgaSA9IDA7IGkgPCBpdGVyYXRpb25zOyBpKyspDQoJ
ew0KCQlpbnQgaiA9IC0xOw0KCQl3aGlsZSAoKGogPSBibXNfbmV4dF9tZW1iZXJfZGF2aWQoYm1z
LCBqKSkgPj0gMCkNCgkJCWNvdW50Kys7DQoJfQ0KDQoJZW5kID0gZ2V0X3RpbWUoKTsNCglwcmlu
dGYoIkRhdmlkJ3M6CSAgJS41ZiBzZWNvbmRzXG4iLCBlbmQgLSBzdGFydCk7DQoNCgkvLyBUZXN0
IENoYW8ncyB2ZXJzaW9uDQoJc3RhcnQgPSBnZXRfdGltZSgpOw0KCWZvciAoaW50IGkgPSAwOyBp
IDwgaXRlcmF0aW9uczsgaSsrKQ0KCXsNCgkJaW50IGogPSAtMTsNCgkJd2hpbGUgKChqID0gYm1z
X25leHRfbWVtYmVyX2NoYW8oYm1zLCBqKSkgPj0gMCkNCgkJCWNvdW50Kys7DQoJfQ0KDQoJZW5k
ID0gZ2V0X3RpbWUoKTsNCglwcmludGYoIkNoYW8ncyB2ZXJzaW9uOgkgICUuNWYgc2Vjb25kc1xu
IiwgZW5kIC0gc3RhcnQpOw0KDQoJLy8gUHVsbCB1cCBmaXJzdCBpdGVyYXRpb24NCglzdGFydCA9
IGdldF90aW1lKCk7DQoJZm9yIChpbnQgaSA9IDA7IGkgPCBpdGVyYXRpb25zOyBpKyspDQoJew0K
CQlpbnQgaiA9IC0xOw0KCQl3aGlsZSAoKGogPSBibXNfbmV4dF9tZW1iZXJfdW5yb2xsX2ZpcnN0
KGJtcywgaikpID49IDApDQoJCQljb3VudCsrOw0KCX0NCgllbmQgPSBnZXRfdGltZSgpOw0KCXBy
aW50ZigiVW5yb2xsZWQgbG9vcDogJS41ZiBzZWNvbmRzXG4iLCBlbmQgLSBzdGFydCk7DQoNCglw
cmludGYoIiVsZFxuIiwgY291bnQpOw0KDQoJZnJlZShibXMpOw0KCXJldHVybiAwOw0KfQ==
--000000000000f02158064e8ccf54--