linux-kernel - Re:[PATCH 4/5] lib/union_find: Optimize uf

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <18b085ce.3da3.1926721f823.Coremail.xavier_qy@163.com>
Date: Mon, 7 Oct 2024 21:18:52 +0800 (CST)
From: Xavier  <xavier_qy@....com>
To: "Kuan-Wei Chiu" <visitorckw@...il.com>
Cc: longman@...hat.com, lizefan.x@...edance.com, tj@...nel.org, 
	hannes@...xchg.org, mkoutny@...e.com, akpm@...ux-foundation.org, 
	jserv@...s.ncku.edu.tw, linux-kernel@...r.kernel.org, 
	cgroups@...r.kernel.org
Subject: Re:[PATCH 4/5] lib/union_find: Optimize uf_find() with enhanced
 path compression



At 2024-10-06 05:49:37, "Kuan-Wei Chiu" <visitorckw@...il.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@...il.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