Re: Distribution of longest common hash prefixes

[Linus Torvalds <torvalds@linux-foundation.org>]

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