Hello.

On Mon, Jun 03, 2024 at 08:31:01PM GMT, Xavier [off-list ref] wrote:

The process of constructing scheduling domains involves multiple loops
and repeated evaluations, leading to numerous redundant and ineffective
assessments that impact code efficiency.

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 = 0; i < csn; i++) {
+		nodes[i].parent = i;
+		nodes[i].rank = 0;
+	}

With the suggestion above, nodes could start with parent = 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€,
Michal