[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH 1/6] use Jenkins hash
|
From: |
Paolo Bonzini |
|
Subject: |
[PATCH 1/6] use Jenkins hash |
|
Date: |
Fri, 11 Aug 2017 13:44:28 +0200 |
This is about twice as fast as the current hash, and removes the need
for double hashing (improving locality of reference). The hash function
is based on Bob Jenkins' design, slightly adapted wherever Make needs
to hash NUL-terminated strings. The old hash function is kept for
case-insensitive hashing.
The resulting speedup on QEMU's noop build is 8.5% (from 12.87 to 11.78
seconds).
* configure.ac: Check endianness.
* hash.c (rol32, jhash_mix, jhash_final, JHASH_INITVAL,
sum_get_unaligned_32, jhash): New.
* hash.h (STRING_HASH_1, STRING_N_HASH_1): Use jhash.
(STRING_HASH_2, STRING_N_HASH_2): Return a dummy value.
(STRING_N_COMPARE, return_STRING_N_COMPARE): Prefer memcmp to strncmp.
---
configure.ac | 1 +
hash.c | 148 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
hash.h | 40 ++++++++--------
3 files changed, 169 insertions(+), 20 deletions(-)
diff --git a/configure.ac b/configure.ac
index 1b03135..9b8aed9 100644
--- a/configure.ac
+++ b/configure.ac
@@ -49,6 +49,7 @@ AC_CANONICAL_HOST
AC_AIX
AC_ISC_POSIX
AC_MINIX
+AC_C_BIGENDIAN
# Enable gettext, in "external" mode.
AM_GNU_GETTEXT_VERSION([0.19.4])
diff --git a/hash.c b/hash.c
index e168887..c138aaf 100644
--- a/hash.c
+++ b/hash.c
@@ -327,3 +327,151 @@ round_up_2 (unsigned long n)
return n + 1;
}
+
+#define rol32(v, n) \
+ ((v) << (n) | ((v) >> (32 - (n))))
+
+/* jhash_mix -- mix 3 32-bit values reversibly. */
+#define jhash_mix(a, b, c) \
+{ \
+ a -= c; a ^= rol32(c, 4); c += b; \
+ b -= a; b ^= rol32(a, 6); a += c; \
+ c -= b; c ^= rol32(b, 8); b += a; \
+ a -= c; a ^= rol32(c, 16); c += b; \
+ b -= a; b ^= rol32(a, 19); a += c; \
+ c -= b; c ^= rol32(b, 4); b += a; \
+}
+
+/* jhash_final - final mixing of 3 32-bit values (a,b,c) into c */
+#define jhash_final(a, b, c) \
+{ \
+ c ^= b; c -= rol32(b, 14); \
+ a ^= c; a -= rol32(c, 11); \
+ b ^= a; b -= rol32(a, 25); \
+ c ^= b; c -= rol32(b, 16); \
+ a ^= c; a -= rol32(c, 4); \
+ b ^= a; b -= rol32(a, 14); \
+ c ^= b; c -= rol32(b, 24); \
+}
+
+/* An arbitrary initial parameter */
+#define JHASH_INITVAL 0xdeadbeef
+
+#define sum_get_unaligned_32(r, p) \
+ do { \
+ unsigned int val; \
+ memcpy(&val, (p), 4); \
+ r += val; \
+ } while(0);
+
+unsigned jhash(unsigned const char *k, int length)
+{
+ unsigned int a, b, c;
+
+ /* Set up the internal state */
+ a = b = c = JHASH_INITVAL + length;
+
+ /* All but the last block: affect some 32 bits of (a,b,c) */
+ while (length > 12) {
+ sum_get_unaligned_32(a, k);
+ sum_get_unaligned_32(b, k + 4);
+ sum_get_unaligned_32(c, k + 8);
+ jhash_mix(a, b, c);
+ length -= 12;
+ k += 12;
+ }
+
+ if (!length)
+ return c;
+
+ if (length > 8)
+ {
+ sum_get_unaligned_32(a, k);
+ length -= 4;
+ k += 4;
+ }
+ if (length > 4)
+ {
+ sum_get_unaligned_32(b, k);
+ length -= 4;
+ k += 4;
+ }
+
+ if (length == 4)
+ c += (unsigned)k[3]<<24;
+ if (length >= 3)
+ c += (unsigned)k[2]<<16;
+ if (length >= 2)
+ c += (unsigned)k[1]<<8;
+ c += k[0];
+ jhash_final(a, b, c);
+ return c;
+}
+
+#ifdef WORDS_BIGENDIAN
+/* The ifs are ordered from the first byte in memory to the last. */
+#define sum_up_to_nul(r, p, flag) \
+ do { \
+ unsigned int val; \
+ memcpy(&val, (p), 4); \
+ if ((val & 0xFF000000) == 0) \
+ flag = 1; \
+ else if ((val & 0xFF0000) == 0) \
+ r += val & ~0xFFFF, flag = 1; \
+ else if ((val & 0xFF00) == 0) \
+ r += val & ~0xFF, flag = 1; \
+ else \
+ r += val, flag = (val & 0xFF) == 0; \
+ } while (0)
+#else
+/* First detect the presence of zeroes. If there is none, we can
+ sum the 4 bytes directly. Otherwise, the ifs are ordered as in the
+ big endian case, from the first byte in memory to the last. */
+#define sum_up_to_nul(r, p, flag) \
+ do { \
+ unsigned int val; \
+ unsigned int zeroes; \
+ memcpy(&val, (p), 4); \
+ zeroes = ((val - 0x01010101) & ~val); \
+ if (!(zeroes & 0x80808080)) \
+ r += val; \
+ else if ((val & 0xFF) == 0) \
+ flag = 1; \
+ else if ((val & 0xFF00) == 0) \
+ r += val & 0xFF, flag = 1; \
+ else if ((val & 0xFF0000) == 0) \
+ r += val & 0xFFFF, flag = 1; \
+ else \
+ r += val, flag = 1; \
+ } while (0)
+#endif
+
+unsigned jhash_string(unsigned const char *k)
+{
+ unsigned int a, b, c;
+ unsigned int have_nul = 0;
+ unsigned const char *start = k;
+
+ /* Set up the internal state */
+ a = b = c = JHASH_INITVAL;
+
+ /* All but the last block: affect some 32 bits of (a,b,c) */
+ for (;;) {
+ sum_up_to_nul(a, k, have_nul);
+ if (have_nul)
+ break;
+ k += 4;
+ sum_up_to_nul(b, k, have_nul);
+ if (have_nul)
+ break;
+ k += 4;
+ sum_up_to_nul(c, k, have_nul);
+ if (have_nul)
+ break;
+ k += 4;
+ jhash_mix(a, b, c);
+ }
+
+ jhash_final(a, b, c);
+ return c + (k - start);
+}
diff --git a/hash.h b/hash.h
index 960cbd7..667d650 100644
--- a/hash.h
+++ b/hash.h
@@ -73,6 +73,9 @@ void hash_map_arg __P((struct hash_table *ht,
hash_map_arg_func_t map, void *arg
void hash_print_stats __P((struct hash_table *ht, FILE *out_FILE));
void **hash_dump __P((struct hash_table *ht, void **vector_0, qsort_cmp_t
compare));
+extern unsigned jhash(unsigned char const *key, int n);
+extern unsigned jhash_string(unsigned char const *key);
+
extern void *hash_deleted_item;
#define HASH_VACANT(item) ((item) == 0 || (void *) (item) == hash_deleted_item)
@@ -83,9 +86,8 @@ extern void *hash_deleted_item;
be identical. Take advantage of that to short-circuit string compares. */
#define STRING_HASH_1(KEY, RESULT) do { \
- unsigned char const *_key_ = (unsigned char const *) (KEY) - 1; \
- while (*++_key_) \
- (RESULT) += (*_key_ << (_key_[1] & 0xf)); \
+ unsigned char const *_key_ = (unsigned char const *) (KEY); \
+ (RESULT) += jhash_string(_key_); \
} while (0)
#define return_STRING_HASH_1(KEY) do { \
unsigned long _result_ = 0; \
@@ -93,10 +95,11 @@ extern void *hash_deleted_item;
return _result_; \
} while (0)
+/* No need for a second hash because jhash already provides
+ pretty good results. However, do evaluate the arguments
+ to avoid warnings. */
#define STRING_HASH_2(KEY, RESULT) do { \
- unsigned char const *_key_ = (unsigned char const *) (KEY) - 1; \
- while (*++_key_) \
- (RESULT) += (*_key_ << (_key_[1] & 0x7)); \
+ (void)(KEY); \
} while (0)
#define return_STRING_HASH_2(KEY) do { \
unsigned long _result_ = 0; \
@@ -113,27 +116,24 @@ extern void *hash_deleted_item;
#define STRING_N_HASH_1(KEY, N, RESULT) do { \
- unsigned char const *_key_ = (unsigned char const *) (KEY) - 1; \
- int _n_ = (N); \
- if (_n_) \
- while (--_n_ && *++_key_) \
- (RESULT) += (*_key_ << (_key_[1] & 0xf)); \
- (RESULT) += *++_key_; \
+ unsigned char const *_key_ = (unsigned char const *) (KEY); \
+ (RESULT) += jhash(_key_, N); \
} while (0)
+
#define return_STRING_N_HASH_1(KEY, N) do { \
unsigned long _result_ = 0; \
STRING_N_HASH_1 ((KEY), (N), _result_); \
return _result_; \
} while (0)
+/* No need for a second hash because jhash already provides
+ pretty good results. However, do evaluate the arguments
+ to avoid warnings. */
#define STRING_N_HASH_2(KEY, N, RESULT) do { \
- unsigned char const *_key_ = (unsigned char const *) (KEY) - 1; \
- int _n_ = (N); \
- if (_n_) \
- while (--_n_ && *++_key_) \
- (RESULT) += (*_key_ << (_key_[1] & 0x7)); \
- (RESULT) += *++_key_; \
+ (void)(KEY); \
+ (void)(N); \
} while (0)
+
#define return_STRING_N_HASH_2(KEY, N) do { \
unsigned long _result_ = 0; \
STRING_N_HASH_2 ((KEY), (N), _result_); \
@@ -141,10 +141,10 @@ extern void *hash_deleted_item;
} while (0)
#define STRING_N_COMPARE(X, Y, N, RESULT) do { \
- RESULT = (X) == (Y) ? 0 : strncmp ((X), (Y), (N)); \
+ RESULT = (X) == (Y) ? 0 : memcmp ((X), (Y), (N)); \
} while (0)
#define return_STRING_N_COMPARE(X, Y, N) do { \
- return (X) == (Y) ? 0 : strncmp ((X), (Y), (N)); \
+ return (X) == (Y) ? 0 : memcmp ((X), (Y), (N)); \
} while (0)
#ifdef HAVE_CASE_INSENSITIVE_FS
--
2.13.3
- [PATCH v2 0/6] Miscellaneous speedup patches, Paolo Bonzini, 2017/08/11
- [PATCH 1/6] use Jenkins hash,
Paolo Bonzini <=
- [PATCH 5/6] speedup parsing of functions, Paolo Bonzini, 2017/08/11
- [PATCH 6/6] do not use STOP_SET for singleton sets, Paolo Bonzini, 2017/08/11
- [PATCH 3/6] use strchr/memmove in collapse_continuations, Paolo Bonzini, 2017/08/11
- [PATCH 2/6] use strchr for simple case of find_char_unquote, Paolo Bonzini, 2017/08/11
- [PATCH 4/6] remove MAP_PERCENT, Paolo Bonzini, 2017/08/11