* Strange code in diff-delta.c
@ 2007-08-23 0:59 David Kastrup
2007-08-23 1:45 ` Nicolas Pitre
0 siblings, 1 reply; 4+ messages in thread
From: David Kastrup @ 2007-08-23 0:59 UTC (permalink / raw
To: git
I am currently looking what can be done to speed up deltaing. The
following code can be found here:
for (i = 0; i < hsize; i++) {
if (hash_count[i] < HASH_LIMIT)
continue;
entry = hash[i];
do {
struct index_entry *keep = entry;
int skip = hash_count[i] / HASH_LIMIT / 2;
do {
entry = entry->next;
} while(--skip && entry);
keep->next = entry;
} while(entry);
}
If I analyze what happens for various values of hash_count[i], I get
the following (the first case is by far the worst):
HASH_LIMIT <= hash_count[i] < 2*HASH_LIMIT:
skip = 0;
do .. while terminates with negative skip and entry == 0, keep->next
is set to 0 -> all hashes except the first one get dropped.
Result is new_hash_count = 1. Ugh, ugh, ugh.
2*HASH_LIMIT <= hash_count[i] < 4*HASH_LIMIT
skip = 1;
do .. while does one iteration, every second value is skipped,
result is that HASH_LIMIT <= new_hash_count < 2*HASH_LIMIT
4*HASH_LIMIT <= hash_limit[i] < 6*HASH_LIMIT
skip = 2;
do .. while does two iterations, two of three values are skipped,
result is that 4*HASH_LIMIT/3 <= new_hash_count < 2*HASH_LIMIT
And so on. It would appear that if HASH_LIMIT is supposed to do what
it is seemingly intended for, the skip calculation has to be just
int skip = hash_count[i] / HASH_LIMIT;
Otherwise, there is completely broken behavior for values between
HASH_LIMIT and 2*HASH_LIMIT (where only a single hash survives), and
for larger values, the limit will be 2*HASH_LIMIT rather than
HASH_LIMIT as was probably intended.
--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: Strange code in diff-delta.c
2007-08-23 0:59 Strange code in diff-delta.c David Kastrup
@ 2007-08-23 1:45 ` Nicolas Pitre
2007-08-23 5:51 ` [PATCH] diff-delta.c: Fix broken skip calculation David Kastrup
2007-08-23 7:06 ` Strange code in diff-delta.c Junio C Hamano
0 siblings, 2 replies; 4+ messages in thread
From: Nicolas Pitre @ 2007-08-23 1:45 UTC (permalink / raw
To: David Kastrup; +Cc: git
On Thu, 23 Aug 2007, David Kastrup wrote:
>
> I am currently looking what can be done to speed up deltaing. The
> following code can be found here:
>
> for (i = 0; i < hsize; i++) {
> if (hash_count[i] < HASH_LIMIT)
> continue;
> entry = hash[i];
> do {
> struct index_entry *keep = entry;
> int skip = hash_count[i] / HASH_LIMIT / 2;
> do {
> entry = entry->next;
> } while(--skip && entry);
> keep->next = entry;
> } while(entry);
> }
>
> If I analyze what happens for various values of hash_count[i], I get
> the following (the first case is by far the worst):
>
> HASH_LIMIT <= hash_count[i] < 2*HASH_LIMIT:
> skip = 0;
> do .. while terminates with negative skip and entry == 0, keep->next
> is set to 0 -> all hashes except the first one get dropped.
> Result is new_hash_count = 1. Ugh, ugh, ugh.
>
> 2*HASH_LIMIT <= hash_count[i] < 4*HASH_LIMIT
> skip = 1;
> do .. while does one iteration, every second value is skipped,
> result is that HASH_LIMIT <= new_hash_count < 2*HASH_LIMIT
>
> 4*HASH_LIMIT <= hash_limit[i] < 6*HASH_LIMIT
> skip = 2;
> do .. while does two iterations, two of three values are skipped,
> result is that 4*HASH_LIMIT/3 <= new_hash_count < 2*HASH_LIMIT
>
> And so on. It would appear that if HASH_LIMIT is supposed to do what
> it is seemingly intended for, the skip calculation has to be just
>
> int skip = hash_count[i] / HASH_LIMIT;
>
> Otherwise, there is completely broken behavior for values between
> HASH_LIMIT and 2*HASH_LIMIT (where only a single hash survives), and
> for larger values, the limit will be 2*HASH_LIMIT rather than
> HASH_LIMIT as was probably intended.
You're absolutely right.
I don't know what I was thinking when I wrote that code, but the /2 is
bogus.
Please send a patch to Junio with my ACK.
Nicolas
^ permalink raw reply [flat|nested] 4+ messages in thread
* [PATCH] diff-delta.c: Fix broken skip calculation.
2007-08-23 1:45 ` Nicolas Pitre
@ 2007-08-23 5:51 ` David Kastrup
2007-08-23 7:06 ` Strange code in diff-delta.c Junio C Hamano
1 sibling, 0 replies; 4+ messages in thread
From: David Kastrup @ 2007-08-23 5:51 UTC (permalink / raw
To: git
A particularly bad case was HASH_LIMIT <= hash_count[i] < 2*HASH_LIMIT:
in that case, only a single hash survived. For larger cases,
2*HASH_LIMIT was the actual limiting value after pruning.
Acked-by: Nicolas Pitre <nico@cam.org>
Signed-off-by: David Kastrup <dak@gnu.org>
---
diff-delta.c | 2 +-
1 files changed, 1 insertions(+), 1 deletions(-)
diff --git a/diff-delta.c b/diff-delta.c
index 3af5835..0dde2f2 100644
--- a/diff-delta.c
+++ b/diff-delta.c
@@ -213,7 +213,7 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
entry = hash[i];
do {
struct index_entry *keep = entry;
- int skip = hash_count[i] / HASH_LIMIT / 2;
+ int skip = hash_count[i] / HASH_LIMIT;
do {
entry = entry->next;
} while(--skip && entry);
--
1.5.3.rc2.257.gd8a21
^ permalink raw reply related [flat|nested] 4+ messages in thread
* Re: Strange code in diff-delta.c
2007-08-23 1:45 ` Nicolas Pitre
2007-08-23 5:51 ` [PATCH] diff-delta.c: Fix broken skip calculation David Kastrup
@ 2007-08-23 7:06 ` Junio C Hamano
1 sibling, 0 replies; 4+ messages in thread
From: Junio C Hamano @ 2007-08-23 7:06 UTC (permalink / raw
To: Nicolas Pitre; +Cc: David Kastrup, git
Thanks, both.
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2007-08-23 7:06 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2007-08-23 0:59 Strange code in diff-delta.c David Kastrup
2007-08-23 1:45 ` Nicolas Pitre
2007-08-23 5:51 ` [PATCH] diff-delta.c: Fix broken skip calculation David Kastrup
2007-08-23 7:06 ` Strange code in diff-delta.c Junio C Hamano
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
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 read-only IMAP folder(s) and NNTP newsgroup(s).