Re: Libgit2 on the Summer of Code

[Vicent Marti <tanoku@gmail.com>]

Hey again,

thanks for the bites, Ilari. I've fixed all the formatting issues in
the latest batch of commits [1], and improved the error handling quite
a bit.

Regarding the hashing of OIDs, it's not a random hash, it's an
adaptation of MurmurHash [2], which is made of win -- specially when
it comes to dispersing stuff on hash tables. You are right however
that SHA1 raw bytes are already random enough, and probably not worth
the performance hit of hashing again on top of it -- I've dropped it
for the time being.

More work tomorrow,

Cheers,
Vicent Martí
http://www.bellverde.org

[1]: http://github.com/tanoku/libgit2-gsoc2010/commits/master
[2]: http://sites.google.com/site/murmurhash/

On Thu, May 27, 2010 at 8:35 PM, Ilari Liusvaara
<ilari.liusvaara@elisanet.fi> wrote:
> On Thu, May 27, 2010 at 11:05:54AM -0700, Shawn O. Pearce wrote:
>> Ilari Liusvaara <ilari.liusvaara@elisanet.fi> wrote:
>> > * Where algorithm in git_revpool_table__hash() is from? Since it appears to
>> > hash binary object IDs, wouldn't just simple sum/xor over words be sufficient
>> > (all SHA-1 output bits are very nearly independent). Or do you need to be
>> > compatible with some other implementation (doesn't appear so, because hash
>> > is computed differently depending on endianess)?
>>
>> If you need a hash value for a SHA-1, why not just cast the unsigned
>> char* to unsigned int* and load the first int as the hash code?
>> The output of SHA-1 is pretty evenly distributed, using the first
>> few bytes as an int should yield a sufficient distribution throughout
>> the hashtable.
>
> Yeah, With pseudorandom function[*], all ways of reducing the output to n bits are
> at most as good as just taking first n bits. But if reducing output to [0, m),
> the best way (distribution-wise, not speed-wise) is to take remainder of the whole
> value divided by m...
>
> [*] SHA-1 is not pseudorandom function, but for virtually all practical purposes
> it is.
>
> -Ilari
>