public inbox for [email protected]
help / color / mirror / Atom feedSmall and unlikely overflow hazard in bms_next_member()
17+ messages / 4 participants
[nested] [flat]
* Small and unlikely overflow hazard in bms_next_member()
@ 2026-04-02 04:09 David Rowley <[email protected]>
2026-04-02 04:22 ` Re: Small and unlikely overflow hazard in bms_next_member() Tom Lane <[email protected]>
2026-04-02 06:38 ` Re: Small and unlikely overflow hazard in bms_next_member() Chao Li <[email protected]>
0 siblings, 2 replies; 17+ messages in thread
From: David Rowley @ 2026-04-02 04:09 UTC (permalink / raw)
To: PostgreSQL Developers <[email protected]>
I've been working on bms_left_shift_members() to bitshift members
either left or right in order to tidy up some existing code and
improve a future Bitmapset use case I'm currently working on.
When testing some ERROR code I added to ensure we don't get an
excessively large left shift value and end up with members higher than
INT32_MAX, I discovered that bms_next_member() can't handle that
value, as "prevbit++" will wrap to INT32_MIN and then we'll try to
access a negative array index, i.e. seg fault.
I appreciate that such a large member is quite unlikely, but if this
isn't fixed then I need to code my error checking code to disallow
members >= INT32_MAX rather than > INT32_MAX. I did have a comment
explaining why I was doing that, but fixing the bug saves the weird
special case and the comment.
Patched attached. I was thinking it might not be worthy of
backpatching, but I'll entertain alternative views on that.
David
Attachments:
[application/octet-stream] bms_next_member_fix.patch (905B, 2-bms_next_member_fix.patch)
download | inline diff:
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 786f343b3c9..912a1ab696a 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -1289,6 +1289,7 @@ bms_join(Bitmapset *a, Bitmapset *b)
int
bms_next_member(const Bitmapset *a, int prevbit)
{
+ int64 currbit;
int nwords;
bitmapword mask;
@@ -1297,13 +1298,13 @@ bms_next_member(const Bitmapset *a, int prevbit)
if (a == NULL)
return -2;
nwords = a->nwords;
- prevbit++;
- mask = (~(bitmapword) 0) << BITNUM(prevbit);
- for (int wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
+ currbit = (int64) prevbit + 1;
+ mask = (~(bitmapword) 0) << BITNUM(currbit);
+ for (int wordnum = WORDNUM(currbit); wordnum < nwords; wordnum++)
{
bitmapword w = a->words[wordnum];
- /* ignore bits before prevbit */
+ /* ignore bits before currbit */
w &= mask;
if (w != 0)
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Small and unlikely overflow hazard in bms_next_member()
2026-04-02 04:09 Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
@ 2026-04-02 04:22 ` Tom Lane <[email protected]>
2026-04-02 22:12 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
1 sibling, 1 reply; 17+ messages in thread
From: Tom Lane @ 2026-04-02 04:22 UTC (permalink / raw)
To: David Rowley <[email protected]>; +Cc: PostgreSQL Developers <[email protected]>
David Rowley <[email protected]> writes:
> When testing some ERROR code I added to ensure we don't get an
> excessively large left shift value and end up with members higher than
> INT32_MAX, I discovered that bms_next_member() can't handle that
> value, as "prevbit++" will wrap to INT32_MIN and then we'll try to
> access a negative array index, i.e. seg fault.
> I appreciate that such a large member is quite unlikely,
I think it's impossible, and if it's not then this is not the
only place in bitmapset.c that could theoretically overflow.
As an example, bms_prev_member does
Assert(prevbit <= a->nwords * BITS_PER_BITMAPWORD);
but if the bitmapset were large enough to accommodate INT_MAX
as a member then a->nwords * BITS_PER_BITMAPWORD must overflow.
I don't think we should add cycles here for this purpose.
If it makes you feel better, maybe add Asserts to
bms_make_singleton and bms_add_member to constrain the
maximum member value to somewhat less than INT_MAX?
regards, tom lane
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Small and unlikely overflow hazard in bms_next_member()
2026-04-02 04:09 Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-02 04:22 ` Re: Small and unlikely overflow hazard in bms_next_member() Tom Lane <[email protected]>
@ 2026-04-02 22:12 ` David Rowley <[email protected]>
2026-04-03 02:08 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
0 siblings, 1 reply; 17+ messages in thread
From: David Rowley @ 2026-04-02 22:12 UTC (permalink / raw)
To: Tom Lane <[email protected]>; +Cc: PostgreSQL Developers <[email protected]>
On Thu, 2 Apr 2026 at 17:22, Tom Lane <[email protected]> wrote:
> Assert(prevbit <= a->nwords * BITS_PER_BITMAPWORD);
> but if the bitmapset were large enough to accommodate INT_MAX
> as a member then a->nwords * BITS_PER_BITMAPWORD must overflow.
I missed that one. That's annoying. Even "prevbit = a->nwords *
BITS_PER_BITMAPWORD - 1;" is undefined if it wraps due to the signed
maths.
> I don't think we should add cycles here for this purpose.
I'm not keen on slowing things down for this either. I did do some
experiments in [1] that sees fewer instructions from using 64-bit
maths. I might go off and see if there are any wins there that also
give us the INT_MAX fix. It's not great effort to reward ratio
though...
David
[1] https://godbolt.org/z/Eh1vzssq7
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Small and unlikely overflow hazard in bms_next_member()
2026-04-02 04:09 Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-02 04:22 ` Re: Small and unlikely overflow hazard in bms_next_member() Tom Lane <[email protected]>
2026-04-02 22:12 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
@ 2026-04-03 02:08 ` David Rowley <[email protected]>
2026-04-03 03:24 ` Re: Small and unlikely overflow hazard in bms_next_member() Chao Li <[email protected]>
2026-04-12 13:17 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
0 siblings, 2 replies; 17+ messages in thread
From: David Rowley @ 2026-04-03 02:08 UTC (permalink / raw)
To: Tom Lane <[email protected]>; +Cc: PostgreSQL Developers <[email protected]>
On Fri, 3 Apr 2026 at 11:12, David Rowley <[email protected]> wrote:
>
> On Thu, 2 Apr 2026 at 17:22, Tom Lane <[email protected]> wrote:
> > I don't think we should add cycles here for this purpose.
>
> I'm not keen on slowing things down for this either. I did do some
> experiments in [1] that sees fewer instructions from using 64-bit
> maths. I might go off and see if there are any wins there that also
> give us the INT_MAX fix. It's not great effort to reward ratio
> though...
The reduction in instructions with the patched version got me curious
to see if it would translate into a performance increase. I tested on
an AMD Zen2 machine, and it's a decent amount faster than master. I
tested with gcc and clang.
I also scanned over the remaining parts of bitmapset.c and didn't find
anywhere else that has overflow risk aside from what you pointed out
in bms_prev_member().
The attached patch contains the benchmark function I added to the
test_bitmapset module. It should apply to master with a bit of noise.
CREATE EXTENSION test_bitmapset;
SELECT
generate_series(1,3) AS run,
bench_bms_next_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 AS
bms_next_member_us,
bench_bms_prev_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 AS
bms_prev_member_us;
master (gcc)
run | bms_next_member_us | bms_prev_member_us
-----+--------------------+--------------------
1 | 26473 | 40404
2 | 26218 | 40413
3 | 26209 | 40387
patched (gcc)
run | bms_next_member_us | bms_prev_member_us
-----+--------------------+--------------------
1 | 25409 | 29705
2 | 24905 | 29693
3 | 24870 | 29707
Times are in microseconds to do 1 million bms_*_member() loops over
the entire set.
I've also attached the full results I got. I've also included the
results from Chao's version, which does slow things down decently on
clang.
IMO, if we can make bitmapset.c work with INT_MAX members and get a
performance increase, then we should do it.
David
> [1] https://godbolt.org/z/Eh1vzssq7
** GCC **
Master:
postgres=# select generate_series(1,10) run,bench_bms_next_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_next_member_us, bench_bms_prev_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_prev_member_us;
run | bms_next_member_us | bms_prev_member_us
-----+--------------------+--------------------
1 | 26473 | 40404
2 | 26218 | 40413
3 | 26209 | 40387
4 | 26245 | 40521
5 | 26343 | 40559
6 | 26343 | 40580
7 | 26366 | 40639
8 | 26735 | 40467
9 | 26201 | 40334
10 | 26208 | 40343
(10 rows)
Time: 735.560 ms
postgres=# select generate_series(1,10) run,bench_bms_next_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_next_member_us, bench_bms_prev_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_prev_member_us;
run | bms_next_member_us | bms_prev_member_us
-----+--------------------+--------------------
1 | 26616 | 40392
2 | 26239 | 40374
3 | 26191 | 40374
4 | 26230 | 40370
5 | 26232 | 40380
6 | 26210 | 40377
7 | 26206 | 40395
8 | 26249 | 40431
9 | 26209 | 40374
10 | 26234 | 40432
(10 rows)
Time: 733.927 ms
Patched:
postgres=# select generate_series(1,10) run,bench_bms_next_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_next_member_us, bench_bms_prev_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_prev_member_us;
run | bms_next_member_us | bms_prev_member_us
-----+--------------------+--------------------
1 | 25409 | 29705
2 | 24905 | 29693
3 | 24870 | 29707
4 | 24933 | 29869
5 | 25059 | 29870
6 | 25026 | 29906
7 | 25055 | 29897
8 | 25055 | 29875
9 | 25031 | 29870
10 | 25042 | 29816
(10 rows)
Time: 604.086 ms
postgres=# select generate_series(1,10) run,bench_bms_next_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_next_member_us, bench_bms_prev_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_prev_member_us;
run | bms_next_member_us | bms_prev_member_us
-----+--------------------+--------------------
1 | 25074 | 29723
2 | 24882 | 29721
3 | 24875 | 29710
4 | 24976 | 29854
5 | 25052 | 29865
6 | 25021 | 29904
7 | 25025 | 29818
8 | 25034 | 29813
9 | 25029 | 29828
10 | 25042 | 29866
(10 rows)
Time: 603.708 ms
Chao's idea:
postgres=# select generate_series(1,10) run,bench_bms_next_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_next_member_us, bench_bms_prev_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_prev_member_us;
run | bms_next_member_us | bms_prev_member_us
-----+--------------------+--------------------
1 | 25677 | 40376
2 | 25271 | 40430
3 | 25263 | 40370
4 | 25301 | 40377
5 | 25357 | 40552
6 | 25394 | 40560
7 | 25412 | 40501
8 | 25401 | 40558
9 | 25381 | 40565
10 | 25370 | 40548
(10 rows)
Time: 725.376 ms
** CLANG **
master:
postgres=# select generate_series(1,10) run,bench_bms_next_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_next_member_us, bench_bms_prev_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_prev_member_us;
run | bms_next_member_us | bms_prev_member_us
-----+--------------------+--------------------
1 | 29970 | 42551
2 | 29479 | 42765
3 | 29475 | 42805
4 | 29523 | 42825
5 | 29578 | 42898
6 | 29529 | 42997
7 | 29535 | 42985
8 | 29593 | 43021
9 | 29575 | 42976
10 | 29562 | 42967
(10 rows)
Time: 798.131 ms
postgres=# select generate_series(1,10) run,bench_bms_next_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_next_member_us, bench_bms_prev_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_prev_member_us;
run | bms_next_member_us | bms_prev_member_us
-----+--------------------+--------------------
1 | 30919 | 42516
2 | 29312 | 42629
3 | 29422 | 42777
4 | 29307 | 42811
5 | 29273 | 42852
6 | 29219 | 42826
7 | 29860 | 43264
8 | 29325 | 42814
9 | 29299 | 42837
10 | 29351 | 42909
(10 rows)
Time: 796.495 ms
Patched:
postgres=# select generate_series(1,10) run,bench_bms_next_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_next_member_us, bench_bms_prev_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_prev_member_us;
run | bms_next_member_us | bms_prev_member_us
-----+--------------------+--------------------
1 | 26741 | 33537
2 | 26094 | 33590
3 | 26087 | 33724
4 | 26276 | 33868
5 | 26346 | 33943
6 | 26433 | 33815
7 | 26324 | 33927
8 | 26274 | 33893
9 | 26350 | 33878
10 | 26304 | 33841
(10 rows)
Time: 661.924 ms
postgres=# select generate_series(1,10) run,bench_bms_next_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_next_member_us, bench_bms_prev_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_prev_member_us;
run | bms_next_member_us | bms_prev_member_us
-----+--------------------+--------------------
1 | 26502 | 33523
2 | 26173 | 33635
3 | 26188 | 33772
4 | 26290 | 33767
5 | 26325 | 33935
6 | 26326 | 33951
7 | 26335 | 33883
8 | 26571 | 33884
9 | 26472 | 33837
10 | 26277 | 33919
(10 rows)
Time: 662.422 ms
Chao's idea:
postgres=# select generate_series(1,10) run,bench_bms_next_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_next_member_us, bench_bms_prev_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_prev_member_us;
run | bms_next_member_us | bms_prev_member_us
-----+--------------------+--------------------
1 | 34865 | 42599
2 | 34547 | 42817
3 | 34623 | 42948
4 | 34689 | 42954
5 | 34733 | 42928
6 | 34731 | 42845
7 | 34727 | 42967
8 | 34763 | 43014
9 | 34775 | 42987
10 | 34788 | 43038
(10 rows)
Time: 854.851 ms
Attachments:
[text/plain] benchmark_results.txt (8.0K, 2-benchmark_results.txt)
download | inline:
** GCC **
Master:
postgres=# select generate_series(1,10) run,bench_bms_next_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_next_member_us, bench_bms_prev_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_prev_member_us;
run | bms_next_member_us | bms_prev_member_us
-----+--------------------+--------------------
1 | 26473 | 40404
2 | 26218 | 40413
3 | 26209 | 40387
4 | 26245 | 40521
5 | 26343 | 40559
6 | 26343 | 40580
7 | 26366 | 40639
8 | 26735 | 40467
9 | 26201 | 40334
10 | 26208 | 40343
(10 rows)
Time: 735.560 ms
postgres=# select generate_series(1,10) run,bench_bms_next_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_next_member_us, bench_bms_prev_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_prev_member_us;
run | bms_next_member_us | bms_prev_member_us
-----+--------------------+--------------------
1 | 26616 | 40392
2 | 26239 | 40374
3 | 26191 | 40374
4 | 26230 | 40370
5 | 26232 | 40380
6 | 26210 | 40377
7 | 26206 | 40395
8 | 26249 | 40431
9 | 26209 | 40374
10 | 26234 | 40432
(10 rows)
Time: 733.927 ms
Patched:
postgres=# select generate_series(1,10) run,bench_bms_next_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_next_member_us, bench_bms_prev_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_prev_member_us;
run | bms_next_member_us | bms_prev_member_us
-----+--------------------+--------------------
1 | 25409 | 29705
2 | 24905 | 29693
3 | 24870 | 29707
4 | 24933 | 29869
5 | 25059 | 29870
6 | 25026 | 29906
7 | 25055 | 29897
8 | 25055 | 29875
9 | 25031 | 29870
10 | 25042 | 29816
(10 rows)
Time: 604.086 ms
postgres=# select generate_series(1,10) run,bench_bms_next_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_next_member_us, bench_bms_prev_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_prev_member_us;
run | bms_next_member_us | bms_prev_member_us
-----+--------------------+--------------------
1 | 25074 | 29723
2 | 24882 | 29721
3 | 24875 | 29710
4 | 24976 | 29854
5 | 25052 | 29865
6 | 25021 | 29904
7 | 25025 | 29818
8 | 25034 | 29813
9 | 25029 | 29828
10 | 25042 | 29866
(10 rows)
Time: 603.708 ms
Chao's idea:
postgres=# select generate_series(1,10) run,bench_bms_next_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_next_member_us, bench_bms_prev_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_prev_member_us;
run | bms_next_member_us | bms_prev_member_us
-----+--------------------+--------------------
1 | 25677 | 40376
2 | 25271 | 40430
3 | 25263 | 40370
4 | 25301 | 40377
5 | 25357 | 40552
6 | 25394 | 40560
7 | 25412 | 40501
8 | 25401 | 40558
9 | 25381 | 40565
10 | 25370 | 40548
(10 rows)
Time: 725.376 ms
** CLANG **
master:
postgres=# select generate_series(1,10) run,bench_bms_next_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_next_member_us, bench_bms_prev_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_prev_member_us;
run | bms_next_member_us | bms_prev_member_us
-----+--------------------+--------------------
1 | 29970 | 42551
2 | 29479 | 42765
3 | 29475 | 42805
4 | 29523 | 42825
5 | 29578 | 42898
6 | 29529 | 42997
7 | 29535 | 42985
8 | 29593 | 43021
9 | 29575 | 42976
10 | 29562 | 42967
(10 rows)
Time: 798.131 ms
postgres=# select generate_series(1,10) run,bench_bms_next_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_next_member_us, bench_bms_prev_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_prev_member_us;
run | bms_next_member_us | bms_prev_member_us
-----+--------------------+--------------------
1 | 30919 | 42516
2 | 29312 | 42629
3 | 29422 | 42777
4 | 29307 | 42811
5 | 29273 | 42852
6 | 29219 | 42826
7 | 29860 | 43264
8 | 29325 | 42814
9 | 29299 | 42837
10 | 29351 | 42909
(10 rows)
Time: 796.495 ms
Patched:
postgres=# select generate_series(1,10) run,bench_bms_next_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_next_member_us, bench_bms_prev_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_prev_member_us;
run | bms_next_member_us | bms_prev_member_us
-----+--------------------+--------------------
1 | 26741 | 33537
2 | 26094 | 33590
3 | 26087 | 33724
4 | 26276 | 33868
5 | 26346 | 33943
6 | 26433 | 33815
7 | 26324 | 33927
8 | 26274 | 33893
9 | 26350 | 33878
10 | 26304 | 33841
(10 rows)
Time: 661.924 ms
postgres=# select generate_series(1,10) run,bench_bms_next_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_next_member_us, bench_bms_prev_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_prev_member_us;
run | bms_next_member_us | bms_prev_member_us
-----+--------------------+--------------------
1 | 26502 | 33523
2 | 26173 | 33635
3 | 26188 | 33772
4 | 26290 | 33767
5 | 26325 | 33935
6 | 26326 | 33951
7 | 26335 | 33883
8 | 26571 | 33884
9 | 26472 | 33837
10 | 26277 | 33919
(10 rows)
Time: 662.422 ms
Chao's idea:
postgres=# select generate_series(1,10) run,bench_bms_next_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_next_member_us, bench_bms_prev_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 as bms_prev_member_us;
run | bms_next_member_us | bms_prev_member_us
-----+--------------------+--------------------
1 | 34865 | 42599
2 | 34547 | 42817
3 | 34623 | 42948
4 | 34689 | 42954
5 | 34733 | 42928
6 | 34731 | 42845
7 | 34727 | 42967
8 | 34763 | 43014
9 | 34775 | 42987
10 | 34788 | 43038
(10 rows)
Time: 854.851 ms
[application/octet-stream] bms_fixes.patch (5.0K, 3-bms_fixes.patch)
download | inline diff:
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index ac3e763de43..46b4ca4b0f1 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -1444,6 +1444,7 @@ bms_join(Bitmapset *a, Bitmapset *b)
int
bms_next_member(const Bitmapset *a, int prevbit)
{
+ int64 currbit;
int nwords;
bitmapword mask;
@@ -1452,13 +1453,13 @@ bms_next_member(const Bitmapset *a, int prevbit)
if (a == NULL)
return -2;
nwords = a->nwords;
- prevbit++;
- mask = (~(bitmapword) 0) << BITNUM(prevbit);
- for (int wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
+ currbit = (int64) prevbit + 1;
+ mask = (~(bitmapword) 0) << BITNUM(currbit);
+ for (int wordnum = WORDNUM(currbit); wordnum < nwords; wordnum++)
{
bitmapword w = a->words[wordnum];
- /* ignore bits before prevbit */
+ /* ignore bits before currbit */
w &= mask;
if (w != 0)
@@ -1505,6 +1506,7 @@ int
bms_prev_member(const Bitmapset *a, int prevbit)
{
int ushiftbits;
+ uint32 currbit;
bitmapword mask;
Assert(bms_is_valid_set(a));
@@ -1517,18 +1519,18 @@ bms_prev_member(const Bitmapset *a, int prevbit)
return -2;
/* Validate callers didn't give us something out of range */
- Assert(prevbit <= a->nwords * BITS_PER_BITMAPWORD);
+ Assert(prevbit <= (int64) a->nwords * BITS_PER_BITMAPWORD);
Assert(prevbit >= -1);
/* transform -1 to the highest possible bit we could have set */
if (prevbit == -1)
- prevbit = a->nwords * BITS_PER_BITMAPWORD - 1;
+ currbit = (uint32) a->nwords * BITS_PER_BITMAPWORD - 1;
else
- prevbit--;
+ currbit = prevbit - 1;
- ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(prevbit) + 1);
+ ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(currbit) + 1);
mask = (~(bitmapword) 0) >> ushiftbits;
- for (int wordnum = WORDNUM(prevbit); wordnum >= 0; wordnum--)
+ for (int wordnum = WORDNUM(currbit); wordnum >= 0; wordnum--)
{
bitmapword w = a->words[wordnum];
diff --git a/src/test/modules/test_bitmapset/test_bitmapset--1.0.sql b/src/test/modules/test_bitmapset/test_bitmapset--1.0.sql
index 6668bcef9a9..d6c0f739e13 100644
--- a/src/test/modules/test_bitmapset/test_bitmapset--1.0.sql
+++ b/src/test/modules/test_bitmapset/test_bitmapset--1.0.sql
@@ -3,6 +3,15 @@
-- complain if script is sourced in psql, rather than via CREATE EXTENSION
\echo Use "CREATE EXTENSION test_bitmapset" to load this file. \quit
+-- Benchmark functions
+CREATE FUNCTION bench_bms_next_member(text, integer)
+RETURNS bigint
+AS 'MODULE_PATHNAME' LANGUAGE C;
+
+CREATE FUNCTION bench_bms_prev_member(text, integer)
+RETURNS bigint
+AS 'MODULE_PATHNAME' LANGUAGE C;
+
-- Bitmapset API functions
CREATE FUNCTION test_bms_make_singleton(integer)
RETURNS text STRICT
diff --git a/src/test/modules/test_bitmapset/test_bitmapset.c b/src/test/modules/test_bitmapset/test_bitmapset.c
index 4fe22ee64d2..990347a0f22 100644
--- a/src/test/modules/test_bitmapset/test_bitmapset.c
+++ b/src/test/modules/test_bitmapset/test_bitmapset.c
@@ -17,6 +17,7 @@
#include "postgres.h"
#include <stddef.h>
+#include <time.h>
#include "catalog/pg_type.h"
#include "common/pg_prng.h"
#include "utils/array.h"
@@ -27,8 +28,13 @@
#include "utils/builtins.h"
#include "utils/timestamp.h"
+
PG_MODULE_MAGIC;
+/* Benchmark functions */
+PG_FUNCTION_INFO_V1(bench_bms_next_member);
+PG_FUNCTION_INFO_V1(bench_bms_prev_member);
+
/* Bitmapset API functions in order of appearance in bitmapset.c */
PG_FUNCTION_INFO_V1(test_bms_make_singleton);
PG_FUNCTION_INFO_V1(test_bms_add_member);
@@ -105,6 +111,73 @@ PG_FUNCTION_INFO_V1(test_random_shift_operations);
#define PG_RETURN_BITMAPSET_AS_TEXT(bms) \
PG_RETURN_TEXT_P(BITMAPSET_TO_TEXT(bms))
+#define NANOSEC_PER_SEC 1000000000
+
+int64 get_clock_diff(struct timespec* t1, struct timespec* t2);
+
+int64
+get_clock_diff(struct timespec* t1, struct timespec* t2)
+{
+ int64_t nanosec = (t1->tv_sec - t2->tv_sec) * NANOSEC_PER_SEC;
+ nanosec += (t1->tv_nsec - t2->tv_nsec);
+
+ return nanosec;
+}
+
+Datum
+bench_bms_next_member(PG_FUNCTION_ARGS)
+{
+ Bitmapset* bms = PG_ARG_GETBITMAPSET(0);
+ int32 loops = PG_GETARG_INT32(1);
+
+ struct timespec start, end;
+ int64 nanoseconds;
+ int64 counter = 0;
+
+ clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
+
+ for (int i = 0; i < loops; i++)
+ {
+ int m = -1;
+ while ((m = bms_next_member(bms, m)) >= 0)
+ {
+ counter++;
+ }
+ }
+
+ clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);
+ nanoseconds = get_clock_diff(&end, &start);
+
+ PG_RETURN_INT64(nanoseconds);
+}
+
+Datum
+bench_bms_prev_member(PG_FUNCTION_ARGS)
+{
+ Bitmapset* bms = PG_ARG_GETBITMAPSET(0);
+ int32 loops = PG_GETARG_INT32(1);
+
+ struct timespec start, end;
+ int64 nanoseconds;
+ int64 counter = 0;
+
+ clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
+
+ for (int i = 0; i < loops; i++)
+ {
+ int m = -1;
+ while ((m = bms_prev_member(bms, m)) >= 0)
+ {
+ counter++;
+ }
+ }
+
+ clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);
+ nanoseconds = get_clock_diff(&end, &start);
+
+ PG_RETURN_INT64(nanoseconds);
+}
+
/*
* Individual test functions for each bitmapset API function
*
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Small and unlikely overflow hazard in bms_next_member()
2026-04-02 04:09 Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-02 04:22 ` Re: Small and unlikely overflow hazard in bms_next_member() Tom Lane <[email protected]>
2026-04-02 22:12 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-03 02:08 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
@ 2026-04-03 03:24 ` Chao Li <[email protected]>
2026-04-03 11:42 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
1 sibling, 1 reply; 17+ messages in thread
From: Chao Li @ 2026-04-03 03:24 UTC (permalink / raw)
To: David Rowley <[email protected]>; +Cc: Tom Lane <[email protected]>; PostgreSQL Developers <[email protected]>
> On Apr 3, 2026, at 10:08, David Rowley <[email protected]> wrote:
>
> On Fri, 3 Apr 2026 at 11:12, David Rowley <[email protected]> wrote:
>>
>> On Thu, 2 Apr 2026 at 17:22, Tom Lane <[email protected]> wrote:
>>> I don't think we should add cycles here for this purpose.
>>
>> I'm not keen on slowing things down for this either. I did do some
>> experiments in [1] that sees fewer instructions from using 64-bit
>> maths. I might go off and see if there are any wins there that also
>> give us the INT_MAX fix. It's not great effort to reward ratio
>> though...
>
> The reduction in instructions with the patched version got me curious
> to see if it would translate into a performance increase. I tested on
> an AMD Zen2 machine, and it's a decent amount faster than master. I
> tested with gcc and clang.
>
> I also scanned over the remaining parts of bitmapset.c and didn't find
> anywhere else that has overflow risk aside from what you pointed out
> in bms_prev_member().
>
> The attached patch contains the benchmark function I added to the
> test_bitmapset module. It should apply to master with a bit of noise.
>
> CREATE EXTENSION test_bitmapset;
> SELECT
> generate_series(1,3) AS run,
> bench_bms_next_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 AS
> bms_next_member_us,
> bench_bms_prev_member('(b 1 2 3 4 5 6 7 8 64)', 1000000)/1000 AS
> bms_prev_member_us;
>
> master (gcc)
>
> run | bms_next_member_us | bms_prev_member_us
> -----+--------------------+--------------------
> 1 | 26473 | 40404
> 2 | 26218 | 40413
> 3 | 26209 | 40387
>
> patched (gcc)
>
> run | bms_next_member_us | bms_prev_member_us
> -----+--------------------+--------------------
> 1 | 25409 | 29705
> 2 | 24905 | 29693
> 3 | 24870 | 29707
>
> Times are in microseconds to do 1 million bms_*_member() loops over
> the entire set.
>
> I've also attached the full results I got. I've also included the
> results from Chao's version, which does slow things down decently on
> clang.
>
> IMO, if we can make bitmapset.c work with INT_MAX members and get a
> performance increase, then we should do it.
>
> David
>
>> [1] https://godbolt.org/z/Eh1vzssq7
> <benchmark_results.txt><bms_fixes.patch>
I also did a load test with a standalone c program with 4 versions:
* The original bms_next_member (Original)
* The fast version from [1], that uses 64bit maths (Fast)
* The original version + INT32_MAX check + 64bit maths (Original2)
* I tried the other approach that pulls up the first iteration, so that removes "mask = (~(bitmapword) 0);” from the loop. (PullUp)
Note: all tests used -O2 to build the executable.
On my MacBook M4, the Fast version constantly won, and PullUp version performed badly.
```
% gcc --version
Apple clang version 17.0.0 (clang-1700.6.4.2)
Target: arm64-apple-darwin25.3.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin
```
A typical test run:
```
Benchmarking 100000 iterations...
Original: 0.48893 seconds
Fast: 0.46979 seconds
Original2: 0.47740 seconds
PullUp: 0.48029 seconds
```
On my Windows laptop, Intel(R) Core Ultra 5, with WSL based Ubuntu, Orignal2 won in the most runs, and the PullUp version was faster than Fast version.
```
chaol@lichao-highgo:~$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
```
A typical test run:
```
Original: 0.99849 seconds
Fast: 0.74722 seconds
Original2: 0.59407 seconds
PullUp: 0.62746 seconds
```
Then I also tried to run on Windows directly. Here, PullUp version performed the best.
```
$ gcc --version
gcc.exe (Rev13, Built by MSYS2 project) 15.2.0
Copyright (C) 2025 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
```
A typical test run:
```
Original: 0.32931 seconds
Fast: 0.32740 seconds
Original2: 0.32378 seconds
PullUp: 0.30795 seconds
```
I’m curious that, when something performs differently across platforms, which platform should take priority?
Please see the attached test program. It’s possible I did something wrong.
[1] https://godbolt.org/z/Eh1vzssq7
--
Chao Li (Evan)
HighGo Software Co., Ltd.
https://www.highgo.com/
Attachments:
[application/octet-stream] test_bms_next.c (5.4K, 2-test_bms_next.c)
download
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Small and unlikely overflow hazard in bms_next_member()
2026-04-02 04:09 Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-02 04:22 ` Re: Small and unlikely overflow hazard in bms_next_member() Tom Lane <[email protected]>
2026-04-02 22:12 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-03 02:08 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-03 03:24 ` Re: Small and unlikely overflow hazard in bms_next_member() Chao Li <[email protected]>
@ 2026-04-03 11:42 ` David Rowley <[email protected]>
2026-04-03 13:28 ` Re: Small and unlikely overflow hazard in bms_next_member() Chao Li <[email protected]>
0 siblings, 1 reply; 17+ messages in thread
From: David Rowley @ 2026-04-03 11:42 UTC (permalink / raw)
To: Chao Li <[email protected]>; +Cc: Tom Lane <[email protected]>; PostgreSQL Developers <[email protected]>
On Fri, 3 Apr 2026 at 16:24, Chao Li <[email protected]> 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 = 20000; // Large set to bypass CPU cache slightly
Bitmapset *bms = malloc(sizeof(Bitmapset) + words_to_alloc *
sizeof(bitmapword));
bms->nwords = 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 = (words_to_alloc - 1) * 64 + 10;
bms->words[words_to_alloc - 1] |= (1ULL << 10);
A set with 20k words! Then you're doing:
for (int i = 0; i < iterations; i++) sink = 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’m curious that, when something performs differently across platforms, 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
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>
#include <limits.h>
//#define NULL ((void *) 0)
typedef uint64_t uint64;
typedef int64_t int64;
#define BITS_PER_BITMAPWORD 64
typedef uint64 bitmapword; /* must be an unsigned type */
typedef int64 signedbitmapword; /* must be the matching signed type */
#define WORDNUM(x) ((x) / BITS_PER_BITMAPWORD)
#define BITNUM(x) ((x) % BITS_PER_BITMAPWORD)
typedef struct Bitmapset
{
int nwords; /* number of words in array */
bitmapword words[]; /* really [nwords] */
} Bitmapset;
static inline int
bmw_rightmost_one_pos(uint64 word)
{
return __builtin_ctzll(word);
}
// 1. Original version
int
bms_next_member(const Bitmapset *a, int prevbit)
{
int nwords;
bitmapword mask;
if (a == NULL)
return -2;
nwords = a->nwords;
prevbit++;
mask = (~(bitmapword) 0) << BITNUM(prevbit);
for (int wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
{
bitmapword w = a->words[wordnum];
/* ignore bits before prevbit */
w &= mask;
if (w != 0)
{
int result;
result = wordnum * BITS_PER_BITMAPWORD;
result += bmw_rightmost_one_pos(w);
return result;
}
/* in subsequent words, consider all bits */
mask = (~(bitmapword) 0);
}
return -2;
}
// 2. David's version
int
bms_next_member_david(const Bitmapset *a, int prevbit)
{
int64 currbit;
size_t nwords;
bitmapword mask;
if (a == NULL)
return-2;
nwords = a->nwords;
currbit = (int64) prevbit + 1;
mask = (~(bitmapword) 0) << BITNUM(currbit);
for (size_t wordnum = WORDNUM(currbit); wordnum < nwords; wordnum++)
{
bitmapword w = a->words[wordnum];
/* ignore bits before currbit */
w &= mask;
if (w != 0)
{
int result;
result = (int) wordnum * BITS_PER_BITMAPWORD;
result += bmw_rightmost_one_pos(w);
return result;
}
/* in subsequent words, consider all bits */
mask = (~(bitmapword) 0);
}
return -2;
}
// 3. Original version + INT32_MAX check + 64bit
int
bms_next_member_chao(const Bitmapset *a, int prevbit)
{
size_t nwords;
bitmapword mask;
if (a == NULL || prevbit == INT32_MAX)
return -2;
nwords = (size_t) a->nwords;
prevbit++;
mask = (~(bitmapword) 0) << BITNUM(prevbit);
for (size_t wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
{
bitmapword w = a->words[wordnum];
/* ignore bits before prevbit */
w &= mask;
if (w != 0)
{
int result;
result = (int)wordnum * BITS_PER_BITMAPWORD;
result += bmw_rightmost_one_pos(w);
return result;
}
/* in subsequent words, consider all bits */
mask = (~(bitmapword) 0);
}
return -2;
}
// 4. Pull up first iteration
int bms_next_member_unroll_first(const Bitmapset *a, int prevbit)
{
uint64 currbit;
int wordnum;
int nwords;
if (a == NULL)
return -2;
currbit = (int64) prevbit + 1;
wordnum = WORDNUM(currbit);
nwords = a->nwords;
if (wordnum >= nwords)
return -2;
/* Handle first word with mask */
const bitmapword *p = &a->words[wordnum];
bitmapword w = (*p) & ((~(bitmapword) 0) << BITNUM(currbit));
if (w != 0)
return (wordnum * BITS_PER_BITMAPWORD) + bmw_rightmost_one_pos(w);
/* The "Tight" Pointer Scan */
const bitmapword *end = &a->words[nwords];
for (p++; p < end; p++)
{
if (*p != 0)
{
wordnum = p - a->words; // Pointer arithmetic to get index
return (wordnum * BITS_PER_BITMAPWORD) + bmw_rightmost_one_pos(*p);
}
}
return -2;
}
double get_time() {
struct timespec ts;
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts);
return ts.tv_sec + ts.tv_nsec * 1e-9;
}
int main() {
int words_to_alloc = 1; // Large set to bypass CPU cache slightly
Bitmapset *bms = malloc(sizeof(Bitmapset) + words_to_alloc * sizeof(bitmapword));
bms->nwords = words_to_alloc;
memset(bms->words, 0, words_to_alloc * sizeof(bitmapword));
double end;
int64 count = 0;
/* Set a bit far into the set to force a long scan */
bms->words[words_to_alloc - 1] |= 0xaf4;
int iterations = 100000000;
printf("Benchmarking %d iterations...\n\n", iterations);
// Test Original
double start = get_time();
for (int i = 0; i < iterations; i++)
{
int j = -1;
while ((j = bms_next_member(bms, j)) >= 0)
count++;
}
end = get_time();
printf("Original: %.5f seconds\n", end - start);
// Test Fast
start = get_time();
for (int i = 0; i < iterations; i++)
{
int j = -1;
while ((j = bms_next_member_david(bms, j)) >= 0)
count++;
}
end = get_time();
printf("David's: %.5f seconds\n", end - start);
// Test Chao's version
start = get_time();
for (int i = 0; i < iterations; i++)
{
int j = -1;
while ((j = bms_next_member_chao(bms, j)) >= 0)
count++;
}
end = get_time();
printf("Chao's version: %.5f seconds\n", end - start);
// Pull up first iteration
start = get_time();
for (int i = 0; i < iterations; i++)
{
int j = -1;
while ((j = bms_next_member_unroll_first(bms, j)) >= 0)
count++;
}
end = get_time();
printf("Unrolled loop: %.5f seconds\n", end - start);
printf("%ld\n", count);
free(bms);
return 0;
}
Attachments:
[text/plain] test_bms_next2.c (5.2K, 2-test_bms_next2.c)
download | inline:
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>
#include <limits.h>
//#define NULL ((void *) 0)
typedef uint64_t uint64;
typedef int64_t int64;
#define BITS_PER_BITMAPWORD 64
typedef uint64 bitmapword; /* must be an unsigned type */
typedef int64 signedbitmapword; /* must be the matching signed type */
#define WORDNUM(x) ((x) / BITS_PER_BITMAPWORD)
#define BITNUM(x) ((x) % BITS_PER_BITMAPWORD)
typedef struct Bitmapset
{
int nwords; /* number of words in array */
bitmapword words[]; /* really [nwords] */
} Bitmapset;
static inline int
bmw_rightmost_one_pos(uint64 word)
{
return __builtin_ctzll(word);
}
// 1. Original version
int
bms_next_member(const Bitmapset *a, int prevbit)
{
int nwords;
bitmapword mask;
if (a == NULL)
return -2;
nwords = a->nwords;
prevbit++;
mask = (~(bitmapword) 0) << BITNUM(prevbit);
for (int wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
{
bitmapword w = a->words[wordnum];
/* ignore bits before prevbit */
w &= mask;
if (w != 0)
{
int result;
result = wordnum * BITS_PER_BITMAPWORD;
result += bmw_rightmost_one_pos(w);
return result;
}
/* in subsequent words, consider all bits */
mask = (~(bitmapword) 0);
}
return -2;
}
// 2. David's version
int
bms_next_member_david(const Bitmapset *a, int prevbit)
{
int64 currbit;
size_t nwords;
bitmapword mask;
if (a == NULL)
return-2;
nwords = a->nwords;
currbit = (int64) prevbit + 1;
mask = (~(bitmapword) 0) << BITNUM(currbit);
for (size_t wordnum = WORDNUM(currbit); wordnum < nwords; wordnum++)
{
bitmapword w = a->words[wordnum];
/* ignore bits before currbit */
w &= mask;
if (w != 0)
{
int result;
result = (int) wordnum * BITS_PER_BITMAPWORD;
result += bmw_rightmost_one_pos(w);
return result;
}
/* in subsequent words, consider all bits */
mask = (~(bitmapword) 0);
}
return -2;
}
// 3. Original version + INT32_MAX check + 64bit
int
bms_next_member_chao(const Bitmapset *a, int prevbit)
{
size_t nwords;
bitmapword mask;
if (a == NULL || prevbit == INT32_MAX)
return -2;
nwords = (size_t) a->nwords;
prevbit++;
mask = (~(bitmapword) 0) << BITNUM(prevbit);
for (size_t wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
{
bitmapword w = a->words[wordnum];
/* ignore bits before prevbit */
w &= mask;
if (w != 0)
{
int result;
result = (int)wordnum * BITS_PER_BITMAPWORD;
result += bmw_rightmost_one_pos(w);
return result;
}
/* in subsequent words, consider all bits */
mask = (~(bitmapword) 0);
}
return -2;
}
// 4. Pull up first iteration
int bms_next_member_unroll_first(const Bitmapset *a, int prevbit)
{
uint64 currbit;
int wordnum;
int nwords;
if (a == NULL)
return -2;
currbit = (int64) prevbit + 1;
wordnum = WORDNUM(currbit);
nwords = a->nwords;
if (wordnum >= nwords)
return -2;
/* Handle first word with mask */
const bitmapword *p = &a->words[wordnum];
bitmapword w = (*p) & ((~(bitmapword) 0) << BITNUM(currbit));
if (w != 0)
return (wordnum * BITS_PER_BITMAPWORD) + bmw_rightmost_one_pos(w);
/* The "Tight" Pointer Scan */
const bitmapword *end = &a->words[nwords];
for (p++; p < end; p++)
{
if (*p != 0)
{
wordnum = p - a->words; // Pointer arithmetic to get index
return (wordnum * BITS_PER_BITMAPWORD) + bmw_rightmost_one_pos(*p);
}
}
return -2;
}
double get_time() {
struct timespec ts;
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts);
return ts.tv_sec + ts.tv_nsec * 1e-9;
}
int main() {
int words_to_alloc = 1; // Large set to bypass CPU cache slightly
Bitmapset *bms = malloc(sizeof(Bitmapset) + words_to_alloc * sizeof(bitmapword));
bms->nwords = words_to_alloc;
memset(bms->words, 0, words_to_alloc * sizeof(bitmapword));
double end;
int64 count = 0;
/* Set a bit far into the set to force a long scan */
bms->words[words_to_alloc - 1] |= 0xaf4;
int iterations = 100000000;
printf("Benchmarking %d iterations...\n\n", iterations);
// Test Original
double start = get_time();
for (int i = 0; i < iterations; i++)
{
int j = -1;
while ((j = bms_next_member(bms, j)) >= 0)
count++;
}
end = get_time();
printf("Original: %.5f seconds\n", end - start);
// Test Fast
start = get_time();
for (int i = 0; i < iterations; i++)
{
int j = -1;
while ((j = bms_next_member_david(bms, j)) >= 0)
count++;
}
end = get_time();
printf("David's: %.5f seconds\n", end - start);
// Test Chao's version
start = get_time();
for (int i = 0; i < iterations; i++)
{
int j = -1;
while ((j = bms_next_member_chao(bms, j)) >= 0)
count++;
}
end = get_time();
printf("Chao's version: %.5f seconds\n", end - start);
// Pull up first iteration
start = get_time();
for (int i = 0; i < iterations; i++)
{
int j = -1;
while ((j = bms_next_member_unroll_first(bms, j)) >= 0)
count++;
}
end = get_time();
printf("Unrolled loop: %.5f seconds\n", end - start);
printf("%ld\n", count);
free(bms);
return 0;
}
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Small and unlikely overflow hazard in bms_next_member()
2026-04-02 04:09 Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-02 04:22 ` Re: Small and unlikely overflow hazard in bms_next_member() Tom Lane <[email protected]>
2026-04-02 22:12 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-03 02:08 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-03 03:24 ` Re: Small and unlikely overflow hazard in bms_next_member() Chao Li <[email protected]>
2026-04-03 11:42 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
@ 2026-04-03 13:28 ` Chao Li <[email protected]>
2026-04-04 03:30 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
0 siblings, 1 reply; 17+ messages in thread
From: Chao Li @ 2026-04-03 13:28 UTC (permalink / raw)
To: David Rowley <[email protected]>; +Cc: Tom Lane <[email protected]>; PostgreSQL Developers <[email protected]>
> On Apr 3, 2026, at 19:42, David Rowley <[email protected]> wrote:
>
> On Fri, 3 Apr 2026 at 16:24, Chao Li <[email protected]> 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 = 20000; // Large set to bypass CPU cache slightly
> Bitmapset *bms = malloc(sizeof(Bitmapset) + words_to_alloc *
> sizeof(bitmapword));
> bms->nwords = 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 = (words_to_alloc - 1) * 64 + 10;
> bms->words[words_to_alloc - 1] |= (1ULL << 10);
>
> A set with 20k words! Then you're doing:
>
> for (int i = 0; i < iterations; i++) sink = 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’m curious that, when something performs differently across platforms, 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
> <test_bms_next2.c>
In test_bms_next2.c, you set words_to_alloc = 1, which disables the optimization in the unrolled version. If I change words_to_alloc = 2, then on 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
```
(I also checked on Godbolt, from the instruction-count perspective, the unrolled version actually looks the worst.)
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 improvement. If we really want to study the performance more deeply, I think that would be a separate topic.
It was fun working on this patch, and thank you for your patience.
Best regards,
--
Chao Li (Evan)
HighGo Software Co., Ltd.
https://www.highgo.com/
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Small and unlikely overflow hazard in bms_next_member()
2026-04-02 04:09 Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-02 04:22 ` Re: Small and unlikely overflow hazard in bms_next_member() Tom Lane <[email protected]>
2026-04-02 22:12 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-03 02:08 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-03 03:24 ` Re: Small and unlikely overflow hazard in bms_next_member() Chao Li <[email protected]>
2026-04-03 11:42 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-03 13:28 ` Re: Small and unlikely overflow hazard in bms_next_member() Chao Li <[email protected]>
@ 2026-04-04 03:30 ` David Rowley <[email protected]>
2026-04-06 02:00 ` Re: Small and unlikely overflow hazard in bms_next_member() Chao Li <[email protected]>
0 siblings, 1 reply; 17+ messages in thread
From: David Rowley @ 2026-04-04 03:30 UTC (permalink / raw)
To: Chao Li <[email protected]>; +Cc: Tom Lane <[email protected]>; PostgreSQL Developers <[email protected]>
On Sat, 4 Apr 2026 at 02:28, Chao Li <[email protected]> wrote:
> In test_bms_next2.c, you set words_to_alloc = 1, which disables the optimization in the unrolled version. If I change words_to_alloc = 2, then on 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 improvement. If we really want to study the performance more deeply, I think that would 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 >= 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 = WORDNUM(x);
@@ -811,6 +815,9 @@ bms_add_member(Bitmapset *a, int x)
wordnum = WORDNUM(x);
bitnum = BITNUM(x);
+ if (x >= 64 && a->nwords == 1)
+ elog(NOTICE, "multi-set bms_add_member");
+
/* enlarge the set if necessary */
if (wordnum >= 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
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Small and unlikely overflow hazard in bms_next_member()
2026-04-02 04:09 Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-02 04:22 ` Re: Small and unlikely overflow hazard in bms_next_member() Tom Lane <[email protected]>
2026-04-02 22:12 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-03 02:08 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-03 03:24 ` Re: Small and unlikely overflow hazard in bms_next_member() Chao Li <[email protected]>
2026-04-03 11:42 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-03 13:28 ` Re: Small and unlikely overflow hazard in bms_next_member() Chao Li <[email protected]>
2026-04-04 03:30 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
@ 2026-04-06 02:00 ` Chao Li <[email protected]>
2026-04-12 12:33 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
0 siblings, 1 reply; 17+ messages in thread
From: Chao Li @ 2026-04-06 02:00 UTC (permalink / raw)
To: David Rowley <[email protected]>; +Cc: Tom Lane <[email protected]>; PostgreSQL Developers <[email protected]>
> On Apr 4, 2026, at 11:30, David Rowley <[email protected]> wrote:
>
> On Sat, 4 Apr 2026 at 02:28, Chao Li <[email protected]> wrote:
>> In test_bms_next2.c, you set words_to_alloc = 1, which disables the optimization in the unrolled version. If I change words_to_alloc = 2, then on 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 just tried my Windows laptop with both MSYS2 and WSL Ubuntu, and on both of them the original version and David’s version consistently performed better than the other versions.
I have a new finding from Godbolt: adding likely(w != 0) seems to reduce the instruction count by one. bms_next_member_fast has 26 instructions, while after adding "likely", bms_next_member_fast2 has 25. It seems that this may avoid one jump and perhaps be slightly better, but I’m not sure. I’m really not an expert in assembly.
Then I tested. “likely” doesn’t seem to help on Mac:
```
chaol@ChaodeMacBook-Air test % ./test_bms_next2
Benchmarking 100000000 iterations...
Original: 0.54994 seconds
David's: 0.78218 seconds
David's likely: 0.78990 seconds
Chao's version: 1.11530 seconds
Unrolled loop: 0.47660 seconds
3500000000
```
But it helps slightly on Windows:
```
$ ./test_bms_next2
Benchmarking 100000000 iterations...
Original: 1.45312 seconds
David's: 1.48438 seconds
David's likely: 1.40625 seconds
Chao's version: 3.12500 seconds
Unrolled loop: 2.95312 seconds
-794967296
```
I’m not suggesting adding likely() to your version, I’m just sharing the information for your reference and leaving the decision to you.
>
>> 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 improvement. If we really want to study the performance more deeply, I think that would 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.
Fully agreed.
> 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 >= 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 = WORDNUM(x);
> @@ -811,6 +815,9 @@ bms_add_member(Bitmapset *a, int x)
> wordnum = WORDNUM(x);
> bitnum = BITNUM(x);
>
> + if (x >= 64 && a->nwords == 1)
> + elog(NOTICE, "multi-set bms_add_member");
> +
> /* enlarge the set if necessary */
> if (wordnum >= 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.
>
What tests did you run after adding the logs to collect the data? This is a method I might borrow in the future for similar investigations.
Best regards,
--
Chao Li (Evan)
HighGo Software Co., Ltd.
https://www.highgo.com/
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Small and unlikely overflow hazard in bms_next_member()
2026-04-02 04:09 Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-02 04:22 ` Re: Small and unlikely overflow hazard in bms_next_member() Tom Lane <[email protected]>
2026-04-02 22:12 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-03 02:08 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-03 03:24 ` Re: Small and unlikely overflow hazard in bms_next_member() Chao Li <[email protected]>
2026-04-03 11:42 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-03 13:28 ` Re: Small and unlikely overflow hazard in bms_next_member() Chao Li <[email protected]>
2026-04-04 03:30 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-06 02:00 ` Re: Small and unlikely overflow hazard in bms_next_member() Chao Li <[email protected]>
@ 2026-04-12 12:33 ` David Rowley <[email protected]>
0 siblings, 0 replies; 17+ messages in thread
From: David Rowley @ 2026-04-12 12:33 UTC (permalink / raw)
To: Chao Li <[email protected]>; +Cc: Tom Lane <[email protected]>; PostgreSQL Developers <[email protected]>
On Mon, 6 Apr 2026 at 14:01, Chao Li <[email protected]> wrote:
> > On Apr 4, 2026, at 11:30, David Rowley <[email protected]> wrote:
> > 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.
> >
>
> What tests did you run after adding the logs to collect the data? This is a method I might borrow in the future for similar investigations.
"make check" then grep regression.diffs for the NOTICE message and
pipe to "wc -l"
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Small and unlikely overflow hazard in bms_next_member()
2026-04-02 04:09 Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-02 04:22 ` Re: Small and unlikely overflow hazard in bms_next_member() Tom Lane <[email protected]>
2026-04-02 22:12 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-03 02:08 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
@ 2026-04-12 13:17 ` David Rowley <[email protected]>
2026-04-12 23:41 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-13 00:23 ` Re: Small and unlikely overflow hazard in bms_next_member() Chao Li <[email protected]>
1 sibling, 2 replies; 17+ messages in thread
From: David Rowley @ 2026-04-12 13:17 UTC (permalink / raw)
To: Tom Lane <[email protected]>; +Cc: PostgreSQL Developers <[email protected]>
On Fri, 3 Apr 2026 at 15:08, David Rowley <[email protected]> wrote:
> IMO, if we can make bitmapset.c work with INT_MAX members and get a
> performance increase, then we should do it.
Re-thinking this after a week's holiday, it seems fine to use an
unsigned 32-bit int rather than a 64-bit int to fix this bug. I'd
previously been uncertain if there were any guarantees in C to what
(unsigned int) -1 would return, but going by [1] at 6.3.1.3, it says:
"Otherwise, if the new type is unsigned, the value is converted by
repeatedly adding or subtracting one more than the maximum value that
can be represented in the new type until the value is in the range of
the new type."
So, it seems even on one's complement that -1 as an unsigned int will
be UINT_MAX. When we add 1 to UINT_MAX, we're guaranteed to get 0, as
it's unsigned maths and overflows are going to result in a value
modulus the max value for the type.
That leads me to the attached v2 patch. Compiler Explorer link showing
the assembly at [2].
Testing the performance, it's better than master, so I got rid of the
size_t wordnum stuff. We're post-freeze now, so fiddling with other
optimisations seems a bit off the table as there appears to be no
performance regression to compensate for now, per:
drowley@amd3990x:~$ gcc test_bms_next3.c -O2 -o test_bms_next3 &&
./test_bms_next3
Benchmarking 100000000 bms_next_member iterations...
master: 1.18330 seconds
Patched: 1.05493 seconds
Benchmarking 100000000 bms_prev_member iterations...
master: 2.94522 seconds
Patched: 1.86130 seconds
drowley@amd3990x:~$ clang test_bms_next3.c -O2 -o test_bms_next3 &&
./test_bms_next3
Benchmarking 100000000 bms_next_member iterations...
master: 1.07860 seconds
Patched: 1.07896 seconds
Benchmarking 100000000 bms_prev_member iterations...
master: 2.76550 seconds
Patched: 2.12369 seconds
David
[1] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1548.pdf
[2] https://godbolt.org/z/xW96rxd3P
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>
#include <limits.h>
//#define NULL ((void *) 0)
typedef uint32_t uint32;
typedef int32_t int32;
typedef uint64_t uint64;
typedef int64_t int64;
#define BITS_PER_BITMAPWORD 64
typedef uint64 bitmapword; /* must be an unsigned type */
typedef int64 signedbitmapword; /* must be the matching signed type */
#define WORDNUM(x) ((x) / BITS_PER_BITMAPWORD)
#define BITNUM(x) ((x) % BITS_PER_BITMAPWORD)
#ifdef __GNUC__
#define likely(x) __builtin_expect((x) != 0, 1)
#define unlikely(x) __builtin_expect((x) != 0, 0)
#else
#define likely(x) ((x) != 0)
#define unlikely(x) ((x) != 0)
#endif
typedef struct Bitmapset
{
int nwords; /* number of words in array */
bitmapword words[]; /* really [nwords] */
} Bitmapset;
static inline int
bmw_rightmost_one_pos(uint64 word)
{
return __builtin_ctzll(word);
}
static inline int
bmw_leftmost_one_pos(uint64 word)
{
return 63 - __builtin_clzll(word);
}
int
bms_next_member(const Bitmapset *a, int prevbit)
{
int nwords;
bitmapword mask;
if (a == NULL)
return -2;
nwords = a->nwords;
prevbit++;
mask = (~(bitmapword) 0) << BITNUM(prevbit);
for (int wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
{
bitmapword w = a->words[wordnum];
/* ignore bits before prevbit */
w &= mask;
if (w != 0)
{
int result;
result = wordnum * BITS_PER_BITMAPWORD;
result += bmw_rightmost_one_pos(w);
return result;
}
/* in subsequent words, consider all bits */
mask = (~(bitmapword) 0);
}
return -2;
}
int
bms_next_member_patched(const Bitmapset *a, int prevbit)
{
unsigned int currbit = prevbit;
int nwords;
bitmapword mask;
if (a == NULL)
return -2;
nwords = a->nwords;
/* use an unsigned int to avoid the risk that int overflows */
currbit++;
mask = (~(bitmapword) 0) << BITNUM(currbit);
for (int wordnum = WORDNUM(currbit); wordnum < nwords; wordnum++)
{
bitmapword w = a->words[wordnum];
/* ignore bits before currbit */
w &= mask;
if (w != 0)
{
int result;
result = wordnum * BITS_PER_BITMAPWORD;
result += bmw_rightmost_one_pos(w);
return result;
}
/* in subsequent words, consider all bits */
mask = (~(bitmapword) 0);
}
return -2;
}
int
bms_prev_member(const Bitmapset *a, int prevbit)
{
int ushiftbits;
bitmapword mask;
/*
* If set is NULL or if there are no more bits to the right then we've
* nothing to do.
*/
if (a == NULL || prevbit == 0)
return -2;
/* transform -1 to the highest possible bit we could have set */
if (prevbit == -1)
prevbit = a->nwords * BITS_PER_BITMAPWORD - 1;
else
prevbit--;
ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(prevbit) + 1);
mask = (~(bitmapword) 0) >> ushiftbits;
for (int wordnum = WORDNUM(prevbit); wordnum >= 0; wordnum--)
{
bitmapword w = a->words[wordnum];
/* mask out bits left of prevbit */
w &= mask;
if (w != 0)
{
int result;
result = wordnum * BITS_PER_BITMAPWORD;
result += bmw_leftmost_one_pos(w);
return result;
}
/* in subsequent words, consider all bits */
mask = (~(bitmapword) 0);
}
return -2;
}
int
bms_prev_member_patched(const Bitmapset *a, int prevbit)
{
unsigned int currbit;
int ushiftbits;
bitmapword mask;
/*
* If set is NULL or if there are no more bits to the right then we've
* nothing to do.
*/
if (a == NULL || prevbit == 0)
return -2;
/*
* Transform -1 to the highest possible bit we could have set. We do this
* in unsigned math to avoid the risk of overflowing a signed int.
*/
if (prevbit < 0)
currbit = (unsigned int) a->nwords * BITS_PER_BITMAPWORD - 1;
else
currbit = prevbit - 1;
ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(currbit) + 1);
mask = (~(bitmapword) 0) >> ushiftbits;
for (int wordnum = WORDNUM(currbit); wordnum >= 0; wordnum--)
{
bitmapword w = a->words[wordnum];
/* mask out bits left of currbit */
w &= mask;
if (w != 0)
{
int result;
result = wordnum * BITS_PER_BITMAPWORD;
result += bmw_leftmost_one_pos(w);
return result;
}
/* in subsequent words, consider all bits */
mask = (~(bitmapword) 0);
}
return -2;
}
double get_time() {
struct timespec ts;
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts);
return ts.tv_sec + ts.tv_nsec * 1e-9;
}
Bitmapset *bms;
int main() {
int words_to_alloc = 1; // Large set to bypass CPU cache slightly
bms = malloc(sizeof(Bitmapset) + words_to_alloc * sizeof(bitmapword));
bms->nwords = words_to_alloc;
memset(bms->words, 0, words_to_alloc * sizeof(bitmapword));
double start, end;
int64 count = 0;
/* Set a bit far into the set to force a long scan */
bms->words[words_to_alloc - 1] |= 0xaf4;
int iterations = 100000000;
printf("Benchmarking %d bms_next_member iterations...\n", iterations);
/* master */
start = get_time();
for (int i = 0; i < iterations; i++)
{
int j = -1;
while ((j = bms_next_member(bms, j)) >= 0)
count++;
}
end = get_time();
printf("master: %.5f seconds\n", end - start);
// Test David
start = get_time();
for (int i = 0; i < iterations; i++)
{
int j = -1;
while ((j = bms_next_member_patched(bms, j)) >= 0)
count++;
}
end = get_time();
printf("Patched: %.5f seconds\n", end - start);
printf("\nBenchmarking %d bms_prev_member iterations...\n", iterations);
/* master */
start = get_time();
for (int i = 0; i < iterations; i++)
{
int j = -1;
while ((j = bms_prev_member(bms, j)) >= 0)
count++;
}
end = get_time();
printf("master: %.5f seconds\n", end - start);
// Test David
start = get_time();
for (int i = 0; i < iterations; i++)
{
int j = -1;
while ((j = bms_prev_member_patched(bms, j)) >= 0)
count++;
}
end = get_time();
printf("Patched: %.5f seconds\n", end - start);
printf("%ld\n", count);
free(bms);
return 0;
}
Attachments:
[text/plain] test_bms_next3.c (5.7K, 2-test_bms_next3.c)
download | inline:
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>
#include <limits.h>
//#define NULL ((void *) 0)
typedef uint32_t uint32;
typedef int32_t int32;
typedef uint64_t uint64;
typedef int64_t int64;
#define BITS_PER_BITMAPWORD 64
typedef uint64 bitmapword; /* must be an unsigned type */
typedef int64 signedbitmapword; /* must be the matching signed type */
#define WORDNUM(x) ((x) / BITS_PER_BITMAPWORD)
#define BITNUM(x) ((x) % BITS_PER_BITMAPWORD)
#ifdef __GNUC__
#define likely(x) __builtin_expect((x) != 0, 1)
#define unlikely(x) __builtin_expect((x) != 0, 0)
#else
#define likely(x) ((x) != 0)
#define unlikely(x) ((x) != 0)
#endif
typedef struct Bitmapset
{
int nwords; /* number of words in array */
bitmapword words[]; /* really [nwords] */
} Bitmapset;
static inline int
bmw_rightmost_one_pos(uint64 word)
{
return __builtin_ctzll(word);
}
static inline int
bmw_leftmost_one_pos(uint64 word)
{
return 63 - __builtin_clzll(word);
}
int
bms_next_member(const Bitmapset *a, int prevbit)
{
int nwords;
bitmapword mask;
if (a == NULL)
return -2;
nwords = a->nwords;
prevbit++;
mask = (~(bitmapword) 0) << BITNUM(prevbit);
for (int wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
{
bitmapword w = a->words[wordnum];
/* ignore bits before prevbit */
w &= mask;
if (w != 0)
{
int result;
result = wordnum * BITS_PER_BITMAPWORD;
result += bmw_rightmost_one_pos(w);
return result;
}
/* in subsequent words, consider all bits */
mask = (~(bitmapword) 0);
}
return -2;
}
int
bms_next_member_patched(const Bitmapset *a, int prevbit)
{
unsigned int currbit = prevbit;
int nwords;
bitmapword mask;
if (a == NULL)
return -2;
nwords = a->nwords;
/* use an unsigned int to avoid the risk that int overflows */
currbit++;
mask = (~(bitmapword) 0) << BITNUM(currbit);
for (int wordnum = WORDNUM(currbit); wordnum < nwords; wordnum++)
{
bitmapword w = a->words[wordnum];
/* ignore bits before currbit */
w &= mask;
if (w != 0)
{
int result;
result = wordnum * BITS_PER_BITMAPWORD;
result += bmw_rightmost_one_pos(w);
return result;
}
/* in subsequent words, consider all bits */
mask = (~(bitmapword) 0);
}
return -2;
}
int
bms_prev_member(const Bitmapset *a, int prevbit)
{
int ushiftbits;
bitmapword mask;
/*
* If set is NULL or if there are no more bits to the right then we've
* nothing to do.
*/
if (a == NULL || prevbit == 0)
return -2;
/* transform -1 to the highest possible bit we could have set */
if (prevbit == -1)
prevbit = a->nwords * BITS_PER_BITMAPWORD - 1;
else
prevbit--;
ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(prevbit) + 1);
mask = (~(bitmapword) 0) >> ushiftbits;
for (int wordnum = WORDNUM(prevbit); wordnum >= 0; wordnum--)
{
bitmapword w = a->words[wordnum];
/* mask out bits left of prevbit */
w &= mask;
if (w != 0)
{
int result;
result = wordnum * BITS_PER_BITMAPWORD;
result += bmw_leftmost_one_pos(w);
return result;
}
/* in subsequent words, consider all bits */
mask = (~(bitmapword) 0);
}
return -2;
}
int
bms_prev_member_patched(const Bitmapset *a, int prevbit)
{
unsigned int currbit;
int ushiftbits;
bitmapword mask;
/*
* If set is NULL or if there are no more bits to the right then we've
* nothing to do.
*/
if (a == NULL || prevbit == 0)
return -2;
/*
* Transform -1 to the highest possible bit we could have set. We do this
* in unsigned math to avoid the risk of overflowing a signed int.
*/
if (prevbit < 0)
currbit = (unsigned int) a->nwords * BITS_PER_BITMAPWORD - 1;
else
currbit = prevbit - 1;
ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(currbit) + 1);
mask = (~(bitmapword) 0) >> ushiftbits;
for (int wordnum = WORDNUM(currbit); wordnum >= 0; wordnum--)
{
bitmapword w = a->words[wordnum];
/* mask out bits left of currbit */
w &= mask;
if (w != 0)
{
int result;
result = wordnum * BITS_PER_BITMAPWORD;
result += bmw_leftmost_one_pos(w);
return result;
}
/* in subsequent words, consider all bits */
mask = (~(bitmapword) 0);
}
return -2;
}
double get_time() {
struct timespec ts;
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts);
return ts.tv_sec + ts.tv_nsec * 1e-9;
}
Bitmapset *bms;
int main() {
int words_to_alloc = 1; // Large set to bypass CPU cache slightly
bms = malloc(sizeof(Bitmapset) + words_to_alloc * sizeof(bitmapword));
bms->nwords = words_to_alloc;
memset(bms->words, 0, words_to_alloc * sizeof(bitmapword));
double start, end;
int64 count = 0;
/* Set a bit far into the set to force a long scan */
bms->words[words_to_alloc - 1] |= 0xaf4;
int iterations = 100000000;
printf("Benchmarking %d bms_next_member iterations...\n", iterations);
/* master */
start = get_time();
for (int i = 0; i < iterations; i++)
{
int j = -1;
while ((j = bms_next_member(bms, j)) >= 0)
count++;
}
end = get_time();
printf("master: %.5f seconds\n", end - start);
// Test David
start = get_time();
for (int i = 0; i < iterations; i++)
{
int j = -1;
while ((j = bms_next_member_patched(bms, j)) >= 0)
count++;
}
end = get_time();
printf("Patched: %.5f seconds\n", end - start);
printf("\nBenchmarking %d bms_prev_member iterations...\n", iterations);
/* master */
start = get_time();
for (int i = 0; i < iterations; i++)
{
int j = -1;
while ((j = bms_prev_member(bms, j)) >= 0)
count++;
}
end = get_time();
printf("master: %.5f seconds\n", end - start);
// Test David
start = get_time();
for (int i = 0; i < iterations; i++)
{
int j = -1;
while ((j = bms_prev_member_patched(bms, j)) >= 0)
count++;
}
end = get_time();
printf("Patched: %.5f seconds\n", end - start);
printf("%ld\n", count);
free(bms);
return 0;
}
[application/octet-stream] v2-0001-Fix-unlikely-overflow-bug-in-bms_next_member.patch (3.2K, 3-v2-0001-Fix-unlikely-overflow-bug-in-bms_next_member.patch)
download | inline diff:
From d1c644ba4de05624fc5a63b3d5f4026c71ed4aa5 Mon Sep 17 00:00:00 2001
From: David Rowley <[email protected]>
Date: Sat, 4 Apr 2026 16:41:23 +1300
Subject: [PATCH v2] Fix unlikely overflow bug in bms_next_member()
... and bms_prev_member().
Both of these functions won't work correctly when given a prevbit of
INT_MAX. Here we fix that by using an unsigned int to calculate which
member to look for next.
In practise, Bitmapsets will never have such a large member, so no
backpatch.
Author: David Rowley <[email protected]>
Reviewed-by: Chao Li <[email protected]>
Discussion: https://postgr.es/m/CAApHDvq0T%3DiJ0Sf5TNE9yyWwfOeVjmrBt0wSywDnGD9Y4YJQBA%40mail.gmail.com
---
src/backend/nodes/bitmapset.c | 33 +++++++++++++++++++--------------
1 file changed, 19 insertions(+), 14 deletions(-)
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 786f343b3c9..957172648c3 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -1289,6 +1289,7 @@ bms_join(Bitmapset *a, Bitmapset *b)
int
bms_next_member(const Bitmapset *a, int prevbit)
{
+ unsigned int currbit = prevbit;
int nwords;
bitmapword mask;
@@ -1297,13 +1298,15 @@ bms_next_member(const Bitmapset *a, int prevbit)
if (a == NULL)
return -2;
nwords = a->nwords;
- prevbit++;
- mask = (~(bitmapword) 0) << BITNUM(prevbit);
- for (int wordnum = WORDNUM(prevbit); wordnum < nwords; wordnum++)
+
+ /* use an unsigned int to avoid the risk that int overflows */
+ currbit++;
+ mask = (~(bitmapword) 0) << BITNUM(currbit);
+ for (int wordnum = WORDNUM(currbit); wordnum < nwords; wordnum++)
{
bitmapword w = a->words[wordnum];
- /* ignore bits before prevbit */
+ /* ignore bits before currbit */
w &= mask;
if (w != 0)
@@ -1345,10 +1348,10 @@ bms_next_member(const Bitmapset *a, int prevbit)
* It makes no difference in simple loop usage, but complex iteration logic
* might need such an ability.
*/
-
int
bms_prev_member(const Bitmapset *a, int prevbit)
{
+ unsigned int currbit;
int ushiftbits;
bitmapword mask;
@@ -1362,22 +1365,24 @@ bms_prev_member(const Bitmapset *a, int prevbit)
return -2;
/* Validate callers didn't give us something out of range */
- Assert(prevbit <= a->nwords * BITS_PER_BITMAPWORD);
- Assert(prevbit >= -1);
+ Assert(prevbit < 0 || prevbit <= (unsigned int) (a->nwords * BITS_PER_BITMAPWORD));
- /* transform -1 to the highest possible bit we could have set */
- if (prevbit == -1)
- prevbit = a->nwords * BITS_PER_BITMAPWORD - 1;
+ /*
+ * Transform -1 to the highest possible bit we could have set. We do this
+ * in unsigned math to avoid the risk of overflowing a signed int.
+ */
+ if (prevbit < 0)
+ currbit = (unsigned int) a->nwords * BITS_PER_BITMAPWORD - 1;
else
- prevbit--;
+ currbit = prevbit - 1;
- ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(prevbit) + 1);
+ ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(currbit) + 1);
mask = (~(bitmapword) 0) >> ushiftbits;
- for (int wordnum = WORDNUM(prevbit); wordnum >= 0; wordnum--)
+ for (int wordnum = WORDNUM(currbit); wordnum >= 0; wordnum--)
{
bitmapword w = a->words[wordnum];
- /* mask out bits left of prevbit */
+ /* mask out bits left of currbit */
w &= mask;
if (w != 0)
--
2.51.0
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Small and unlikely overflow hazard in bms_next_member()
2026-04-02 04:09 Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-02 04:22 ` Re: Small and unlikely overflow hazard in bms_next_member() Tom Lane <[email protected]>
2026-04-02 22:12 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-03 02:08 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-12 13:17 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
@ 2026-04-12 23:41 ` David Rowley <[email protected]>
1 sibling, 0 replies; 17+ messages in thread
From: David Rowley @ 2026-04-12 23:41 UTC (permalink / raw)
To: Tom Lane <[email protected]>; +Cc: PostgreSQL Developers <[email protected]>
On Mon, 13 Apr 2026 at 01:17, David Rowley <[email protected]> wrote:
> Re-thinking this after a week's holiday, it seems fine to use an
> unsigned 32-bit int rather than a 64-bit int to fix this bug. I'd
> previously been uncertain if there were any guarantees in C to what
> (unsigned int) -1 would return, but going by [1] at 6.3.1.3, it says:
>
> "Otherwise, if the new type is unsigned, the value is converted by
> repeatedly adding or subtracting one more than the maximum value that
> can be represented in the new type until the value is in the range of
> the new type."
>
> So, it seems even on one's complement that -1 as an unsigned int will
> be UINT_MAX. When we add 1 to UINT_MAX, we're guaranteed to get 0, as
> it's unsigned maths and overflows are going to result in a value
> modulus the max value for the type.
I've pushed that version. No backpatch.
David
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Small and unlikely overflow hazard in bms_next_member()
2026-04-02 04:09 Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-02 04:22 ` Re: Small and unlikely overflow hazard in bms_next_member() Tom Lane <[email protected]>
2026-04-02 22:12 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-03 02:08 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-12 13:17 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
@ 2026-04-13 00:23 ` Chao Li <[email protected]>
2026-04-13 02:43 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
1 sibling, 1 reply; 17+ messages in thread
From: Chao Li @ 2026-04-13 00:23 UTC (permalink / raw)
To: David Rowley <[email protected]>; +Cc: Tom Lane <[email protected]>; PostgreSQL Developers <[email protected]>
> On Apr 12, 2026, at 21:17, David Rowley <[email protected]> wrote:
>
> On Fri, 3 Apr 2026 at 15:08, David Rowley <[email protected]> wrote:
>> IMO, if we can make bitmapset.c work with INT_MAX members and get a
>> performance increase, then we should do it.
>
> Re-thinking this after a week's holiday, it seems fine to use an
> unsigned 32-bit int rather than a 64-bit int to fix this bug. I'd
> previously been uncertain if there were any guarantees in C to what
> (unsigned int) -1 would return, but going by [1] at 6.3.1.3, it says:
>
> "Otherwise, if the new type is unsigned, the value is converted by
> repeatedly adding or subtracting one more than the maximum value that
> can be represented in the new type until the value is in the range of
> the new type."
>
> So, it seems even on one's complement that -1 as an unsigned int will
> be UINT_MAX. When we add 1 to UINT_MAX, we're guaranteed to get 0, as
> it's unsigned maths and overflows are going to result in a value
> modulus the max value for the type.
>
> That leads me to the attached v2 patch. Compiler Explorer link showing
> the assembly at [2].
>
> Testing the performance, it's better than master, so I got rid of the
> size_t wordnum stuff. We're post-freeze now, so fiddling with other
> optimisations seems a bit off the table as there appears to be no
> performance regression to compensate for now, per:
>
> drowley@amd3990x:~$ gcc test_bms_next3.c -O2 -o test_bms_next3 &&
> ./test_bms_next3
> Benchmarking 100000000 bms_next_member iterations...
> master: 1.18330 seconds
> Patched: 1.05493 seconds
>
> Benchmarking 100000000 bms_prev_member iterations...
> master: 2.94522 seconds
> Patched: 1.86130 seconds
>
> drowley@amd3990x:~$ clang test_bms_next3.c -O2 -o test_bms_next3 &&
> ./test_bms_next3
> Benchmarking 100000000 bms_next_member iterations...
> master: 1.07860 seconds
> Patched: 1.07896 seconds
>
> Benchmarking 100000000 bms_prev_member iterations...
> master: 2.76550 seconds
> Patched: 2.12369 seconds
>
> David
>
> [1] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1548.pdf
> [2] https://godbolt.org/z/xW96rxd3P
> <test_bms_next3.c><v2-0001-Fix-unlikely-overflow-bug-in-bms_next_member.patch>
I just tried test_bms_next3 on my MacBook, looks like patched bms_prev_member is much faster there. I ran about 10 times, the results were consistent.
```
chaol@ChaodeMacBook-Air test % gcc test_bms_next3.c -O2 -o test_bms_next3
test_bms_next3.c:281:18: warning: format specifies type 'long' but the argument has type 'int64' (aka 'long long') [-Wformat]
281 | printf("%ld\n", count);
| ~~~ ^~~~~
| %lld
1 warning generated.
chaol@ChaodeMacBook-Air test % ./test_bms_next3
Benchmarking 100000000 bms_next_member iterations...
master: 0.49287 seconds
Patched: 0.47315 seconds
Benchmarking 100000000 bms_prev_member iterations...
master: 1.04644 seconds
Patched: 0.58053 seconds
2800000000
```
Best regards,
--
Chao Li (Evan)
HighGo Software Co., Ltd.
https://www.highgo.com/
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Small and unlikely overflow hazard in bms_next_member()
2026-04-02 04:09 Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-02 04:22 ` Re: Small and unlikely overflow hazard in bms_next_member() Tom Lane <[email protected]>
2026-04-02 22:12 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-03 02:08 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-12 13:17 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-13 00:23 ` Re: Small and unlikely overflow hazard in bms_next_member() Chao Li <[email protected]>
@ 2026-04-13 02:43 ` David Rowley <[email protected]>
0 siblings, 0 replies; 17+ messages in thread
From: David Rowley @ 2026-04-13 02:43 UTC (permalink / raw)
To: Chao Li <[email protected]>; +Cc: Tom Lane <[email protected]>; PostgreSQL Developers <[email protected]>
On Mon, 13 Apr 2026 at 12:24, Chao Li <[email protected]> wrote:
> I just tried test_bms_next3 on my MacBook, looks like patched bms_prev_member is much faster there. I ran about 10 times, the results were consistent.
Thanks. I saw similar results.
David
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Small and unlikely overflow hazard in bms_next_member()
2026-04-02 04:09 Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
@ 2026-04-02 06:38 ` Chao Li <[email protected]>
2026-04-02 07:54 ` Re: Small and unlikely overflow hazard in bms_next_member() jie wang <[email protected]>
2026-04-02 22:20 ` Re: Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
1 sibling, 2 replies; 17+ messages in thread
From: Chao Li @ 2026-04-02 06:38 UTC (permalink / raw)
To: David Rowley <[email protected]>; +Cc: PostgreSQL Developers <[email protected]>
> On Apr 2, 2026, at 12:09, David Rowley <[email protected]> wrote:
>
> I've been working on bms_left_shift_members() to bitshift members
> either left or right in order to tidy up some existing code and
> improve a future Bitmapset use case I'm currently working on.
>
> When testing some ERROR code I added to ensure we don't get an
> excessively large left shift value and end up with members higher than
> INT32_MAX, I discovered that bms_next_member() can't handle that
> value, as "prevbit++" will wrap to INT32_MIN and then we'll try to
> access a negative array index, i.e. seg fault.
>
> I appreciate that such a large member is quite unlikely, but if this
> isn't fixed then I need to code my error checking code to disallow
> members >= INT32_MAX rather than > INT32_MAX. I did have a comment
> explaining why I was doing that, but fixing the bug saves the weird
> special case and the comment.
>
> Patched attached. I was thinking it might not be worthy of
> backpatching, but I'll entertain alternative views on that.
>
> David
> <bms_next_member_fix.patch>
Both the return value of bms_next_member() and the parameter “prevbit" are defined as int, which seems to imply that a bitmap can hold at most INT32_MAX elements. So I wonder if a cleaner fix would be to just add a range guard, like this:
```
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 786f343b3c9..7f79f81f278 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -1294,7 +1294,7 @@ bms_next_member(const Bitmapset *a, int prevbit)
Assert(bms_is_valid_set(a));
- if (a == NULL)
+ if (a == NULL || prevbit == INT32_MAX)
return -2;
nwords = a->nwords;
prevbit++;
```
Best regards,
--
Chao Li (Evan)
HighGo Software Co., Ltd.
https://www.highgo.com/
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Small and unlikely overflow hazard in bms_next_member()
2026-04-02 04:09 Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-02 06:38 ` Re: Small and unlikely overflow hazard in bms_next_member() Chao Li <[email protected]>
@ 2026-04-02 07:54 ` jie wang <[email protected]>
1 sibling, 0 replies; 17+ messages in thread
From: jie wang @ 2026-04-02 07:54 UTC (permalink / raw)
To: Chao Li <[email protected]>; +Cc: David Rowley <[email protected]>; PostgreSQL Developers <[email protected]>
Chao Li <[email protected]> 于2026年4月2日周四 14:39写道：
>
>
> > On Apr 2, 2026, at 12:09, David Rowley <[email protected]> wrote:
> >
> > I've been working on bms_left_shift_members() to bitshift members
> > either left or right in order to tidy up some existing code and
> > improve a future Bitmapset use case I'm currently working on.
> >
> > When testing some ERROR code I added to ensure we don't get an
> > excessively large left shift value and end up with members higher than
> > INT32_MAX, I discovered that bms_next_member() can't handle that
> > value, as "prevbit++" will wrap to INT32_MIN and then we'll try to
> > access a negative array index, i.e. seg fault.
> >
> > I appreciate that such a large member is quite unlikely, but if this
> > isn't fixed then I need to code my error checking code to disallow
> > members >= INT32_MAX rather than > INT32_MAX. I did have a comment
> > explaining why I was doing that, but fixing the bug saves the weird
> > special case and the comment.
> >
> > Patched attached. I was thinking it might not be worthy of
> > backpatching, but I'll entertain alternative views on that.
> >
> > David
> > <bms_next_member_fix.patch>
>
> Both the return value of bms_next_member() and the parameter “prevbit" are
> defined as int, which seems to imply that a bitmap can hold at most
> INT32_MAX elements. So I wonder if a cleaner fix would be to just add a
> range guard, like this:
>
> ```
> diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
> index 786f343b3c9..7f79f81f278 100644
> --- a/src/backend/nodes/bitmapset.c
> +++ b/src/backend/nodes/bitmapset.c
> @@ -1294,7 +1294,7 @@ bms_next_member(const Bitmapset *a, int prevbit)
>
> Assert(bms_is_valid_set(a));
>
> - if (a == NULL)
> + if (a == NULL || prevbit == INT32_MAX)
> return -2;
> nwords = a->nwords;
> prevbit++;
> ```
>
> Best regards,
> --
> Chao Li (Evan)
> HighGo Software Co., Ltd.
> https://www.highgo.com/
>
>
>
>
>
>
>
Hi,
The both solutions look good to me. I am slightly keen on Chao's version
that looks simpler to me.
Thanks!
wang jie
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Small and unlikely overflow hazard in bms_next_member()
2026-04-02 04:09 Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-02 06:38 ` Re: Small and unlikely overflow hazard in bms_next_member() Chao Li <[email protected]>
@ 2026-04-02 22:20 ` David Rowley <[email protected]>
1 sibling, 0 replies; 17+ messages in thread
From: David Rowley @ 2026-04-02 22:20 UTC (permalink / raw)
To: Chao Li <[email protected]>; +Cc: PostgreSQL Developers <[email protected]>
On Thu, 2 Apr 2026 at 19:39, Chao Li <[email protected]> wrote:
> Both the return value of bms_next_member() and the parameter “prevbit" are defined as int, which seems to imply that a bitmap can hold at most INT32_MAX elements. So I wonder if a cleaner fix would be to just add a range guard, like this:
>
> ```
> diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
> index 786f343b3c9..7f79f81f278 100644
> --- a/src/backend/nodes/bitmapset.c
> +++ b/src/backend/nodes/bitmapset.c
> @@ -1294,7 +1294,7 @@ bms_next_member(const Bitmapset *a, int prevbit)
>
> Assert(bms_is_valid_set(a));
>
> - if (a == NULL)
> + if (a == NULL || prevbit == INT32_MAX)
I don't think that's a nice way at all. Adding a special case plus
extra instructions, including a new jump instruction for the boolean
short-circuiting. More instruction decoding, more L1i space needed,
more branches to predict and more space in the branch predictor tables
to overwrite other useful branches. Adds run-time overhead.
I was aiming for low overhead and no special cases. 2a600a93c means we
don't care about the performance on 32-bit hardware anymore, so that
can't be used as a counterargument.
David
^ permalink raw reply [nested|flat] 17+ messages in thread
end of thread, other threads:[~2026-04-13 02:43 UTC | newest]
Thread overview: 17+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2026-04-02 04:09 Small and unlikely overflow hazard in bms_next_member() David Rowley <[email protected]>
2026-04-02 04:22 ` Tom Lane <[email protected]>
2026-04-02 22:12 ` David Rowley <[email protected]>
2026-04-03 02:08 ` David Rowley <[email protected]>
2026-04-03 03:24 ` Chao Li <[email protected]>
2026-04-03 11:42 ` David Rowley <[email protected]>
2026-04-03 13:28 ` Chao Li <[email protected]>
2026-04-04 03:30 ` David Rowley <[email protected]>
2026-04-06 02:00 ` Chao Li <[email protected]>
2026-04-12 12:33 ` David Rowley <[email protected]>
2026-04-12 13:17 ` David Rowley <[email protected]>
2026-04-12 23:41 ` David Rowley <[email protected]>
2026-04-13 00:23 ` Chao Li <[email protected]>
2026-04-13 02:43 ` David Rowley <[email protected]>
2026-04-02 06:38 ` Chao Li <[email protected]>
2026-04-02 07:54 ` jie wang <[email protected]>
2026-04-02 22:20 ` David Rowley <[email protected]>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox