Content-Type: text/plain;
	charset=us-ascii
Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3864.400.21\))
Subject: Re: Small and unlikely overflow hazard in bms_next_member()
From: Chao Li <li.evan.chao@gmail.com>
In-Reply-To: 
 <CAApHDvr1B2gbf6JF69QmueM2QNRvbQeeKLxDnF=w9f9--022uA@mail.gmail.com>
Date: Mon, 13 Apr 2026 08:23:26 +0800
Cc: Tom Lane <tgl@sss.pgh.pa.us>,
 PostgreSQL Developers <pgsql-hackers@lists.postgresql.org>
Content-Transfer-Encoding: quoted-printable
Message-Id: <5E98992A-62D3-4961-B2F1-61246DB9D814@gmail.com>
References: 
 <CAApHDvq0T=iJ0Sf5TNE9yyWwfOeVjmrBt0wSywDnGD9Y4YJQBA@mail.gmail.com>
 <3190647.1775103768@sss.pgh.pa.us>
 <CAApHDvrvvq_m+nRwjsOpCsFa4EtVtmvJX7zAD=Siria-x6DpbQ@mail.gmail.com>
 <CAApHDvqTUm3Cbgz3ZLV+ad8s_HJHZYrVbrBvGyPQdxCRR-6dvA@mail.gmail.com>
 <CAApHDvr1B2gbf6JF69QmueM2QNRvbQeeKLxDnF=w9f9--022uA@mail.gmail.com>
To: David Rowley <dgrowleyml@gmail.com>
Archived-At: 
 <https://www.postgresql.org/message-id/5E98992A-62D3-4961-B2F1-61246DB9D814%40gmail.com>
Precedence: bulk


> On Apr 12, 2026, at 21:17, David Rowley <dgrowleyml@gmail.com> wrote:
>=20
> On Fri, 3 Apr 2026 at 15:08, David Rowley <dgrowleyml@gmail.com> =
wrote:
>> IMO, if we can make bitmapset.c work with INT_MAX members and get a
>> performance increase, then we should do it.
>=20
> 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:
>=20
> "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."
>=20
> 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.
>=20
> That leads me to the attached v2 patch. Compiler Explorer link showing
> the assembly at [2].
>=20
> 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:
>=20
> 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
>=20
> Benchmarking 100000000 bms_prev_member iterations...
> master: 2.94522 seconds
> Patched: 1.86130 seconds
>=20
> 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
>=20
> Benchmarking 100000000 bms_prev_member iterations...
> master: 2.76550 seconds
> Patched: 2.12369 seconds
>=20
> David
>=20
> [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.pa=
tch>

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/