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
bms_fixes.patch
Description: Binary data
