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

From: Marko Kreen <markokr@gmail.com>
Date: Jan 24, 2008, 16:13 UTC
Message-ID: <e51f66da0801240813v61d3bc74x2863eb37678439db@mail.gmail.com>
In-Reply-To: <4798B633.8040606@op5.se>

On 1/24/08, Andreas Ericsson <ae@op5.se> wrote:

Show 15 quoted lines

> Marko Kreen wrote:
> > On 1/23/08, Andreas Ericsson <ae@op5.se> wrote:
> >> Marko Kreen wrote:
> >>> (not lookup3) because lookup3 beat easily all the "simple" hashes
> >> By how much? FNV beat Linus' hash by 0.01 microseconds / insertion,
> >> and 0.1 microsecons / lookup. We're talking about a case here where
> >> there will never be more lookups than insertions (unless I'm much
> >> mistaken).
> >
> > FNV is around 40% slower than lookup3 on my Intel Core CPU, on 4byte aligned
> > input. See below for more detailed info.
> >
>
> But the tests surely need to check for unaligned cases, as that's what
> we're likely to hash, no?

Show 12 quoted lines

> >> It would have to be a significant improvement in wall-clock time
> >> on a test-case of hashing 30k strings to warrant going from 6 to 80
> >> lines of code, imo. I still believe the original dumb hash Linus
> >> wrote is "good enough".
> >
> > Well, ad-hoc dumb hashes may have horrible worst-cases that you cant
> > see with light testing.  Therefore I'd still suggest some better
> > researched dumb hash (eg. FNV or OAT).
> >
>
> True. FNV is used in both MySQL and PostgreSQL. I'd say it's safe to
> assume it's fairly well tested.

PostgreSQL uses lookup2...

Show 10 quoted lines

> > Here is my raw-speed test of different hashes.  Input is 4-byte
> > aligned which should be common case for malloc()-ed strings.
>
> Unless arena allocated, like we do in git.
>
> I'm not surprised that this test favours Jenkin's and Hsie's.
> That's to be expected as those benefit far more than simpler
> hashing algorithms for long strings. The overhead when trying
> shorter strings (say, between 3 and 15 chars, and not necessarily
> 4-byte aligned) sometimes make them quite a lot slower though.

Ok, here is 0..15 chars, random alignment:

Testing: seed=34 align=0 minlen=0 maxlen=15 trycnt=2 duration=10

lookup3 : try=0: ... 69.8092 MB/s lookup3 : try=1: ... 69.8146 MB/s own_memcpy: try=0: ... 66.7808 MB/s own_memcpy: try=1: ... 66.7814 MB/s memcpy_hack: try=0: ... 74.0635 MB/s memcpy_hack: try=1: ... 74.0518 MB/s lookup2 : try=0: ... 68.6582 MB/s lookup2 : try=1: ... 68.6634 MB/s fnv : try=0: ... 74.5098 MB/s fnv : try=1: ... 74.5283 MB/s hsieh : try=0: ... 71.6708 MB/s hsieh : try=1: ... 71.6814 MB/s oat : try=0: ... 74.7828 MB/s oat : try=1: ... 74.7716 MB/s elf : try=0: ... 65.2077 MB/s elf : try=1: ... 65.2128 MB/s

Results compared to reference:

lookup3 : 100.000 % own_memcpy : 95.659 % memcpy_hack : 106.082 % lookup2 : 98.351 % fnv : 106.743 % hsieh : 102.670 % oat : 107.112 % elf : 93.409 %

Show 10 quoted lines

> > This also is best case for original lookup3(), on unaligned
> > input the memcpy variants beat it easily.  Input string
> > length varies randomly in range 0..64.
> >
>
> Well, memcpy() isn't very interesting to compare against
> hashes, as they test vastly different parts of the hardware's
> parts' performance. memcpy() should also perform exactly the
> same no matter what the test-data, which isn't always true for
> hashes.

Sorry, I meant my "simple-memcpy-based-lookup3".

> What *would* be interesting would be something along the lines
> of "duff_cpy()": ie, an unrolled loop that aligns itself and
> copies each byte to the same address each time.

How the hash fetched data from mempry is _very_ relevant.

> Interesting output, but not very surprising. Do you have the code
> available somewhere?

I can put it out.

-- 
marko