Re: I'm a total push-over..

From: Marko Kreen <markokr@gmail.com>
Date: Jan 25, 2008, 20:52 UTC
Message-ID: <e51f66da0801251252r1950c2d5g12caa5e71b9a37a@mail.gmail.com>
In-Reply-To: <alpine.LFD.1.00.0801240839590.2803@woody.linux-foundation.org>

On 1/24/08, Linus Torvalds <torvalds@linux-foundation.org> wrote:

Show 10 quoted lines

> You can do a perfectly fine 8-bytes-at-a-time hash for almost 100% of all
> source code projects in UTF-8, without *ever* doing any format changes at
> all. Admittedly, it's a lot easier if the hash is a pure in-memory one (ie
> we don't care about byte-order or size of integers or anything like that),
> but that's the common case for most hashes that aren't used for BTree
> lookup on disk or something like that.
>
> Here, let me show you:
>
>         unsigned int name_hash(const char *name, int size)

Well, although this is very clever approach, I suggest against it. You'll end up with complex code that gives out substandard results.

I think its better to have separate case-folding function (or several), that copies string to temp buffer and then run proper optimized hash function on that buffer.

That way you can use already tested building blocks and can optimize both sides separately. Eg. the folding-only function can aswell be optimized to load 4 or 8-byte at-a-time. This also isolates hashing from exact details how folding happens to access the input string which seem to be the weak point in your approach. (In both collision and complexity sense.)

Such temp buffer happens to fits my lookup3_memcpy also better (heh). Its weak point is that on platforms that do not allow unaligned access, it degenerates to byte-by-byte loading. But if know you always have aligned buffer, you can notify gcc to do 4-byte fetch there too. It should be as simple as tagging data pointer as uint32_t *.

Anyway, now you dont need to worry about folding when picking hash.

> Basically, it's almost always a stupid thing to actually normalize a whole
> string. You do those things character-by-character, and only lazily when
> you actually need to!

If your input strings are over kilobyte on average then I'd agree with you, but if you process 20-30 bytes on average, is the additional complexity worth it?

-- 
marko