Feedback-ID: i0fe9450f:Fastmail
Date: Thu, 9 Oct 2025 11:12:50 +0900
From: Michael Paquier <michael@paquier.xyz>
To: David Rowley <dgrowleyml@gmail.com>
Cc: Greg Burd <greg@burd.me>, Ranier Vilela <ranier.vf@gmail.com>,
	Daniel Gustafsson <daniel@yesql.se>,
	PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: [PATCH] Add tests for Bitmapset
Message-ID: <aOcaIr8QKMvbIlnA@paquier.xyz>
References: 
 <CAEudQAq_zOSA2NUQSWePTGV_=90Uw0WcXxGOWnN-vwF046OOqA@mail.gmail.com>
 <2D90FFB0-C80A-4189-A5BF-C37F05E271D7@greg.burd.me>
 <CAApHDvqXdBWMwGuzJBSbq4eiNLDaR738-upd8NJpmhUq3a+XLQ@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha512;
	protocol="application/pgp-signature"; boundary="NCxJX7g75OVnq8Gg"
Content-Disposition: inline
In-Reply-To: 
 <CAApHDvqXdBWMwGuzJBSbq4eiNLDaR738-upd8NJpmhUq3a+XLQ@mail.gmail.com>
Archived-At: 
 <https://www.postgresql.org/message-id/aOcaIr8QKMvbIlnA%40paquier.xyz>
Precedence: bulk


--NCxJX7g75OVnq8Gg
Content-Type: multipart/mixed; boundary="edRvHQr1T2/lWe2i"
Content-Disposition: inline


--edRvHQr1T2/lWe2i
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Thu, Oct 09, 2025 at 02:57:41PM +1300, David Rowley wrote:
> I don't think there's any need to maintain the order of that members
> array, so couldn't you just do this?:
>=20
> bms =3D bms_del_member(bms, member);
> members[pos] =3D members[--num_members];

Yep, I was just playing with all that and moving the last element to
the member we know is gone would be cheaper.  I have also added more
comments to document everything in a more precise way, while going
through.

I also do not see a point in preventing inserts in the second set at
the beginning of the function.  This forces bms_union() to do more
operations with overlapping sets.

What do you think about the attached?
--
Michael

--edRvHQr1T2/lWe2i
Content-Type: text/x-diff; charset=us-ascii
Content-Disposition: attachment;
	filename="v2-0001-test_bitmapset-Improve-random-function.patch"
Content-Transfer-Encoding: quoted-printable

=46rom 03c6ee49b133e9f77dbd07e1df0a4e0aece511d7 Mon Sep 17 00:00:00 2001
=46rom: Michael Paquier <michael@paquier.xyz>
Date: Thu, 9 Oct 2025 11:11:51 +0900
Subject: [PATCH v2] test_bitmapset: Improve random function

---
 .../modules/test_bitmapset/test_bitmapset.c   | 48 ++++++++++++++-----
 1 file changed, 36 insertions(+), 12 deletions(-)

diff --git a/src/test/modules/test_bitmapset/test_bitmapset.c b/src/test/mo=
dules/test_bitmapset/test_bitmapset.c
index 8bc9b1f48e9a..ce2034b43290 100644
--- a/src/test/modules/test_bitmapset/test_bitmapset.c
+++ b/src/test/modules/test_bitmapset/test_bitmapset.c
@@ -618,23 +618,23 @@ test_random_operations(PG_FUNCTION_ARGS)
 	pg_prng_seed(&state, seed);
 	members =3D palloc(sizeof(int) * num_ops);
=20
-	/* Phase 1: Random insertions */
+	/* Phase 1: Random insertions in first set */
 	for (int i =3D 0; i < num_ops / 2; i++)
 	{
 		member =3D pg_prng_uint32(&state) % max_range + min_value;
=20
 		if (!bms_is_member(member, bms1))
-		{
 			members[num_members++] =3D member;
-			bms1 =3D bms_add_member(bms1, member);
-		}
+		bms1 =3D bms_add_member(bms1, member);
 	}
=20
-	/* Phase 2: Random set operations */
+	/* Phase 2: Random insertions in second set */
 	for (int i =3D 0; i < num_ops / 4; i++)
 	{
 		member =3D pg_prng_uint32(&state) % max_range + min_value;
=20
+		if (!bms_is_member(member, bms2))
+			members[num_members++] =3D member;
 		bms2 =3D bms_add_member(bms2, member);
 	}
=20
@@ -642,7 +642,7 @@ test_random_operations(PG_FUNCTION_ARGS)
 	result =3D bms_union(bms1, bms2);
 	EXPECT_NOT_NULL(result);
=20
-	/* Verify union contains all members from first set */
+	/* Verify union contains all members from first and second sets */
 	for (int i =3D 0; i < num_members; i++)
 	{
 		if (!bms_is_member(members[i], result))
@@ -650,7 +650,10 @@ test_random_operations(PG_FUNCTION_ARGS)
 	}
 	bms_free(result);
=20
-	/* Test intersection */
+	/*
+	 * Test intersection, checking that all the members in the result are from
+	 * both the first and second sets.
+	 */
 	result =3D bms_intersect(bms1, bms2);
 	if (result !=3D NULL)
 	{
@@ -683,24 +686,44 @@ test_random_operations(PG_FUNCTION_ARGS)
 	bms_free(bms1);
 	bms_free(bms2);
=20
-	for (int i =3D 0; i < num_ops; i++)
+	/*
+	 * Phase 4: mix of operations on a single set, cross-checking a bitmap
+	 * with a secondary state, "members".  There can be up to "num_ops"
+	 * members added, very unlikely still possible if all the operations hit
+	 * the "0" case.
+	 */
+	num_members =3D 0;
+	members =3D palloc(sizeof(int) * num_ops);
+
+	for (int op =3D 0; op < num_ops; op++)
 	{
-		member =3D pg_prng_uint32(&state) % max_range + min_value;
 		switch (pg_prng_uint32(&state) % 3)
 		{
 			case 0:				/* add */
+				member =3D pg_prng_uint32(&state) % max_range + min_value;
+				if (!bms_is_member(member, bms))
+					members[num_members++] =3D member;
 				bms =3D bms_add_member(bms, member);
 				break;
 			case 1:				/* delete */
-				if (bms !=3D NULL)
+				if (num_members > 0)
 				{
+					int			pos =3D pg_prng_uint32(&state) % num_members;
+
+					member =3D members[pos];
+					if (!bms_is_member(member, bms))
+						elog(ERROR, "expected %d to be a valid member", member);
+
 					bms =3D bms_del_member(bms, member);
+					members[pos] =3D members[--num_members];
 				}
 				break;
 			case 2:				/* test membership */
-				if (bms !=3D NULL)
+				/* Verify that bitmap contains all members */
+				for (int i =3D 0; i < num_members; i++)
 				{
-					bms_is_member(member, bms);
+					if (!bms_is_member(members[i], bms))
+						elog(ERROR, "missing member %d", members[i]);
 				}
 				break;
 		}
@@ -708,6 +731,7 @@ test_random_operations(PG_FUNCTION_ARGS)
 	}
=20
 	bms_free(bms);
+	pfree(members);
=20
 	PG_RETURN_INT32(total_ops);
 }
--=20
2.51.0


--edRvHQr1T2/lWe2i--

--NCxJX7g75OVnq8Gg
Content-Type: application/pgp-signature; name="signature.asc"

-----BEGIN PGP SIGNATURE-----

iQIzBAABCgAdFiEEG72nH6vTowiyblFKnvQgOdbyQH0FAmjnGiIACgkQnvQgOdby
QH3fARAAimK3+s9E6+BKR9GMgY3oEk/JkmV+52PvFsalK4tbX7pLirhQS0095RPq
ipGpqS8Nf466PcbhDiJwRmOw+MM4MCXFiXn1m0Or1RL7PNVHcFcu249D1kHS0sO0
u7Eo8r0emIFMRvKb1vwAp3gmOlqlsgnpNsGz925U87kyAfdwak2/C3sXHc/1NQtn
vA24BT7ItLoGKYaJDXXGTaeQXKFNJbEuEtn3Bvsw1EqjBY0fIc+zdwR5OK8gdXmC
EdrEgeIZz/DDm2JlDiCwPAORmKXDXIga0OJZcb13tADP9g3+LKu7ubXO82SA2UID
70wVsRtNWTGO8JONRJ5Rnzx53fpIiUZnIvLu+fPFQTX56OweeJCMEHwp8Ei//ATR
EYVPWrffx0iDWhMoLurgu08U5/HcRVTbELTr8jLszlS2I9TClbyFrMerMcbq2qQ0
gHCPPZhmj+yacSHBbhIxTPIyuPSFkUSvOix2t+K8tFVjYgcspwQJnRS9Wjb+AcPe
bh2xzQd3RMj1Fsdf1Br8A4HwQLYrh0zEmynWUPIHXow08Ew5Y3QYj8p7UVg2W5pF
IolxBpSBL2Q03zBnmZSiGWoTEh/s6mBQcbX6/+ENIZKljaQFmaK8DLwMUGA/dcvh
1/UE4NnFFF1Jms5g2HvCTrwFk8mJahh7eKZzmBzbNZVG7DArqAY=
=xjvv
-----END PGP SIGNATURE-----

--NCxJX7g75OVnq8Gg--