Re: Further diff optimization ideas

On 15.02.2011 01:42, Johan Corveleyn wrote:
> 2) Faster hash function for hashing lines. [ Quick win ]
>
> - Currently, we use adler32 (after the line has been normalized).
>
> - GNU diff uses some simple bit shifting scheme, which seems to be a
> lot faster (maybe it has more hash-collisions, but that doesn't seem
> to matter that much).

Is it (x << 5) + x? If so, that's the (in)famous "times 33" hash
function, also see the essay in apr_hashfunc_default in
http://svn.apache.org/viewvc/apr/apr/trunk/tables/apr_hash.c?view=markup

I prefer APR's implementation, because a reasonably good compiler these
days /should/ be able to optimize (x * 33) to ((x << 5) + x), depending
on the characteristics of the target architecture.

In other news, why do we need our own hash function anyway? Or our own
table or tree or whatever? NIH syndrome?

-- Brane
Received on 2011-02-15 09:56:12 CET