Patchwork D9491: copies-rust: add smarter approach for merging small mapping with large mapping

login
register
mail settings
Submitter phabricator
Date Dec. 2, 2020, 4:02 p.m.
Message ID <differential-rev-PHID-DREV-qgywvsg2ey3c52giq7s4-req@mercurial-scm.org>
Download mbox | patch
Permalink /patch/47773/
State Superseded
Headers show

Comments

phabricator - Dec. 2, 2020, 4:02 p.m.
marmoute created this revision.
Herald added a reviewer: hg-reviewers.
Herald added a subscriber: mercurial-patches.

REVISION SUMMARY
  The current approach (finding the smaller updated set) works great when the
  mapping have similar size, but do a lot of unnecessary work when one side is
  tinier than the other one. So we do better in theses cases. See inline
  documentation for details.
  
  It give a sizeable boost to many of out slower cases:
  
  Repo            Case                                  Source-Rev   Dest-Rev      # of revisions  old time    new time      Difference    Factor    time per rev
  ---------------------------------------------------------------------------------------------------------------------------------------------------------------
  
  mozilla-try     x00000_revs_x_added_0_copies          6a320851d377 1ebb79acd503 : 363753 revs,  18.123103 s,   5.693818 s, -12.429285 s, × 0.3142,    15 µs/rev
  mozilla-try     x00000_revs_x_added_x_copies          5173c4b6f97c 95d83ee7242d : 362229 revs,  17.907312 s,   5.677655 s, -12.229657 s, × 0.3171,    15 µs/rev
  mozilla-try     x00000_revs_x000_added_x_copies       9126823d0e9c ca82787bb23c : 359344 revs,  17.684797 s,   5.563370 s, -12.121427 s, × 0.3146,    15 µs/rev
  mozilla-try     x00000_revs_x0000_added_x0000_copies  8d3fafa80d4b eb884023b810 : 192665 revs,   2.881471 s,   2.864099 s,  -0.017372 s, × 0.9940,    14 µs/rev
  mozilla-try     x00000_revs_x00000_added_x000_copies  9b2a99adc05e 8e29777b48e6 : 382065 revs,  63.148971 s,  59.498652 s,  -3.650319 s, × 0.9422,   155 µs/rev
  mozilla-try     x00000_revs_x00000_added_x000_copies  9b2a99adc05e 8e29777b48e6 : 382065 revs,  63.148971 s,  59.498652 s,  -3.650319 s, × 0.9422,   155 µs/rev
  
  ideally, the im-rs object would have a `merge` method, but it does not (yet)
  
  Full timing comparison below (they are one pathological case than become even
  worse, for unclear reason).
  
  Repo            Case                                  Source-Rev   Dest-Rev      # of revisions  old time    new time      Difference    Factor    time per rev
  ---------------------------------------------------------------------------------------------------------------------------------------------------------------
  
  mercurial       x_revs_x_added_0_copies               ad6b123de1c7 <https://phab.mercurial-scm.org/rHGad6b123de1c7868a4be537a0e3fa5eb6a962dd3b> 39cfcef4f463 <https://phab.mercurial-scm.org/rHG39cfcef4f46358a25ebf32670191687826ca2bdf> :      1 revs,   0.000043 s,   0.000042 s,  -0.000001 s, × 0.9767,    42 µs/rev
  mercurial       x_revs_x_added_x_copies               2b1c78674230 <https://phab.mercurial-scm.org/rHG2b1c786742301bb757226a898fafe595a90462fb> 0c1d10351869 <https://phab.mercurial-scm.org/rHG0c1d103518698454c9a8825b66276becf2820f86> :      6 revs,   0.000105 s,   0.000104 s,  -0.000001 s, × 0.9905,    17 µs/rev
  mercurial       x000_revs_x000_added_x_copies         81f8ff2a9bf2 <https://phab.mercurial-scm.org/rHG81f8ff2a9bf20606fc89bc787983f592183e25b5> dd3267698d84 <https://phab.mercurial-scm.org/rHGdd3267698d84458686b3c5682ce027438900ffbd> :   1032 revs,   0.004895 s,   0.004913 s,  +0.000018 s, × 1.0037,     4 µs/rev
  pypy            x_revs_x_added_0_copies               aed021ee8ae8 099ed31b181b :      9 revs,   0.000194 s,   0.000191 s,  -0.000003 s, × 0.9845,    21 µs/rev
  pypy            x_revs_x000_added_0_copies            4aa4e1f8e19a 359343b9ac0e :      1 revs,   0.000050 s,   0.000050 s,  +0.000000 s, × 1.0000,    50 µs/rev
  pypy            x_revs_x_added_x_copies               ac52eb7bbbb0 72e022663155 :      7 revs,   0.000115 s,   0.000112 s,  -0.000003 s, × 0.9739,    16 µs/rev
  pypy            x_revs_x00_added_x_copies             c3b14617fbd7 ace7255d9a26 :      1 revs,   0.000289 s,   0.000288 s,  -0.000001 s, × 0.9965,   288 µs/rev
  pypy            x_revs_x000_added_x000_copies         df6f7a526b60 a83dc6a2d56f :      6 revs,   0.010513 s,   0.010411 s,  -0.000102 s, × 0.9903,  1735 µs/rev
  pypy            x000_revs_xx00_added_0_copies         89a76aede314 2f22446ff07e :   4785 revs,   0.051474 s,   0.052852 s,  +0.001378 s, × 1.0268,    11 µs/rev
  pypy            x000_revs_x000_added_x_copies         8a3b5bfd266e 2c68e87c3efe :   6780 revs,   0.088086 s,   0.092828 s,  +0.004742 s, × 1.0538,    13 µs/rev
  pypy            x000_revs_x000_added_x000_copies      89a76aede314 7b3dda341c84 :   5441 revs,   0.062176 s,   0.063269 s,  +0.001093 s, × 1.0176,    11 µs/rev
  pypy            x0000_revs_x_added_0_copies           d1defd0dc478 c9cb1334cc78 :  43645 revs,   0.720950 s,   0.711975 s,  -0.008975 s, × 0.9876,    16 µs/rev
  pypy            x0000_revs_xx000_added_0_copies       bf2c629d0071 4ffed77c095c :      2 revs,   0.012897 s,   0.012771 s,  -0.000126 s, × 0.9902,  6385 µs/rev
  pypy            x0000_revs_xx000_added_x000_copies    08ea3258278e d9fa043f30c0 :  11316 revs,   0.121524 s,   0.124505 s,  +0.002981 s, × 1.0245,    11 µs/rev
  netbeans        x_revs_x_added_0_copies               fb0955ffcbcd a01e9239f9e7 :      2 revs,   0.000082 s,   0.000082 s,  +0.000000 s, × 1.0000,    41 µs/rev
  netbeans        x_revs_x000_added_0_copies            6f360122949f 20eb231cc7d0 :      2 revs,   0.000109 s,   0.000111 s,  +0.000002 s, × 1.0183,    55 µs/rev
  netbeans        x_revs_x_added_x_copies               1ada3faf6fb6 5a39d12eecf4 :      3 revs,   0.000175 s,   0.000171 s,  -0.000004 s, × 0.9771,    57 µs/rev
  netbeans        x_revs_x00_added_x_copies             35be93ba1e2c 9eec5e90c05f :      9 revs,   0.000719 s,   0.000708 s,  -0.000011 s, × 0.9847,    78 µs/rev
  netbeans        x000_revs_xx00_added_0_copies         eac3045b4fdd 51d4ae7f1290 :   1421 revs,   0.010426 s,   0.010608 s,  +0.000182 s, × 1.0175,     7 µs/rev
  netbeans        x000_revs_x000_added_x_copies         e2063d266acd 6081d72689dc :   1533 revs,   0.015712 s,   0.015635 s,  -0.000077 s, × 0.9951,    10 µs/rev
  netbeans        x000_revs_x000_added_x000_copies      ff453e9fee32 411350406ec2 :   5750 revs,   0.077353 s,   0.072072 s,  -0.005281 s, × 0.9317,    12 µs/rev
  netbeans        x0000_revs_xx000_added_x000_copies    588c2d1ced70 1aad62e59ddd :  66949 revs,   0.673930 s,   0.682732 s,  +0.008802 s, × 1.0131,    10 µs/rev
  mozilla-central x_revs_x_added_0_copies               3697f962bb7b 7015fcdd43a2 :      2 revs,   0.000089 s,   0.000090 s,  +0.000001 s, × 1.0112,    45 µs/rev
  mozilla-central x_revs_x000_added_0_copies            dd390860c6c9 40d0c5bed75d :      8 revs,   0.000212 s,   0.000210 s,  -0.000002 s, × 0.9906,    26 µs/rev
  mozilla-central x_revs_x_added_x_copies               8d198483ae3b 14207ffc2b2f :      9 revs,   0.000183 s,   0.000182 s,  -0.000001 s, × 0.9945,    20 µs/rev
  mozilla-central x_revs_x00_added_x_copies             98cbc58cc6bc 446a150332c3 :      7 revs,   0.000595 s,   0.000594 s,  -0.000001 s, × 0.9983,    84 µs/rev
  mozilla-central x_revs_x000_added_x000_copies         3c684b4b8f68 0a5e72d1b479 :      3 revs,   0.003117 s,   0.003102 s,  -0.000015 s, × 0.9952,  1034 µs/rev
  mozilla-central x_revs_x0000_added_x0000_copies       effb563bb7e5 c07a39dc4e80 :      6 revs,   0.060197 s,   0.060234 s,  +0.000037 s, × 1.0006, 10039 µs/rev
  mozilla-central x000_revs_xx00_added_0_copies         6100d773079a 04a55431795e :   1593 revs,   0.006379 s,   0.006300 s,  -0.000079 s, × 0.9876,     3 µs/rev
  mozilla-central x000_revs_x000_added_x_copies         9f17a6fc04f9 2d37b966abed :     41 revs,   0.005008 s,   0.004817 s,  -0.000191 s, × 0.9619,   117 µs/rev
  mozilla-central x000_revs_x000_added_x000_copies      7c97034feb78 4407bd0c6330 :   7839 revs,   0.065123 s,   0.065451 s,  +0.000328 s, × 1.0050,     8 µs/rev
  mozilla-central x0000_revs_xx000_added_0_copies       9eec5917337d 67118cc6dcad :    615 revs,   0.026404 s,   0.026282 s,  -0.000122 s, × 0.9954,    42 µs/rev
  mozilla-central x0000_revs_xx000_added_x000_copies    f78c615a656c 96a38b690156 :  30263 revs,   0.203456 s,   0.206873 s,  +0.003417 s, × 1.0168,     6 µs/rev
  mozilla-central x00000_revs_x0000_added_x0000_copies  6832ae71433c 4c222a1d9a00 : 153721 revs,   1.929809 s,   1.935918 s,  +0.006109 s, × 1.0032,    12 µs/rev
  mozilla-central x00000_revs_x00000_added_x000_copies  76caed42cf7c 1daa622bbe42 : 204976 revs,   2.825064 s,   2.827320 s,  +0.002256 s, × 1.0008,    13 µs/rev
  mozilla-try     x_revs_x_added_0_copies               aaf6dde0deb8 9790f499805a :      2 revs,   0.000857 s,   0.000842 s,  -0.000015 s, × 0.9825,   421 µs/rev
  mozilla-try     x_revs_x000_added_0_copies            d8d0222927b4 5bb8ce8c7450 :      2 revs,   0.000870 s,   0.000870 s,  +0.000000 s, × 1.0000,   435 µs/rev
  mozilla-try     x_revs_x_added_x_copies               092fcca11bdb 936255a0384a :      4 revs,   0.000161 s,   0.000165 s,  +0.000004 s, × 1.0248,    41 µs/rev
  mozilla-try     x_revs_x00_added_x_copies             b53d2fadbdb5 017afae788ec :      2 revs,   0.001147 s,   0.001145 s,  -0.000002 s, × 0.9983,   572 µs/rev
  mozilla-try     x_revs_x000_added_x000_copies         20408ad61ce5 6f0ee96e21ad :      1 revs,   0.026640 s,   0.026500 s,  -0.000140 s, × 0.9947, 26500 µs/rev
  mozilla-try     x_revs_x0000_added_x0000_copies       effb563bb7e5 c07a39dc4e80 :      6 revs,   0.059849 s,   0.059407 s,  -0.000442 s, × 0.9926,  9901 µs/rev
  mozilla-try     x000_revs_xx00_added_0_copies         6100d773079a 04a55431795e :   1593 revs,   0.006326 s,   0.006325 s,  -0.000001 s, × 0.9998,     3 µs/rev
  mozilla-try     x000_revs_x000_added_x_copies         9f17a6fc04f9 2d37b966abed :     41 revs,   0.005188 s,   0.005171 s,  -0.000017 s, × 0.9967,   126 µs/rev
  mozilla-try     x000_revs_x000_added_x000_copies      1346fd0130e4 4c65cbdabc1f :   6657 revs,   0.067633 s,   0.066837 s,  -0.000796 s, × 0.9882,    10 µs/rev
  mozilla-try     x0000_revs_x_added_0_copies           63519bfd42ee a36a2a865d92 :  40314 revs,   0.306969 s,   0.314252 s,  +0.007283 s, × 1.0237,     7 µs/rev
  mozilla-try     x0000_revs_x_added_x_copies           9fe69ff0762d bcabf2a78927 :  38690 revs,   0.293370 s,   0.304160 s,  +0.010790 s, × 1.0368,     7 µs/rev
  mozilla-try     x0000_revs_xx000_added_x_copies       156f6e2674f2 4d0f2c178e66 :   8598 revs,   0.087159 s,   0.089223 s,  +0.002064 s, × 1.0237,    10 µs/rev
  mozilla-try     x0000_revs_xx000_added_0_copies       9eec5917337d 67118cc6dcad :    615 revs,   0.027251 s,   0.026711 s,  -0.000540 s, × 0.9802,    43 µs/rev
  mozilla-try     x0000_revs_xx000_added_x000_copies    89294cd501d9 7ccb2fc7ccb5 :  97052 revs,   3.010011 s,   3.243010 s,  +0.232999 s, × 1.0774,    33 µs/rev
  mozilla-try     x0000_revs_x0000_added_x0000_copies   e928c65095ed e951f4ad123a :  52031 revs,   0.753434 s,   0.756500 s,  +0.003066 s, × 1.0041,    14 µs/rev
  mozilla-try     x00000_revs_x_added_0_copies          6a320851d377 1ebb79acd503 : 363753 revs,  18.123103 s,   5.693818 s, -12.429285 s, × 0.3142,    15 µs/rev
  mozilla-try     x00000_revs_x00000_added_0_copies     dc8a3ca7010e d16fde900c9c :  34414 revs,   0.583206 s,   0.590904 s,  +0.007698 s, × 1.0132,    17 µs/rev
  mozilla-try     x00000_revs_x_added_x_copies          5173c4b6f97c 95d83ee7242d : 362229 revs,  17.907312 s,   5.677655 s, -12.229657 s, × 0.3171,    15 µs/rev
  mozilla-try     x00000_revs_x000_added_x_copies       9126823d0e9c ca82787bb23c : 359344 revs,  17.684797 s,   5.563370 s, -12.121427 s, × 0.3146,    15 µs/rev
  mozilla-try     x00000_revs_x0000_added_x0000_copies  8d3fafa80d4b eb884023b810 : 192665 revs,   2.881471 s,   2.864099 s,  -0.017372 s, × 0.9940,    14 µs/rev
  mozilla-try     x00000_revs_x00000_added_x0000_copies 1b661134e2ca 1ae03d022d6d : 228985 revs, 101.062002 s, 113.297287 s, +12.235285 s, × 1.1211,   494 µs/rev
  mozilla-try     x00000_revs_x00000_added_x000_copies  9b2a99adc05e 8e29777b48e6 : 382065 revs,  63.148971 s,  59.498652 s,  -3.650319 s, × 0.9422,   155 µs/rev

REPOSITORY
  rHG Mercurial

BRANCH
  default

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

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

CHANGE DETAILS




To: marmoute, #hg-reviewers
Cc: mercurial-patches, mercurial-devel

Patch

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
@@ -491,8 +491,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 {
@@ -509,6 +509,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();