hash binary sha1 into patch id

Since commit 2f82f760 (Take binary diffs into account for "git rebase"), binary files are included in patch ID computation. Binary files are diffed using the text diff algorithm, however, which has a huge impact on performance. The following tests performance for a 50000 line file marked as binary in .gitattributes.

$ git format-patch --stdout --full-index --ignore-if-in-upstream master

real 0m0.367s
user 0m0.354s
sys 0m0.010s

Instead of hashing the diff of binary files, use the post-image sha1, which is just as unique. As a result, performance is much improved.

$ git format-patch --stdout --full-index --ignore-if-in-upstream master

real 0m0.016s
user 0m0.015s
sys 0m0.001s

---

This may be related to the rebase performance issue discussed in the following thread.

http://mid.gmane.org/[email protected]

I am attaching the script which I used to test performance.

 diff.c |    6 ++++++
 1 files changed, 6 insertions(+), 0 deletions(-)

index 17873f3..20fc6db 100644
@@ -3758,6 +3758,12 @@ static int diff_get_patch_id(struct diff_options *options, unsigned char *sha1)
 					len2, p->two->path);
 		git_SHA1_Update(&ctx, buffer, len1);
 
+		if (diff_filespec_is_binary(p->two)) {
+			len1 = sprintf(buffer, "%s", sha1_to_hex(p->two->sha1));
+			git_SHA1_Update(&ctx, buffer, len1);
+			continue;
+		}
+
 		xpp.flags = 0;
 		xecfg.ctxlen = 3;
 		xecfg.flags = XDL_EMIT_FUNCNAMES;

1.7.2.1.1.g202c

[...]

Maybe it should use both the pre- and post-image?

			git_SHA1_Update(&ctx, sha1_to_hex(p->one->sha1), 40);

Hi Jonathan,

That would make the patch ID more correct in that it will identify a particular change. But ultimately, we want to know whether or not a change has been applied already. If the contents of a binary file are the same in both commits, this is almost certainly true, regardless of whether or not the pre-images match.

So I think we get better behavior if we ignore the pre-image. Although the difference is probably minuscule.

Thanks.

[...]

As long as you’ve thought it over, I’m happy with it. As you say, the postimage matching without the preimage matching should be a rare event.

FWIW what I was imagining was some structured binary format:

With A some long string, patch 1:

A --> AAA

Patch 2:

AA --> AAA

Ideally one would want an attempt to apply patch 2 to result in a conflict. Probably that is far-fetched.

Actually, rebase will try to merge the respective branches and it will typically succeed, because the post-images are the same. It will fail due to conflict only if yet another patch has been applied upstream on top of patch 1.

But that is also how textual changes behave. So for the sake of consistency, it makes sense to require the pre-images to be the same. I will resend an appropriate patch tomorrow.

Since commit 2f82f760 (Take binary diffs into account for "git rebase"), binary files are included in patch ID computation. Binary files are diffed using the text diff algorithm, however, which has a huge impact on performance. The following tests performance for a 50000 line file marked as binary in .gitattributes.

$ git format-patch --stdout --ignore-if-in-upstream master

real    0m0.367s
user    0m0.354s
sys     0m0.010s

Instead of diffing the binary files, hash the pre- and post-image sha1, which is just as unique. As a result, performance is much improved.

$ git format-patch --stdout --ignore-if-in-upstream master

real    0m0.016s
user    0m0.015s
sys     0m0.001s

---

I am again attaching the corresponding test script. Since it mostly tests performance, I am not sure how to incorporate it into the main test suite.

 diff.c |    7 +++++++
 1 files changed, 7 insertions(+), 0 deletions(-)

index 17873f3..f4a23ab 100644
@@ -3758,6 +3758,13 @@ static int diff_get_patch_id(struct diff_options *options, unsigned char *sha1)
 					len2, p->two->path);
 		git_SHA1_Update(&ctx, buffer, len1);
 
+		if (diff_filespec_is_binary(p->one) ||
+		    diff_filespec_is_binary(p->two)) {
+			git_SHA1_Update(&ctx, sha1_to_hex(p->one->sha1), 40);
+			git_SHA1_Update(&ctx, sha1_to_hex(p->two->sha1), 40);
+			continue;
+		}
+
 		xpp.flags = 0;
 		xecfg.ctxlen = 3;
 		xecfg.flags = XDL_EMIT_FUNCNAMES;

1.7.2.1.1.g202c

Nice. :)

Maybe t3302-notes-index-expensive.sh would be a good example to compare.

I haven’t looked carefully at your test script; is it possible to extract a non-expensive test (i.e., just for correctness) from it, too?

Jonathan

As I see, this recently hit git master. I want to say big thanks since it improved git rebase from tens of minutes to just minutes here (warm disk caches).

However, I can't say I'm completely satisfied with git rebase speed (I'd like it to be < 1 min). So, are there known performance hotspots in 'git rev-list --cherry-pick'/'git format-patch --ignore-if-in-upstream' (these are two flags have biggest impact on git rebase [-i] speed) or I should run some kind of profiles in order to determine what else could be improved?

git format-patch is still slow if you have large text files (>10000 lines). This patch only helps for binary files or files marked as binary in .gitattributes. There is also a patch

http://mid.gmane.org/645d8a9bf671937c1a6962b49cf1c512e0af0d82.1279008702.git.git@drmicha.warpmail.net

to turn off patch ID computation entirely.

Other than that, I am not aware of performance issues with rebase that would cause it to take more than a minute. Possibly you can use 'perf' to profile your use case. I used it to test this patch in the script below (pass -p to enable). But it's only testing format-patch right now, so you would have to modify it to profile rebase as a whole.

Clemens
---

#!/bin/bash

set -e

NLINES=50000
NRAND=32768

# probability of change in percent
CHG_PROB=30
perf=
while test $# -gt 0
do
	case $1 in
	-p)
		perf=t
		;;
	-n)
		shift
		NLINES=$1
		;;
	*)
		break
		;;
	esac
	shift
done

if test $# -gt 0
then

	export PATH="$1:$PATH"
	shift

fi

if test $# -gt 0
then
echo "too many arguments" >&2
exit 1
fi

dir=$(mktemp -d)

scramble()

{
	while read x
	do
		if test $RANDOM -lt $((($CHG_PROB * $NRAND)/100))
		then
			echo $RANDOM
		else
			echo "$x"
		fi
	done < "$1" > "$1.new"
	mv -f "$1.new" "$1"
}

run()

{
	echo \$ "$@"
	if test -n "$perf"
	then
		perf record -g -f "$@" >/dev/null
		perf report -g
	else
		time "$@" >/dev/null
	fi
}

cd "$dir"
git init -q

for i in $(seq $NLINES)
do
echo $i
done > file
git add file
echo "file binary" >.gitattributes
git add .gitattributes
git commit -q -m initial
git branch other

scramble file
git add file
git commit -q -m 'change big file'

git checkout -q other
: >newfile
git add newfile
git commit -q -m 'add small file'

gfp="git format-patch --stdout"

run $gfp master
run $gfp --ignore-if-in-upstream master

git cherry-pick master >/dev/null 2>&1

git checkout -q master
scramble file
git add file
git commit -q -m 'change big file again'

git checkout -q other^{}
run git rebase master
if test -n "$(git rev-list master...HEAD~)"
then
echo "patch not identified" >&2
exit 1
fi

git checkout -q -b squashed master
git reset -q --soft HEAD~2
git commit -q -m squashed
git checkout -q other^{}
if git rebase squashed >/dev/null
then
echo "patch dropped" >&2
exit 1
fi

cd - >/dev/null
rm -rf "$dir"

So, here's some gprof data of git-rev-list:
http://git.661346.n2.nabble.com/file/n5629905/gprof_-p.txt gprof -p output
http://git.661346.n2.nabble.com/file/n5629905/gprof_-q.txt gprof -q output

View this message in context: http://git.661346.n2.nabble.com/PATCH-hash-binary-sha1-into-patch-id-tp5419375p5629905.html
Sent from the git mailing list archive at Nabble.com.

Does diff_get_patch_id (in diff.c) really need to set xecfg.flags = XDL_EMIT_FUNCNAMES? Removing that makes git-rev-list (called by rebase) 2x faster here. Not sure about consequences though.

View this message in context: http://git.661346.n2.nabble.com/PATCH-hash-binary-sha1-into-patch-id-tp5419375p5630164.html
Sent from the git mailing list archive at Nabble.com.

Hi Marat,

Yes, this has already been fixed in ad14b450 (do not search functions for patch ID), which is currently in git.git's pu branch. Function name search performance has also been improved for some obscure cases in c099789b (diff: avoid repeated scanning while looking for funcname).

Thanks anyways. If you notice anything else, please let us know.

I had a look at your gprof results, but I cannot make much sense of it. I do not understand why git rev-list would even do any diffs. For me, rev-list spends more than 50% in libz. Can you give more details on the kind of repository you have (binaries, memory size, history size, any special attributes or options?), which git version you are using, and which options you are passing to rev-list?

Clemens

I'm running git-rev-list from git master in the form git rebase does:
git-rev-list --no-merges --cherry-pick --pretty=oneline --abbrev-commit --abbrev=7 --reverse --left-right --topo-order FOO...BAR

New gprof output (I compiled without -O2 to prevent function inlining and removed xecfg.flags = XDL_EMIT_FUNCNAMES):
http://git.661346.n2.nabble.com/file/n5633988/gprof_-p.txt gprof -p
http://git.661346.n2.nabble.com/file/n5633988/gprof_-q.txt gprof -q

This thing takes ~3 minutes of cpu time.

So, it takes ~3 minutes of cpu time and looks like all time is spent in xdl_cleanup_records.

Repo info: 80GB, 200K revisions (~200 per working day), 500K files (15GB) in master working copy, running git-rev-list to rebase ~5 commits over ~800 commits that happened upstream.

View this message in context: http://git.661346.n2.nabble.com/PATCH-hash-binary-sha1-into-patch-id-tp5419375p5633988.html
Sent from the git mailing list archive at Nabble.com.