git/xdiff, branch v2.19.2

Merge branch 'sb/indent-heuristic-optim'

2018-08-17T20:09:57Z

"git diff --indent-heuristic" had a bad corner case performance. * sb/indent-heuristic-optim: xdiff: reduce indent heuristic overhead

Merge branch 'sb/histogram-less-memory'

2018-08-15T22:08:25Z

"git diff --histogram" had a bad memory usage pattern, which has been rearranged to reduce the peak usage. * sb/histogram-less-memory: xdiff/histogram: remove tail recursion xdiff/xhistogram: move index allocation into find_lcs xdiff/xhistogram: factor out memory cleanup into free_index() xdiff/xhistogram: pass arguments directly to fall_back_to_classic_diff

xdiff: reduce indent heuristic overhead

2018-08-01T20:36:22Z

Skip searching for better indentation heuristics if we'd slide a hunk more than its size. This is the easiest fix proposed in the analysis[1] in response to a patch that mercurial took for xdiff to limit searching by a constant. Using a performance test as: #!python open('a', 'w').write(" \n" * 1000000) open('b', 'w').write(" \n" * 1000001) This patch reduces the execution of "git diff --no-index a b" from 0.70s to 0.31s. However limiting the sliding to the size of the diff hunk, which was proposed as a solution (that I found easiest to implement for now) is not optimal for cases like open('a', 'w').write(" \n" * 1000000) open('b', 'w').write(" \n" * 2000000) as then we'd still slide 1000000 times. In addition to limiting the sliding to size of the hunk, also limit by a constant. Choose 100 lines as the constant as that fits more than a screen, which really means that the diff sliding is probably not providing a lot of benefit anyway. [1] https://public-inbox.org/git/72ac1ac2-f567-f241-41d6-d0f83072e0b3@alum.mit.edu/ Reported-by: Jun Wu Analysis-by: Michael Haggerty Signed-off-by: Stefan Beller Signed-off-by: Junio C Hamano

xdiff/histogram: remove tail recursion

2018-07-23T17:12:16Z

When running the same reproduction script as the previous patch, it turns out the stack is too small, which can be easily avoided. Signed-off-by: Stefan Beller Signed-off-by: Junio C Hamano

xdiff/xhistogram: move index allocation into find_lcs

2018-07-19T19:46:03Z

This fixes a memory issue when recursing a lot, which can be reproduced as seq 1 100000 >one seq 1 4 100000 >two git diff --no-index --histogram one two Before this patch, histogram_diff would call itself recursively before calling free_index, which would mean a lot of memory is allocated during the recursion and only freed afterwards. By moving the memory allocation (and its free call) into find_lcs, the memory is free'd before we recurse, such that memory is reused in the next step of the recursion instead of using new memory. This addresses only the memory pressure, not the run time complexity, that is also awful for the corner case outlined above. Helpful in understanding the code (in addition to the sparse history of this file), was https://stackoverflow.com/a/32367597 which reproduces most of the code comments of the JGit implementation. Signed-off-by: Stefan Beller Signed-off-by: Junio C Hamano

xdiff/xhistogram: factor out memory cleanup into free_index()

2018-07-19T19:46:01Z

This will be useful in the next patch as we'll introduce multiple callers. Signed-off-by: Stefan Beller Signed-off-by: Junio C Hamano

xdiff/xhistogram: pass arguments directly to fall_back_to_classic_diff

2018-07-19T19:46:00Z

By passing the 'xpp' and 'env' argument directly to the function 'fall_back_to_classic_diff', we eliminate an occurrence of the 'index' in histogram_diff, which will prove useful in a bit. While at it, move it up in the file. This will make the diff of one of the next patches more legible. Signed-off-by: Stefan Beller Signed-off-by: Junio C Hamano

xdiff/xdiffi.c: remove unneeded function declarations

2018-07-17T18:25:31Z

There is no need to forward-declare these functions, as they are used after their implementation only. Signed-off-by: Stefan Beller Signed-off-by: Junio C Hamano

xdiff/xdiff.h: remove unused flags

2018-07-17T18:25:31Z

These flags were there since the beginning (3443546f6e (Use a *real* built-in diff generator, 2006-03-24), but were never used. Remove them. Signed-off-by: Stefan Beller Signed-off-by: Junio C Hamano

Merge branch 'jt/diff-anchored-patience'

2017-12-19T19:33:56Z

"git diff" learned a variant of the "--patience" algorithm, to which the user can specify which 'unique' line to be used as anchoring points. * jt/diff-anchored-patience: diff: support anchoring line(s)