Hello.
On Mon, Jun 03, 2024 at 08:31:01PM GMT, Xavier <ghostxavier@xxxxxxxx> 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
Attachment:
signature.asc
Description: PGP signature
