commit e1b40baded4458cfb46a46426f99a2fae3267300
author bluss <bluss@users.noreply.github.com> Sat Sep 07 23:16:06 2019 +0200
committer bluss <bluss@users.noreply.github.com> Sat Sep 07 23:19:41 2019 +0200
tree a7dc3d499b525f799ee158d3dcecf6ac7c094219
parent d10a476fd3f07daa659c50877e72c2a1a8ff69e7

FEAT: Improve performance of UnionFind's find_mut

Use an iterative implementation instead of recursive, the performance
difference is rather large, in fact.

Tested using the benchmarks from PR #274

src/unionfind.rs

diff --git a/src/unionfind.rs b/src/unionfind.rs
index 6521468..e05b830 100644
--- a/src/unionfind.rs
+++ b/src/unionfind.rs
@@ -33,6 +33,13 @@
     xs.get_unchecked(index)
 }
 
+#[inline]
+unsafe fn get_unchecked_mut<K>(xs: &mut [K], index: usize) -> &mut K
+{
+    debug_assert!(index < xs.len());
+    xs.get_unchecked_mut(index)
+}
+
 impl<K> UnionFind<K>
     where K: IndexType
 {
@@ -79,17 +86,16 @@
         }
     }
 
-    unsafe fn find_mut_recursive(&mut self, x: K) -> K
+    unsafe fn find_mut_recursive(&mut self, mut x: K) -> K
     {
-        let xparent = *get_unchecked(&self.parent, x.index());
-        if xparent != x {
-            let xrep = self.find_mut_recursive(xparent);
-            let xparent = self.parent.get_unchecked_mut(x.index());
-            *xparent = xrep;
-            *xparent
-        } else {
-            xparent
+        let mut parent = *get_unchecked(&self.parent, x.index());
+        while parent != x {
+            let grandparent = *get_unchecked(&self.parent, parent.index());
+            *get_unchecked_mut(&mut self.parent, x.index()) = grandparent;
+            x = parent;
+            parent = grandparent;
         }
+        x
     }