Changeset: 2793dd623e23 for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB/rev/2793dd623e23
Branch: pp_hashjoin
Log Message:
merged
diffs (truncated from 432 to 300 lines):
diff --git a/gdk/CMakeLists.txt b/gdk/CMakeLists.txt
--- a/gdk/CMakeLists.txt
+++ b/gdk/CMakeLists.txt
@@ -90,7 +90,6 @@ target_sources(bat
gdk_tracer.c gdk_tracer.h
gdk_rtree.c
gdk_strimps.c
- murmurhash3.h
gdk_sketch.c
PUBLIC
${gdk_public_headers})
diff --git a/gdk/gdk_sketch.c b/gdk/gdk_sketch.c
--- a/gdk/gdk_sketch.c
+++ b/gdk/gdk_sketch.c
@@ -9,14 +9,10 @@
*/
#include "gdk.h"
-
+#include "xxhash.h"
#if defined(HAVE_GETENTROPY) && defined(HAVE_SYS_RANDOM_H)
#include <sys/random.h>
#endif
-// #include "murmurhash3.h"
-#define XXH_STATIC_LINKING_ONLY
-#define XXH_IMPLEMENTATION
-#include "xxhash.h"
// Helper function sigma as defined in
// "New cardinality estimation algorithms for HyperLogLog sketches"
@@ -58,10 +54,10 @@ tau(double x)
return z / 3;
}
-/// Estimator as defined in
-/// "New cardinality estimation algorithms for HyperLogLog sketches"
-/// Otmar Ertl, arXiv:1702.01284.
-/// Only difference is how the multiplicity array is computed
+// Estimator as defined in
+// "New cardinality estimation algorithms for HyperLogLog sketches"
+// Otmar Ertl, arXiv:1702.01284.
+// Only difference is how the multiplicity array is computed
double
sketch_estimate(uint8_t cnt_sketch[BUCKETS][CLZ_BUCKETS])
{
@@ -149,7 +145,6 @@ leading_zeroes(uint64_t x)
#define SKETCH_POPULATE(TYPE) \
do { \
oid hseq = b->hseqbase; \
- /* uint64_t murmur3_out[2]; */ \
uint64_t hash; \
uint8_t bucket; \
uint8_t clz; \
diff --git a/gdk/murmurhash3.h b/gdk/murmurhash3.h
deleted file mode 100644
--- a/gdk/murmurhash3.h
+++ /dev/null
@@ -1,374 +0,0 @@
-//-----------------------------------------------------------------------------
-// MurmurHash3 was written by Austin Appleby, and is placed in the public
-// domain. The author hereby disclaims copyright to this source code.
-
-// Note - The x86 and x64 versions do _not_ produce the same results, as the
-// algorithms are optimized for their respective platforms. You can still
-// compile and run any of them on any platform, but your performance with the
-// non-native version will be less than optimal.
-
-#ifndef _MURMURHASH3_H_
-#define _MURMURHASH3_H_
-
-//-----------------------------------------------------------------------------
-// Platform-specific functions and macros
-
-// Microsoft Visual Studio
-
-#if defined(_MSC_VER) && (_MSC_VER < 1600)
-
-typedef unsigned char uint8_t;
-typedef unsigned int uint32_t;
-typedef unsigned __int64 uint64_t;
-
-// Other compilers
-
-#else // defined(_MSC_VER)
-
-#include <stdint.h>
-
-#endif // !defined(_MSC_VER)
-
-//-----------------------------------------------------------------------------
-
-void MurmurHash3_x86_32 ( const void * key, int len, uint32_t seed, void *
out );
-
-void MurmurHash3_x86_128 ( const void * key, int len, uint32_t seed, void *
out );
-
-void MurmurHash3_x64_128 ( const void * key, int len, uint32_t seed, void *
out );
-
-//-----------------------------------------------------------------------------
-// Platform-specific functions and macros
-
-// Microsoft Visual Studio
-
-#if defined(_MSC_VER)
-
-#define FORCE_INLINE __forceinline
-
-#include <stdlib.h>
-
-#define ROTL32(x,y) _rotl(x,y)
-#define ROTL64(x,y) _rotl64(x,y)
-
-#define BIG_CONSTANT(x) (x)
-
-// Other compilers
-
-#else // defined(_MSC_VER)
-
-#define FORCE_INLINE inline __attribute__((always_inline))
-
-static inline uint32_t
-rotl32 ( uint32_t x, int8_t r )
-{
- return (x << r) | (x >> (32 - r));
-}
-
-static inline uint64_t
-rotl64 ( uint64_t x, int8_t r )
-{
- return (x << r) | (x >> (64 - r));
-}
-
-#define ROTL32(x,y) rotl32(x,y)
-#define ROTL64(x,y) rotl64(x,y)
-
-#define BIG_CONSTANT(x) (x##LLU)
-
-#endif // !defined(_MSC_VER)
-
-//-----------------------------------------------------------------------------
-// Block read - if your platform needs to do endian-swapping or can only
-// handle aligned reads, do the conversion here
-
-FORCE_INLINE uint32_t getblock32 ( const uint32_t * p, int i )
-{
- return p[i];
-}
-
-FORCE_INLINE uint64_t getblock64 ( const uint64_t * p, int i )
-{
- return p[i];
-}
-
-//-----------------------------------------------------------------------------
-// Finalization mix - force all bits of a hash block to avalanche
-
-FORCE_INLINE uint32_t fmix32 ( uint32_t h )
-{
- h ^= h >> 16;
- h *= 0x85ebca6b;
- h ^= h >> 13;
- h *= 0xc2b2ae35;
- h ^= h >> 16;
-
- return h;
-}
-
-//----------
-
-FORCE_INLINE uint64_t fmix64 ( uint64_t k )
-{
- k ^= k >> 33;
- k *= BIG_CONSTANT(0xff51afd7ed558ccd);
- k ^= k >> 33;
- k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
- k ^= k >> 33;
-
- return k;
-}
-
-//-----------------------------------------------------------------------------
-
-void MurmurHash3_x86_32 ( const void * key, int len,
- uint32_t seed, void * out )
-{
- const uint8_t * data = (const uint8_t*)key;
- const int nblocks = len / 4;
-
- uint32_t h1 = seed;
-
- const uint32_t c1 = 0xcc9e2d51;
- const uint32_t c2 = 0x1b873593;
-
- //----------
- // body
-
- const uint32_t * blocks = (const uint32_t *)(data + nblocks*4);
-
- for(int i = -nblocks; i; i++)
- {
- uint32_t k1 = getblock32(blocks,i);
-
- k1 *= c1;
- k1 = ROTL32(k1,15);
- k1 *= c2;
-
- h1 ^= k1;
- h1 = ROTL32(h1,13);
- h1 = h1*5+0xe6546b64;
- }
-
- //----------
- // tail
-
- const uint8_t * tail = (const uint8_t*)(data + nblocks*4);
-
- uint32_t k1 = 0;
-
- switch(len & 3)
- {
- case 3: k1 ^= tail[2] << 16; /* fall through */
- case 2: k1 ^= tail[1] << 8; /* fall through */
- case 1: k1 ^= tail[0];
- k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
- /* fall through */
- };
-
- //----------
- // finalization
-
- h1 ^= len;
-
- h1 = fmix32(h1);
-
- *(uint32_t*)out = h1;
-}
-
-//-----------------------------------------------------------------------------
-
-void MurmurHash3_x86_128 ( const void * key, const int len,
- uint32_t seed, void * out )
-{
- const uint8_t * data = (const uint8_t*)key;
- const int nblocks = len / 16;
-
- uint32_t h1 = seed;
- uint32_t h2 = seed;
- uint32_t h3 = seed;
- uint32_t h4 = seed;
-
- const uint32_t c1 = 0x239b961b;
- const uint32_t c2 = 0xab0e9789;
- const uint32_t c3 = 0x38b34ae5;
- const uint32_t c4 = 0xa1e38b93;
-
- //----------
- // body
-
- const uint32_t * blocks = (const uint32_t *)(data + nblocks*16);
-
- for(int i = -nblocks; i; i++)
- {
- uint32_t k1 = getblock32(blocks,i*4+0);
- uint32_t k2 = getblock32(blocks,i*4+1);
- uint32_t k3 = getblock32(blocks,i*4+2);
- uint32_t k4 = getblock32(blocks,i*4+3);
-
- k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
-
- h1 = ROTL32(h1,19); h1 += h2; h1 = h1*5+0x561ccd1b;
-
- k2 *= c2; k2 = ROTL32(k2,16); k2 *= c3; h2 ^= k2;
-
- h2 = ROTL32(h2,17); h2 += h3; h2 = h2*5+0x0bcaa747;
-
- k3 *= c3; k3 = ROTL32(k3,17); k3 *= c4; h3 ^= k3;
-
- h3 = ROTL32(h3,15); h3 += h4; h3 = h3*5+0x96cd1c35;
-
- k4 *= c4; k4 = ROTL32(k4,18); k4 *= c1; h4 ^= k4;
-
- h4 = ROTL32(h4,13); h4 += h1; h4 = h4*5+0x32ac3b17;
- }
-
- //----------
- // tail
-
- const uint8_t * tail = (const uint8_t*)(data + nblocks*16);
-
- uint32_t k1 = 0;
- uint32_t k2 = 0;
- uint32_t k3 = 0;
- uint32_t k4 = 0;
-
- switch(len & 15)
- {
- case 15: k4 ^= tail[14] << 16; /* fall through */
- case 14: k4 ^= tail[13] << 8; /* fall through */
- case 13: k4 ^= tail[12] << 0; /* fall through */
- k4 *= c4; k4 = ROTL32(k4,18); k4 *= c1; h4 ^= k4;
- /* fall through */
_______________________________________________
checkin-list mailing list -- [email protected]
To unsubscribe send an email to [email protected]
