[Commented On] D9491: copies-rust: add smarter approach for merging small mapping with large mapping

[baymax (Baymax, Your Personal Patch-care Companion)]

baymax added a comment.
baymax updated this revision to Diff 24246.


  ✅ refresh by Heptapod after a successful CI run (🐙 💚)

REPOSITORY
  rHG Mercurial

CHANGES SINCE LAST UPDATE
  https://phab.mercurial-scm.org/D9491?vs=24214&id=24246

BRANCH
  default

CHANGES SINCE LAST ACTION
  https://phab.mercurial-scm.org/D9491/new/

REVISION DETAIL
  https://phab.mercurial-scm.org/D9491

AFFECTED FILES
  rust/hg-core/src/copy_tracing.rs

CHANGE DETAILS

diff --git a/rust/hg-core/src/copy_tracing.rs b/rust/hg-core/src/copy_tracing.rs
--- a/rust/hg-core/src/copy_tracing.rs
+++ b/rust/hg-core/src/copy_tracing.rs
@@ -497,8 +497,8 @@
 /// In case of conflict, value from "major" will be picked, unless in some
 /// cases. See inline documentation for details.
 fn merge_copies_dict<A: Fn(Revision, Revision) -> bool>(
-    minor: TimeStampedPathCopies,
-    major: TimeStampedPathCopies,
+    mut minor: TimeStampedPathCopies,
+    mut major: TimeStampedPathCopies,
     changes: &ChangedFiles,
     oracle: &mut AncestorOracle<A>,
 ) -> TimeStampedPathCopies {
@@ -515,6 +515,51 @@
         major
     } else if major.is_empty() {
         minor
+    } else if minor.len() * 2 < major.len() {
+        // Lets says we are merging two TimeStampedPathCopies instance A and B.
+        //
+        // If A contains N items, the merge result will never contains more
+        // than N values differents than the one in A
+        //
+        // If B contains M items, with M > N, the merge result will always
+        // result in a minimum of M - N value differents than the on in
+        // A
+        //
+        // As a result, if N < (M-N), we know that simply iterating over A will
+        // yield less difference than iterating over the difference
+        // between A and B.
+        //
+        // This help performance a lot in case were a tiny
+        // TimeStampedPathCopies is merged with a much larger one.
+        for (dest, src_minor) in minor {
+            let src_major = major.get(&dest);
+            match src_major {
+                None => major.insert(dest, src_minor),
+                Some(src_major) => {
+                    match cmp_value(&dest, &src_minor, src_major) {
+                        MergePick::Any | MergePick::Major => None,
+                        MergePick::Minor => major.insert(dest, src_minor),
+                    }
+                }
+            };
+        }
+        major
+    } else if major.len() * 2 < minor.len() {
+        // This use the same rational than the previous block.
+        // (Check previous block documentation for details.)
+        for (dest, src_major) in major {
+            let src_minor = minor.get(&dest);
+            match src_minor {
+                None => minor.insert(dest, src_major),
+                Some(src_minor) => {
+                    match cmp_value(&dest, src_minor, &src_major) {
+                        MergePick::Any | MergePick::Minor => None,
+                        MergePick::Major => minor.insert(dest, src_major),
+                    }
+                }
+            };
+        }
+        minor
     } else {
         let mut override_minor = Vec::new();
         let mut override_major = Vec::new();



To: marmoute, #hg-reviewers, Alphare, pulkit
Cc: mercurial-patches
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mercurial-scm.org/pipermail/mercurial-patches/attachments/20201214/e4398d88/attachment-0002.html>