Re: Distribution of longest common hash prefixes

quoted

quoted

quoted

quoted

"Linus" == Linus Torvalds [off-list ref] writes:

Linus> On Mon, 2 Apr 2007, Peter Eriksen wrote:

Linus> #include <stdio.h>
Linus> #include <string.h>


Linus> int h2d(char c)
Linus> {
Linus> 	if ('a' <= c && c <= 'f')
Linus> 		return c-'a'+10;
Linus> 	else
Linus> 		return c-'0';
Linus> }

Linus> int lcprefix(char *a, char *b)
Linus> {
Linus> 	int bits = 0;
Linus> 	unsigned n1, n2;

Linus> 	while (*a == *b) {
Linus> 		bits += 4;
Linus> 		a++;
Linus> 		b++;
Linus> 	}

Linus> 	n1 = h2d(*a);
Linus> 	n2 = h2d(*b);

Linus> 	/* Would make more sense to start from bit 0.. */
Linus> 	while ((n1 & 8) == (n2 & 8)) {
Linus> 		bits++;
Linus> 		n1 <<= 1;
Linus> 		n2 <<= 1;
Linus> 	}
	
Linus> 	return bits;
Linus> }

Linus> int main(int argc, char **argv)
Linus> {
Linus> 	FILE *fp;
Linus> 	char old[41];
Linus> 	char cur[41];
Linus> 	int lcp = 0;
Linus> 	int table[64];
Linus> 	int i;

Linus> 	memset(table, 0, 64*sizeof(int));
Linus> 	memset(old, '0', 40);
Linus> 	old[40] = '\0';

Linus> 	fp = fopen(argv[1], "r");
Linus> 	fscanf(fp, "%s\n", cur);

Linus> 	if (lcp < lcprefix(old, cur)) {
Linus> 		lcp = lcprefix(old, cur);
Linus> 	}

Linus> 	table[lcp]++;
Linus> 	while (fscanf(fp, "%s\n", cur) != EOF) {
Linus> 		int newlcp = lcprefix(old, cur);
Linus> 		table[newlcp]++;
Linus> 		if (lcp < newlcp) {
Linus> 			printf("%s\n%s\n", old, cur);
Linus> 			lcp = newlcp;
Linus> 			printf("lcprefix = %d\n", newlcp);
Linus> 		}
Linus> 		memcpy(old, cur, 40);
Linus> 	}

Linus> 	for(i = 0; i < 64; i++) {
Linus> 		printf("%2d: %2d\n", i, table[i]);
Linus> 	}
	
Linus> 	return 0;
Linus> }

I don't have access to the linux-2.6 kernel, but on git.git at
d8b6a1a10b93666246984a50d64a163e71163aeb I get this:

    $ git-rev-list --objects HEAD | sort | perl -lne '
      substr($_, 40) = "";
      ($p ^ $_) =~ /^(\0*)/;
      $count[length $1]++;
      $p = $_;
      END { print "$_: $count[$_]" for 0..$#count }
    '
    0: 16
    1: 240
    2: 3839
    3: 24458
    4: 8275
    5: 619
    6: 45
    7: 
    8: 1

Yeay Perl. :)

-- 
Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095
[off-list ref] <URL:http://www.stonehenge.com/merlyn/>
Perl/Unix/security consulting, Technical writing, Comedy, etc. etc.
See PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training!

On Mon, 2 Apr 2007, Randal L. Schwartz wrote:

I don't have access to the linux-2.6 kernel, but on git.git at
d8b6a1a10b93666246984a50d64a163e71163aeb I get this:

    $ git-rev-list --objects HEAD | sort | perl -lne '
      substr($_, 40) = "";
      ($p ^ $_) =~ /^(\0*)/;
      $count[length $1]++;
      $p = $_;
      END { print "$_: $count[$_]" for 0..$#count }
    '
    0: 16
    1: 240
    2: 3839
    3: 24458
    4: 8275
    5: 619
    6: 45
    7: 
    8: 1

Yeay Perl. :)

No yay yet.. That counts hex digits, not bits.

However, both this and Peter's original thing show an interesting pattern 
in common: for the case where the data is dense (ie a few bits in common), 
you actually don't end up counting "bits in common", but "edges when the 
bits change in the sorted output".

For example, in the above, the 16/240/3839 comes simply from the fact that 
there are sixteen times that the first digit changes (and that makes the 
program think that it has zero bits in common). There are 256 times that 
the two first digit changes, but 16 of those the first one changed too, so 
only in 240 cases did just the second digit change).

And there are 4096 places where the three first digit change, but 256 of 
those were already counted, so you get 3840 for the third case (but the 
git repo didn't have enough objects, so you missed one, and then the next 
ones will hit a peak and then start an exponential decrease.

So with a nice random linear distribution (which we'd expect from a good 
hash), you should see an exponential increase to a maximum (which you'd 
expect to be at "floor(lnx(nr-objects))", and then an exponential decrease 
right back.

With the kernel, with 439342 objects reachable from HEAD, the peak should 
be around 4 (for a base-16 thing) and around 18 for the binary thing. 
Which is exactly what you get..

		Linus

--- for the kernel, using your nybble-counter ---

0: 16
1: 240
2: 3840
3: 61357
4: 293375
5: 74775
6: 5372
7: 350
8: 16
9: 1