Received-SPF: pass (google.com: domain of linux-kernel+bounces-208641-linux.lists.archive=gmail.com@vger.kernel.org designates 139.178.88.99 as permitted sender) client-ip=139.178.88.99;
Date: Mon, 10 Jun 2024 19:18:50 +0200
From: Michal =?utf-8?Q?Koutn=C3=BD?= <mkoutny@suse.com>
To: Xavier <ghostxavier@sina.com>
Cc: longman@redhat.com, lizefan.x@bytedance.com, tj@kernel.org, 
	hannes@cmpxchg.org, cgroups@vger.kernel.org, linux-kernel@vger.kernel.org
Subject: Re: [PATCH v3] cpuset: use Union-Find to optimize the merging of
 cpumasks
Message-ID: <wu4m2m5igc752s5vrmtsnd7ekaq6opeqdtrzegs7oxlwgypdcx@qhcnow5txxiv>
References: <20240531024837.255293-1-ghostxavier@sina.com>
 <20240603123101.590760-1-ghostxavier@sina.com>
Precedence: bulk
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha512;
	protocol="application/pgp-signature"; boundary="fekhs4szurscavjp"
Content-Disposition: inline
In-Reply-To: <20240603123101.590760-1-ghostxavier@sina.com>


--fekhs4szurscavjp
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

Hello.

On Mon, Jun 03, 2024 at 08:31:01PM GMT, Xavier <ghostxavier@sina.com> wrote:
> The process of constructing scheduling domains involves multiple loops
> and repeated evaluations, leading to numerous redundant and ineffective
> assessments that impact code efficiency.
>=20
> Here, we use Union-Find to optimize the merging of cpumasks. By employing
> path compression and union by rank, we effectively reduce the number of
> lookups and merge comparisons.

Nice that you found such an application. (As Waiman wrote, the
efficiency is not so important here and it may not be dencreased but I
still think it makes the code more understandable by using standard data
structures.)

Have you looked whether there are other instances of U-F in the kernel?
(My quick search didn't show any.) Still, I think it'd be a good idea to
decouple this into two commits -- 1) implementation of the new U-F (into
lib/), 2) application within cpuset.

> +/*define a union find node struct*/
> +struct uf_node {
> +	int parent;

I think this would be better as `struct uf_node *`.

> +	int rank;
> +};

`unsigned int` if rank cannot be negative?

> +	/* Each node is initially its own parent */
> +	for (i =3D 0; i < csn; i++) {
> +		nodes[i].parent =3D i;
> +		nodes[i].rank =3D 0;
> +	}

With the suggestion above, nodes could start with parent =3D NULL and
self-parent be corrected during the first find_root -- thus whole array
could be simply init'd to zeroes with kzalloc.


My 0.02=E2=82=AC,
Michal

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

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

iHUEABYKAB0WIQQpEWyjXuwGT2dDBqAGvrMr/1gcjgUCZmc1eAAKCRAGvrMr/1gc
jvyLAQDIN3U4NIzzpH9PYRDkt6vi5r2Od5Fva82LPD+KYsJk0AD+MVtyOpfg+GiR
jomUt+u2dcuyjjPN2cfbN3PhSJVFnwk=
=y5ot
-----END PGP SIGNATURE-----

--fekhs4szurscavjp--