From: Ildar Musin <i.musin@postgrespro.ru>
To: Fabien COELHO <coelho@cri.ensmp.fr>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Subject: Re: General purpose hashing func in pgbench
Date: Thu, 21 Dec 2017 14:38:14 +0300
Message-ID: <699225ee-c30c-b22e-4028-415e9eab26b2@postgrespro.ru> (raw)
In-Reply-To: <alpine.DEB.2.20.1712200807550.5165@lancre>
References: <0e8bd39e-dfcd-2879-f88f-272799ad7ef2@postgrespro.ru>
<alpine.DEB.2.20.1712200807550.5165@lancre>
Hello Fabien,
20/12/2017 10:36, Fabien COELHO пишет:
> As there may be several hash functions included in the long run. I'd
> suggest that the hash function should be named more precisely, eg
> "hash_fnv1a".
Done. Added "hash_murmur2" too, see below.
> The image looks like the distribution is more regularly scattered than
> actually randomized... Maybe this is because the first highest 256
> values are really scattered by the process multiply/modulo process. Or
> maybe this is an optical effect?
>
After your comment I searched the internet for different hashing
algorithms comparison wrt randomness and found an interesting post at
stackexchange [1]. According to author's research the murmur2 algorithm
has the best randomness rate (among those he tested). So I implemented
it (using original code by Austin Appleby as a reference [2]) and
conducted few experiments. Results are in attachement. Indeed, comparing
to murmur2 the FNV distribution seems pretty regular.
> ISTM that there are undesired utf8 chars in a comment. Should be kept
> ASCII.
Oops, I copy-pasted the algorithm name from wikipedia, didn't notice
there were some fancy unicode hyphens.
> I would put the actual hash computation in a separate function rather
> than inlined in the evaluator.
Done.
> Add the submission to the next CF?
I think it is not commitfest ready yet -- I need to add some
documentation and tests first.
[1]
https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-un...
[2] https://github.com/aappleby/smhasher/blob/master/src/MurmurHash2.cpp
--
Ildar Musin
Postgres Professional:
http://www.postgrespro.com
Russian Postgres Company
Attachments:pgbench_hash_v2.patch (text/plain, 2.5K) downloaddiff --git a/src/bin/pgbench/exprparse.y b/src/bin/pgbench/exprparse.yindex 25d5ad4..9cb47f0 100644--- a/src/bin/pgbench/exprparse.y+++ b/src/bin/pgbench/exprparse.y@@ -194,6 +194,12 @@ static const struct
{
"random_zipfian", 3, PGBENCH_RANDOM_ZIPFIAN
},
+ {+ "hash_fnv1a", 1, PGBENCH_HASH_FNV1A+ },+ {+ "hash_murmur2", 1, PGBENCH_HASH_MURMUR2+ },
/* keep as last array element */
{
NULL, 0, 0
diff --git a/src/bin/pgbench/pgbench.c b/src/bin/pgbench/pgbench.cindex 7ce6f60..0a32fac 100644--- a/src/bin/pgbench/pgbench.c+++ b/src/bin/pgbench/pgbench.c@@ -61,6 +61,12 @@
#define ERRCODE_UNDEFINED_TABLE "42P01"
/*
+ * Hashing constants+ */+#define FNV_PRIME 1099511628211+#define FNV_OFFSET_BASIS 0xcbf29ce484222325++/*
* Multi-platform pthread implementations
*/
@@ -912,6 +918,50 @@ getZipfianRand(TState *thread, int64 min, int64 max, double s)
}
/*
+ * FNV-1a hash function+ */+static int64+getHashFnv1a(int64 val)+{+ int64 result;+ int i;++ result = FNV_OFFSET_BASIS;+ for (i = 0; i < 8; ++i)+ {+ int32 octet = val & 0xff;++ val = val >> 8;+ result = result ^ octet;+ result = result * FNV_PRIME;+ }++ return result;+}++static int64+getHashMurmur2(int64 val)+{+ const uint64 m = 0xc6a4a7935bd1e995;+ const int r = 47;+ uint64 result = val ^ (sizeof(int64) * m);+ uint64 k = (uint64) val;++ k *= m;+ k ^= k >> r;+ k *= m;++ result ^= k;+ result *= m;++ result ^= result >> r;+ result *= m;+ result ^= result >> r;++ return (int64) result;+}++/*
* Initialize the given SimpleStats struct to all zeroes
*/
static void
@@ -1850,6 +1900,22 @@ evalFunc(TState *thread, CState *st,
return true;
}
+ /* hashing */+ case PGBENCH_HASH_FNV1A:+ case PGBENCH_HASH_MURMUR2:+ {+ int64 val;+ int64 result;++ if (!coerceToInt(&vargs[0], &val))+ return false;++ result = (func == PGBENCH_HASH_FNV1A) ?+ getHashFnv1a(val) : getHashMurmur2(val);+ setIntValue(retval, result);+ return true;+ }+
default:
/* cannot get here */
Assert(0);
diff --git a/src/bin/pgbench/pgbench.h b/src/bin/pgbench/pgbench.hindex 83fee1a..d00b195 100644--- a/src/bin/pgbench/pgbench.h+++ b/src/bin/pgbench/pgbench.h@@ -76,7 +76,9 @@ typedef enum PgBenchFunction
PGBENCH_RANDOM,
PGBENCH_RANDOM_GAUSSIAN,
PGBENCH_RANDOM_EXPONENTIAL,
- PGBENCH_RANDOM_ZIPFIAN+ PGBENCH_RANDOM_ZIPFIAN,+ PGBENCH_HASH_FNV1A,+ PGBENCH_HASH_MURMUR2
} PgBenchFunction;
typedef struct PgBenchExpr PgBenchExpr;
fnv_vs_murmur2_2K.png (image/png, 473.1K) downloadview imagefnv_vs_murmur2_500.png (image/png, 627.9K) downloadview image
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: i.musin@postgrespro.ru, coelho@cri.ensmp.fr
Subject: Re: General purpose hashing func in pgbench
In-Reply-To: <699225ee-c30c-b22e-4028-415e9eab26b2@postgrespro.ru>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox