| // Licensed to the Apache Software Foundation (ASF) under one |
| // or more contributor license agreements. See the NOTICE file |
| // distributed with this work for additional information |
| // regarding copyright ownership. The ASF licenses this file |
| // to you under the Apache License, Version 2.0 (the |
| // "License"); you may not use this file except in compliance |
| // with the License. You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, |
| // software distributed under the License is distributed on an |
| // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| // KIND, either express or implied. See the License for the |
| // specific language governing permissions and limitations |
| // under the License. |
| |
| #include <stdint.h> |
| |
| #include <iostream> |
| #include <limits> |
| #include <memory> |
| #include <vector> |
| |
| #include <immintrin.h> |
| |
| #include "util/benchmark.h" |
| #include "util/cpu-info.h" |
| #include "util/hash-util.h" |
| #include "util/sse-util.h" |
| |
| using namespace std; |
| using namespace impala; |
| |
| // Test hash functions that take integers as arguments and produce integers as the result. |
| // |
| // Machine Info: Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz |
| // 32 -> 32: Function iters/ms 10%ile 50%ile 90%ile 10%ile 50%ile 90%ile |
| // (relative) (relative) (relative) |
| // --------------------------------------------------------------------------------------------------------- |
| // FNV 25.7 26 26.4 1X 1X 1X |
| // Zobrist 30.2 30.7 30.9 1.18X 1.18X 1.17X |
| // MultRot 42.6 43.4 43.4 1.66X 1.67X 1.64X |
| // MultiplyAddShift 42.4 43.2 43.2 1.65X 1.66X 1.64X |
| // Jenkins1 51.8 54 54 2.02X 2.08X 2.05X |
| // Jenkins2 66.2 67.4 67.5 2.58X 2.59X 2.56X |
| // CRC 98.6 100 101 3.84X 3.85X 3.84X |
| // MultiplyShift 150 152 153 5.84X 5.86X 5.79X |
| // |
| // 32 x 4 -> 32 x 4: Function iters/ms 10%ile 50%ile 90%ile 10%ile 50%ile 90%ile |
| // (relative) (relative) (relative) |
| // --------------------------------------------------------------------------------------------------------- |
| // (Multiple<Zobrist, 4>) 30.8 31.2 31.4 1X 1X 1X |
| // (Multiple<MultiplyAddShift, 4>) 44.2 45 45 1.43X 1.44X 1.43X |
| // (Multiple<CRC, 4>) 118 120 121 3.84X 3.86X 3.85X |
| // (Multiple<MultiplyShift, 4>) 156 159 159 5.07X 5.1X 5.08X |
| // MultiplyAddShift128 75.7 77.2 77.2 2.46X 2.48X 2.46X |
| // MultiplyShift128 128 131 133 4.16X 4.21X 4.23X |
| // |
| // 32 x 8 -> 32 x 8: Function iters/ms 10%ile 50%ile 90%ile 10%ile 50%ile 90%ile |
| // (relative) (relative) (relative) |
| // --------------------------------------------------------------------------------------------------------- |
| // (Multiple<Zobrist, 8>) 31 31.5 31.8 1X 1X 1X |
| // (Multiple<MultiplyAddShift, 8>) 44.3 44.5 45.2 1.43X 1.41X 1.42X |
| // (Multiple<CRC, 8>) 121 123 123 3.9X 3.9X 3.88X |
| // (Multiple<MultiplyShift, 8>) 158 159 160 5.11X 5.05X 5.04X |
| // Zobrist256simple 16.5 16.5 16.6 0.533X 0.524X 0.522X |
| // Zobrist256gather 18.8 19.2 19.4 0.608X 0.608X 0.61X |
| // MultiplyAddShift256 151 154 154 4.88X 4.88X 4.84X |
| // MultiplyShift256 209 212 212 6.73X 6.71X 6.67X |
| |
| // Rotate 32 bits right by 'shift'. This is _rotr in the intel instrinsics, but that isn't |
| // usable on Clang yet. Fortunately, both GCC and Clang can optimize this to use the 'ror' |
| // instruction. |
| template<int SHIFT> |
| inline uint32_t RotateRight(uint32_t x) { |
| static_assert(SHIFT > 0, "Only positive shifts are defined behavior and useful"); |
| static_assert( |
| SHIFT < std::numeric_limits<decltype(x)>::digits, "This much shift is just 0"); |
| return (x << (std::numeric_limits<decltype(x)>::digits - SHIFT)) | (x >> SHIFT); |
| } |
| |
| // Make a random uint32_t, avoiding the absent high bit and the low-entropy low bits |
| // produced by rand(). |
| uint32_t MakeRandU32() { |
| uint32_t result = (rand() >> 8) & 0xffff; |
| result <<= 16; |
| result |= (rand() >> 8) & 0xffff; |
| return result; |
| } |
| |
| // Almost universal hashing, M. Dietzfelbinger, T. Hagerup, J. Katajainen, and M. |
| // Penttonen, "A reliable randomized algorithm for the closest-pair problem". |
| inline void MultiplyShift(uint32_t* x) { |
| static const uint32_t m = 0x61eaf8e9u; |
| *x = *x * m; |
| } |
| |
| // Like MultiplyShift, but using SSE's 128-bit SIMD registers to do 4 at once. |
| // |
| // TODO: Add the Intel intrinsics used in this function and the other functions in this |
| // file to sse-util.h so that these functions can be inlined. |
| inline void MultiplyShift128(__m128i* x) __attribute__((__target__("sse4.1"))); |
| inline void MultiplyShift128(__m128i* x) { |
| const __m128i m = _mm_set1_epi32(0x61eaf8e9); |
| _mm_storeu_si128(x, _mm_mullo_epi32(_mm_loadu_si128(x), m)); |
| } |
| |
| // Like MultiplyShift, but using AVX2's 256-bit SIMD registers to do 8 at once. |
| // |
| // Not inline, because it degrades the performance for unknown reasons. |
| void MultiplyShift256(__m256i* x) __attribute__((__target__("avx2"))); |
| void MultiplyShift256(__m256i* x) { |
| const __m256i m = _mm256_set1_epi32(0x61eaf8e9); |
| _mm256_storeu_si256(x, _mm256_mullo_epi32(_mm256_loadu_si256(x), m)); |
| } |
| |
| // 2-independent hashing. M. Dietzfelbinger, "Universal hashing and k-wise independent |
| // random variables via integer arithmetic without primes" |
| inline void MultiplyAddShift(uint32_t* x) { |
| static const uint64_t m = 0xa1f1bd3e020b4be0ull, a = 0x86b0426193d86e66ull; |
| *x = (static_cast<uint64_t>(*x) * m + a) >> 32; |
| } |
| |
| // Like MultiplyAddShift, but using SSE's 128-bit SIMD registers to do 4 at once. |
| inline void MultiplyAddShift128(__m128i* x) __attribute__((__target__("sse4.1"))); |
| inline void MultiplyAddShift128(__m128i* x) { |
| const auto m = _mm_set1_epi64x(0xa1f1bd3e020b4be0ull), |
| mhi = _mm_set1_epi32(0xa1f1bd3e), |
| a = _mm_set1_epi64x(0x86b0426193d86e66ull); |
| auto input = _mm_loadu_si128(x); |
| auto prod32easy = _mm_mullo_epi32(input, mhi); |
| auto input_odds = _mm_srli_epi64(input, 32); |
| auto prod64_evens = _mm_mul_epu32(input, m), |
| prod64_odds = _mm_mul_epu32(input_odds, m); |
| prod64_evens = _mm_add_epi64(a, prod64_evens); |
| prod64_odds = _mm_add_epi64(a, prod64_odds); |
| auto prod32hard = _mm_unpackhi_epi32(prod64_evens, prod64_odds); |
| _mm_storeu_si128(x, _mm_add_epi32(prod32easy, prod32hard)); |
| } |
| |
| // Like MultiplyAddShift, but using AVX2's 256-bit SIMD registers to do 8 at once. |
| inline void MultiplyAddShift256(__m256i* x) __attribute__((__target__("avx2"))); |
| inline void MultiplyAddShift256(__m256i* x) { |
| const __m256i m = _mm256_set1_epi64x(0xa1f1bd3e020b4be0ull), |
| mhi = _mm256_set1_epi32(0xa1f1bd3e), |
| a = _mm256_set1_epi64x(0x86b0426193d86e66ull); |
| __m256i input = _mm256_loadu_si256(x); |
| __m256i prod32easy = _mm256_mullo_epi32(input, mhi); |
| __m256i input_odds = _mm256_srli_epi64(input, 32); |
| __m256i prod64_evens = _mm256_mul_epu32(input, m), |
| prod64_odds = _mm256_mul_epu32(input_odds, m); |
| prod64_evens = _mm256_add_epi64(a, prod64_evens); |
| prod64_odds = _mm256_add_epi64(a, prod64_odds); |
| __m256i prod32hard = _mm256_unpackhi_epi32(prod64_evens, prod64_odds); |
| _mm256_storeu_si256(x, _mm256_add_epi32(prod32easy, prod32hard)); |
| } |
| |
| // From http://web.archive.org/web/20071223173210/http://www.concentric.net/~Ttwang/tech/inthash.htm: |
| inline void Jenkins1(int32_t* x) { |
| *x = ~*x + (*x << 15); // x = (x << 15) - x - 1; |
| *x = *x ^ RotateRight<12>(*x); |
| *x = *x + (*x << 2); |
| *x = *x ^ RotateRight<4>(*x); |
| *x = *x * 2057; // x = (x + (x << 3)) + (x << 11); |
| *x = *x ^ RotateRight<16>(*x); |
| } |
| |
| // From http://web.archive.org/web/20071223173210/http://www.concentric.net/~Ttwang/tech/inthash.htm: |
| inline void Jenkins2(uint32_t* a) { |
| *a = (*a + 0x7ed55d16) + (*a << 12); |
| *a = (*a ^ 0xc761c23c) ^ (*a >> 19); |
| *a = (*a + 0x165667b1) + (*a << 5); |
| *a = (*a + 0xd3a2646c) ^ (*a << 9); |
| *a = (*a + 0xfd7046c5) + (*a << 3); |
| *a = (*a ^ 0xb55a4f09) ^ (*a >> 16); |
| } |
| |
| // From http://web.archive.org/web/20071223173210/http://www.concentric.net/~Ttwang/tech/inthash.htm: |
| inline void MultRot(int32_t* key) { |
| static const int32_t c2 = 0x27d4eb2d; // a prime or an odd constant |
| *key = (*key ^ 61) ^ RotateRight<16>(*key); |
| *key = *key + (*key << 3); |
| *key = *key ^ RotateRight<4>(*key); |
| *key = *key * c2; |
| *key = *key ^ RotateRight<15>(*key); |
| } |
| |
| inline void CRC(uint32_t* x) { |
| *x = SSE4_crc32_u32(*x, 0xab8ce2abu); |
| } |
| |
| inline void FNV(uint32_t* key) { |
| *key = HashUtil::FnvHash64to32(key, sizeof(*key), HashUtil::FNV_SEED); |
| } |
| |
| // Zobrist hashing, also known as tabulation hashing or simple tabulation hashing, is an |
| // old technique that has been recently analyzed and found to be very good for a number of |
| // applications. See "The Power of Simple Tabulation Hashing", by Mihai Patrascu and |
| // Mikkel Thorup. |
| |
| uint32_t ZOBRIST_DATA[4][256]; |
| |
| inline void Zobrist(uint32_t* key) { |
| const uint8_t* key_chars = reinterpret_cast<const uint8_t*>(key); |
| *key = ZOBRIST_DATA[0][key_chars[0]] ^ ZOBRIST_DATA[1][key_chars[1]] |
| ^ ZOBRIST_DATA[2][key_chars[2]] ^ ZOBRIST_DATA[3][key_chars[3]]; |
| } |
| |
| // Like Zobrist, but uses AVX2's "gather" primatives to hash 8 values at once. |
| inline void Zobrist256gather(__m256i* key) __attribute__((__target__("avx2"))); |
| inline void Zobrist256gather(__m256i* key) { |
| const auto k = _mm256_loadu_si256(key); |
| const auto low_mask = _mm256_set1_epi32(0xff); |
| auto k0 = _mm256_and_si256(low_mask, k), |
| k1 = _mm256_and_si256(low_mask, _mm256_srli_epi32(k, 8)), |
| k2 = _mm256_and_si256(low_mask, _mm256_srli_epi32(k, 16)), |
| k3 = _mm256_and_si256(low_mask, _mm256_srli_epi32(k, 24)); |
| k0 = _mm256_i32gather_epi32(reinterpret_cast<const int*>(ZOBRIST_DATA[0]), k0, 1); |
| k1 = _mm256_i32gather_epi32(reinterpret_cast<const int*>(ZOBRIST_DATA[1]), k1, 1); |
| k2 = _mm256_i32gather_epi32(reinterpret_cast<const int*>(ZOBRIST_DATA[2]), k2, 1); |
| k3 = _mm256_i32gather_epi32(reinterpret_cast<const int*>(ZOBRIST_DATA[3]), k3, 1); |
| auto k01 = _mm256_xor_si256(k0, k1), k23 = _mm256_xor_si256(k2, k3); |
| _mm256_storeu_si256(key, _mm256_xor_si256(k01, k23)); |
| } |
| |
| // Like Zobrist256gather, but only uses AVX2's SIMD xor, not its gather. |
| inline void Zobrist256simple(uint32_t (*key)[8]) __attribute__((__target__("avx2"))); |
| inline void Zobrist256simple(uint32_t (*key)[8]) { |
| uint32_t row[4][8]; |
| const uint8_t (*key_chars)[8][4] = reinterpret_cast<const uint8_t (*)[8][4]>(key); |
| for (int i = 0; i < 4; ++i) { |
| for (int j = 0; j < 8; ++j) { |
| row[i][j] = ZOBRIST_DATA[i][(*key_chars)[j][i]]; |
| } |
| } |
| auto result0 = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(row[0])), |
| result1 = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(row[1])), |
| result2 = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(row[2])), |
| result3 = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(row[3])); |
| auto k01 = _mm256_xor_si256(result0, result1), k23 = _mm256_xor_si256(result2, result3); |
| _mm256_storeu_si256(reinterpret_cast<__m256i*>(*key), _mm256_xor_si256(k01, k23)); |
| } |
| |
| // Perform one hash function the given number of times. This can sometimes auto-vectorize. |
| // |
| // TODO: We could also test the costs of running on non-contiguous uint32_t's. For |
| // instance, ExprValuesCache.expr_values_array_ might have multiple values to hash per |
| // input row. |
| template <void (*F)(uint32_t*), size_t N> |
| inline void Multiple(uint32_t (*x)[N]) { |
| for (int i = 0; i < N; ++i) { |
| F((*x) + i); |
| } |
| } |
| |
| // The size of the test data we run each hash function on: |
| static const size_t DATA_SIZE = 1 << 15; |
| |
| template<typename T, void (*HASH)(T*)> |
| void Run(int batch_size, void* data) { |
| T* d = reinterpret_cast<T*>(data); |
| for (int i = 0; i < batch_size; ++i) { |
| for (int j = 0; j < ((sizeof(uint32_t)) * DATA_SIZE) / sizeof(T); ++j) { |
| HASH(&d[j]); |
| } |
| } |
| } |
| |
| int main() { |
| CpuInfo::Init(); |
| cout << endl |
| << Benchmark::GetMachineInfo() << endl; |
| |
| unique_ptr<uint32_t[]> ud(new uint32_t[DATA_SIZE]); |
| for (size_t i = 0; i < (DATA_SIZE); ++i) { |
| ud[i] = MakeRandU32(); |
| } |
| |
| for (size_t i = 0; i < 4; ++i) { |
| for (size_t j = 0; j < 256; ++j) { |
| ZOBRIST_DATA[i][j] = MakeRandU32(); |
| } |
| } |
| |
| Benchmark suite32("32 -> 32"); |
| |
| #define BENCH(T,x) AddBenchmark(#x, Run<T, x>, ud.get()) |
| |
| suite32.BENCH(uint32_t, FNV); |
| suite32.BENCH(uint32_t, Zobrist); |
| suite32.BENCH(int32_t, MultRot); |
| suite32.BENCH(uint32_t, MultiplyAddShift); |
| suite32.BENCH(int32_t, Jenkins1); |
| suite32.BENCH(uint32_t, Jenkins2); |
| if (CpuInfo::IsSupported(CpuInfo::SSE4_2)) suite32.BENCH(uint32_t, CRC); |
| suite32.BENCH(uint32_t, MultiplyShift); |
| |
| cout << suite32.Measure() << endl; |
| |
| Benchmark suite32x4("32 x 4 -> 32 x 4"); |
| |
| suite32x4.BENCH(uint32_t[4], (Multiple<Zobrist, 4>)); |
| suite32x4.BENCH(uint32_t[4], (Multiple<MultiplyAddShift, 4>)); |
| if (CpuInfo::IsSupported(CpuInfo::SSE4_2)) { |
| suite32x4.BENCH(uint32_t[4], (Multiple<CRC, 4>)); |
| } |
| suite32x4.BENCH(uint32_t[4], (Multiple<MultiplyShift, 4>)); |
| if (CpuInfo::IsSupported(CpuInfo::SSE4_1)) { |
| suite32x4.BENCH(__m128i, MultiplyAddShift128); |
| suite32x4.BENCH(__m128i, MultiplyShift128); |
| } |
| |
| cout << suite32x4.Measure() << endl; |
| |
| Benchmark suite32x8("32 x 8 -> 32 x 8"); |
| |
| suite32x8.BENCH(uint32_t[8], (Multiple<Zobrist, 8>)); |
| suite32x8.BENCH(uint32_t[8], (Multiple<MultiplyAddShift, 8>)); |
| suite32x8.BENCH(uint32_t[8], (Multiple<CRC, 8>)); |
| suite32x8.BENCH(uint32_t[8], (Multiple<MultiplyShift, 8>)); |
| if (CpuInfo::IsSupported(CpuInfo::AVX2)) { |
| suite32x8.BENCH(uint32_t[8], Zobrist256simple); |
| suite32x8.BENCH(__m256i, Zobrist256gather); |
| suite32x8.BENCH(__m256i, MultiplyAddShift256); |
| suite32x8.BENCH(__m256i, MultiplyShift256); |
| } |
| |
| cout << suite32x8.Measure() << endl; |
| |
| #undef BENCH |
| } |
