Re:[PATCH 4/5] lib/union_find: Optimize uf_find() with enhanced path compression

[Xavier <xavier_qy@163.com>]

At 2024-10-06 05:49:37, "Kuan-Wei Chiu" <visitorckw@gmail.com> wrote:
>Optimize the uf_find() function to enhance its efficiency by
>implementing a more effective path compression strategy. The original
>implementation only updated the parent pointer of the current node to
>its grandparent, resulting in a relatively shallow tree.
>
>In the updated version, once the root of the node is identified, all
>nodes along the search path are updated to directly point to the root.
>This change minimizes the height of the tree and improves the
>efficiency for subsequent find operations, providing better performance
>for the Union-Find data structure.
>
>Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
>---
>Note: Tested with the KUnit tests introduced in the previous patch.
>
> lib/union_find.c | 9 +++++++--
> 1 file changed, 7 insertions(+), 2 deletions(-)
>
>diff --git a/lib/union_find.c b/lib/union_find.c
>index a20678da0220..7c553fa622c8 100644
>--- a/lib/union_find.c
>+++ b/lib/union_find.c
>@@ -13,14 +13,19 @@
>  */
> struct uf_node *uf_find(struct uf_node *node)
> {
>+	struct uf_node *root = node;
> 	struct uf_node *parent;
> 
>+	while (root->parent != root)
>+		root = root->parent;
>+
> 	while (node->parent != node) {

Using “root” for this judgment might be better, as it could
reduce unnecessary entering.
        while (node->parent != root) {

> 		parent = node->parent;
>-		node->parent = parent->parent;
>+		node->parent = root;
> 		node = parent;
> 	}
>-	return node;
>+
>+	return root;
> }
> EXPORT_SYMBOL(uf_find);
> 
>-- 
>2.34.1