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

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] [thread-next>] [day] [month] [year] [list]

Message-Id: <20241005214938.2147393-5-visitorckw@gmail.com>
Date: Sun,  6 Oct 2024 05:49:37 +0800
From: Kuan-Wei Chiu <visitorckw@...il.com>
To: xavier_qy@....com,
	longman@...hat.com,
	lizefan.x@...edance.com,
	tj@...nel.org,
	hannes@...xchg.org,
	mkoutny@...e.com,
	akpm@...ux-foundation.org
Cc: jserv@...s.ncku.edu.tw,
	linux-kernel@...r.kernel.org,
	cgroups@...r.kernel.org,
	Kuan-Wei Chiu <visitorckw@...il.com>
Subject: [PATCH 4/5] lib/union_find: Optimize uf_find() with enhanced path compression

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) {
 		parent = node->parent;
-		node->parent = parent->parent;
+		node->parent = root;
 		node = parent;
 	}
-	return node;
+
+	return root;
 }
 EXPORT_SYMBOL(uf_find);

-- 
2.34.1