* [RFC/PATCH] git-fetch: Use already fetched branch with the --local flag.
From: Santi Béjar @ 2006-10-16 13:40 UTC (permalink / raw)
To: Git Mailing List
It allows to separate when you fetch from when you merge. So, a "git pull"
can be:
$ git fetch
$ git pull --local
and the pull call can be made later. This is usefull when you have multiple
branches and you want to merge the same "upstream" branch, or when you are
offline but you have already fetched the remote branch.
Note that this is different from:
$ git fetch
$ git pull . origin
(1) you do not have to tell explicitly the branch to merge
(2) the commit message is exactly as with "git pull"
Signed-off-by: Santi Béjar <sbejar@gmail.com>
---
Documentation/fetch-options.txt | 3 +++
git-fetch.sh | 25 +++++++++++++++++++------
git-parse-remote.sh | 22 ++++++++++++++++++++++
3 files changed, 44 insertions(+), 6 deletions(-)
diff --git a/Documentation/fetch-options.txt b/Documentation/fetch-options.txt
index 13f34d3..3a6cb3d 100644
--- a/Documentation/fetch-options.txt
+++ b/Documentation/fetch-options.txt
@@ -39,3 +39,6 @@
check. Note that fetching into the current branch will not
update the index and working directory, so use it with care.
+\--local::
+ Do not fetch from the remote repository. Use the already fetched
+ branches to program the merge for `git-pull`.
diff --git a/git-fetch.sh b/git-fetch.sh
index 79222fb..5ff800a 100755
--- a/git-fetch.sh
+++ b/git-fetch.sh
@@ -21,6 +21,7 @@ update_head_ok=
exec=
upload_pack=
keep=--thin
+local_fetch=
while case "$#" in 0) break ;; esac
do
case "$1" in
@@ -56,6 +57,9 @@ do
--reflog-action=*)
rloga=`expr "z$1" : 'z-[^=]*=\(.*\)'`
;;
+ --local)
+ local_fetch=t
+ ;;
-*)
usage
;;
@@ -80,6 +84,10 @@ refs=
rref=
rsync_slurped_objects=
+[ "$local_fetch" = t ] && [ "$remote_nick" = "$remote" ] && \
+ [ "$remote" != "." ] && \
+ die "Flag --local only compatible with remote shorthands"
+
rloga="$rloga $remote_nick"
test "$remote_nick" = "$remote" || rloga="$rloga $remote"
@@ -285,8 +293,8 @@ fetch_main () {
rref="$rref$LF$remote_name"
# There are transports that can fetch only one head at a time...
- case "$remote" in
- http://* | https://* | ftp://*)
+ case "$local_fetch,$remote" in
+ ,http://* | ,https://* | ,ftp://*)
if [ -n "$GIT_SSL_NO_VERIFY" ]; then
curl_extra_args="-k"
fi
@@ -313,7 +321,7 @@ fetch_main () {
echo >&2 Fetching "$remote_name from $remote" using http
git-http-fetch -v -a "$head" "$remote/" || exit
;;
- rsync://*)
+ ,rsync://*)
TMP_HEAD="$GIT_DIR/TMP_HEAD"
rsync -L -q "$remote/$remote_name" "$TMP_HEAD" || exit 1
head=$(git-rev-parse --verify TMP_HEAD)
@@ -343,6 +351,11 @@ fetch_main () {
rsync_slurped_objects=t
}
;;
+ t,*)
+ [ -z "$local_name" ] &&\
+ local_name=$(get_ref_for_remote_branch "$remote_nick" "$remote_name")
+ head=$(git-rev-parse --verify $local_name^0) || exit
+ ;;
*)
# We will do git native transport with just one call later.
continue ;;
@@ -353,8 +366,8 @@ fetch_main () {
done
- case "$remote" in
- http://* | https://* | ftp://* | rsync://* )
+ case "$local_fetch,$remote" in
+ ,http://* | ,https://* | ,ftp://* | ,rsync://* | t,*)
;; # we are already done.
*)
( : subshell because we muck with IFS
@@ -406,7 +419,7 @@ fetch_main () {
fetch_main "$reflist"
# automated tag following
-case "$no_tags$tags" in
+case "$no_tags$tags$local_fetch" in
'')
case "$reflist" in
*:refs/*)
diff --git a/git-parse-remote.sh b/git-parse-remote.sh
index c325ef7..679f73c 100755
--- a/git-parse-remote.sh
+++ b/git-parse-remote.sh
@@ -236,3 +236,25 @@ resolve_alternates () {
esac
done
}
+
+get_ref_for_remote_branch (){
+ data_source=$(get_data_source "$1")
+ case "$data_source" in
+ '' | config-partial | branches | branches-partial)
+ test "$1" = . && echo $2
+ ;;
+ config)
+ ref=$(git-repo-config --get-all "remote.$1.fetch" |\
+ grep "^$2:")
+ expr "z$ref" : 'z[^:]*:\(.*\)'
+ ;;
+ remotes)
+ ref=$(sed -ne '/^Pull: */{
+ s///p
+ }' "$GIT_DIR/remotes/$1" | grep "$2:")
+ expr "z$ref" : 'z[^:]*:\(.*\)'
+ ;;
+ *)
+ die "internal error: get-ref-for-remote-branch $1 $2" ;;
+ esac
+}
--
1.4.3.rc2.ga442
^ permalink raw reply related
* Re: [PATCH] pack-objects: use of version 3 delta is now optional.
From: Nicolas Pitre @ 2006-10-16 13:43 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Junio C Hamano, git
In-Reply-To: <Pine.LNX.4.64.0610151150530.3952@g5.osdl.org>
On Sun, 15 Oct 2006, Linus Torvalds wrote:
>
>
> On Sun, 15 Oct 2006, Junio C Hamano wrote:
> >
> > I think that is sensible. I also was thinking that we should
> > call the current one packv3 and the one with delta-base-offset
> > packv4.
>
> Quite frankly, I wonder if the pure "copy size extension" (aka "v3") thing
> is really worth it at all.
>
> I mean, seriously, how much does it buy us? A couple of bytes per every
> 64kB of delta copied? And the downside is that you can't re-use the deltas
> with old clients and/or you have to re-create a "v2" delta at run-time
> from a v3 delta by inflating, fixing and deflating it.
Right. This is why I suggested Junio to just drop it for now. Let's
just wait some more until this is just not an issue any longer, say in a
year from now when all major distributions have switched to a GIT
version that can read V3.
If until then we find the saving really worth the backward compatibility
v3-to-v2 conversion then we could reconsider. But I don't think it is
worth it just yet.
In the mean time, if Junio adds the patch I posted yesterday advertising
the pack version capability over the native protocol then it'll help us
make things forward compatible if ever we decide to go with generating
packs v3 sooner.
Nicolas
^ permalink raw reply
* Re: On blame/pickaxe
From: Josef Weidendorfer @ 2006-10-16 14:02 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Petr Baudis, Luben Tuikov, git, Linus Torvalds
In-Reply-To: <7v8xjgvjys.fsf@assigned-by-dhcp.cox.net>
Hi,
this blame-passing thing really looks very promising and powerful.
On Monday 16 October 2006 08:43, you wrote:
> If the user is not prepared to see code movement, pickaxe can be
> run without -M nor -C to get the classic blame output.
Another blame-passing heuristic would be very interesting for code:
"Ignore white-space changes".
This way, commits which only do some reindentations simply are skipped.
It looks like such a thing would just be a matter of passing "-b" to
executions of "diff" in the blame-passing algorithm.
Josef
^ permalink raw reply
* git-diff-tree inordinately (O(M*N)) slow on files with many changes
From: Jim Meyering @ 2006-10-16 14:12 UTC (permalink / raw)
To: git
[using very latest code, built an hour ago:
git version 1.4.3.rc3.gb32db-dirty ]
I found that git-diff-tree is *very* slow when processing files with
many changes. The offending example involves comparing the configure
file from coreutils-6.3 with that from the latest coreutils development
sources. Both are over 50k lines long, and the diff -u output is almost
50k-lines long, divided into ~700 hunks.
http://meyering.net/code/git-perf/configure.gz
http://meyering.net/code/git-perf/configure-curr.gz
Comparing them with "diff -u" takes about 0.3s.
Putting them in a git repo (uncompressed, and with the same name,
of course) and comparing with git-diff-tree takes over a minute.
That's 200 times slower.
I traced the problem to xdiff/xprepare.c's xdl_cleanup_records function.
Each of its two doubly-nested loops ends up running the inner-loop
code more than 2 *billion* times.
That seems to be due to the two typos fixed by this patch:
With this patch, my "git-diff-tree --no-commit-id -r -p 2c2172"
command completes in just 2 seconds.
diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c
index 1be7b31..e5438a9 100644
--- a/xdiff/xprepare.c
+++ b/xdiff/xprepare.c
@@ -381,7 +381,7 @@ static int xdl_cleanup_records(xdfile_t
hav = (*recs)->ha;
rhi = (long) XDL_HASHLONG(hav, xdf2->hbits);
for (nm = 0, rec = xdf2->rhash[rhi]; rec; rec = rec->next)
- if (rec->ha == hav && ++nm == mlim)
+ if (rec->ha == hav || ++nm == mlim)
break;
dis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;
}
@@ -392,7 +392,7 @@ static int xdl_cleanup_records(xdfile_t
hav = (*recs)->ha;
rhi = (long) XDL_HASHLONG(hav, xdf1->hbits);
for (nm = 0, rec = xdf1->rhash[rhi]; rec; rec = rec->next)
- if (rec->ha == hav && ++nm == mlim)
+ if (rec->ha == hav || ++nm == mlim)
break;
dis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;
}
However, that change causes the t800*.sh (14,16,18) annotate/blame
tests to fail, so take it with a grain of salt.
I.e., running one of them manually gave this:
$ sh t8001-annotate.sh --immediate --verbose
* expecting success: check_count A 2 B 1 B1 2 B2 1 "A U Thor" 1
Author A (expected 2, attributed 2) good
Author B1 (expected 2, attributed 1) bad
Author A U Thor (expected 1, attributed 2) bad
Author B2 (expected 1, attributed 1) good
Author B (expected 1, attributed 1) good
* FAIL 14: Two lines blamed on A, one on B, two on B1, one on B2, one on A U Thor
check_count A 2 B 1 B1 2 B2 1 "A U Thor" 1
[Exit 1]
^ permalink raw reply related
* Re: On blame/pickaxe
From: Andy Whitcroft @ 2006-10-16 14:15 UTC (permalink / raw)
To: Josef Weidendorfer
Cc: Junio C Hamano, Petr Baudis, Luben Tuikov, git, Linus Torvalds
In-Reply-To: <200610161602.49811.Josef.Weidendorfer@gmx.de>
Josef Weidendorfer wrote:
> Hi,
>
> this blame-passing thing really looks very promising and powerful.
>
> On Monday 16 October 2006 08:43, you wrote:
>> If the user is not prepared to see code movement, pickaxe can be
>> run without -M nor -C to get the classic blame output.
>
> Another blame-passing heuristic would be very interesting for code:
> "Ignore white-space changes".
> This way, commits which only do some reindentations simply are skipped.
>
> It looks like such a thing would just be a matter of passing "-b" to
> executions of "diff" in the blame-passing algorithm.
I am thinking that that is probabally going to need to be optional, for
example python the indentation is everything to the meaning of the code.
-apw
^ permalink raw reply
* Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes
From: Linus Torvalds @ 2006-10-16 15:47 UTC (permalink / raw)
To: Jim Meyering, Davide Libenzi; +Cc: Git Mailing List
In-Reply-To: <87slhopcws.fsf@rho.meyering.net>
Davide? I'm quoting the whole report, because I suspect you don't follow
the git lists, and this is all original libxdiff code.
Jim: the annotation failure _may_ just be due to a "valid" diff change
(there is not always a unique correct answer for a diff, and so two
different diff algorithms can validly give two different answers, which
will also mean that git-annotate/blame would give different explanations).
But it could certainly also be that you just broke the diffs entirely, so
I would like to wait for Davide to comment on your diff before Junio
should apply it.
Others may be intimately familiar with the diff algorithms too, of course.
It just scares me personally ;)
Linus
On Mon, 16 Oct 2006, Jim Meyering wrote:
>
> [using very latest code, built an hour ago:
> git version 1.4.3.rc3.gb32db-dirty ]
>
> I found that git-diff-tree is *very* slow when processing files with
> many changes. The offending example involves comparing the configure
> file from coreutils-6.3 with that from the latest coreutils development
> sources. Both are over 50k lines long, and the diff -u output is almost
> 50k-lines long, divided into ~700 hunks.
>
> http://meyering.net/code/git-perf/configure.gz
> http://meyering.net/code/git-perf/configure-curr.gz
>
> Comparing them with "diff -u" takes about 0.3s.
> Putting them in a git repo (uncompressed, and with the same name,
> of course) and comparing with git-diff-tree takes over a minute.
> That's 200 times slower.
>
> I traced the problem to xdiff/xprepare.c's xdl_cleanup_records function.
> Each of its two doubly-nested loops ends up running the inner-loop
> code more than 2 *billion* times.
>
> That seems to be due to the two typos fixed by this patch:
> With this patch, my "git-diff-tree --no-commit-id -r -p 2c2172"
> command completes in just 2 seconds.
>
> diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c
> index 1be7b31..e5438a9 100644
> --- a/xdiff/xprepare.c
> +++ b/xdiff/xprepare.c
> @@ -381,7 +381,7 @@ static int xdl_cleanup_records(xdfile_t
> hav = (*recs)->ha;
> rhi = (long) XDL_HASHLONG(hav, xdf2->hbits);
> for (nm = 0, rec = xdf2->rhash[rhi]; rec; rec = rec->next)
> - if (rec->ha == hav && ++nm == mlim)
> + if (rec->ha == hav || ++nm == mlim)
> break;
> dis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;
> }
> @@ -392,7 +392,7 @@ static int xdl_cleanup_records(xdfile_t
> hav = (*recs)->ha;
> rhi = (long) XDL_HASHLONG(hav, xdf1->hbits);
> for (nm = 0, rec = xdf1->rhash[rhi]; rec; rec = rec->next)
> - if (rec->ha == hav && ++nm == mlim)
> + if (rec->ha == hav || ++nm == mlim)
> break;
> dis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;
> }
>
> However, that change causes the t800*.sh (14,16,18) annotate/blame
> tests to fail, so take it with a grain of salt.
>
> I.e., running one of them manually gave this:
>
> $ sh t8001-annotate.sh --immediate --verbose
> * expecting success: check_count A 2 B 1 B1 2 B2 1 "A U Thor" 1
> Author A (expected 2, attributed 2) good
> Author B1 (expected 2, attributed 1) bad
> Author A U Thor (expected 1, attributed 2) bad
> Author B2 (expected 1, attributed 1) good
> Author B (expected 1, attributed 1) good
> * FAIL 14: Two lines blamed on A, one on B, two on B1, one on B2, one on A U Thor
> check_count A 2 B 1 B1 2 B2 1 "A U Thor" 1
> [Exit 1]
> -
> To unsubscribe from this list: send the line "unsubscribe git" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at http://vger.kernel.org/majordomo-info.html
>
^ permalink raw reply
* Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes
From: Linus Torvalds @ 2006-10-16 16:12 UTC (permalink / raw)
To: Jim Meyering, Davide Libenzi; +Cc: Git Mailing List
In-Reply-To: <Pine.LNX.4.64.0610160838200.3962@g5.osdl.org>
On Mon, 16 Oct 2006, Linus Torvalds wrote:
>
> But it could certainly also be that you just broke the diffs entirely, so
> I would like to wait for Davide to comment on your diff before Junio
> should apply it.
I think you broke it.
If the "&& vs ||" makes a difference (and it clearly does), that implies
that you have lots of different hash values on the same hash chain, and
you end up considering those _different_ hash values to be all equivalent
for the counting, even though they obviously aren't.
I think the real problem is that with big input, the hash tables are too
small, making the hash chains too long - even though the values on the
chains are different (ie we're not hashing different records with the same
hash value over and over again - if that was true, the "&& vs ||" change
wouldn't make any difference).
So I think xdiff has chosen too small a hash. Can you try what happens if
you change xdl_hashbits() (in xdiff/xutil.c) instead? Try making it return
a bigger value (for example, by initializing "bits" to 2 instead of 0),
and see if that makes a difference.
But again, I'm not actually all _that_ familiar with the libxdiff
algorithms, _especially_ the line-based ones (I can follow the regular
binary delta code, but the line-based one just makes my head hurt). So
take anything I say with a pinch of salt.
Linus
^ permalink raw reply
* Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes
From: Davide Libenzi @ 2006-10-16 16:24 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Jim Meyering, Git Mailing List
In-Reply-To: <Pine.LNX.4.64.0610160838200.3962@g5.osdl.org>
On Mon, 16 Oct 2006, Linus Torvalds wrote:
>
> Davide? I'm quoting the whole report, because I suspect you don't follow
> the git lists, and this is all original libxdiff code.
>
> Jim: the annotation failure _may_ just be due to a "valid" diff change
> (there is not always a unique correct answer for a diff, and so two
> different diff algorithms can validly give two different answers, which
> will also mean that git-annotate/blame would give different explanations).
>
> But it could certainly also be that you just broke the diffs entirely, so
> I would like to wait for Davide to comment on your diff before Junio
> should apply it.
>
> Others may be intimately familiar with the diff algorithms too, of course.
> It just scares me personally ;)
The test is fine as is. Only really bad hash collisions can show O(M*N).
Can I have the two sample files to test?
- Davide
^ permalink raw reply
* Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes
From: Jim Meyering @ 2006-10-16 16:33 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Davide Libenzi, Git Mailing List
In-Reply-To: <Pine.LNX.4.64.0610160904400.3962@g5.osdl.org>
Linus Torvalds <torvalds@osdl.org> wrote:
> On Mon, 16 Oct 2006, Linus Torvalds wrote:
...
> So I think xdiff has chosen too small a hash. Can you try what happens if
> you change xdl_hashbits() (in xdiff/xutil.c) instead? Try making it return
> a bigger value (for example, by initializing "bits" to 2 instead of 0),
> and see if that makes a difference.
It makes no difference.
Bear in mind that there are a *lot* of duplicate lines in the files
being compared: filtering each through "sort -u" removes 40-50k lines.
^ permalink raw reply
* Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes
From: Davide Libenzi @ 2006-10-16 16:36 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Jim Meyering, Git Mailing List
In-Reply-To: <Pine.LNX.4.64.0610160904400.3962@g5.osdl.org>
On Mon, 16 Oct 2006, Linus Torvalds wrote:
> On Mon, 16 Oct 2006, Linus Torvalds wrote:
> >
> > But it could certainly also be that you just broke the diffs entirely, so
> > I would like to wait for Davide to comment on your diff before Junio
> > should apply it.
>
> I think you broke it.
>
> If the "&& vs ||" makes a difference (and it clearly does), that implies
> that you have lots of different hash values on the same hash chain, and
> you end up considering those _different_ hash values to be all equivalent
> for the counting, even though they obviously aren't.
>
> I think the real problem is that with big input, the hash tables are too
> small, making the hash chains too long - even though the values on the
> chains are different (ie we're not hashing different records with the same
> hash value over and over again - if that was true, the "&& vs ||" change
> wouldn't make any difference).
>
> So I think xdiff has chosen too small a hash. Can you try what happens if
> you change xdl_hashbits() (in xdiff/xutil.c) instead? Try making it return
> a bigger value (for example, by initializing "bits" to 2 instead of 0),
> and see if that makes a difference.
I think the xdl_hashbits() picks up the hash table size "almost"
correctly. I think we're looking at some bad hash *collisions* (not
records with same hash value, that'd be stopped by the mlim check).
Send me the files and I'll take a look ...
> But again, I'm not actually all _that_ familiar with the libxdiff
> algorithms, _especially_ the line-based ones (I can follow the regular
> binary delta code, but the line-based one just makes my head hurt). So
> take anything I say with a pinch of salt.
That's my revenge on myself having to follow your code in the kernel :D
- Davide
^ permalink raw reply
* Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes
From: Davide Libenzi @ 2006-10-16 16:42 UTC (permalink / raw)
To: Jim Meyering; +Cc: Linus Torvalds, Git Mailing List
In-Reply-To: <87mz7wp6ek.fsf@rho.meyering.net>
On Mon, 16 Oct 2006, Jim Meyering wrote:
> Linus Torvalds <torvalds@osdl.org> wrote:
> > On Mon, 16 Oct 2006, Linus Torvalds wrote:
> ...
> > So I think xdiff has chosen too small a hash. Can you try what happens if
> > you change xdl_hashbits() (in xdiff/xutil.c) instead? Try making it return
> > a bigger value (for example, by initializing "bits" to 2 instead of 0),
> > and see if that makes a difference.
>
> It makes no difference.
>
> Bear in mind that there are a *lot* of duplicate lines in the files
> being compared: filtering each through "sort -u" removes 40-50k lines.
Ok, try to bring down XDL_MAX_EQLIMIT to something like 8 or 16 ...
- Davide
^ permalink raw reply
* Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes
From: Jim Meyering @ 2006-10-16 16:50 UTC (permalink / raw)
To: Davide Libenzi; +Cc: Linus Torvalds, Git Mailing List
In-Reply-To: <Pine.LNX.4.64.0610160941270.7697@alien.or.mcafeemobile.com>
Davide Libenzi <davidel@xmailserver.org> wrote:
> On Mon, 16 Oct 2006, Jim Meyering wrote:
>
>> Linus Torvalds <torvalds@osdl.org> wrote:
>> > On Mon, 16 Oct 2006, Linus Torvalds wrote:
>> ...
>> > So I think xdiff has chosen too small a hash. Can you try what happens if
>> > you change xdl_hashbits() (in xdiff/xutil.c) instead? Try making it return
>> > a bigger value (for example, by initializing "bits" to 2 instead of 0),
>> > and see if that makes a difference.
>>
>> It makes no difference.
>>
>> Bear in mind that there are a *lot* of duplicate lines in the files
>> being compared: filtering each through "sort -u" removes 40-50k lines.
>
> Ok, try to bring down XDL_MAX_EQLIMIT to something like 8 or 16 ...
That helps a little.
Now, instead of taking 63s, my test takes ~30s.
(32 for XDL_MAX_EQLIMIT = 16, 30 for XDL_MAX_EQLIMIT = 8)
^ permalink raw reply
* Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes
From: Jakub Narebski @ 2006-10-16 16:54 UTC (permalink / raw)
To: git
In-Reply-To: <Pine.LNX.4.64.0610160920250.7697@alien.or.mcafeemobile.com>
<opublikowany i wysłany>
Davide Libenzi wrote:
> The test is fine as is. Only really bad hash collisions can show O(M*N).
> Can I have the two sample files to test?
Jim Meyering wrote:
> http://meyering.net/code/git-perf/configure.gz
> http://meyering.net/code/git-perf/configure-curr.gz
--
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git
^ permalink raw reply
* Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes
From: Linus Torvalds @ 2006-10-16 16:54 UTC (permalink / raw)
To: Jim Meyering; +Cc: Davide Libenzi, Git Mailing List
In-Reply-To: <87mz7wp6ek.fsf@rho.meyering.net>
On Mon, 16 Oct 2006, Jim Meyering wrote:
> Linus Torvalds <torvalds@osdl.org> wrote:
> > On Mon, 16 Oct 2006, Linus Torvalds wrote:
> ...
> > So I think xdiff has chosen too small a hash. Can you try what happens if
> > you change xdl_hashbits() (in xdiff/xutil.c) instead? Try making it return
> > a bigger value (for example, by initializing "bits" to 2 instead of 0),
> > and see if that makes a difference.
>
> It makes no difference.
>
> Bear in mind that there are a *lot* of duplicate lines in the files
> being compared: filtering each through "sort -u" removes 40-50k lines.
It can't be due to duplicate lines. If the lines are truly duplicate, then
they'd get the same 32-bit hash value, and then the first conditional in
the expression would always be true, and then it wouldn't _matter_ if it's
a "&&" or a "||".
See?
So as far as I can tell it has to be some kind of collission on the hash
queue with _different_ hash values being queued on the same hash queue.
Now, it could be that there's a bad hash algorithm somewhere (eg if
XDL_HASHLONG() just does horribly badly in distributing the hash values
onto the hash queues, you'd see this _regardless_ of how many bits you
have, just because it clumps).
Or there could be something else that I'm just missing..
It would probably be nice to just get a sampling of what the hash-queue
looks like for the bad case? Maybe it would be obvious that certain
different hash values then get the same XDL_HASHLONG() thing..
Linus
^ permalink raw reply
* Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes
From: Davide Libenzi @ 2006-10-16 16:54 UTC (permalink / raw)
To: Jim Meyering; +Cc: Linus Torvalds, Git Mailing List
In-Reply-To: <87ejt8p5l9.fsf@rho.meyering.net>
On Mon, 16 Oct 2006, Jim Meyering wrote:
> Davide Libenzi <davidel@xmailserver.org> wrote:
> > On Mon, 16 Oct 2006, Jim Meyering wrote:
> >
> >> Linus Torvalds <torvalds@osdl.org> wrote:
> >> > On Mon, 16 Oct 2006, Linus Torvalds wrote:
> >> ...
> >> > So I think xdiff has chosen too small a hash. Can you try what happens if
> >> > you change xdl_hashbits() (in xdiff/xutil.c) instead? Try making it return
> >> > a bigger value (for example, by initializing "bits" to 2 instead of 0),
> >> > and see if that makes a difference.
> >>
> >> It makes no difference.
> >>
> >> Bear in mind that there are a *lot* of duplicate lines in the files
> >> being compared: filtering each through "sort -u" removes 40-50k lines.
> >
> > Ok, try to bring down XDL_MAX_EQLIMIT to something like 8 or 16 ...
>
> That helps a little.
> Now, instead of taking 63s, my test takes ~30s.
> (32 for XDL_MAX_EQLIMIT = 16, 30 for XDL_MAX_EQLIMIT = 8)
That's too much still. May I have the offending files?
- Davide
^ permalink raw reply
* Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes
From: Jim Meyering @ 2006-10-16 16:57 UTC (permalink / raw)
To: Davide Libenzi; +Cc: Linus Torvalds, Git Mailing List
In-Reply-To: <Pine.LNX.4.64.0610160953480.7697@alien.or.mcafeemobile.com>
Davide Libenzi <davidel@xmailserver.org> wrote:
>> That helps a little.
>> Now, instead of taking 63s, my test takes ~30s.
>> (32 for XDL_MAX_EQLIMIT = 16, 30 for XDL_MAX_EQLIMIT = 8)
>
> That's too much still. May I have the offending files?
These URLs were in at least one of the messages to which
you've replied. Would you like me to send them instead?
> http://meyering.net/code/git-perf/configure.gz
> http://meyering.net/code/git-perf/configure-curr.gz
^ permalink raw reply
* Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes
From: Linus Torvalds @ 2006-10-16 16:57 UTC (permalink / raw)
To: Davide Libenzi; +Cc: Jim Meyering, Git Mailing List
In-Reply-To: <Pine.LNX.4.64.0610160932100.7697@alien.or.mcafeemobile.com>
On Mon, 16 Oct 2006, Davide Libenzi wrote:
>
> I think the xdl_hashbits() picks up the hash table size "almost"
> correctly. I think we're looking at some bad hash *collisions* (not
> records with same hash value, that'd be stopped by the mlim check).
> Send me the files and I'll take a look ...
Davide, they were mentioned in the original report:
http://meyering.net/code/git-perf/configure.gz
http://meyering.net/code/git-perf/configure-curr.gz
I'd take a look myself, but I need to run..
Linus
^ permalink raw reply
* Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes
From: Davide Libenzi @ 2006-10-16 17:02 UTC (permalink / raw)
To: Jim Meyering; +Cc: Linus Torvalds, Git Mailing List
In-Reply-To: <878xjgp5az.fsf@rho.meyering.net>
On Mon, 16 Oct 2006, Jim Meyering wrote:
> Davide Libenzi <davidel@xmailserver.org> wrote:
> >> That helps a little.
> >> Now, instead of taking 63s, my test takes ~30s.
> >> (32 for XDL_MAX_EQLIMIT = 16, 30 for XDL_MAX_EQLIMIT = 8)
> >
> > That's too much still. May I have the offending files?
>
> These URLs were in at least one of the messages to which
> you've replied. Would you like me to send them instead?
>
> > http://meyering.net/code/git-perf/configure.gz
> > http://meyering.net/code/git-perf/configure-curr.gz
Thanks, those are fine.
- Davide
^ permalink raw reply
* Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes
From: Linus Torvalds @ 2006-10-16 17:56 UTC (permalink / raw)
To: Jim Meyering; +Cc: Davide Libenzi, Git Mailing List
In-Reply-To: <87ejt8p5l9.fsf@rho.meyering.net>
On Mon, 16 Oct 2006, Jim Meyering wrote:
>
> That helps a little.
> Now, instead of taking 63s, my test takes ~30s.
> (32 for XDL_MAX_EQLIMIT = 16, 30 for XDL_MAX_EQLIMIT = 8)
Btw, what architecture is this on?
I'm testing those two files, and I get much more reasonable numbers with
both ppc32 and x86. Both 32-bit:
[torvalds@macmini test-perf]$ time git show | wc -l
25221
real 0m1.437s
user 0m1.436s
sys 0m0.012s
ie it generated the diff in less than a second and a half. Not wonderful,
but certainly not your 63s either.
HOWEVER. On x86-64, it takes forever (still not 63 seconds, but it takes
17 seconds on my 2GHz merom machine).
So I think there's something seriously broken with hashing on 64-bit.
And I think I know what it is.
Try this patch. And make sure to do a "make clean" first, since I think
the dependencies on xdiff may be broken.
Davide: there's two things wrong with your old XDL_HASHLONG():
- the GR_PRIME was just 32-bit, so it wouldn't shift low bits up far
enough on a 64-bit architecture, so then shifting things down caused
pretty much everything to be very small.
- The whole idea of shifting up by multiplying and then shifting down to
get the high bits is _broken_. Even on 32-bit architectures. Think
about what happens when "hashbits" is 16 on a 32-bit architecture: the
multiply moves the low bits _up_, but it doesn't move the high bits
_down_. And with hashbits being a large fraction of the whole word, you
need to shift things down, not up.
So just making GR_PRIME be a bigger value on a 64-bit architecture would
not have fixed it. The whole hash was simply broken. Do it the sane and
obvious way instead: always pick the low bits, but mix in upper bits there
too..
This patch brings the time down from 17 seconds to 0.8 seconds for me.
Linus
---
diff --git a/xdiff/xmacros.h b/xdiff/xmacros.h
index 4c2fde8..bb4830b 100644
--- a/xdiff/xmacros.h
+++ b/xdiff/xmacros.h
@@ -24,14 +24,27 @@ #if !defined(XMACROS_H)
#define XMACROS_H
-#define GR_PRIME 0x9e370001UL
+static inline unsigned long xdl_hashlong(unsigned long val, unsigned int bits)
+{
+ unsigned long shift = val >> bits;
+
+ /* Shift in the upper bits too */
+ val += shift;
+
+ /* Do it twice for small values of bits */
+ if (bits < 4*sizeof(unsigned long))
+ val += shift >> bits;
+
+ /* Return the resulting low bits */
+ return val & ((1ul << bits)-1);
+}
#define XDL_MIN(a, b) ((a) < (b) ? (a): (b))
#define XDL_MAX(a, b) ((a) > (b) ? (a): (b))
#define XDL_ABS(v) ((v) >= 0 ? (v): -(v))
#define XDL_ISDIGIT(c) ((c) >= '0' && (c) <= '9')
-#define XDL_HASHLONG(v, b) (((unsigned long)(v) * GR_PRIME) >> ((CHAR_BIT * sizeof(unsigned long)) - (b)))
+#define XDL_HASHLONG(v, b) xdl_hashlong(v,b)
#define XDL_PTRFREE(p) do { if (p) { xdl_free(p); (p) = NULL; } } while (0)
#define XDL_LE32_PUT(p, v) \
do { \
^ permalink raw reply related
* Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes
From: Linus Torvalds @ 2006-10-16 18:03 UTC (permalink / raw)
To: Jim Meyering; +Cc: Davide Libenzi, Git Mailing List
In-Reply-To: <Pine.LNX.4.64.0610161038200.3962@g5.osdl.org>
On Mon, 16 Oct 2006, Linus Torvalds wrote:
>
> So just making GR_PRIME be a bigger value on a 64-bit architecture would
> not have fixed it.
Side note: in _practice_ I think it would have fixed it. The "not mixing
in high bits" is not a real problem if the original hash-value has a good
distribution of bits, which I think we do have. So it's unclear whether we
even need any mixing in of bits at all, and it's possible that it would be
fine to just have
#define XDL_HASHLONG(v,b) ((unsigned long)(v) & ((1ul << (b))-1))
which is simpler than my patch.
I prefer the mixing in of high bits just because it can help if the
original hash was bad (or had a tendency to have patterns in the low bits,
which could be the case). But I'm not sure xdiff actually needs it in this
case.
Linus
^ permalink raw reply
* Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes
From: Davide Libenzi @ 2006-10-16 18:18 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Jim Meyering, Git Mailing List
In-Reply-To: <Pine.LNX.4.64.0610161038200.3962@g5.osdl.org>
On Mon, 16 Oct 2006, Linus Torvalds wrote:
> On Mon, 16 Oct 2006, Jim Meyering wrote:
> >
> > That helps a little.
> > Now, instead of taking 63s, my test takes ~30s.
> > (32 for XDL_MAX_EQLIMIT = 16, 30 for XDL_MAX_EQLIMIT = 8)
>
> Btw, what architecture is this on?
>
> I'm testing those two files, and I get much more reasonable numbers with
> both ppc32 and x86. Both 32-bit:
>
> [torvalds@macmini test-perf]$ time git show | wc -l
> 25221
>
> real 0m1.437s
> user 0m1.436s
> sys 0m0.012s
>
> ie it generated the diff in less than a second and a half. Not wonderful,
> but certainly not your 63s either.
>
> HOWEVER. On x86-64, it takes forever (still not 63 seconds, but it takes
> 17 seconds on my 2GHz merom machine).
>
> So I think there's something seriously broken with hashing on 64-bit.
>
> And I think I know what it is.
>
> Try this patch. And make sure to do a "make clean" first, since I think
> the dependencies on xdiff may be broken.
>
> Davide: there's two things wrong with your old XDL_HASHLONG():
>
> - the GR_PRIME was just 32-bit, so it wouldn't shift low bits up far
> enough on a 64-bit architecture, so then shifting things down caused
> pretty much everything to be very small.
>
> - The whole idea of shifting up by multiplying and then shifting down to
> get the high bits is _broken_. Even on 32-bit architectures. Think
> about what happens when "hashbits" is 16 on a 32-bit architecture: the
> multiply moves the low bits _up_, but it doesn't move the high bits
> _down_. And with hashbits being a large fraction of the whole word, you
> need to shift things down, not up.
>
> So just making GR_PRIME be a bigger value on a 64-bit architecture would
> not have fixed it. The whole hash was simply broken. Do it the sane and
> obvious way instead: always pick the low bits, but mix in upper bits there
> too..
Yeah, using an appropriate golden ratio prime for 64 bits fixes it. I
think it's the best/minimal fix (use 0x9e37fffffffc0001UL, like the
kernel does).
I'm also looking into optimizing the multi-match discard loop, that
actually loses the classifier informations collected in the context
prepare phase.
- Davide
^ permalink raw reply
* Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes
From: Jim Meyering @ 2006-10-16 18:24 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Davide Libenzi, Git Mailing List
In-Reply-To: <Pine.LNX.4.64.0610161038200.3962@g5.osdl.org>
Linus Torvalds <torvalds@osdl.org> wrote:
> On Mon, 16 Oct 2006, Jim Meyering wrote:
>>
>> That helps a little.
>> Now, instead of taking 63s, my test takes ~30s.
>> (32 for XDL_MAX_EQLIMIT = 16, 30 for XDL_MAX_EQLIMIT = 8)
>
> Btw, what architecture is this on?
>
> I'm testing those two files, and I get much more reasonable numbers with
> both ppc32 and x86. Both 32-bit:
>
> [torvalds@macmini test-perf]$ time git show | wc -l
> 25221
>
> real 0m1.437s
> user 0m1.436s
> sys 0m0.012s
>
> ie it generated the diff in less than a second and a half. Not wonderful,
> but certainly not your 63s either.
>
> HOWEVER. On x86-64, it takes forever (still not 63 seconds, but it takes
> 17 seconds on my 2GHz merom machine).
>
> So I think there's something seriously broken with hashing on 64-bit.
amd_64 @ 2.0GHz
> Try this patch. And make sure to do a "make clean" first, since I think
> the dependencies on xdiff may be broken.
Yep. Dependencies are definitely broken.
Applied your patch. No improvement after a plain "make",
but doing "make clean && make" solved the problem.
Now, my diff-tree takes 2s (it's comparing other files, too).
Thank you!
IMHO, my "&& vs. ||" patch is still worth applying.
If not, then the existing code doesn't make sense, and
there can be significant simplification in the affected loops.
With my patch, I get an additional 3x speed-up: diff-tree takes 0.7s
^ permalink raw reply
* Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes
From: Davide Libenzi @ 2006-10-16 18:30 UTC (permalink / raw)
To: Jim Meyering; +Cc: Linus Torvalds, Git Mailing List
In-Reply-To: <873b9op19n.fsf@rho.meyering.net>
On Mon, 16 Oct 2006, Jim Meyering wrote:
> IMHO, my "&& vs. ||" patch is still worth applying.
> If not, then the existing code doesn't make sense, and
> there can be significant simplification in the affected loops.
> With my patch, I get an additional 3x speed-up: diff-tree takes 0.7s
No, the patch is broken. It will discard *any* line seen at least two
times, that is an extremely low threashold.
- Davide
^ permalink raw reply
* [RFH] git-svn documentation [was Re: git-svn and u-boot broken]
From: Eric Wong @ 2006-10-16 18:31 UTC (permalink / raw)
To: Joakim Tjernlund; +Cc: git
In-Reply-To: <453359A2.5090704@transmode.se>
Joakim Tjernlund <Joakim.Tjernlund@transmode.se> wrote:
> Eric Wong wrote:
> > I would do something like this:
> >
> > ... (same stuff as above before with svn setup...)
> > git clone $ORG_REPO $GIT_REPO
> > cd $GIT_REPO
> > git-svn init "$REPO"/trunk
> > git-svn fetch
> >
> > # sync the SVN repo with initial-uboot
> > # this will just commit a snapshot, without history, which I assume
> > # is what you want.
> > git-branch initial-uboot f5e0d03970409feb3c77ab0107d5dece6b7d45c9
> > git-svn commit initial-uboot
> > git checkout -b svn-branch remotes/git-svn
> > git-pull . tmcu2
> >
> > # this should work assuming the path from initial-uboot..tmcu2 is linear
> > # use gitk initial-uboot..tmcu2 to check
> > git-svn dcommit
>
> Great! This was exactly what I wanted, thanks. I never realized that one should
> do git-svn commit initial-uboot to get that single commit.
> I also replaced git-svn dcommit with git-svn commit remotes/git-svn..svn-branch
> as I don't have that version yet.
>
> You should add this as an example I think.
>
> Can I ask for an example that used multi-init and multi-fetch? I tried, but
> could not make it work.
git-svn multi-init https://svn.musicpd.org/mpd -T trunk -t tags -b branches
git-svn multi-fetch
In the latest git-svn (should be in 1.4.3), you can re-run 'git-svn
multi-init' with no arguments to discover new tags+branches.
Anybody willing to supply patches for better documentation? I'll be
quite busy with other projects the next two weeks, asciidoc is quite
slow for me; but I'd like to have better docs for git-svn in 1.4.3.
--
Eric Wong
^ permalink raw reply
* Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes
From: Davide Libenzi @ 2006-10-16 18:41 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Jim Meyering, Git Mailing List
In-Reply-To: <Pine.LNX.4.64.0610161100070.3962@g5.osdl.org>
On Mon, 16 Oct 2006, Linus Torvalds wrote:
> On Mon, 16 Oct 2006, Linus Torvalds wrote:
> >
> > So just making GR_PRIME be a bigger value on a 64-bit architecture would
> > not have fixed it.
>
> Side note: in _practice_ I think it would have fixed it. The "not mixing
> in high bits" is not a real problem if the original hash-value has a good
> distribution of bits, which I think we do have. So it's unclear whether we
> even need any mixing in of bits at all, and it's possible that it would be
> fine to just have
>
> #define XDL_HASHLONG(v,b) ((unsigned long)(v) & ((1ul << (b))-1))
>
> which is simpler than my patch.
>
> I prefer the mixing in of high bits just because it can help if the
> original hash was bad (or had a tendency to have patterns in the low bits,
> which could be the case). But I'm not sure xdiff actually needs it in this
> case.
ATM, I added AC_CHECK_SIZEOF(long) inside libxdiff's configure.in, and I
have (inside xmacros.h):
#if SIZEOF_LONG == 4
#define GR_PRIME 0x9e370001UL
#else
#define GR_PRIME 0x9e37fffffffc0001UL
#endif
I'm also looking into streamlining the discard loop to reuse information
collected during the context-setup phase ...
- Davide
^ permalink raw reply
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox