threads / discuss / 9617

Strange code in diff-delta.c

Subject: Strange code in diff-delta.c

## tl;dr

4 messages between Aug 23, 2007 and Aug 23, 2007.

replies: 3people: 3as markdown or json

David Kastrup· Aug 23, 2007, 00:59 UTC · lore

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
Nicolas Pitre· Aug 23, 2007, 01:45 UTC · re: David Kastrup · lore

Re: Strange code in diff-delta.c

On Thu, 23 Aug 2007, David Kastrup wrote:
Show 46 quoted lines
> 
> 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
David Kastrup· Aug 23, 2007, 05:51 UTC · re: Nicolas Pitre · lore

[PATCH] diff-delta.c: Fix broken skip calculation.

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

← back to recent threads