Re: [PATCH-cpuset v10 1/2] Union-Find: add a new module in kernel library

[Michal Koutný]

On Wed, Jul 03, 2024 at 07:20:09PM GMT, Xavier <xavier_qy@xxxxxxx> wrote:
> >Xavier, not sure if you responded to my suggestion of considered zeroed
> >object a valid initialized one. That could save some init work (and
> >move it to alternative uf_find, see below).
> >
> >With uf_find body checking for NULL:
> >
> >	while (node->parent != node) {
> >		parent = node->parent;
> >		node->parent = parent ? parent->parent : node;
> >		node = node->parent;
> >	}
> 
> Yes, I noticed your suggestion. In patch v4, I implemented it by
> initializing to 0 and adding a check for whether the parent is 0 in
> uf_find.

Ah, I didn't read all versions. (You may consider adding a short
changelog when sending a new version of patches where main evolution
points are summed up. ;-))

> However, later, when I was reviewing the algorithm's documentation, I
> noticed it requires initialization to itself.

Well, that's not a hard requirement.

> Moreover, uf_find is a high-frequency operation, if we add a parent
> check within it, the efficiency impact each time would be more
> significant than initializing once. Therefore, I adhered to the
> initialization to itself approach.

I see, thanks for the clarifications,
Michal

Attachment: signature.asc
Description: PGP signature