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
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html