Skip to content
Snippets Groups Projects
  1. Apr 26, 2017
  2. Feb 13, 2017
  3. Dec 15, 2016
  4. Nov 15, 2016
    • Mads Kiilerich's avatar
      bdiff: give slight preference to removing trailing lines · 96f2f50d923f
      Mads Kiilerich authored
      [This change could be folded into the previous changeset to minimize the repo
      churn ...]
      
      Similar to the previous change, introduce an exception to the general
      preference for matches in the middle of bdiff ranges: If the best match on the
      B side starts at the beginning of the bdiff range, don't aim for the
      middle-most A side match but for the earliest.
      
      New (later) matches on the A side will only be considered better if the
      corresponding match on the B side *not* is at the beginning of the range.
      Thus, if the best (middle-most) match on the B side turns out to be at the
      beginning of the range, the earliest match on the A side will be used.
      
      The bundle size for 4.0 (hg bundle --base null -r 4.0 x.hg) happens to go from
      22807275 to 22808120 bytes - a 0.004% increase.
      96f2f50d923f
    • Mads Kiilerich's avatar
      bdiff: give slight preference to appending lines · 3633403888ae
      Mads Kiilerich authored
      [This change could be folded into the previous changeset to minimize the repo
      churn ...]
      
      The general preference to matches in the middle of bdiff ranges helps getting
      balanced recursion and efficient computation. But, as previous changes have
      shown, it might also give diffs that seems "obviously wrong".
      
      To mitigate that: If the best match on the A side starts at the beginning of
      the bdiff range, don't aim for the middle-most B side match but for the
      earliest.
      
      This will make the matches balanced (by both sides being "early") even though
      the bisection will be less balanced. Still, this case only apply if the *best*
      and middle-most match was fully unbalanced on the A side. Each recursion will
      thus even in this worst case reduce the problem significantly and we are not
      re-introducing the problem that was fixed in f1ca249696ed.
      
      The bundle size for 4.0 (hg bundle --base null -r 4.0 x.hg) happens to go from
      22806817 to 22807275 bytes - a 0.002% increase.
      
      This make the recent test-bdiff.py changes give a more pretty output ... but
      they no longer show that the recursion is around middle matches (because it in
      these cases isn't).
      3633403888ae
  5. Nov 08, 2016
    • Mads Kiilerich's avatar
      bdiff: give slight preference to longest matches in the middle of the B side · 8c0c75aa3ff4
      Mads Kiilerich authored
      We already have a slight preference for matches close to the middle on the A
      side. Now, do the same on the B side.
      
      j is iterating the b range backwards and we thus accept a new j if the previous
      match was in the upper half.
      
      This makes the test-bhalf diff "correct". It obviously also gives more
      preference to balanced recursion than to appending to sequences. That is kind
      of correct, but will also unfortunately make some bundles bigger. No doubt, we
      can also create examples where it will make them smaller ...
      
      The bundle size for 4.0 (hg bundle --base null -r 4.0 x.hg) happens to go from
      22803824 to 22806817 bytes - an 0.01% increase.
      8c0c75aa3ff4
    • Mads Kiilerich's avatar
      bdiff: adjust criteria for getting optimal longest match in the A side middle · 38ed54888617
      Mads Kiilerich authored
      We prefer matches closer to the middle to balance recursion, as introduced in
      f1ca249696ed.
      
      For ranges with uneven length, matches starting exactly in the middle should
      have preference. That will be optimal for matches of length 1. We will thus
      accept equality in the half check.
      
      For ranges with even length, half was ceil'ed when calculated but we got the
      preference for low matches from the 'less than half' check. To get the same
      result as before when we also accept equality, floor it. Without that,
      test-annotate.t would show some different (still correct but less optimal)
      results.
      
      This will change the heuristics. Tests shows a slightly different output - and
      sometimes slightly smaller bundles.
      
      The bundle size for 4.0 (hg bundle --base null -r 4.0 x.hg) happens to go from
      22804885 to 22803824 bytes - an 0.005% reduction.
      38ed54888617
    • Mads Kiilerich's avatar
      tests: explore some bdiff cases · 3743e5dbb824
      Mads Kiilerich authored
      3743e5dbb824
  6. Nov 15, 2016
  7. Apr 22, 2016
    • Matt Mackall's avatar
      bdiff: deal better with duplicate lines · 9a8363d23419
      Matt Mackall authored
      The longest_match code compares all the possible positions in two
      files to find the best match. Given a pair of sequences, it
      effectively searches a grid like this:
      
        a b b b c . d e . f
        0 1 2 3 4 5 6 7 8 9
      a 1 - - - - - - - - -
      b - 2 1 1 - - - - - -
      b - 1 3 2 - - - - - -
      b - 1 2 4 - - - - - -
      . - - - - - 1 - - 1 -
      
      
      Here, the 4 in the middle says "the first four lines of the
      file match", which it can compute be comparing the fourth lines and
      then adding one to the result found when comparing the third lines in
      the entry to the upper left.
      
      We generally avoid the quadratic worst case by only looking at lines
      that match, which is precomputed. We also avoid quadratic storage by
      only keeping a single column vector and then keeping track of the best
      match.
      
      Unfortunately, this can get us into trouble with the sequences above.
      Because we want to reuse the '3' value when calculating the '4', we
      need to be careful not to overwrite it with the '2' we calculate
      immediately before. If we scan left to right, top to bottom, we're
      going to have a problem: we'll overwrite our 3 before we use it and
      calculate a suboptimal best match.
      
      To address this, we can either keep two column vectors and swap
      between them (which significantly complicates bookkeeping), or change
      our scanning order. If we instead scan from left to right, bottom to
      top, we'll avoid ever overwriting values we'll need in the future.
      
      This unfortunately needs several changes to be made simultaneously:
      
      - change the order we build the initial hash chains for the b sequence
      - change the sentinel values from INT_MAX to -1
      - change the visit order in the longest_match inner loop
      - add a tie-breaker preference for earlier matches
      
      This last is needed because we previously had an implicit tie-breaker
      from our visitation order that our test suite relies on. Later matches
      can also trigger a bug in the normalization code in diff().
      9a8363d23419
  8. Apr 03, 2016
  9. Nov 18, 2011
  10. Oct 26, 2010
  11. May 30, 2009
  12. May 16, 2009
  13. Dec 06, 2008
  14. Oct 14, 2008
    • Benoit Boissinot's avatar
      bdiff: normalize the diff (issue1295) · 9514cbb6e4f6
      Benoit Boissinot authored
      When the common part of a diff can be moved forward, move it forward.
      Otherwise we don't get deterministic results (it would depends on the way we
      split for the recursion).
      That way we get identical hunks when doing the same change, it helps to solve
      issue1295 (inconsistent diffs on different side during a merge).
      9514cbb6e4f6
  15. Jul 30, 2005
  16. Jul 29, 2005
  17. Jun 22, 2005
    • mpm's avatar
      Add a fast binary diff extension (not yet used) · 8b067bde6679
      mpm authored
      -----BEGIN PGP SIGNED MESSAGE-----
      Hash: SHA1
      
      Add a fast binary diff extension (not yet used)
      
      manifest hash: fbfdcab2b1f4856af45176fcf2423d602dfe88c4
      -----BEGIN PGP SIGNATURE-----
      Version: GnuPG v1.4.0 (GNU/Linux)
      
      iD8DBQFCuL6eywK+sNU5EO8RAoT+AJ95z9gx2IrucBS30CnCQFkZT7lSbgCgnXh5
      ScZcgwzJ/mEo9i5vuKNlCIs=
      =Gr58
      -----END PGP SIGNATURE-----
      8b067bde6679
Loading