# Strange code in diff-delta.c 4 messages from 2007-08-23 to 2007-08-23. Participants: David Kastrup, Nicolas Pitre, Junio C Hamano. Thread: https://gitlist.dev/t/9617 ## David Kastrup, 2007-08-23 00:59 Subject: Strange code in diff-delta.c Message-ID: <85k5rnjcbu.fsf@lola.goethe.zz> URL: https://gitlist.dev/e/85k5rnjcbu.fsf%40lola.goethe.zz ``` 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, 2007-08-23 01:45 Subject: Re: Strange code in diff-delta.c Message-ID: URL: https://gitlist.dev/e/alpine.LFD.0.999.0708222126590.16727%40xanadu.home In-Reply-To: <85k5rnjcbu.fsf@lola.goethe.zz> ``` 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 ``` ## David Kastrup, 2007-08-23 05:51 Subject: [PATCH] diff-delta.c: Fix broken skip calculation. Message-ID: <85veb6iyry.fsf@lola.goethe.zz> URL: https://gitlist.dev/e/85veb6iyry.fsf%40lola.goethe.zz In-Reply-To: ``` 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 Signed-off-by: David Kastrup --- 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 ``` ## Junio C Hamano, 2007-08-23 07:06 Subject: Re: Strange code in diff-delta.c Message-ID: <7vk5rmvifh.fsf@gitster.siamese.dyndns.org> URL: https://gitlist.dev/e/7vk5rmvifh.fsf%40gitster.siamese.dyndns.org In-Reply-To: ``` Thanks, both. ```