public inbox for [email protected]
help / color / mirror / Atom feedFrom: Chao Li <[email protected]>
To: David Rowley <[email protected]>
Cc: Tom Lane <[email protected]>
Cc: PostgreSQL Developers <[email protected]>
Subject: Re: Small and unlikely overflow hazard in bms_next_member()
Date: Mon, 6 Apr 2026 10:00:38 +0800
Message-ID: <[email protected]> (raw)
In-Reply-To: <CAApHDvo+WtKHWbgmPA+H2K24P6h6aUJ_9kAdS__G1L9LDFGwgQ@mail.gmail.com>
References: <CAApHDvq0T=iJ0Sf5TNE9yyWwfOeVjmrBt0wSywDnGD9Y4YJQBA@mail.gmail.com>
<[email protected]>
<CAApHDvrvvq_m+nRwjsOpCsFa4EtVtmvJX7zAD=Siria-x6DpbQ@mail.gmail.com>
<CAApHDvqTUm3Cbgz3ZLV+ad8s_HJHZYrVbrBvGyPQdxCRR-6dvA@mail.gmail.com>
<[email protected]>
<CAApHDvocDY0qvhxRNBaNRjEr46j8TsGFig+=6bHN-NYS_dhSCw@mail.gmail.com>
<[email protected]>
<CAApHDvo+WtKHWbgmPA+H2K24P6h6aUJ_9kAdS__G1L9LDFGwgQ@mail.gmail.com>
> 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/
view thread (17+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected], [email protected], [email protected], [email protected]
Subject: Re: Small and unlikely overflow hazard in bms_next_member()
In-Reply-To: <[email protected]>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox