From: Linus Torvalds <torvalds@osdl.org>
To: Jim Meyering <jim@meyering.net>
Cc: Davide Libenzi <davidel@xmailserver.org>,
Git Mailing List <git@vger.kernel.org>
Subject: Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes
Date: Mon, 16 Oct 2006 11:03:41 -0700 (PDT) [thread overview]
Message-ID: <Pine.LNX.4.64.0610161100070.3962@g5.osdl.org> (raw)
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
next prev parent reply other threads:[~2006-10-16 18:03 UTC|newest]
Thread overview: 27+ messages / expand[flat|nested] mbox.gz Atom feed top
2006-10-16 14:12 git-diff-tree inordinately (O(M*N)) slow on files with many changes Jim Meyering
2006-10-16 15:47 ` Linus Torvalds
2006-10-16 16:12 ` Linus Torvalds
2006-10-16 16:33 ` Jim Meyering
2006-10-16 16:42 ` Davide Libenzi
2006-10-16 16:50 ` Jim Meyering
2006-10-16 16:54 ` Davide Libenzi
2006-10-16 16:57 ` Jim Meyering
2006-10-16 17:02 ` Davide Libenzi
2006-10-16 17:56 ` Linus Torvalds
2006-10-16 18:03 ` Linus Torvalds [this message]
2006-10-16 18:41 ` Davide Libenzi
2006-10-16 18:18 ` Davide Libenzi
2006-10-16 18:51 ` Linus Torvalds
2006-10-16 19:44 ` Davide Libenzi
2006-10-16 20:29 ` Jakub Narebski
2006-10-16 22:53 ` Junio C Hamano
2006-10-16 23:24 ` Linus Torvalds
2006-10-16 23:52 ` Davide Libenzi
2006-10-16 18:24 ` Jim Meyering
2006-10-16 18:30 ` Davide Libenzi
2006-10-16 18:43 ` Jim Meyering
2006-10-16 16:54 ` Linus Torvalds
2006-10-16 16:36 ` Davide Libenzi
2006-10-16 16:57 ` Linus Torvalds
2006-10-16 16:24 ` Davide Libenzi
2006-10-16 16:54 ` Jakub Narebski
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=Pine.LNX.4.64.0610161100070.3962@g5.osdl.org \
--to=torvalds@osdl.org \
--cc=davidel@xmailserver.org \
--cc=git@vger.kernel.org \
--cc=jim@meyering.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).