{"thread":{"id":"9617","subject":"Strange code in diff-delta.c","startedAt":"2007-08-23T00:59:01Z","lastAt":"2007-08-23T07:06:26Z","messageCount":4,"participants":["David Kastrup","Nicolas Pitre","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"51313","messageId":"85k5rnjcbu.fsf@lola.goethe.zz","threadId":"9617","inReplyTo":null,"subject":"Strange code in diff-delta.c","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2007-08-23T00:59:01Z","receivedAt":"2007-08-23T00:59:01Z","isPatch":false,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"\nI am currently looking what can be done to speed up deltaing. The\nfollowing code can be found here:\n\n\tfor (i = 0; i < hsize; i++) {\n\t\tif (hash_count[i] < HASH_LIMIT)\n\t\t\tcontinue;\n\t\tentry = hash[i];\n\t\tdo {\n\t\t\tstruct index_entry *keep = entry;\n\t\t\tint skip = hash_count[i] / HASH_LIMIT / 2;\n\t\t\tdo {\n\t\t\t\tentry = entry->next;\n\t\t\t} while(--skip && entry);\n\t\t\tkeep->next = entry;\n\t\t} while(entry);\n\t}\n\nIf I analyze what happens for various values of hash_count[i], I get\nthe following (the first case is by far the worst):\n\nHASH_LIMIT <= hash_count[i] < 2*HASH_LIMIT:\n skip = 0;\n do .. while terminates with negative skip and entry == 0, keep->next\n is set to 0 -> all hashes except the first one get dropped.\n Result is new_hash_count = 1. Ugh, ugh, ugh.\n\n2*HASH_LIMIT <= hash_count[i] < 4*HASH_LIMIT\n skip = 1;\n do .. while does one iteration, every second value is skipped,\n result is that HASH_LIMIT <= new_hash_count < 2*HASH_LIMIT\n\n4*HASH_LIMIT <= hash_limit[i] < 6*HASH_LIMIT\n skip = 2;\n do .. while does two iterations, two of three values are skipped,\n result is that 4*HASH_LIMIT/3 <= new_hash_count < 2*HASH_LIMIT\n\nAnd so on. It would appear that if HASH_LIMIT is supposed to do what\nit is seemingly intended for, the skip calculation has to be just\n\n\t\t\tint skip = hash_count[i] / HASH_LIMIT;\n\nOtherwise, there is completely broken behavior for values between\nHASH_LIMIT and 2*HASH_LIMIT (where only a single hash survives), and\nfor larger values, the limit will be 2*HASH_LIMIT rather than\nHASH_LIMIT as was probably intended.\n\n-- \nDavid Kastrup, Kriemhildstr. 15, 44793 Bochum\n"},{"id":"51318","messageId":"alpine.LFD.0.999.0708222126590.16727@xanadu.home","threadId":"9617","inReplyTo":"85k5rnjcbu.fsf@lola.goethe.zz","subject":"Re: Strange code in diff-delta.c","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-08-23T01:45:34Z","receivedAt":"2007-08-23T01:45:34Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 23 Aug 2007, David Kastrup wrote:\n\n> \n> I am currently looking what can be done to speed up deltaing. The\n> following code can be found here:\n> \n> \tfor (i = 0; i < hsize; i++) {\n> \t\tif (hash_count[i] < HASH_LIMIT)\n> \t\t\tcontinue;\n> \t\tentry = hash[i];\n> \t\tdo {\n> \t\t\tstruct index_entry *keep = entry;\n> \t\t\tint skip = hash_count[i] / HASH_LIMIT / 2;\n> \t\t\tdo {\n> \t\t\t\tentry = entry->next;\n> \t\t\t} while(--skip && entry);\n> \t\t\tkeep->next = entry;\n> \t\t} while(entry);\n> \t}\n> \n> If I analyze what happens for various values of hash_count[i], I get\n> the following (the first case is by far the worst):\n> \n> HASH_LIMIT <= hash_count[i] < 2*HASH_LIMIT:\n> skip = 0;\n> do .. while terminates with negative skip and entry == 0, keep->next\n> is set to 0 -> all hashes except the first one get dropped.\n> Result is new_hash_count = 1. Ugh, ugh, ugh.\n> \n> 2*HASH_LIMIT <= hash_count[i] < 4*HASH_LIMIT\n> skip = 1;\n> do .. while does one iteration, every second value is skipped,\n> result is that HASH_LIMIT <= new_hash_count < 2*HASH_LIMIT\n> \n> 4*HASH_LIMIT <= hash_limit[i] < 6*HASH_LIMIT\n> skip = 2;\n> do .. while does two iterations, two of three values are skipped,\n> result is that 4*HASH_LIMIT/3 <= new_hash_count < 2*HASH_LIMIT\n> \n> And so on. It would appear that if HASH_LIMIT is supposed to do what\n> it is seemingly intended for, the skip calculation has to be just\n> \n> \t\t\tint skip = hash_count[i] / HASH_LIMIT;\n> \n> Otherwise, there is completely broken behavior for values between\n> HASH_LIMIT and 2*HASH_LIMIT (where only a single hash survives), and\n> for larger values, the limit will be 2*HASH_LIMIT rather than\n> HASH_LIMIT as was probably intended.\n\nYou're absolutely right.\n\nI don't know what I was thinking when I wrote that code, but the /2 is \nbogus.\n\nPlease send a patch to Junio with my ACK.\n\n\nNicolas\n"},{"id":"51325","messageId":"85veb6iyry.fsf@lola.goethe.zz","threadId":"9617","inReplyTo":"alpine.LFD.0.999.0708222126590.16727@xanadu.home","subject":"[PATCH] diff-delta.c: Fix broken skip calculation.","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2007-08-23T05:51:45Z","receivedAt":"2007-08-23T05:51:45Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"A particularly bad case was HASH_LIMIT <= hash_count[i] < 2*HASH_LIMIT:\nin that case, only a single hash survived. For larger cases,\n2*HASH_LIMIT was the actual limiting value after pruning.\n\nAcked-by: Nicolas Pitre \nSigned-off-by: David Kastrup \n---\n diff-delta.c | 2 +-\n 1 files changed, 1 insertions(+), 1 deletions(-)\n\ndiff --git a/diff-delta.c b/diff-delta.c\nindex 3af5835..0dde2f2 100644\n--- a/diff-delta.c\n+++ b/diff-delta.c\n@@ -213,7 +213,7 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)\n \t\tentry = hash[i];\n \t\tdo {\n \t\t\tstruct index_entry *keep = entry;\n-\t\t\tint skip = hash_count[i] / HASH_LIMIT / 2;\n+\t\t\tint skip = hash_count[i] / HASH_LIMIT;\n \t\t\tdo {\n \t\t\t\tentry = entry->next;\n \t\t\t} while(--skip && entry);\n-- \n1.5.3.rc2.257.gd8a21\n"},{"id":"51335","messageId":"7vk5rmvifh.fsf@gitster.siamese.dyndns.org","threadId":"9617","inReplyTo":"alpine.LFD.0.999.0708222126590.16727@xanadu.home","subject":"Re: Strange code in diff-delta.c","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-08-23T07:06:26Z","receivedAt":"2007-08-23T07:06:26Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thanks, both.\n"}]}