Re: svn commit: r1495204 - /subversion/trunk/subversion/libsvn_fs_fs/tree.c

[Blair Zajac <bl...@orcaware.com>]

On 06/20/2013 02:40 PM, stefan2@apache.org wrote:
> Author: stefan2
> Date: Thu Jun 20 21:40:50 2013
> New Revision: 1495204
>
> URL: http://svn.apache.org/r1495204
> Log:
> Follow-up to r1495063: integer overflows result in an inefficient hash
> function and reduce cache effectiveness.
>
> * subversion/libsvn_fs_fs/tree.c
>    (cache_lookup): prevent unnecessary integer overflows in hash function

Hi Stefan,

I've been reading up on hash functions and am curious about this how 
overflow can reduce cache effectiveness.  Do you have any links or can 
offer an explanation?

Thanks,
Blair

Re: svn commit: r1495204 - /subversion/trunk/subversion/libsvn_fs_fs/tree.c

[Stefan Fuhrmann <st...@wandisco.com>]

On Thu, Jun 20, 2013 at 11:43 PM, Blair Zajac <bl...@orcaware.com> wrote:

> On 06/20/2013 02:40 PM, stefan2@apache.org wrote:
>
>> Author: stefan2
>> Date: Thu Jun 20 21:40:50 2013
>> New Revision: 1495204
>>
>> URL: http://svn.apache.org/r1495204
>> Log:
>> Follow-up to r1495063: integer overflows result in an inefficient hash
>> function and reduce cache effectiveness.
>>
>> * subversion/libsvn_fs_fs/tree.c
>>    (cache_lookup): prevent unnecessary integer overflows in hash function
>>
>
> Hi Stefan,
>
> I've been reading up on hash functions and am curious about this how
> overflow can reduce cache effectiveness.  Do you have any links or can
> offer an explanation?
>
>
This illustrates what happened before the patch:

char c = 99;
unsigned hash = 0;
hash |= c << 8; /* c << 8 is often 0, actually it's undefined */

On a more general note, you don't want to make
it easy for parts of the input to cancel each other out.
So, adding (potentially) negative values is a bad thing
(strategically).

-- Stefan^2.