Re: Distribution of longest common hash prefixes

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Apr 2, 2007, 17:00 UTC
Message-ID: <Pine.LNX.4.64.0704020938470.6730@woody.linux-foundation.org>
In-Reply-To: <86bqi6kae7.fsf@blue.stonehenge.com>

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

Show 22 quoted lines

> 
> 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