git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Strange code in diff-delta.c

From
David Kastrup <dak@gnu.org>
Date
Aug 23, 2007, 00:59 UTC
Message-ID
<85k5rnjcbu.fsf@lola.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
Next: Nicolas Pitre
Message 1 of 4 in “Strange code in diff-delta.c”
  1. David KastrupAug 23, 2007
  2. Nicolas PitreAug 23, 2007
  3. diff-delta.c: Fix broken skip calculation.David Kastrup, Aug 23, 2007
  4. Junio C HamanoAug 23, 2007

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.