| Age | Commit message (Collapse) | Author |
|---|
|
This macro has been unused since 43ca7530df (xdiff/xhistogram: rely on
xdl_trim_ends(), 2011-08-01). The function that called it went away
there, and its use in the CMP() macro was inlined. It probably should
have been deleted then, but nobody noticed.
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Now that the histogram algorithm calls xdl_classify_record() it is no
longer necessary to use xdl_recmatch() to compare lines, it is
sufficient just to compare the hash values. This has a negligible
effect on performance.
Test HEAD~1 HEAD
-----------------------------------------------------------------------------
4000.1: log -3000 (baseline) 0.19(0.12+0.07) 0.18(0.14+0.04) -5.3%
4000.2: log --raw -3000 (tree-only) 0.98(0.81+0.16) 0.98(0.79+0.18) +0.0%
4000.3: log -p -3000 (Myers) 4.81(4.23+0.56) 4.80(4.26+0.53) -0.2%
4000.4: log -p -3000 --histogram 5.83(5.11+0.70) 5.82(5.15+0.65) -0.2%
4000.5: log -p -3000 --patience 5.31(4.61+0.69) 5.30(4.54+0.75) -0.2%
Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
rindex and ha are only used by xdl_cleanup_records() which is not
called by the histogram or patience algorithms. The perf test results
show a small reduction in run time but that is probably within the
noise.
Test HEAD^ HEAD
-----------------------------------------------------------------------------
4000.1: log -3000 (baseline) 0.19(0.17+0.02) 0.19(0.12+0.07) +0.0%
4000.2: log --raw -3000 (tree-only) 0.98(0.78+0.20) 0.98(0.81+0.16) +0.0%
4000.3: log -p -3000 (Myers) 4.81(4.15+0.64) 4.81(4.23+0.56) +0.0%
4000.4: log -p -3000 --histogram 5.87(5.19+0.66) 5.83(5.11+0.70) -0.7%
4000.5: log -p -3000 --patience 5.35(4.60+0.73) 5.31(4.61+0.69) -0.7%
Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Histogram is the only diff algorithm not to call
xdl_classify_record(). xdl_classify_record() ensures that the hash
values of two strings that are not equal differ which means that it is
not necessary to use xdl_recmatch() when comparing lines, all that is
necessary is to compare the hash values. This gives a 7% reduction in
the runtime of "git log --patch" when using the histogram diff
algorithm.
Test HEAD^ HEAD
-----------------------------------------------------------------------------
4000.1: log -3000 (baseline) 0.18(0.14+0.04) 0.19(0.17+0.02) +5.6%
4000.2: log --raw -3000 (tree-only) 0.99(0.77+0.21) 0.98(0.78+0.20) -1.0%
4000.3: log -p -3000 (Myers) 4.84(4.31+0.51) 4.81(4.15+0.64) -0.6%
4000.4: log -p -3000 --histogram 6.34(5.86+0.46) 5.87(5.19+0.66) -7.4%
4000.5: log -p -3000 --patience 5.39(4.60+0.76) 5.35(4.60+0.73) -0.7%
Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Rewrite the backend for "diff -G/-S" to use pcre2 engine when
available.
* ab/pickaxe-pcre2: (22 commits)
xdiff-interface: replace discard_hunk_line() with a flag
xdiff users: use designated initializers for out_line
pickaxe -G: don't special-case create/delete
pickaxe -G: terminate early on matching lines
xdiff-interface: allow early return from xdiff_emit_line_fn
xdiff-interface: prepare for allowing early return
pickaxe -S: slightly optimize contains()
pickaxe: rename variables in has_changes() for brevity
pickaxe -S: support content with NULs under --pickaxe-regex
pickaxe: assert that we must have a needle under -G or -S
pickaxe: refactor function selection in diffcore-pickaxe()
perf: add performance test for pickaxe
pickaxe/style: consolidate declarations and assignments
diff.h: move pickaxe fields together again
pickaxe: die when --find-object and --pickaxe-all are combined
pickaxe: die when -G and --pickaxe-regex are combined
pickaxe tests: add missing test for --no-pickaxe-regex being an error
pickaxe tests: test for -G, -S and --find-object incompatibility
pickaxe tests: add test for "log -S" not being a regex
pickaxe tests: add test for diffgrep_consume() internals
...
|
|
Code clean-up.
* ab/xdiff-bug-cleanup:
xdiff: use BUG(...), not xdl_bug(...)
|
|
The xdl_bug() function was introduced in
e8adf23d1e (xdl_change_compact(): introduce the concept of a change
group, 2016-08-22), let's use our usual BUG() function instead.
We'll now have meaningful line numbers if we encounter bugs in xdiff,
and less code duplication.
Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Code clean-up.
* pw/patience-diff-clean-up:
patience diff: remove unused variable
patience diff: remove unnecessary string comparisons
|
|
Remove the dummy discard_hunk_line() function added in
3b40a090fd4 (diff: avoid generating unused hunk header lines,
2018-11-02) in favor of having a new XDL_EMIT_NO_HUNK_HDR flag, for
use along with the two existing and similar XDL_EMIT_* flags.
Unlike the recently amended xdiff_emit_line_fn interface which'll be
called in a loop in xdl_emit_diff(), the hunk header is only emitted
once.
It makes more sense to pass this as a flag than provide a dummy
callback because that function may be able to skip doing certain work
if it knows the caller is doing nothing with the hunk header.
It would be possible to do so in the case of -U0 now, but the benefit
of doing so is so small that I haven't bothered. But this leaves the
door open to that, and more importantly makes the API use more
intuitive.
The reason we're putting a flag in the gap between 1<<0 and 1<<2 is
that the old 1<<1 flag was removed in 907681e940d (xdiff: drop
XDL_EMIT_COMMON, 2016-02-23) without re-ordering the remaining flags.
Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
xdl_prepare_env() calls xdl_classify_record() which arranges for the
hashes of non-matching lines to be different so lines can be tested
for equality by comparing just their hashes.
This reduces the time taken to calculate the diff of v2.28.0 to
v2.29.0 by ~3-4%.
Signed-off-by: Phillip Wood <phillip.wood@dunelm.org.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Add a new diff option that enables ignoring changes whose all lines
(changed, removed, and added) match a given regular expression. This is
similar to the -I/--ignore-matching-lines option in standalone diff
utilities and can be used e.g. to ignore changes which only affect code
comments or to look for unrelated changes in commits containing a large
number of automatically applied modifications (e.g. a tree-wide string
replacement). The difference between -G/-S and the new -I option is
that the latter filters output on a per-change basis.
Use the 'ignore' field of xdchange_t for marking a change as ignored or
not. Since the same field is used by --ignore-blank-lines, identical
hunk emitting rules apply for --ignore-blank-lines and -I. These two
options can also be used together in the same git invocation (they are
complementary to each other).
Rename xdl_mark_ignorable() to xdl_mark_ignorable_lines(), to indicate
that it is logically a "sibling" of xdl_mark_ignorable_regex() rather
than its "parent".
Signed-off-by: Michał Kępień <michal@isc.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
xpparam_t structures are usually zero-initialized before their specific
fields are assigned to, but there are three locations in the tree where
that does not happen. Add the missing memset() calls in order to make
initialization of xpparam_t structures consistent tree-wide and to
prevent stack garbage from being used as field values.
Signed-off-by: Michał Kępień <michal@isc.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The "diff" machinery learned not to lose added/removed blank lines
in the context when --ignore-blank-lines and --function-context are
used at the same time.
* rs/xdiff-ignore-ws-w-func-context:
xdiff: unignore changes in function context
|
|
Changes involving only blank lines are hidden with --ignore-blank-lines,
unless they appear in the context lines of other changes. This is
handled by xdl_get_hunk() for context added by --inter-hunk-context, -u
and -U.
Function context for -W and --function-context added by xdl_emit_diff()
doesn't pay attention to such ignored changes; it relies fully on
xdl_get_hunk() and shows just the post-image of ignored changes
appearing in function context. That's inconsistent and confusing.
Improve the result of using --ignore-blank-lines and --function-context
together by fully showing ignored changes if they happen to fall within
function context.
Signed-off-by: René Scharfe <l.s.r@web.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Inspired by the thoroughly stale https://github.com/git/git/pull/159,
this patch fixes a couple of typos, rewraps and clarifies some comments.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Compilation fix.
* cb/xdiff-no-system-includes-in-dot-c:
xdiff: remove duplicate headers from xpatience.c
xdiff: remove duplicate headers from xhistogram.c
xdiff: drop system includes in xutils.c
|
|
The internal diff machinery can be made to read out of bounds while
looking for --funcion-context line in a corner case, which has been
corrected.
* jk/xdiff-clamp-funcname-context-index:
xdiff: clamp function context indices in post-image
|
|
92b7de93fb (Implement the patience diff algorithm, 2009-01-07) added them
but were already part of xinclude.h
Signed-off-by: Carlo Marcelo Arenas Belón <carenas@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
8c912eea94 ("teach --histogram to diff", 2011-07-12) included them, but
were already part of xinclude.h
Signed-off-by: Carlo Marcelo Arenas Belón <carenas@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
After b46054b374 ("xdiff: use git-compat-util", 2019-04-11), two system
headers added with 6942efcfa9 ("xdiff: load full words in the inner loop
of xdl_hash_record", 2012-04-06) to xutils.c are no longer needed and
could conflict as shown below from an OpenIndiana build:
In file included from xdiff/xinclude.h:26:0,
from xdiff/xutils.c:25:
./git-compat-util.h:4:0: warning: "_FILE_OFFSET_BITS" redefined
#define _FILE_OFFSET_BITS 64
In file included from /usr/include/limits.h:37:0,
from xdiff/xutils.c:23:
/usr/include/sys/feature_tests.h:231:0: note: this is the location of the previous definition
#define _FILE_OFFSET_BITS 32
Make sure git-compat-util.h is the first header (through xinclude.h)
Signed-off-by: Carlo Marcelo Arenas Belón <carenas@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
After finding a function line for --function-context in the pre-image,
xdl_emit_diff() calculates the equivalent line in the post-image. It
assumes that the lines between changes are the same on both sides. If
the option --ignore-blank-lines was also given then this is not
necessarily true.
Clamp the calculation results for start and end of the function context
to prevent out-of-bounds array accesses.
Note that this _just_ fixes the case where our mismatch sends us off the
beginning of the file. There are likely other cases where our assumption
causes us to go to the wrong line within the file. Nobody has developed
a test case yet, and the ultimate fix is likely more complicated than
this patch. But this at least prevents a segfault in the meantime.
Credit for finding the bug goes to "Liu Wei of Tencent Security Xuanwu
Lab".
Reported-by: 刘炜 <lw17qhdz@gmail.com>
Helped-by: René Scharfe <l.s.r@web.de>
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Most of xdiff uses a bare malloc() to allocate memory, and returns an
error when we get NULL. However, there are a few spots which don't check
the return value and may segfault, including at least xdl_merge() and
xpatience.c's find_longest_common_sequence().
Let's use xmalloc() everywhere instead, so that we get a graceful die()
for these cases, without having to do further auditing. This does mean
the existing cases which check errors will now die() instead of
returning an error up the stack. But:
- that's how the rest of Git behaves already for malloc errors
- all of the callers of xdi_diff(), etc, die upon seeing an error
So while we might one day want to fully lib-ify the diff code and make
it possible to use as part of a long-running process, we're not close to
that now. And because we're just tweaking the xdl_malloc() macro here,
we're not really moving ourselves any further away from that. We
could, for example, simplify some of the functions which handle malloc()
errors which can no longer occur. But that would probably be taking us
in the wrong direction.
This also makes our malloc handling more consistent with the rest of
Git, including enforcing GIT_ALLOC_LIMIT and trying to reclaim pack
memory when needed.
Reported-by: 王健强 <jianqiang.wang@securitygossip.com>
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Since the xdiff library was not originally part of Git, it does its own
system includes. Let's instead use git-compat-util, which has two
benefits:
1. It adjusts for any system-specific quirks in how or what we should
include (though xdiff's needs are light enough that this hasn't
been a problem in the past).
2. It lets us use wrapper functions like xmalloc().
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The xdiff library always emits hunk header lines to our callbacks as
formatted strings like "@@ -a,b +c,d @@\n". This is convenient if we're
going to output a diff, but less so if we actually need to compute using
those numbers, which requires re-parsing the line.
In preparation for moving away from this, let's teach xdiff a new
callback function which gets the broken-out hunk information. To help
callers that don't want to use this new callback, if it's NULL we'll
continue to format the hunk header into a string.
Note that this function renames the "outf" callback to "out_line", as
well. This isn't strictly necessary, but helps in two ways:
1. Now that there are two callbacks, it's nice to use more descriptive
names.
2. Many callers did not zero the emit_callback_data struct, and needed
to be modified to set ecb.out_hunk to NULL. By changing the name of
the existing struct member, that guarantees that any new callers
from in-flight topics will break the build and be examined
manually.
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
"git diff --indent-heuristic" had a bad corner case performance.
* sb/indent-heuristic-optim:
xdiff: reduce indent heuristic overhead
|
|
"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
|
|
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 <quark@fb.com>
Analysis-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Stefan Beller <sbeller@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
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 <sbeller@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
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 <sbeller@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
This will be useful in the next patch as we'll introduce multiple
callers.
Signed-off-by: Stefan Beller <sbeller@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
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 <sbeller@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
There is no need to forward-declare these functions, as they are used
after their implementation only.
Signed-off-by: Stefan Beller <sbeller@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
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 <sbeller@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
"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)
|
|
"git grep -W", "git diff -W" and their friends learned a heuristic
to extend a pre-context beyond the line that matches the "function
pattern" (aka "diff.*.xfuncname") to include a comment block, if
exists, that immediately precedes it.
* rs/include-comments-before-the-function-header:
grep: show non-empty lines before functions with -W
grep: update boundary variable for pre-context
t7810: improve check of -W with user-defined function lines
xdiff: show non-empty lines before functions with -W
xdiff: factor out is_func_rec()
t4051: add test for comments preceding function lines
|
|
Teach diff a new algorithm, one that attempts to prevent user-specified
lines from appearing as a deletion or addition in the end result. The
end user can use this by specifying "--anchored=<text>" one or more
times when using Git commands like "diff" and "show".
Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The "diff" family of commands learned to ignore differences in
carriage return at the end of line.
* jc/ignore-cr-at-eol:
diff: --ignore-cr-at-eol
xdiff: reassign xpparm_t.flags bits
|
|
Non-empty lines before a function definition are most likely comments
for that function and thus relevant. Include them in function context.
Such a non-empty line might also belong to the preceeding function if
there is no separating blank line. Stop extending the context upwards
also at the next function line to make sure only one extra function body
is shown at most.
Original-patch-by: Vegard Nossum <vegard.nossum@oracle.com>
Signed-off-by: Rene Scharfe <l.s.r@web.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Add a helper for checking if a given record is a function line. It
frees callers from having to deal with the buffer arguments of
match_func_rec().
Signed-off-by: Rene Scharfe <l.s.r@web.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The mailing address for the FSF has changed over the years. Rather than
updating the address across all files, refer readers to gnu.org, as the
GNU GPL documentation now suggests for license notices. The mailing
address is retained in the full license files (COPYING and LGPL-2.1).
The old address is still present in t/diff-lib/COPYING. This is
intentional, as the file is used in tests and the contents are not
expected to change.
Signed-off-by: Todd Zullinger <tmz@pobox.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
A new option --ignore-cr-at-eol tells the diff machinery to treat a
carriage-return at the end of a (complete) line as if it does not
exist.
Just like other "--ignore-*" options to ignore various kinds of
whitespace differences, this will help reviewing the real changes
you made without getting distracted by spurious CRLF<->LF conversion
made by your editor program.
Helped-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>
[jch: squashed in command line completion by Dscho]
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
We have packed the bits too tightly in such a way that it is not
easy to add a new type of whitespace ignoring option, a new type
of LCS algorithm, or a new type of post-cleanup heuristics.
Reorder bits a bit to give room for these three classes of options
to grow. Also make use of XDF_WHITESPACE_FLAGS macro where we check
any of these bits are on, instead of using DIFF_XDL_TST() macro on
individual possibilities. That way, the "is any of the bits on?"
code does not have to change when we add more ways to ignore
whitespaces.
While at it, add a comment in front of the bit definitions to
clarify in which structure these defined bits may appear.
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
A common mistake when writing binary search is to allow possible
integer overflow by using the simple average:
mid = (min + max) / 2;
Instead, use the overflow-safe version:
mid = min + (max - min) / 2;
This translation is safe since the operation occurs inside a loop
conditioned on "min < max". The included changes were found using
the following git grep:
git grep '/ *2;' '*.c'
Making this cleanup will prevent future review friction when a new
binary search is contructed based on existing code.
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
Reviewed-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
When adding a new function to the end of a file, it's enough to know
that 1) the addition is at the end of the file; and 2) there is a
function _somewhere_ in there.
If we had simply been changing the end of an existing function, then we
would also be deleting something from the old version.
This fixes the case where we add e.g.
// Begin of dummy
static int dummy(void)
{
}
to the end of the file.
Signed-off-by: Vegard Nossum <vegard.nossum@oracle.com>
Acked-by: René Scharfe <l.s.r@web.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
"git diff" and its family had two experimental heuristics to shift
the contents of a hunk to make the patch easier to read. One of
them turns out to be better than the other, so leave only the
"--indent-heuristic" option and remove the other one.
* jc/retire-compaction-heuristics:
diff: retire "compaction" heuristics
|
|
When a patch inserts a block of lines, whose last lines are the
same as the existing lines that appear before the inserted block,
"git diff" can choose any place between these existing lines as the
boundary between the pre-context and the added lines (adjusting the
end of the inserted block as appropriate) to come up with variants
of the same patch, and some variants are easier to read than others.
We have been trying to improve the choice of this boundary, and Git
2.11 shipped with an experimental "compaction-heuristic". Since
then another attempt to improve the logic further resulted in a new
"indent-heuristic" logic. It is agreed that the latter gives better
result overall, and the former outlived its usefulness.
Retire "compaction", and keep "indent" as an experimental feature.
The latter hopefully will be turned on by default in a future
release, but that should be done as a separate step.
Suggested-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
The xdiff code hashes every line of both sides of a diff,
and then compares those hashes to find duplicates. The
overall performance depends both on how fast we can compute
the hashes, but also on how many hash collisions we see.
The idea of XDL_FAST_HASH is to speed up the hash
computation. But the generated hashes have worse collision
behavior. This means that in some cases it speeds diffs up
(running "git log -p" on git.git improves by ~8% with it),
but in others it can slow things down. One pathological case
saw over a 100x slowdown[1].
There may be a better hash function that covers both
properties, but in the meantime we are better off with the
original hash. It's slightly slower in the common case, but
it has fewer surprising pathological cases.
[1] http://public-inbox.org/git/20141222041944.GA441@peff.net/
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
Clean-up for a recently graduated topic.
* mh/diff-indent-heuristic:
xdiff: rename "struct group" to "struct xdlgroup"
|
|
"git diff -W" output needs to extend the context backward to
include the header line of the current function and also forward to
include the body of the entire current function up to the header
line of the next one. This process may have to merge to adjacent
hunks, but the code forgot to do so in some cases.
* rs/xdiff-merge-overlapping-hunks-for-W-context:
xdiff: fix merging of hunks with -W context and -u context
|
