Subject: Re: General purpose hashing func in pgbench
To: Fabien COELHO <coelho@cri.ensmp.fr>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
References: <0e8bd39e-dfcd-2879-f88f-272799ad7ef2@postgrespro.ru>
 <alpine.DEB.2.20.1712200807550.5165@lancre>
 <699225ee-c30c-b22e-4028-415e9eab26b2@postgrespro.ru>
 <alpine.DEB.2.20.1712211620040.32625@lancre>
 <80e9c570-5c49-1a01-f309-3d8d0cbbae42@postgrespro.ru>
 <alpine.DEB.2.20.1712240846440.22976@lancre>
From: Ildar Musin <i.musin@postgrespro.ru>
Message-ID: <38f1503e-7b63-4612-24a9-041af25bb022@postgrespro.ru>
Date: Mon, 25 Dec 2017 16:24:38 +0300
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.12; rv:52.0)
 Gecko/20100101 Thunderbird/52.5.0
MIME-Version: 1.0
In-Reply-To: <alpine.DEB.2.20.1712240846440.22976@lancre>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Content-Language: ru
Precedence: bulk

Hello Fabien,


24/12/2017 11:12, Fabien COELHO пишет:
>
> Yep. The ugliness is significantly linked to the choice of name. With
> MM2_MUL and MM2_ROT ISTM that it is more readable:
>
>>     k *= MM2_MUL;
>>     k ^= k >> MM2_ROT;
>>     k *= MM2_MUL;
>>     result ^= k;
>>     result *= MM2_MUL;
Ok, will do.
>
>> [...] So I'd better leave it the way it is. Actually I was thinking
>> to do the same to fnv1a too : )
>
> I think that the implementation style should be homogeneous, so I'd
> suggest at least to stick to one style.
>
> I noticed from the source of all human knowledege (aka Wikipedia:-)
> that there seems to be a murmur3 successor. Have you considered it?
> One good reason to skip it would be that the implementation is long
> and complex. I'm not sure about a 8-byte input simplified version.
Murmur2 naturally supports 8-byte data. Murmur3 has 32- and 128-bit
versions. So to handle int64 I could
1) split input value into two halfs and combine somehow the results of
32 bit version or
2) use 128-bit version and discard higher bytes.

Btw, postgres core already has a 32bit murmur3 implementation, but it
only uses the finalization part of algorithm (see murmurhash32). As my
colleague Yura Sokolov told me in a recent conversation it alone
provides pretty good randomization. I haven't tried it yet though.

>
> Just a question: Have you looked at SipHash24?
>
>     https://en.wikipedia.org/wiki/SipHash
>
> The interesting point is that it can use a key and seems somehow
> cryptographically secure, for a similar cost. However the how to
> decide for/control the key is unclear.
>
Not yet. As I can understand from the wiki its main feature is to
prevent attacks with crafted input data. How can it be useful in
benchmarking? Unless it shows superior performance and randomization.

-- 
Ildar Musin
Postgres Professional: http://www.postgrespro.com
Russian Postgres Company