patch, 8 partsxdl_change_compact(): clarify code

I've talked about this quite a bit on the list already. The idea is to improve ugly diffs like

    @@ -231,6 +231,9 @@ if (!defined $initial_reply_to && $prompting) {
     }

     if (!$smtp_server) {
    +       $smtp_server = $repo->config('sendemail.smtpserver');
    +}
    +if (!$smtp_server) {
            foreach (qw( /usr/sbin/sendmail /usr/lib/sendmail )) {
                    if (-x $_) {
                            $smtp_server = $_;

by feeding clues from the surrounding lines (namely their patterns of indentation and blank lines) into a heuristic that more often produces the diffs that users would rather see, like

    --- a/9c572b21dd090a1e5c5bb397053bf8043ffe7fb4:git-send-email.perl
    +++ b/6dcfa306f2b67b733a7eb2d7ded1bc9987809edb:git-send-email.perl
    @@ -230,6 +230,9 @@ if (!defined $initial_reply_to && $prompting) {
            $initial_reply_to =~ s/(^\s+|\s+$)//g;
     }

    +if (!$smtp_server) {
    +       $smtp_server = $repo->config('sendemail.smtpserver');
    +}
     if (!$smtp_server) {
            foreach (qw( /usr/sbin/sendmail /usr/lib/sendmail )) {
                    if (-x $_) {

See the last commit's log message for a very detailed explanation of the heuristic, how it was optimized, and how you can get involved to make sure that the heuristic also works well for your favorite language.

When tested against a corpus of 2700 diffs that I optimized by hand, this heuristic gets a "wrong" answer only about 1.7% as frequently as the current default Git algorithm and only about 5.3% as often as `git diff --compaction-heuristic`. (Though please don't treat these numbers as final; I want to verify them again first.)

For now the new algorithm has to be enabled explicitly using either `--indent-heuristic` or `git config diff.indentheuristic true`.

Michael Haggerty (8):
  xdl_change_compact(): rename some local variables for clarity
  xdl_change_compact(): clarify code
  xdl_change_compact(): rename i to end
  xdl_change_compact(): do one final shift or the other, not both
  xdl_change_compact(): fix compaction heuristic to adjust io
  xdl_change_compact(): keep track of the earliest end
  is_blank_line: take a single xrecord_t as argument
  diff: improve positioning of add/delete blocks in diffs

 Documentation/diff-options.txt |   6 +-
 diff.c                         |  11 +
 git-add--interactive.perl      |   5 +-
 xdiff/xdiff.h                  |   1 +
 xdiff/xdiffi.c                 | 458 ++++++++++++++++++++++++++++++++++-------
 5 files changed, 409 insertions(+), 72 deletions(-)

Write things out a bit longer but less cryptically. Add more comments.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
I find the loops in the old code, with unfamiliar patterns of embedded
increment/decrement operators, confusing, and I think that writing
things out a little bit more verbosely (and with more comments) makes
it much easier to read the code and be sure that it is correct.
The compiled code and performance shouldn't be affected materially.

 xdiff/xdiffi.c | 106 +++++++++++++++++++++++++++++++++++++++------------------
 1 file changed, 73 insertions(+), 33 deletions(-)

On Wed, Aug 3, 2016 at 3:00 PM, Michael Haggerty <mhagger@alum.mit.edu> wrote:

By less cryptic you mean in Git coding style ;) The original author (do we want to cc Davido?) may disagree.

IIRC this comment is not quite correct as this 'only' counts the number of blank lines within the forward shifting section, i.e. in the movable space.

Later we use it as a boolean indicator (whether or not it is equal to 0) to see if we can do better.

Any other change in code and comments looks good to me, but this stood out like a sore thumb. (Probably the old heuristic as a whole stood out, but the comment here specifically sounds /wrong/ to me in this place. How can a question document a variable? I'd rather expect a question comment to ease the understanding of a condition)

Thanks for reviving this topic! Stefan

On 08/04/2016 12:11 AM, Stefan Beller wrote:

Davide hasn't contributed since 2008 and libxdiff is not being developed, so I didn't think he'd be interested.

Yes, tastes certainly differ. If more people like the old version better, I will gnash my teeth and undo these "clarification" patches. I mean, what's not to like about variable names like "grpsiz" and "ixref"?

I don't understand your objection. A blank line can appear as the last line of the group if and only if it is within the shift range ("movable space") of the group, right? So it seems like our formulations are equivalent.

Since the variable is used as a boolean, it seemed natural to document it by stating the question that the true/false value is the answer to.

If you have a concrete suggestion for a better comment, please let me know.

Michael

On Wed, Aug 3, 2016 at 4:14 PM, Michael Haggerty <mhagger@alum.mit.edu> wrote:

ok.

I was not asking for undoing these, but giving short cryptic answers myself. ;) While I agree the variable names are way better than before, the use of while instead of for (and then doing another final ++ after the loop) extended some one liners to about 5. I am totally fine with that as they are easier to read for me as I understand them as Git style, hence easier to read.

There may be old timers (who have knowledge of C from other projects), that would prefer the style as before:

e.g.

-               start = i;
-               for (i++; rchg[i]; i++);
-               for (; rchgo[io]; io++);
+               start = i++;
+
+               while (rchg[i])
+                       i++;
+
+               while (rchgo[io])
+                      io++;

This doesn't change variable names, but it only transforms a for loop with no body in a more readable structure of while loops separated by white space. So for such a chunk I could imagine people arguing about adding lines of code (which is valuable screen real estate) for only slight gain if any. I am not one of these.

faster typng ;)

Sure, e.g. in 0fe5043da (2016-06-17, dir_iterator: new API for iterating over a directory tree), struct dir_iterator_int we have a member

    struct dir_iterator_int {
...
         /*
         * The number of levels currently on the stack. This is always
         * at least 1, because when it becomes zero the iteration is
         * ended and this struct is freed.
         */
         size_t levels_nr;
...
};

you could have written that comment as

    /* How many levels do we have to free? */

but that would be misleading the same way as here.

I think a comment should carry useful information that is not obvious from the code. So in this comment we want to convey the message that we need to count blank lines to apply a heuristic later on. Maybe

  /* Number of blank lines in the sliding area of the group */

as that

* states the actual thing we do
* doesn't hint at one particular intended use case later on
* it assumes you know what a "sliding area" is though.

I think what triggered me on questioning this comment, was the fact that it is a question as we rarely have comments stated as questions.

Oh I see. Another example (that maybe looks constructed) is the comment of S_IFGITLINK in cache.h which is not "Is this entry a submodule?" but rather some sentence of what a git link actually is. (though very short)

I'd go with the imperative form,

 /* Number of blank lines in the sliding area of the group */

if that makes sense to you?

Sorry for the bike shedding and not focusing on the real issues,

Stefan

On Wed, Aug 03, 2016 at 04:50:46PM -0700, Stefan Beller wrote:

One thing I try to do with loops is to use "for" loops only when I truly want an iteration from point A to point B. If I care about the value of the iterator _after_ the loop, I prefer a "while" loop.

Not everybody necessarily has the same taste, but I assume Michael does, since that's what's happening in this hunk:

-Peff

On 08/04/2016 01:50 AM, Stefan Beller wrote:

Thanks for your comments, Stefan.

I realized that the main thing that took me a while to grok when I was reading this code was that blank_lines was really only used as a boolean value, even though it was updated with "+=". That's the main information that I'd like to convey to the reader.

So I decided to change the comment to emphasize this fact (and change it from a question to a statement), and also changed the place that blank_lines is updated to treat it more like a boolean. The latter change also has the advantage of not calling is_blank_line() unnecessarily when blank_lines is already true.

If you have no objections, that is what I will put in v2 of this patch series:

Michael

On Wed, Aug 10, 2016 at 9:39 AM, Michael Haggerty <mhagger@alum.mit.edu> wrote:

Oh :(

I think there was some discussion when we added the blank line counting whether we would want to have it boolean or counting. And we settled for counting as "future algorithms can make use of this additional information" IIRC.

No objections from my side, sorry for this lengthy discussion about a comment,

Thanks, Stefan

The code branch used for the compaction heuristic incorrectly forgot to keep io in sync while the group was shifted. I think that could have led to reading past the end of the rchgo array.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
I didn't actually try to verify the presence of a bug, because it
seems like more work than worthwhile. But here is my reasoning:

If io is not decremented correctly during one iteration of the outer `while` loop, then it will loose sync with the `end` counter. In particular it will be too large.

Suppose that the next iterations of the outer `while` loop (i.e., processing the next block of add/delete lines) don't have any sliders. Then the `io` counter would be incremented by the number of non-changed lines in xdf, which is the same as the number of non-changed lines in xdfo that *should have* followed the group that experienced the malfunction. But since `io` was too large at the end of that iteration, it will be incremented past the end of the xdfo->rchg array, and will try to read that memory illegally.

 xdiff/xdiffi.c | 4 ++++
 1 file changed, 4 insertions(+)

On Thu, Aug 04, 2016 at 12:00:33AM +0200, Michael Haggerty wrote:

Hmm. In the loop:

  while (rchgo[io])
	io++;

that implies that rchgo has a zero-marker that we can rely on hitting. And it looks like rchgo[io] always ends the loop on a 0. So it seems like we would just hit that condition again.

That doesn't make it _right_, but I'm not sure I see how it would walk off the end of the array. But I'm very sure I don't understand this code completely, so I may be missing something.

Anyway, I'd suggest putting your cover letter bits into the commit message. Even though they are all suppositions, they are the kind of thing that could really help somebody debugging this in 2 years, and are better than nothing.

-Peff

On 08/04/2016 09:27 AM, Jeff King wrote:

I agree.

Correct...in this loop. But there is another place where `io` is incremented unconditionally. In the version before my changes, it is via the preincrement operator in this while statement conditional:

https://github.com/mhagger/git/blob/a28705da929ad746abcb34270947f738549d3246/xdiff/xdiffi.c#L502

After my changes, the unconditional increment is more obvious because I took it out of the while condition:

https://github.com/mhagger/git/blob/39a135da93834fd72ee923d95d0cebfe525dfe7a/xdiff/xdiffi.c#L541

(BTW, I think this is a good example of how patch 2/8 makes the code easier to reason about.)

I didn't do the hard work to determine whether `io` could *really* walk off the end of the array, but I don't see an obvious reason why it *couldn't*.

Good idea. Will do.

Michael

On 08/10/2016 06:58 PM, Michael Haggerty wrote:

Actually, for the case that no more sliders are found in the file, the key lines where io is incremented unconditionally are

https://github.com/mhagger/git/blob/a28705da929ad746abcb34270947f738549d3246/xdiff/xdiffi.c#L438

before the change (note that the post-increment happens even if the while condition returns false), and

https://github.com/mhagger/git/blob/39a135da93834fd72ee923d95d0cebfe525dfe7a/xdiff/xdiffi.c#L443-L444

after the change. (The lines I mentioned in my previous email are also unconditional increments, but those are only executed in the case that more sliders are found.)

Michael

On Wed, Aug 10, 2016 at 06:58:06PM +0200, Michael Haggerty wrote:

Ah, yeah, I totally missed that case (and I agree the code after your 2/8 makes it much more obvious).

Yeah, I'm in agreement.

-Peff

Michael Haggerty <mhagger@alum.mit.edu> writes:

I had to read the first sentence three times as "incorrectly forgot" was a bit strange thing to say (as if there is a situation where 'forgetting to do' is the correct thing to do, but in that case we would phrase it to stress that not doing is a deliberate choice, e.g. 'refraining from doing'). Perhaps s/incorrectly // is the simplest readability improvement?

I agree with Peff that these should be in the log message.

On 08/04/2016 08:43 PM, Junio C Hamano wrote:

Yes, that makes it clearer. Will change.

Michael

There is no reason for it to take an array and index as argument, as it only accesses a single element of the array.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 xdiff/xdiffi.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

Michael Haggerty <mhagger@alum.mit.edu> writes:

Yup, I think I am partly guilty.  The result looks much nicer.

This makes it easier to detect whether shifting is possible, and will also make the next change easier.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 xdiff/xdiffi.c | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)

Michael Haggerty <mhagger@alum.mit.edu> writes:

I can see the code keeping track of earliest_end but the above does not make it clear what the new "continue" is about.

... easier to detect whether shifting is possible (in which case we can skip the shifting), and will also make ...

perhaps.

On 08/04/2016 08:46 PM, Junio C Hamano wrote:

Thanks. I will make the change that you suggest.

Michael

There is no need to shift the group to match a diff in the other file if we're just going to override that shift based on the compaction heuristic. Note that this changes the behavior if the matching shift would have shifted the group higher than the last blank line: the old code would have ignored the compaction heuristic in that case, whereas the new code always gives precedence to the compaction heuristic when it is turned on.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 xdiff/xdiffi.c | 44 ++++++++++++++++++++++----------------------
 1 file changed, 22 insertions(+), 22 deletions(-)

* ix -> i
* ixo -> io
* ixs -> start
* grpsiz -> groupsize

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
Thankfully, we don't have to limit indentifers to six characters, so
start naming things more understandably.

 xdiff/xdiffi.c | 66 +++++++++++++++++++++++++++++-----------------------------
 1 file changed, 33 insertions(+), 33 deletions(-)

On Thu, Aug 04, 2016 at 12:00:29AM +0200, Michael Haggerty wrote:

After your change, I immediately understand three of them. But what is "io"?

-Peff

Jeff King <peff@peff.net> writes:

I had the same reaction.

On 08/04/2016 09:06 AM, Jeff King wrote:

The (pre-existing) convention in this function is that variable names dealing with the "other" file have a trailing "o"; e.g., (xdf, xdfo), (rchg, rchgo). There used to also be (i, io), the indexes tracking the current line number in the file and the other file. But I renamed "i".

At first I was just going to add a comment for variable "io", but in trying to figure out its exact semantics I realized that this code is still pretty hard to follow. Part of the problem is that "the line in the other file corresponding to a line in the to-be-compacted file" is not a well-defined concept. In fact it is *groups of lines* that correlate with each other. So I totally refactored the function, using a

    struct group {
            long start, end;
    };

as a kind of a cursor used to iterate through the groups on both sides. I think the result is a lot easier to read, and while refactoring I found and fixed another bug in the pre-existing code :-O

I hope to have v2 out soon.

Michael

On Sat, Aug 13, 2016 at 09:38:33PM +0200, Michael Haggerty wrote:

Yeah, after reading the rest of the patches, the "o" prefix sort of started to make sense.

That sounds like it would be nicer. And bug fixes are always good.

Don't kill yourself polishing up the function names, though (unless you keep finding bugs. ;) ).

-Peff

On 08/04/2016 12:00 AM, Michael Haggerty wrote:

I forgot to note that this patch series is also available from my GitHub account [1] as branch "diff-indent-heuristics".

Also, I will be away from my computer for the next five days, so don't be insulted if I don't respond promptly to your emails. (Well, actually I'm never that prompt so people might not even notice :-/ ).

Michael

[1] https://github.com/mhagger/git

Rename i to end, and alternate between using start and end as the indexing variable as appropriate.

Rename ixref to end_matching_other.

Add some more comments.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 xdiff/xdiffi.c | 70 ++++++++++++++++++++++++++++++++--------------------------
 1 file changed, 39 insertions(+), 31 deletions(-)

On Thu, Aug 04, 2016 at 12:00:31AM +0200, Michael Haggerty wrote:

I'd usually complain that there is too much "what" in your commit message, but in this case, the diff really is hard to read. Having a summary up front is nice.

There's no "why", but I imagine it is just "I had to do this to even make sense of this function".

-Peff

Some groups of added/deleted lines in diffs can be slid up or down, because lines at the edges of the group are not unique. Picking good shifts for such groups is not a matter of correctness but definitely has a big effect on aesthetics. For example, consider the following two diffs. The first is what standard Git emits:

    --- a/9c572b21dd090a1e5c5bb397053bf8043ffe7fb4:git-send-email.perl
    +++ b/6dcfa306f2b67b733a7eb2d7ded1bc9987809edb:git-send-email.perl
    @@ -231,6 +231,9 @@ if (!defined $initial_reply_to && $prompting) {
     }

     if (!$smtp_server) {
    +       $smtp_server = $repo->config('sendemail.smtpserver');
    +}
    +if (!$smtp_server) {
            foreach (qw( /usr/sbin/sendmail /usr/lib/sendmail )) {
                    if (-x $_) {
                            $smtp_server = $_;

The following diff is equivalent, but is obviously preferable from an aesthetic point of view:

    --- a/9c572b21dd090a1e5c5bb397053bf8043ffe7fb4:git-send-email.perl
    +++ b/6dcfa306f2b67b733a7eb2d7ded1bc9987809edb:git-send-email.perl
    @@ -230,6 +230,9 @@ if (!defined $initial_reply_to && $prompting) {
            $initial_reply_to =~ s/(^\s+|\s+$)//g;
     }

    +if (!$smtp_server) {
    +       $smtp_server = $repo->config('sendemail.smtpserver');
    +}
     if (!$smtp_server) {
            foreach (qw( /usr/sbin/sendmail /usr/lib/sendmail )) {
                    if (-x $_) {

This patch teaches Git to pick better positions for such "diff sliders".

The original Git code basically always shifted such "sliders" as far down in the file as possible. The only exception is when the slider can be aligned with a group of the lines in the other file, in which case Git favors one add+delete block over one add and a slightly offset delete block. This naive algorithm often yields ugly diffs.

Commit d634d61ed6 improved the situation somewhat by preferring to position add/delete groups to make their last line a blank line, when that is possible. This heuristic does more good than harm, but can only help if there are blank lines in the right places. It still leaves a lot of ugly diffs.

This commit implements a new and much better heuristic for picking optimal "slider" positions using the following approach: First observe that each hypothetical positioning of a diff slider introduces two splits: one between the context lines preceding the group and the first added/deleted line, and the other between the last added/deleted line and the first line of context following it. It tries to find the positioning that creates the least bad splits.

Splits are evaluated based only on the presence and locations of nearby blank lines, and the indentation of lines near the split. Basically, it prefers to introduce splits between lines that are indented less and adjacent to blank lines. In more detail:

1. It measures the following characteristics of a proposed splitting
   position:

   * the number of blank lines above the proposed split
   * whether the line directly after the split is blank
   * the number of blank lines following that line
   * the indentation of the nearest non-blank line above the split
   * the indentation of the line directly below the split
   * the indentation of the nearest non-blank line after that line

2. It combines these attributes using a bunch of empirically-optimized
   weighting factors to estimate a score of the "badness" of splitting
   the text at that position.

3. It defines the score for a positioning of a diff slider to be the sum
   of the scores for the splits at the top and bottom of the slider.

4. It computes scores like this for all possible positions of the diff
   slider, and selects the position with the smallest "badness" score.

The weighting factors were found by collecting a corpus of code samples in various programming languages, deciding "by eye" the best positioning for about 2700 diff sliders, then optimizing the weights against this corpus to get the best agreement with the manually-determined values. (One caveat is that the same corpus was used for both optimization and testing.)

The resulting numbers of non-optimal diff groups were as follows:

| repository           | default | compaction | indent | optimized |
| -------------------- | ------- | ---------- | ------ | --------- |
| ant                  |     225 |        102 |      7 |         5 |
| bugzilla             |     208 |         81 |     14 |         8 |
| couchdb              |      44 |         24 |     13 |         4 |
| docker               |     180 |        160 |     29 |         7 |
| git                  |     446 |         59 |     27 |         4 |
| ipython              |     358 |        163 |     61 |        11 |
| junit                |     146 |         67 |      5 |         1 |
| nodejs               |     489 |         78 |     12 |         2 |
| phpmyadmin           |     330 |         49 |      1 |         0 |
| test-more            |      15 |          2 |      2 |         0 |
| test-unit            |      33 |         13 |      4 |         0 |
| xmonad               |      20 |          1 |      1 |         0 |
| -------------------- | ------- | ---------- | ------ | --------- |
| totals               |    2494 |        788 |    176 |        42 |

This table shows the number of diff slider groups that were positioned differently than the human-generated values, for various repositories. "default" is the default "git diff" algorithm. "compaction" is Git 2.9.0 with the `--compaction-heuristic` option "indent" is an earlier, hand-optimized version of this heuristic "optimized" is the machine-optimized version, which is implemented in this patch. As you can see, this new heuristic disagrees with the hand-optimized positions only 1.7% as often as the default Git algorithm.

The tools that were used to do this optimization and analysis and the human-generated data values are recorded in a separate project [1]. If other people add more test data (especially in other programming languages and/or other text formats) and come up with weighting factors that work better over a wider breadth of samples, it will be easy to tweak the factors in the code.

[1] https://github.com/mhagger/diff-slider-tools

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
Most of the testing I've done is to run it against the large number of
diffs in the corpus that I have been using to optimize the heuristic.
The diffs that it generates are "equivalent" to the originals
generated by Git (modulo slider positioning), and they are the same
(including slider positioning) as the diffs generated by the Python
code that I used to prototype this heuristic. Since I have very
carefully tested the output of the Python version, I conclude that
this C version is working correctly.

I think it would be hard to add test cases for this code. Maybe one or two sanity checks would be worthwhile?

 Documentation/diff-options.txt |   6 +-
 diff.c                         |  11 ++
 git-add--interactive.perl      |   5 +-
 xdiff/xdiff.h                  |   1 +
 xdiff/xdiffi.c                 | 276 +++++++++++++++++++++++++++++++++++++++--
 5 files changed, 289 insertions(+), 10 deletions(-)

On Wed, Aug 3, 2016 at 3:00 PM, Michael Haggerty <mhagger@alum.mit.edu> wrote:

Should we return -1 here?

It seems odd to be that a line with "199" spaces and nothing else will return "-1" but a line with 200 spaces and nothing else will return 200..? Would it be safe to just return -1 in both cases (if a line is all spaces or starts with more than 200 spaces just return -1)?

On 08/04/2016 12:29 AM, Jacob Keller wrote:

Thanks for your feedback.

I was implicitly assuming that such lines would have text somewhere after those 200 spaces (or 25 TABs or whatever). But you're right, the line could consist only of whitespace. Unfortunately, the only way to distinguish these two cases is to read the rest of the line, which is exactly what we *don't* want to do.

But I think it doesn't matter anyway. Such "text" will likely never be read by a human, so it's not a big deal if the slider position is not picked perfectly. And remember, this whole saga is just to improve the aesthetics of the diff. The diff is *correct* (e.g., in the sense of applicable) regardless of where we position the sliders.

Michael

On Wed, Aug 3, 2016 at 3:36 PM, Michael Haggerty <mhagger@alum.mit.edu> wrote:

I think in this case treating it as "all whitespace" is more natural than treating it as "200 characters with something following it" because the only thing we've found so far is all white space.

Either way it's not really a big deal here.

Thanks, Jake

Michael Haggerty <mhagger@alum.mit.edu> writes:

Not related to Jacob's review, but "the whole line consists of trailing spaces" made me read it twice; while it is technically correct, "the whole line consists of spaces", or even "this is a blank line", would read a lot more easily, at least for me.

Hmm, why is it exactly what we don't want to do? Is it a performance concern? In other words, is it because this function is called many times to measure the same line multiple times? After all, somebody in this file is already scanning each and every line to see where it ends to split the input into records, so perhaps a "right" (if the "theoretical correctness" of the return value from this function mattered, which you wave-away below) optimization could be to precompute it while the lines are broken into records and store it in the "rec" structure?

A better argument may be "if the user is truly reading a diff output for such an unusual "text", it is likely that she has a very wide display and/or running less -S, and treating such an overindented line as if it were a blank line would give a result that is more consistent to what appears on her display", perhaps?

On 08/04/2016 09:39 PM, Junio C Hamano wrote:

Hehe, yes, ETOOMANYWORDS.

Yes, performance is the reason, and especially the desire to avoid unreasonable runtimes for pathological cases. Thanks for asking, though, because it's worthwhile to look into this more rigorously.

Suppose there is a slider that can be shifted to any of `numshift` positions. Then we have to call `measure_split()` `2*numshift` times (once for the beginning and once for the end of each candidate slider position).

Suppose there are `numblanks` blank lines in the neighborhood of the slider. Each time we call `measure_split()`, we count the number of blank lines before and after the proposed split position. So we end up calling `get_indent()` `2*numshift*numblanks` times.

Finally, suppose that the blank lines each contain `numws` whitespace characters. Then each call to `get_indent()` has to do `O(numws)` work.

So altogether, if there were no limits, then the amount of work to position a slider would scale like

    O(numshift * numblanks * numws)

However, the total number of characters in the file might only be

    O(numblanks * numws)

So without limits, the amount of work to position sliders could scale by numshift times the size of the file.

The worst case is pretty easy to achieve. Just create a file consisting of a million or so LF characters, then add another LF to it. The diff would be a slider with

    numshift = 1000000
    numblanks = 1000000
    numws = 1

so the heuristic would take O(N^2) in the size of the file.

Effectively the limits cap the effective `numblanks` at `2*MAX_BLANKS` (which is 2*20) and the effective `numws` at `MAX_INDENT` (which is 200), meaning that the maximum effort scales like

    numshift * 2*20 * 200

which is still a big number but not absurd. Empirically, for the case described above, `git diff` takes 104 ms and `git diff --indent-heuristic` takes 490 ms. I think that's not prohibitive for a pathological case.

Meanwhile, Myers's algorithm scales like O(ND), where N is the number of lines and D is the edit distance, so I suppose that it is already possible to find diffs that are intractable to compute.

That would certainly be possible, and would help in cases where there are a lot of lines with lots of leading whitespace. You could get nearly the same benefit by recording a single bit in struct rec, indicating whether the line is blank or not.

But it wouldn't help the worst case described above, where each call to `git_indent()` is already very cheap. And I didn't think it was worth allocating the extra memory to optimize this heuristic

* which isn't used all that often in the first place,
* which (for normal inputs) doesn't take a significant amount of time, and
* when the optimization doesn't improve the worst-case scenario (and
thus any DoS potential)

I think the only way to ensure O(size_of_file) runtime in the above case would be to record, along with each line, how many blank lines immediately precede and succeed it. You could achieve something like O(size_of_file lg(size_of_file)) by storing, e.g., the total number of nonblank lines that precede each line and doing a binary search to find the nearest non-blank line.

I don't know. It seems like a pretty contrived justification for what is basically, "your input is too weird for us. We're not going to break our necks trying to give you the best possible slider positioning."

Michael

Michael Haggerty <mhagger@alum.mit.edu> writes:

True.

True again.

On Wed, Aug 3, 2016 at 3:00 PM, Michael Haggerty <mhagger@alum.mit.edu> wrote:

Would it make sense to define-ify the 10 as well as this is the only hardcoded number in the scoring function?

On 08/04/2016 12:30 AM, Stefan Beller wrote:

I started answering this question by explaining why it is not important to *optimize* the number 10 (namely because scores are only ever compared against other scores, so an overall scaling factor makes no difference). The factor 10 only has to be large enough to provide enough dynamic range for the other (adjustable) parameters.

But I think you are asking a simpler question: should we give this constant a name rather than hardcoding it? I don't see a strong reason for or against, so I'll give it a name in the next version, as you suggest.

Michael

On Wed, Aug 3, 2016 at 3:41 PM, Michael Haggerty <mhagger@alum.mit.edu> wrote:

But it only scales the score, not the bonus. So another way to write it would be

    score - bonus/10;

assuming the values of score and bonus are large enough.

In some prior conversation you said you take the indent and add an epsilon for some special conditions to make one indent better than the other.

Epsilons are usually very small compared to the rest of the equation, but if I look at the boni definitions ranging from -63..50 they are scaled up so much that the bonus may become larger than '1' unit of 'score', i.e. it is not an epsilon any more. Or to put it another way: If we were to s/10/100/ the results would be worse.

Rather the 10 describes the ratio of "advanced magic" to pure indentation based scoring in my understanding.

Thanks, Stefan

On 08/04/2016 12:51 AM, Stefan Beller wrote:

Yes, that's how it provides the overall scale of the score. If it multiplied both values, then it would be completely pointless.

This is an important point for the optimization, but less so for the implementation of the heuristic here. I was dynamically optimizing the ten other variables, and everything that goes into the bonus includes one of those factors. If I had also let this factor of 10 vary, then the net behavior of the algorithm would be completely unchanged if I would, say, double all eleven parameters. This is bad for optimization, because (1) it increases the search space unnecessarily, and (2) it means that whole lines in the parameter space give identical behavior, making the algorithm waste time searching along those lines for a minimum.

Score is the number of columns that some line is indented, so it can be 0 or 1 or any other positive integer. It is not "large enough", which is why the "10" can't be "1".

If the calculations were done in floating point, then the factor could be "1", because then the other factors could be made less than one.

I should have mentioned that this heuristic is quite a bit more advanced than my original proposal to use "indent" plus some "epsilon" factors. The old discussion about epsilons is not relevant here except maybe as an inspiration and starting point for this version.

If you would change s/10/100/ and simultaneously multiply the other constants by 10, the end results would be unchanged.

No, it's basically just a number against which the other constants are compared. E.g., if another bonus wants to balance out against exactly one space of indentation, its constant needs to be 10. If it wants to balance out against exactly 5 spaces, its constant needs to be 50. Etc.

Michael

On Wed, Aug 3, 2016 at 4:30 PM, Michael Haggerty <mhagger@alum.mit.edu> wrote:

Right, I should have made it more clear that it was a hypothetical rewrite, just to point out we are looking at only one of score or bonus.

Right, so maybe a good name would be CONSTANT_SCALE_OF_ONE_INDENT as it has the meaning that a bonus of 10 is equivalent of "one indent" in the weighting.

Speaking of which, do we want to "over-optimize" to make that constant a power of 2 as that is a supposedly faster multiplication? (Just asking, feel free to reject; as I can imagine the numbers itself are already magic, so why scale them with 42?^H^H^H 16?)

So another interpretation is that the 10 gives the resolution for all other constants, i.e. if we keep 10, then we can only give weights in 1/10 of "one indent". But the "ideal" weight may not be a multiple of 1/10, so we approximate them to the nearest multiple of 1/10.

If we were to use 1000 here, we could have a higher accuracy of the other constants, but probably we do not care about the 3rd decimal place for these because they are created heuristically from a corpus that may not warrant a precision of constants with a 3rd decimal place.

Stefan

On 08/04/2016 02:04 AM, Stefan Beller wrote:

Not only that. Since all of the inputs to the heuristic are integers, the outputs are discontinuous and can take only certain discrete values. And the outputs are only ever compared against one another. So a small adjustment to the output will only make a difference if it causes the value to become larger/smaller than another of the possible output values. So too high a resolution makes no sense at all.

That being said, I didn't actually check in any systematic way whether the resolution of 10:1 is high enough in practice. But I can say that the overall performance of the heuristic (in terms of number of errors counted) remained constant over a relatively large parameter range, so I think the resolution is sufficient.

Feel free to play with the parameters and/or other heuristics. The tools and raw data are all published in [1]. Let me know if you need help getting started.

Michael

[1] https://github.com/mhagger/diff-slider-tools

On Thu, Aug 04, 2016 at 12:00:36AM +0200, Michael Haggerty wrote:

s/option/&./

These two flags are mutually exclusive in the xdiff code, so we should probably handle that here.

TBH, I do not care that much what:

  [diff]
  compactionHeuristic = true
  indentHeuristic = true

does. But right now:

  git config diff.compactionHeuristic true
  git show --indent-heuristic

still prefers the compaction heuristic, which I think is objectively wrong.

So perhaps we need a single variable:

  enum {
    DIFF_HEURISTIC_COMPACTION,
    DIFF_HEURISTIC_INDENT
  } diff_heuristic;

and set it in last-one-wins fashion (it would be nice if the config and command line options were shaped the same way so it's clear to the user that they are exclusive, but we may have to keep --compaction-heuristic around for compatibility, as an alias for --diff-heuristic=compaction).

Nice touch.

Unfortunately the mutual-exclusivity handling will probably bleed over to here, too.

Speaking of absurd amounts of work, I was curious if there was a noticeable performance penalty for using this heuristic (just because it's a lot more complicated than the others). I couldn't detect any differences running "git log -p --no-merges -3000" on git.git with no heuristic, compaction, and indent. There may be other repositories that behave more pathologically (it looks like having 20 blank lines at the end of each hunk?), but I'd guess in most cases this will always be drowned out in the noise of doing the actual diff.

I see there is a comment below here mentioning that these are empirical voodoo, but it might be worth one at the top (or just moving these below the comment) because the comment looks like it's just associated with the function (and these are sufficiently bizarre that anybody reading is going to double-take on them).

I don't mind this not "10" not being a #define constant, but after reading the exchange between you and Stefan, I think it would be nice to describe what it is in a comment. The rest of the function is commented so nicely that this one left me thinking "huh?" upon seeing the "10".

The rest looks sane to me, though I am not sure I have absorbed all the implications. IMHO the most interesting thing is the actual results, though.

-Peff

On Thu, Aug 4, 2016 at 12:56 AM, Jeff King <peff@peff.net> wrote:

After a night of sleep I agree with Peffs statement here, it's not about the #define, it's about the comment. (which the #define would have given in a short cryptic way in angry capital letters).

I have just reread the scoring function and I think you could pull out the `score=indent` assignment (it is always assigned except for indent <0)

        if (indent == -1)
               score = 0;
        else
               score = indent;
        ... lots of bonus computation below, which in its current implementation
        have lots of "score = indent;" lines as well.

Thanks, Stefan

Stefan Beller <sbeller@google.com> writes:

Yup. If each part in this if/else if/... cascade independently sets complete information (i.e. both "bonus" and "score") necessary for the final result, then I do not mind the same "score = indent" in many of them (these case happen to get the same score), but that is not what we have in this code (i.e. "bonus" has a shared component that is not affected by thie if/else if/ cascade), so setting score to indent upfront and reset it to 0 only on a blank line would make sense.

On 08/04/2016 06:55 PM, Stefan Beller wrote:

Yes. An earlier version of the heuristic used different indent values in different situations, but that's gone away so the code can be made simpler now. I'll make the change.

Thanks, Michael

On 08/04/2016 09:56 AM, Jeff King wrote:

Thanks, will change.

I wasn't worrying about that yet, given that these two features are both still experimental. I also have a strong inkling that at most one of them needs to be made permanent. I propose that I repair the semantics in the simplest way possible for now while we decide on the long-term plan, which might conceivably be:

* keep both options permanently
* keep only one option permanently
* choose one heuristic and use it always (i.e., make it part of the new
standard one-and-only diff algorithm)
* discard both heuristics (I hope not!)

After we've decided on that, *then* let's decide on a suitable UI and implement it before we declare either feature non-experimental.

I included some performance numbers in my response to Junio [1].

Good idea.

Done. Thanks for your review.

Michael

[1] http://public-inbox.org/git/5fe0edbc-3659-058f-3328-639d1343fa05@alum.mit.edu/

On Sat, Aug 13, 2016 at 01:25:05AM +0200, Michael Haggerty wrote:

Is there a case where the compaction heuristic produces a better result than this indent heuristic? AFAICT, you have not found one, and I'd be surprised if there is one, because this _seems_ like a superset generally. I suppose there is always the possibility that the empirical knobs behave badly in some particular case that the compaction heuristic just happens to get right, but it should be quite rare.

So assuming everything I just said isn't complete bollocks, I think we can move to a future where nobody uses the compaction heuristic. And there are three ways to deal with that:

  1. The knob and feature stay. It might be useful for somebody who
     wants to experiment in the future.

  2. The knob and feature go away completely. It was an experiment, but
     now we have something more useful.

  3. The feature goes away, but the knob stays as noop, or maybe as an
     alias for the indent heuristic, just because we did ship a version
     that accepts "--compaction-heuristic", and maybe somebody somewhere
     put it in a script?

I think I'd be in favor of (2). It doesn't seem likely enough for people to experiment with to merit a run-time knob; they can always patch and build if they want to do so. And (3) just seems like a pain for something that was only shipped in one version and was kind of experimental, and was unlikely to end up in scripts (much more likely is that people set the config, but that's easier to ignore). But it does violate our usual backwards-compatibility rules.

So if we assume that indent is useful and compaction goes away, the only questions are "does indent it become the default" and "if so, does it still get a knob". I'd say "yes" to both. Making the new behavior the default was what we planned to do with compaction until we saw that it regressed some cases. But as a new feature, it's nice for users to be able to easily disable it to see if it's causing a problem (or to see what a big improvement it is!).

I think we could get by with just a command-line option for that purpose, rather than a config option; that saves a lot of effort in having porcelains manually propagate the config option when they call a plumbing diff-tree.

I guess the only users that leaves out are ones who really want stable backwards-compatible diff. I guess "patch --stable" is one such user (but that one we could handle internally). But let's say you had a code review system that attached comments to lines of a diff. You might want to disable the feature entirely to avoid invalidating old comments.

-Peff

Jeff King <peff@peff.net> writes:

I am all for (2) [*1*]

This and the previous "take a blank line as a hint" are both heuristics. As long as the resulting code does not tax runtime performance visibly and improves the resulting output 99% of the time, there is no reason to leave end-users a knob. "Among 9 hunks in this patch that touch hello.c, 7 are made much more readable but 2 are worse" cannot even be helped with a command line option.

[Footnote]

*1* I am also strongly against (3), if only to teach people a
    lesson ;-).

On Sat, Aug 13, 2016 at 8:59 AM, Junio C Hamano <gitster@pobox.com> wrote:

I also am in favor of (2). I understand the reasoning for maintaining compatibility, but this was a known experimental feature that was unlikely used by many people. Even if it was, these are the very sorts of people who should be aware that the experimental feature is going away. It reduces code complexity if it just goes away, and I believe the new heuristic is much better (Thank you Michael!!!!!)

As for a knob on the new feature, I think it can become the default with a way to disable the feature via command line. I'm not really sure it needs a config option at all.

Yea I agree. It might be worth having it disabled via the stable patch IDs (? I don't know if we guarantee this?) but otherwise I don't see it being important either way. I would vote for a way to disable it via command line just because we *are* changing behavior here. But I don't think it needs to be a config option at all.

This is how I understand it as well. I would not mind to remove the blank-line-suggested-split heuristic.

Maybe we can enable Michaels heuristic with the same config/command line flag, i.e. "the flag changes its algorithm"? Then people, who read the prior announcement don't have to do anything, while we keep it as an experimental feature for the next release and auto-on it after that?

We could also be a bit more aggressive and auto-on the new heuristic with the old heuristic removed and we only have an (undocumented) emergency-off knob for one or two releases?

Thanks, Stefan

Stefan Beller <sbeller@google.com> writes:

I think that is a very sensible proposal. After all, the name diff.compactionHeuristic only tells us what part of the diff process the heuristic is used, and does not say anything about what the heuristics does. It is neutral between "take a blank as a hint" vs "take indentation leveles as a hint".

Michael Haggerty <mhagger@alum.mit.edu> writes:

I agree with Peff about "comment on the voodoo upfront".

When I read up to here, I thought "Heh, isn't the opposite of INdent DEdent?" and then saw this:

It turns out that you mean by OUTdent a line that indents further (if I am reading the code correctly). Is that obvious to everybody?

This and ...

... this seems to be indented correctly even after getting quoted, which in turn means most of the lines in the added code share indent-with-non-tab badness.

On 08/04/2016 09:52 PM, Junio C Hamano wrote:

I'll comment it better.

The code was copy-pasted from a Python prototype then converted to C :-)

I'll fix the whitespace.

Thanks, Michael

On Thu, Aug 04, 2016 at 12:00:28AM +0200, Michael Haggerty wrote:

Not that you probably need more random cases of C code, but I happened to be looking at a diff in git.git today, b333d0d6, which is another regression for the compaction heuristic. The indent heuristic here gets it right.

Coincidentally, another example is the final patch in this series.

So I am already happier even without digging further yet. :)

-Peff

Jeff King <peff@peff.net> writes:

Wow, that one is _really_ bad. Does it have something to do with the removal being at the very end of the file?

Looks that way.

On Thu, Aug 04, 2016 at 12:54:51PM -0700, Junio C Hamano wrote:

I think so. If it were:

  func1() {
     ... unique stuff ...
     ... shared ending ...
  }

  func2() {
     ... more unique stuff ...
     ... shared ending ...
  }

  unrelated_func() {
  }

and we dropped func2, then I think the blank line between func2() and unrelated_func() would cause the compaction heuristic to stop shifting.

OTOH, if it were:

  func2() {
     ...
  }
  unrelated_func() {
  }

with no newline, you get a similar badly-shifted diff (which is not surprising, as we were given no syntactic hint that "func2" is a separate unit from "unrelated_func").

-Peff