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

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

> On 06/20/2013 02:40 PM, stefan2_at_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.
Received on 2013-06-21 00:42:12 CEST