This is the mail archive of the
binutils@sourceware.org
mailing list for the binutils project.
[PATCH, RFC]: Re-implement gas symbol table hash routines
- From: Gianni Tedesco <gianni at scaramanga dot co dot uk>
- To: binutils at sourceware dot org
- Date: Sat, 30 Jul 2016 14:00:50 +0900
- Subject: [PATCH, RFC]: Re-implement gas symbol table hash routines
- Authentication-results: sourceware.org; auth=none
Hi,
I had a problem assembling large (on the order of 100MB's to gigabytes
-- yes, yes, insane, I know) source files. The main culprit seemed to
be the hash table implementation. Even when I hacked gas to use very
large tables (bigger than the largest settable on command-line) it
didn't help. Profiles would always show it spending consistently 85-95%
of the time in hash_lookup().
So I implemented an open-addressing scheme using linear probing and
robin-hood replacement strategy which reduces variance in load-factors,
which helps tremendously with load-factors vs lookup times.
It implements the strategy of maintaining a target load-factor (0.8125
here) and doubling the hash table when we would exceed it. It uses
similar amounts of memory as before so there's no real time/space
trade-off here for smaller systems.
It might be nice to just use a bigger load factor when --reduce-memory-
overheads is selected. The code should work, all be it a bit slower, up
at load factors past 0.9 but it does become unbearably slow at 1.0.
This code brings in CityHash as a good modern hash function not
requiring prime-number size tables.
CAVEATS:
I can address these things pretty easily if there is interest in the
patch (not sure, since it's obviously addressed at a niche use case).
1. deletion is not yet implemented, it's needed in a few arches
2. Not sure the CityHash code is suitable for use in gas, unfamiliar
with the various portability requirements wrt. headers and such-
like. But any modern hash function like murmur or jenkins would
be just as good I'm sure. I didn't pick City based on any well
defined criteria, just an expedient.
3. There is a hacky use of __attribute__((packed)) for the hash_entry
structures if __x86_64__ is defined but it's just performance woo,
it can be removed if it's not suitable.
4. Hash table is over-sized due to storing key-length, hash_find_n
could be optimised to early-out for inputs with nuls and we could
use strcmp instead of memcmp to do the hash table checks. That'd
save memory for all cases, obviate the alignment issue above,
and improve performance.
PERFORMANCE:
- On the largest assembly file I have (2.4GB, producing a 1.5GB
binary, time is reduced from 38mins to 4mins
- On a wide variety of other, smaller inputs, run-time was either
indistinguishable from the original, or better. Same for memory.
Thanks for reading.
Gianni
>From 17f210930b2dfdcd652558e874dbe349172be2af Mon Sep 17 00:00:00 2001
From: Gianni Tedesco <gianni@scaramanga.co.uk>
Date: Sat, 30 Jul 2016 09:07:10 +0900
Subject: [PATCH] Use city hash and robin hood hashing
---
gas/Makefile.am | 1 +
gas/Makefile.in | 4 +-
gas/city.c | 520 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
gas/city.h | 83 +++++++++
gas/citycrc.h | 49 ++++++
gas/hash.c | 417 ++++++++++++++++++++++++++++-----------------
6 files changed, 914 insertions(+), 160 deletions(-)
create mode 100644 gas/city.c
create mode 100644 gas/city.h
create mode 100644 gas/citycrc.h
diff --git a/gas/Makefile.am b/gas/Makefile.am
index 7e302fb..e557724 100644
--- a/gas/Makefile.am
+++ b/gas/Makefile.am
@@ -78,6 +78,7 @@ GAS_CFILES = \
flonum-mult.c \
frags.c \
hash.c \
+ city.c \
input-file.c \
input-scrub.c \
listing.c \
diff --git a/gas/Makefile.in b/gas/Makefile.in
index 19b63f3..02ff550 100644
--- a/gas/Makefile.in
+++ b/gas/Makefile.in
@@ -113,7 +113,7 @@ am__objects_1 = app.$(OBJEXT) as.$(OBJEXT) atof-generic.$(OBJEXT) \
dwarf2dbg.$(OBJEXT) dw2gencfi.$(OBJEXT) ecoff.$(OBJEXT) \
ehopt.$(OBJEXT) expr.$(OBJEXT) flonum-copy.$(OBJEXT) \
flonum-konst.$(OBJEXT) flonum-mult.$(OBJEXT) frags.$(OBJEXT) \
- hash.$(OBJEXT) input-file.$(OBJEXT) input-scrub.$(OBJEXT) \
+ hash.$(OBJEXT) city.$(OBJEXT) input-file.$(OBJEXT) input-scrub.$(OBJEXT) \
listing.$(OBJEXT) literal.$(OBJEXT) macro.$(OBJEXT) \
messages.$(OBJEXT) output-file.$(OBJEXT) read.$(OBJEXT) \
remap.$(OBJEXT) sb.$(OBJEXT) stabs.$(OBJEXT) subsegs.$(OBJEXT) \
@@ -373,6 +373,7 @@ GAS_CFILES = \
flonum-mult.c \
frags.c \
hash.c \
+ city.c \
input-file.c \
input-scrub.c \
listing.c \
@@ -825,6 +826,7 @@ distclean-compile:
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/flonum-mult.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/frags.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/hash.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/city.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/input-file.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/input-scrub.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/itbl-lex.Po@am__quote@
diff --git a/gas/city.c b/gas/city.c
new file mode 100644
index 0000000..db71b63
--- /dev/null
+++ b/gas/city.c
@@ -0,0 +1,520 @@
+// city.c - cityhash-c
+// CityHash on C
+// Copyright (c) 2011-2012, Alexander Nusov
+//
+// - original copyright notice -
+// Copyright (c) 2011 Google, Inc.
+//
+// Permission is hereby granted, free of charge, to any person obtaining a copy
+// of this software and associated documentation files (the "Software"), to deal
+// in the Software without restriction, including without limitation the rights
+// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+// copies of the Software, and to permit persons to whom the Software is
+// furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+// THE SOFTWARE.
+//
+// CityHash, by Geoff Pike and Jyrki Alakuijala
+//
+// This file provides CityHash64() and related functions.
+//
+// It's probably possible to create even faster hash functions by
+// writing a program that systematically explores some of the space of
+// possible hash functions, by using SIMD instructions, or by
+// compromising on hash quality.
+
+#include <string.h>
+#include "city.h"
+
+static uint64_t UNALIGNED_LOAD64(const char *p) {
+ uint64_t result;
+ memcpy(&result, p, sizeof(result));
+ return result;
+}
+
+static uint32_t UNALIGNED_LOAD32(const char *p) {
+ uint32_t result;
+ memcpy(&result, p, sizeof(result));
+ return result;
+}
+
+#if !defined(WORDS_BIGENDIAN)
+
+#define uint32_in_expected_order(x) (x)
+#define uint64_in_expected_order(x) (x)
+
+#else
+
+#ifdef _MSC_VER
+#include <stdlib.h>
+#define bswap_32(x) _byteswap_ulong(x)
+#define bswap_64(x) _byteswap_uint64(x)
+
+#elif defined(__APPLE__)
+// Mac OS X / Darwin features
+#include <libkern/OSByteOrder.h>
+#define bswap_32(x) OSSwapInt32(x)
+#define bswap_64(x) OSSwapInt64(x)
+
+#else
+#include <byteswap.h>
+#endif
+
+#define uint32_in_expected_order(x) (bswap_32(x))
+#define uint64_in_expected_order(x) (bswap_64(x))
+
+#endif // WORDS_BIGENDIAN
+
+#if !defined(LIKELY)
+#if HAVE_BUILTIN_EXPECT
+#define LIKELY(x) (__builtin_expect(!!(x), 1))
+#else
+#define LIKELY(x) (x)
+#endif
+#endif
+
+static uint64_t Fetch64(const char *p) {
+ return uint64_in_expected_order(UNALIGNED_LOAD64(p));
+}
+
+static uint32_t Fetch32(const char *p) {
+ return uint32_in_expected_order(UNALIGNED_LOAD32(p));
+}
+
+// Some primes between 2^63 and 2^64 for various uses.
+static const uint64_t k0 = 0xc3a5c85c97cb3127ULL;
+static const uint64_t k1 = 0xb492b66fbe98f273ULL;
+static const uint64_t k2 = 0x9ae16a3b2f90404fULL;
+static const uint64_t k3 = 0xc949d7c7509e6557ULL;
+
+// Hash 128 input bits down to 64 bits of output.
+// This is intended to be a reasonably good hash function.
+static inline uint64_t Hash128to64(const uint128 x) {
+ // Murmur-inspired hashing.
+ const uint64_t kMul = 0x9ddfea08eb382d69ULL;
+ uint64_t a = (Uint128Low64(x) ^ Uint128High64(x)) * kMul;
+ a ^= (a >> 47);
+ uint64_t b = (Uint128High64(x) ^ a) * kMul;
+ b ^= (b >> 47);
+ b *= kMul;
+ return b;
+}
+
+
+// Bitwise right rotate. Normally this will compile to a single
+// instruction, especially if the shift is a manifest constant.
+static uint64_t Rotate(uint64_t val, int shift) {
+ // Avoid shifting by 64: doing so yields an undefined result.
+ return shift == 0 ? val : ((val >> shift) | (val << (64 - shift)));
+}
+
+// Equivalent to Rotate(), but requires the second arg to be non-zero.
+// On x86-64, and probably others, it's possible for this to compile
+// to a single instruction if both args are already in registers.
+static uint64_t RotateByAtLeast1(uint64_t val, int shift) {
+ return (val >> shift) | (val << (64 - shift));
+}
+
+static uint64_t ShiftMix(uint64_t val) {
+ return val ^ (val >> 47);
+}
+
+static uint64_t HashLen16(uint64_t u, uint64_t v) {
+ uint128 result;
+ result.first = u;
+ result.second = v;
+ return Hash128to64(result);
+}
+
+static uint64_t HashLen0to16(const char *s, size_t len) {
+ if (len > 8) {
+ uint64_t a = Fetch64(s);
+ uint64_t b = Fetch64(s + len - 8);
+ return HashLen16(a, RotateByAtLeast1(b + len, len)) ^ b;
+ }
+ if (len >= 4) {
+ uint64_t a = Fetch32(s);
+ return HashLen16(len + (a << 3), Fetch32(s + len - 4));
+ }
+ if (len > 0) {
+ uint8_t a = s[0];
+ uint8_t b = s[len >> 1];
+ uint8_t c = s[len - 1];
+ uint32_t y = (uint32_t)(a) + ((uint32_t)(b) << 8);
+ uint32_t z = len + ((uint32_t)(c) << 2);
+ return ShiftMix(y * k2 ^ z * k3) * k2;
+ }
+ return k2;
+}
+
+// This probably works well for 16-byte strings as well, but it may be overkill
+// in that case.
+static uint64_t HashLen17to32(const char *s, size_t len) {
+ uint64_t a = Fetch64(s) * k1;
+ uint64_t b = Fetch64(s + 8);
+ uint64_t c = Fetch64(s + len - 8) * k2;
+ uint64_t d = Fetch64(s + len - 16) * k0;
+ return HashLen16(Rotate(a - b, 43) + Rotate(c, 30) + d,
+ a + Rotate(b ^ k3, 20) - c + len);
+}
+
+// Return a 16-byte hash for 48 bytes. Quick and dirty.
+// Callers do best to use "random-looking" values for a and b.
+// static pair<uint64_t, uint64_t> WeakHashLen32WithSeeds(
+static uint128 WeakHashLen32WithSeeds6(
+ uint64_t w, uint64_t x, uint64_t y, uint64_t z, uint64_t a, uint64_t b) {
+ a += w;
+ b = Rotate(b + a + z, 21);
+ uint64_t c = a;
+ a += x;
+ a += y;
+ b += Rotate(a, 44);
+
+ uint128 result;
+ result.first = (uint64_t) (a + z);
+ result.second = (uint64_t) (b + c);
+ return result;
+}
+
+// Return a 16-byte hash for s[0] ... s[31], a, and b. Quick and dirty.
+// static pair<uint64_t, uint64_t> WeakHashLen32WithSeeds(
+static uint128 WeakHashLen32WithSeeds(
+ const char* s, uint64_t a, uint64_t b) {
+ return WeakHashLen32WithSeeds6(Fetch64(s),
+ Fetch64(s + 8),
+ Fetch64(s + 16),
+ Fetch64(s + 24),
+ a,
+ b);
+}
+
+// Return an 8-byte hash for 33 to 64 bytes.
+static uint64_t HashLen33to64(const char *s, size_t len) {
+ uint64_t z = Fetch64(s + 24);
+ uint64_t a = Fetch64(s) + (len + Fetch64(s + len - 16)) * k0;
+ uint64_t b = Rotate(a + z, 52);
+ uint64_t c = Rotate(a, 37);
+ a += Fetch64(s + 8);
+ c += Rotate(a, 7);
+ a += Fetch64(s + 16);
+ uint64_t vf = a + z;
+ uint64_t vs = b + Rotate(a, 31) + c;
+ a = Fetch64(s + 16) + Fetch64(s + len - 32);
+ z = Fetch64(s + len - 8);
+ b = Rotate(a + z, 52);
+ c = Rotate(a, 37);
+ a += Fetch64(s + len - 24);
+ c += Rotate(a, 7);
+ a += Fetch64(s + len - 16);
+ uint64_t wf = a + z;
+ uint64_t ws = b + Rotate(a, 31) + c;
+ uint64_t r = ShiftMix((vf + ws) * k2 + (wf + vs) * k0);
+ return ShiftMix(r * k0 + vs) * k2;
+}
+
+uint64_t CityHash64(const char *s, size_t len) {
+ if (len <= 32) {
+ if (len <= 16) {
+ return HashLen0to16(s, len);
+ } else {
+ return HashLen17to32(s, len);
+ }
+ } else if (len <= 64) {
+ return HashLen33to64(s, len);
+ }
+
+ // For strings over 64 bytes we hash the end first, and then as we
+ // loop we keep 56 bytes of state: v, w, x, y, and z.
+ uint64_t x = Fetch64(s + len - 40);
+ uint64_t y = Fetch64(s + len - 16) + Fetch64(s + len - 56);
+ uint64_t z = HashLen16(Fetch64(s + len - 48) + len, Fetch64(s + len - 24));
+ uint64_t temp;
+ uint128 v = WeakHashLen32WithSeeds(s + len - 64, len, z);
+ uint128 w = WeakHashLen32WithSeeds(s + len - 32, y + k1, x);
+ x = x * k1 + Fetch64(s);
+
+ // Decrease len to the nearest multiple of 64, and operate on 64-byte chunks.
+ len = (len - 1) & ~(size_t)(63);
+ do {
+ x = Rotate(x + y + v.first + Fetch64(s + 8), 37) * k1;
+ y = Rotate(y + v.second + Fetch64(s + 48), 42) * k1;
+ x ^= w.second;
+ y += v.first + Fetch64(s + 40);
+ z = Rotate(z + w.first, 33) * k1;
+ v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
+ w = WeakHashLen32WithSeeds(s + 32, z + w.second, y + Fetch64(s + 16));
+ temp = z;
+ z = x;
+ x = temp;
+ s += 64;
+ len -= 64;
+ } while (len != 0);
+ return HashLen16(HashLen16(v.first, w.first) + ShiftMix(y) * k1 + z,
+ HashLen16(v.second, w.second) + x);
+}
+
+uint64_t CityHash64WithSeed(const char *s, size_t len, uint64_t seed) {
+ return CityHash64WithSeeds(s, len, k2, seed);
+}
+
+uint64_t CityHash64WithSeeds(const char *s, size_t len,
+ uint64_t seed0, uint64_t seed1) {
+ return HashLen16(CityHash64(s, len) - seed0, seed1);
+}
+
+// A subroutine for CityHash128(). Returns a decent 128-bit hash for strings
+// of any length representable in signed long. Based on City and Murmur.
+static uint128 CityMurmur(const char *s, size_t len, uint128 seed) {
+ uint64_t a = Uint128Low64(seed);
+ uint64_t b = Uint128High64(seed);
+ uint64_t c = 0;
+ uint64_t d = 0;
+ signed long l = len - 16;
+ if (l <= 0) { // len <= 16
+ a = ShiftMix(a * k1) * k1;
+ c = b * k1 + HashLen0to16(s, len);
+ d = ShiftMix(a + (len >= 8 ? Fetch64(s) : c));
+ } else { // len > 16
+ c = HashLen16(Fetch64(s + len - 8) + k1, a);
+ d = HashLen16(b + len, c + Fetch64(s + len - 16));
+ a += d;
+ do {
+ a ^= ShiftMix(Fetch64(s) * k1) * k1;
+ a *= k1;
+ b ^= a;
+ c ^= ShiftMix(Fetch64(s + 8) * k1) * k1;
+ c *= k1;
+ d ^= c;
+ s += 16;
+ l -= 16;
+ } while (l > 0);
+ }
+ a = HashLen16(a, c);
+ b = HashLen16(d, b);
+
+ uint128 result;
+ result.first = (uint64_t) (a ^ b);
+ result.second = (uint64_t) (HashLen16(b,a));
+ return result;
+}
+
+uint128 CityHash128WithSeed(const char *s, size_t len, uint128 seed) {
+ if (len < 128) {
+ return CityMurmur(s, len, seed);
+ }
+
+ // We expect len >= 128 to be the common case. Keep 56 bytes of state:
+ // v, w, x, y, and z.
+ uint128 v, w;
+ uint64_t x = Uint128Low64(seed);
+ uint64_t y = Uint128High64(seed);
+ uint64_t z = len * k1;
+ uint64_t temp;
+ v.first = Rotate(y ^ k1, 49) * k1 + Fetch64(s);
+ v.second = Rotate(v.first, 42) * k1 + Fetch64(s + 8);
+ w.first = Rotate(y + z, 35) * k1 + x;
+ w.second = Rotate(x + Fetch64(s + 88), 53) * k1;
+
+ // This is the same inner loop as CityHash64(), manually unrolled.
+ do {
+ x = Rotate(x + y + v.first + Fetch64(s + 8), 37) * k1;
+ y = Rotate(y + v.second + Fetch64(s + 48), 42) * k1;
+ x ^= w.second;
+ y += v.first + Fetch64(s + 40);
+ z = Rotate(z + w.first, 33) * k1;
+ v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
+ w = WeakHashLen32WithSeeds(s + 32, z + w.second, y + Fetch64(s + 16));
+ temp = z;
+ z = x;
+ x = temp;
+ s += 64;
+ x = Rotate(x + y + v.first + Fetch64(s + 8), 37) * k1;
+ y = Rotate(y + v.second + Fetch64(s + 48), 42) * k1;
+ x ^= w.second;
+ y += v.first + Fetch64(s + 40);
+ z = Rotate(z + w.first, 33) * k1;
+ v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
+ w = WeakHashLen32WithSeeds(s + 32, z + w.second, y + Fetch64(s + 16));
+ temp = z;
+ z = x;
+ x = temp;
+ s += 64;
+ len -= 128;
+ } while (LIKELY(len >= 128));
+ x += Rotate(v.first + z, 49) * k0;
+ z += Rotate(w.first, 37) * k0;
+ // If 0 < len < 128, hash up to 4 chunks of 32 bytes each from the end of s.
+ size_t tail_done;
+ for (tail_done = 0; tail_done < len; ) {
+ tail_done += 32;
+ y = Rotate(x + y, 42) * k0 + v.second;
+ w.first += Fetch64(s + len - tail_done + 16);
+ x = x * k0 + w.first;
+ z += w.second + Fetch64(s + len - tail_done);
+ w.second += v.first;
+ v = WeakHashLen32WithSeeds(s + len - tail_done, v.first + z, v.second);
+ }
+ // At this point our 56 bytes of state should contain more than
+ // enough information for a strong 128-bit hash. We use two
+ // different 56-byte-to-8-byte hashes to get a 16-byte final result.
+ x = HashLen16(x, v.first);
+ y = HashLen16(y + z, w.first);
+
+ uint128 result;
+ result.first = (uint64_t) (HashLen16(x + v.second, w.second) + y);
+ result.second = (uint64_t) HashLen16(x + w.second, y + v.second);
+ return result;
+}
+
+uint128 CityHash128(const char *s, size_t len) {
+ uint128 r;
+ if (len >= 16) {
+ r.first = (uint64_t) (Fetch64(s) ^ k3);
+ r.second = (uint64_t) (Fetch64(s + 8));
+
+ return CityHash128WithSeed(s + 16,
+ len - 16,
+ r);
+
+ } else if (len >= 8) {
+ r.first = (uint64_t) (Fetch64(s) ^ (len * k0));
+ r.second = (uint64_t) (Fetch64(s + len - 8) ^ k1);
+
+ return CityHash128WithSeed(NULL,
+ 0,
+ r);
+ } else {
+ r.first = (uint64_t) k0;
+ r.second = (uint64_t) k1;
+ return CityHash128WithSeed(s, len, r);
+ }
+}
+
+#ifdef __SSE4_2__
+#include "citycrc.h"
+#include <nmmintrin.h>
+
+// Requires len >= 240.
+static void CityHashCrc256Long(const char *s, size_t len,
+ uint32_t seed, uint64_t *result) {
+ uint64_t a = Fetch64(s + 56) + k0;
+ uint64_t b = Fetch64(s + 96) + k0;
+ uint64_t c = result[0] = HashLen16(b, len);
+ uint64_t d = result[1] = Fetch64(s + 120) * k0 + len;
+ uint64_t e = Fetch64(s + 184) + seed;
+ uint64_t f = seed;
+ uint64_t g = 0;
+ uint64_t h = 0;
+ uint64_t i = 0;
+ uint64_t j = 0;
+ uint64_t t = c + d;
+
+ // 240 bytes of input per iter.
+ size_t iters = len / 240;
+ len -= iters * 240;
+ do {
+#define CHUNK(multiplier, z) \
+ { \
+ uint64_t old_a = a; \
+ a = Rotate(b, 41 ^ z) * multiplier + Fetch64(s); \
+ b = Rotate(c, 27 ^ z) * multiplier + Fetch64(s + 8); \
+ c = Rotate(d, 41 ^ z) * multiplier + Fetch64(s + 16); \
+ d = Rotate(e, 33 ^ z) * multiplier + Fetch64(s + 24); \
+ e = Rotate(t, 25 ^ z) * multiplier + Fetch64(s + 32); \
+ t = old_a; \
+ } \
+ f = _mm_crc32_u64(f, a); \
+ g = _mm_crc32_u64(g, b); \
+ h = _mm_crc32_u64(h, c); \
+ i = _mm_crc32_u64(i, d); \
+ j = _mm_crc32_u64(j, e); \
+ s += 40
+
+ CHUNK(1, 1); CHUNK(k0, 0);
+ CHUNK(1, 1); CHUNK(k0, 0);
+ CHUNK(1, 1); CHUNK(k0, 0);
+ } while (--iters > 0);
+
+ while (len >= 40) {
+ CHUNK(k0, 0);
+ len -= 40;
+ }
+ if (len > 0) {
+ s = s + len - 40;
+ CHUNK(k0, 0);
+ }
+ j += i << 32;
+ a = HashLen16(a, j);
+ h += g << 32;
+ b += h;
+ c = HashLen16(c, f) + i;
+ d = HashLen16(d, e + result[0]);
+ j += e;
+ i += HashLen16(h, t);
+ e = HashLen16(a, d) + j;
+ f = HashLen16(b, c) + a;
+ g = HashLen16(j, i) + c;
+ result[0] = e + f + g + h;
+ a = ShiftMix((a + g) * k0) * k0 + b;
+ result[1] += a + result[0];
+ a = ShiftMix(a * k0) * k0 + c;
+ result[2] = a + result[1];
+ a = ShiftMix((a + e) * k0) * k0;
+ result[3] = a + result[2];
+}
+
+// Requires len < 240.
+static void CityHashCrc256Short(const char *s, size_t len, uint64_t *result) {
+ char buf[240];
+ memcpy(buf, s, len);
+ memset(buf + len, 0, 240 - len);
+ CityHashCrc256Long(buf, 240, ~(uint32_t)(len), result);
+}
+
+void CityHashCrc256(const char *s, size_t len, uint64_t *result) {
+ if (LIKELY(len >= 240)) {
+ CityHashCrc256Long(s, len, 0, result);
+ } else {
+ CityHashCrc256Short(s, len, result);
+ }
+}
+
+uint128 CityHashCrc128WithSeed(const char *s, size_t len, uint128 seed) {
+ if (len <= 900) {
+ return CityHash128WithSeed(s, len, seed);
+ } else {
+ uint64_t result[4];
+ CityHashCrc256(s, len, result);
+ uint64_t u = Uint128High64(seed) + result[0];
+ uint64_t v = Uint128Low64(seed) + result[1];
+ uint128 crc;
+ crc.first = (uint64_t) (HashLen16(u, v + result[2]));
+ crc.second = (uint64_t) (HashLen16(Rotate(v, 32), u * k0 + result[3]));
+ return crc;
+ }
+}
+
+uint128 CityHashCrc128(const char *s, size_t len) {
+ if (len <= 900) {
+ return CityHash128(s, len);
+ } else {
+ uint64_t result[4];
+ CityHashCrc256(s, len, result);
+ uint128 crc;
+ crc.first = (uint64_t) result[2];
+ crc.second = (uint64_t) result[3];
+ return crc;
+ }
+}
+
+#endif
+
diff --git a/gas/city.h b/gas/city.h
new file mode 100644
index 0000000..b3296c6
--- /dev/null
+++ b/gas/city.h
@@ -0,0 +1,83 @@
+// city.h - cityhash-c
+// CityHash on C
+// Copyright (c) 2011-2012, Alexander Nusov
+//
+// - original copyright notice -
+// Copyright (c) 2011 Google, Inc.
+//
+// Permission is hereby granted, free of charge, to any person obtaining a copy
+// of this software and associated documentation files (the "Software"), to deal
+// in the Software without restriction, including without limitation the rights
+// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+// copies of the Software, and to permit persons to whom the Software is
+// furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+// THE SOFTWARE.
+//
+// CityHash, by Geoff Pike and Jyrki Alakuijala
+//
+// This file provides a few functions for hashing strings. On x86-64
+// hardware in 2011, CityHash64() is faster than other high-quality
+// hash functions, such as Murmur. This is largely due to higher
+// instruction-level parallelism. CityHash64() and CityHash128() also perform
+// well on hash-quality tests.
+//
+// CityHash128() is optimized for relatively long strings and returns
+// a 128-bit hash. For strings more than about 2000 bytes it can be
+// faster than CityHash64().
+//
+// Functions in the CityHash family are not suitable for cryptography.
+//
+// WARNING: This code has not been tested on big-endian platforms!
+// It is known to work well on little-endian platforms that have a small penalty
+// for unaligned reads, such as current Intel and AMD moderate-to-high-end CPUs.
+//
+// By the way, for some hash functions, given strings a and b, the hash
+// of a+b is easily derived from the hashes of a and b. This property
+// doesn't hold for any hash functions in this file.
+
+#ifndef CITY_HASH_H_
+#define CITY_HASH_H_
+
+#include <stdlib.h>
+#include <stdint.h>
+
+typedef struct _uint128 uint128;
+struct _uint128 {
+ uint64_t first;
+ uint64_t second;
+};
+
+#define Uint128Low64(x) (x).first
+#define Uint128High64(x) (x).second
+
+// Hash function for a byte array.
+uint64_t CityHash64(const char *buf, size_t len);
+
+// Hash function for a byte array. For convenience, a 64-bit seed is also
+// hashed into the result.
+uint64_t CityHash64WithSeed(const char *buf, size_t len, uint64_t seed);
+
+// Hash function for a byte array. For convenience, two seeds are also
+// hashed into the result.
+uint64_t CityHash64WithSeeds(const char *buf, size_t len,
+ uint64_t seed0, uint64_t seed1);
+
+// Hash function for a byte array.
+uint128 CityHash128(const char *s, size_t len);
+
+// Hash function for a byte array. For convenience, a 128-bit seed is also
+// hashed into the result.
+uint128 CityHash128WithSeed(const char *s, size_t len, uint128 seed);
+
+#endif // CITY_HASH_H_
+
diff --git a/gas/citycrc.h b/gas/citycrc.h
new file mode 100644
index 0000000..a71baec
--- /dev/null
+++ b/gas/citycrc.h
@@ -0,0 +1,49 @@
+// citycrc.h - cityhash-c
+// CityHash on C
+// Copyright (c) 2011-2012, Alexander Nusov
+//
+// - original copyright notice -
+// Copyright (c) 2011 Google, Inc.
+//
+// Permission is hereby granted, free of charge, to any person obtaining a copy
+// of this software and associated documentation files (the "Software"), to deal
+// in the Software without restriction, including without limitation the rights
+// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+// copies of the Software, and to permit persons to whom the Software is
+// furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+// THE SOFTWARE.
+//
+// CityHash, by Geoff Pike and Jyrki Alakuijala
+//
+// This file declares the subset of the CityHash functions that require
+// _mm_crc32_u64(). See the CityHash README for details.
+//
+// Functions in the CityHash family are not suitable for cryptography.
+
+#ifndef CITY_HASH_CRC_H_
+#define CITY_HASH_CRC_H_
+
+#include "city.h"
+
+// Hash function for a byte array.
+uint128 CityHashCrc128(const char *s, size_t len);
+
+// Hash function for a byte array. For convenience, a 128-bit seed is also
+// hashed into the result.
+uint128 CityHashCrc128WithSeed(const char *s, size_t len, uint128 seed);
+
+// Hash function for a byte array. Sets result[0] ... result[3].
+void CityHashCrc256(const char *s, size_t len, uint64_t *result);
+
+#endif // CITY_HASH_CRC_H_
+
diff --git a/gas/hash.c b/gas/hash.c
index 655ddfc..cb75150 100644
--- a/gas/hash.c
+++ b/gas/hash.c
@@ -19,41 +19,51 @@
02110-1301, USA. */
/* This version of the hash table code is a wholescale replacement of
- the old hash table code, which was fairly bad. This is based on
- the hash table code in BFD, but optimized slightly for the
- assembler. The assembler does not need to derive structures that
- are stored in the hash table. Instead, it always stores a pointer.
- The assembler uses the hash table mostly to store symbols, and we
- don't need to confuse the symbol structure with a hash table
- structure. */
+ the old hash table code, which was fairly bad.
+
+ It uses an open-addressing scheme with robin-hood replacement. We aim
+ for a max load-factor of 0.8125 which is conservative. Load factors of up
+ to about 0.9 work just as well. When we hit the max loda-factor we double
+ the hash table size. It alsu uses either less memory, or only slightly
+ more depending on word size. Although we do have slack in the hash table
+ we also don't have pointers for list-chaining.
+
+ Changed to use google CityHash which means we don't require prime-number
+ sized tables any more.
+*/
#include "as.h"
#include "safe-ctype.h"
-#include "obstack.h"
+#include "city.h"
/* An entry in a hash table. */
struct hash_entry {
- /* Next entry for this hash code. */
- struct hash_entry *next;
+ /* The hash value */
+ unsigned long hash;
/* String being hashed. */
const char *string;
- /* Hash code. This is the full hash code, not the index into the
- table. */
- unsigned long hash;
/* Pointer being stored in the hash table. */
void *data;
-};
+ unsigned int string_len;
+}
+#ifdef __x86_64__
+/* no penalty for unaligned access on modern x86 so save space */
+__attribute__((packed))
+#endif
+;
/* A hash table. */
struct hash_control {
/* The hash array. */
- struct hash_entry **table;
+ struct hash_entry *table;
/* The number of slots in the hash table. */
unsigned int size;
- /* An obstack for this hash table. */
- struct obstack memory;
+ /* maximum probe length seen so far */
+ unsigned int max_probe;
+ /* number of used items */
+ unsigned int count;
#ifdef HASH_STATISTICS
/* Statistics. */
@@ -71,12 +81,12 @@ struct hash_control {
switch --reduce-memory-overheads, or set to other values by using
the --hash-size=<NUMBER> switch. */
-static unsigned long gas_hash_table_size = 65537;
+static unsigned long gas_hash_table_size = 4096;
void
set_gas_hash_table_size (unsigned long size)
{
- gas_hash_table_size = bfd_hash_set_default_size (size);
+ gas_hash_table_size = size;
}
/* Create a hash table. This return a control block. */
@@ -84,15 +94,12 @@ set_gas_hash_table_size (unsigned long size)
struct hash_control *
hash_new_sized (unsigned long size)
{
- unsigned long alloc;
struct hash_control *ret;
ret = XNEW (struct hash_control);
- obstack_begin (&ret->memory, chunksize);
- alloc = size * sizeof (struct hash_entry *);
- ret->table = (struct hash_entry **) obstack_alloc (&ret->memory, alloc);
- memset (ret->table, 0, alloc);
+ ret->table = xcalloc(size, sizeof(*ret->table));
ret->size = size;
+ ret->count = 0;
#ifdef HASH_STATISTICS
ret->lookups = 0;
@@ -117,86 +124,187 @@ hash_new (void)
void
hash_die (struct hash_control *table)
{
- obstack_free (&table->memory, 0);
+ free (table->table);
free (table);
}
-/* Look up a string in a hash table. This returns a pointer to the
- hash_entry, or NULL if the string is not in the table. If PLIST is
- not NULL, this sets *PLIST to point to the start of the list which
- would hold this hash entry. If PHASH is not NULL, this sets *PHASH
- to the hash code for KEY.
+static const char *
+insert_with_hash (struct hash_control *h,
+ const void *key, unsigned int key_len,
+ void *val, unsigned long hash);
+static int
+rehash (struct hash_control *from)
+{
+ struct hash_control to = *from;
- Each time we look up a string, we move it to the start of the list
- for its hash code, to take advantage of referential locality. */
+ to.table = NULL;
+ to.size *= 2;
-static struct hash_entry *
-hash_lookup (struct hash_control *table, const char *key, size_t len,
- struct hash_entry ***plist, unsigned long *phash)
+#if 0
+ if ( to.max_sz && to.size > to.max_sz ) {
+ return false;
+ }
+#endif
+
+ //printf("Growing from %u/%u(%u) to %u\n",
+ // from->count, from->size, from->max_probe, to.size);
+
+ to.table = xcalloc(to.size, sizeof(*to.table));
+
+ if ( !from->count ) {
+ unsigned int i;
+ for(i = 0; i < from->size; i++) {
+ if ( from->table[i].string ) {
+ insert_with_hash(&to,
+ from->table[i].string,
+ from->table[i].string_len,
+ from->table[i].data,
+ from->table[i].hash);
+ from->table[i].string = NULL;
+ from->table[i].data = NULL;
+ }
+ }
+ }
+
+ from->count = 0;
+ free(from->table);
+
+ *from = to;
+ return 1;
+}
+
+static const char *
+insert_with_hash (struct hash_control *h,
+ const void *key, unsigned int key_len,
+ void *val, unsigned long hash)
{
- unsigned long hash;
- size_t n;
- unsigned int c;
- unsigned int hindex;
- struct hash_entry **list;
- struct hash_entry *p;
- struct hash_entry *prev;
+ unsigned int i;
-#ifdef HASH_STATISTICS
- ++table->lookups;
-#endif
+ /* Aim for load-factor of 0.8125 */
+ if ( h->count >= h->size / 2
+ + h->size / 4
+ + h->size / 16 ) {
+ if ( !rehash(h) )
+ return "rehash";
+ }
+
+ for(i = 0; i < h->size; i++) {
+ unsigned int probe = (hash + i) % h->size;
+ struct hash_entry *c = &h->table[probe];
+ unsigned int disp;
+
+ /* If we found a free slot, then insert it */
+ if ( !c->string ) {
+ c->hash = hash;
+ c->string = key;
+ c->string_len = key_len;
+ c->data = val;
+ if ( i > h->max_probe ) {
+ h->max_probe = i;
+ }
+ h->count++;
+ return NULL;
+ }
- hash = 0;
- for (n = 0; n < len; n++)
- {
- c = key[n];
- hash += c + (c << 17);
- hash ^= hash >> 2;
+ /* Check for duplicates */
+ if ( c->hash == hash
+ && key_len == c->string_len
+ && !memcmp(c->string, key, key_len) ) {
+ return "exists";
}
- hash += len + (len << 17);
- hash ^= hash >> 2;
- if (phash != NULL)
- *phash = hash;
+ /* Check the probe distance of the current slot */
+ disp = (probe - (c->hash % h->size)) % h->size;
+
+ /* If the current slot is earlier in it's probe sequence than us
+ * then steal it's position and try to re-insert it later in
+ * it's probe sequence */
+ if ( disp < i ) {
+ struct hash_entry tmp;
+
+ tmp = *c;
+ c->hash = hash;
+ c->data = val;
+ c->string = key;
+ c->string_len = key_len;
+ if ( i > h->max_probe ) {
+ h->max_probe = i;
+ }
+
+ i = disp;
+ hash = tmp.hash;
+ key = tmp.string;
+ key_len = tmp.string_len;
+ val = tmp.data;
+ }
+ }
- hindex = hash % table->size;
- list = table->table + hindex;
+ return "hash-fail";
+}
- if (plist != NULL)
- *plist = list;
+static struct hash_entry *
+lookup_with_hash (struct hash_control *h, const void *key, unsigned int key_len,
+ unsigned long hv)
+{
+ unsigned int i;
- prev = NULL;
- for (p = *list; p != NULL; p = p->next)
- {
-#ifdef HASH_STATISTICS
- ++table->hash_compares;
-#endif
+ for(i = 0; i < h->size; i++) {
+ unsigned int probe = (hv + i) % h->size;
+ struct hash_entry *c = &h->table[probe];
+ unsigned int disp;
- if (p->hash == hash)
- {
-#ifdef HASH_STATISTICS
- ++table->string_compares;
-#endif
+ /* displacement is higher than longest probe sequence seen
+ * during any insert so far
+ */
+ if ( i > h->max_probe ) {
+ break;
+ }
- if (strncmp (p->string, key, len) == 0 && p->string[len] == '\0')
- {
- if (prev != NULL)
- {
- prev->next = p->next;
- p->next = *list;
- *list = p;
- }
-
- return p;
- }
- }
+ /* empty slot, if key existed, we would have inserted it here */
+ if ( NULL == c->string ) {
+ break;
+ }
- prev = p;
+ if ( c->string
+ && c->hash == hv
+ && key_len == c->string_len
+ && !memcmp(c->string, key, key_len) ) {
+ return c;
}
+ /* calculate displacement of currently probed item. */
+ disp = (probe - (c->hash % h->size)) % h->size;
+
+ /* has a lower displacement than where we're probing
+ * so the robin-hood invariant would have to be broken
+ */
+ if ( disp < i ) {
+ break;
+ }
+ }
+
return NULL;
}
+/* Works the same way as lookup except at the end we remove the item */
+#if 0
+static const char *
+remove_with_hash(struct hash_control *h, const void *key, unsigned int key_len,
+ unsigned long hv)
+{
+ struct hash_entry *c;
+
+ c = lookup_with_hash(h, key, key_len, hv);
+ if ( NULL == c )
+ return "non-existant";
+
+ /* TODO: find empty slot and shift back */
+
+ return NULL;
+}
+#endif
+
+
/* Insert an entry into a hash table. This returns NULL on success.
On error, it returns a printable string indicating the error. It
is considered to be an error if the entry already exists in the
@@ -205,26 +313,20 @@ hash_lookup (struct hash_control *table, const char *key, size_t len,
const char *
hash_insert (struct hash_control *table, const char *key, void *val)
{
- struct hash_entry *p;
- struct hash_entry **list;
unsigned long hash;
+ unsigned int len;
+ const char *ret;
- p = hash_lookup (table, key, strlen (key), &list, &hash);
- if (p != NULL)
- return "exists";
+ len = strlen(key);
+ hash = CityHash64(key, len);
+ ret = insert_with_hash(table, key, len, val, hash);
+ if ( ret )
+ return ret;
#ifdef HASH_STATISTICS
++table->insertions;
#endif
- p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
- p->string = key;
- p->hash = hash;
- p->data = val;
-
- p->next = *list;
- *list = p;
-
return NULL;
}
@@ -235,34 +337,29 @@ hash_insert (struct hash_control *table, const char *key, void *val)
const char *
hash_jam (struct hash_control *table, const char *key, void *val)
{
- struct hash_entry *p;
- struct hash_entry **list;
+ struct hash_entry *c;
unsigned long hash;
+ unsigned int len;
+ const char *ret;
- p = hash_lookup (table, key, strlen (key), &list, &hash);
- if (p != NULL)
- {
+ len = strlen(key);
+ hash = CityHash64(key, len);
+
+ c = lookup_with_hash(table, key, len, hash);
+ if ( c ) {
+ c->data = val;
#ifdef HASH_STATISTICS
- ++table->replacements;
+ ++table->replacements;
#endif
+ return NULL;
+ }
- p->data = val;
- }
- else
- {
+ ret = insert_with_hash(table, key, len, val, hash);
+ if ( ret )
+ return ret;
#ifdef HASH_STATISTICS
++table->insertions;
#endif
-
- p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
- p->string = key;
- p->hash = hash;
- p->data = val;
-
- p->next = *list;
- *list = p;
- }
-
return NULL;
}
@@ -273,22 +370,25 @@ hash_jam (struct hash_control *table, const char *key, void *val)
void *
hash_replace (struct hash_control *table, const char *key, void *value)
{
- struct hash_entry *p;
- void *ret;
+ struct hash_entry *c;
+ unsigned long hash;
+ unsigned int len;
- p = hash_lookup (table, key, strlen (key), NULL, NULL);
- if (p == NULL)
- return NULL;
+ len = strlen(key);
+ hash = CityHash64(key, len);
+ c = lookup_with_hash(table, key, len, hash);
+ if ( c ) {
+ void *old_val;
+ old_val = c->data;
+ c->data = value;
#ifdef HASH_STATISTICS
- ++table->replacements;
+ ++table->replacements;
#endif
+ return old_val;
+ }
- ret = p->data;
-
- p->data = value;
-
- return ret;
+ return NULL;
}
/* Find an entry in a hash table, returning its value. Returns NULL
@@ -297,13 +397,19 @@ hash_replace (struct hash_control *table, const char *key, void *value)
void *
hash_find (struct hash_control *table, const char *key)
{
- struct hash_entry *p;
+ struct hash_entry *c;
+ unsigned long hash;
+ unsigned int len;
- p = hash_lookup (table, key, strlen (key), NULL, NULL);
- if (p == NULL)
- return NULL;
+ len = strlen(key);
+ hash = CityHash64(key, len);
+
+ c = lookup_with_hash(table, key, len, hash);
+ if ( c ) {
+ return c->data;
+ }
- return p->data;
+ return NULL;
}
/* As hash_find, but KEY is of length LEN and is not guaranteed to be
@@ -312,13 +418,17 @@ hash_find (struct hash_control *table, const char *key)
void *
hash_find_n (struct hash_control *table, const char *key, size_t len)
{
- struct hash_entry *p;
+ struct hash_entry *c;
+ unsigned long hash;
- p = hash_lookup (table, key, len, NULL, NULL);
- if (p == NULL)
- return NULL;
+ hash = CityHash64(key, len);
- return p->data;
+ c = lookup_with_hash(table, key, len, hash);
+ if ( c ) {
+ return c->data;
+ }
+
+ return NULL;
}
/* Delete an entry from a hash table. This returns the value stored
@@ -327,26 +437,17 @@ hash_find_n (struct hash_control *table, const char *key, size_t len)
void *
hash_delete (struct hash_control *table, const char *key, int freeme)
{
- struct hash_entry *p;
- struct hash_entry **list;
-
- p = hash_lookup (table, key, strlen (key), &list, NULL);
- if (p == NULL)
- return NULL;
-
- if (p != *list)
- abort ();
-
+ static __attribute__((used)) struct hash_control *t;
+ static __attribute__((used)) const void *k;
+ static __attribute__((used)) int f;
+ t = table;
+ k = key;
+ f = freeme;
#ifdef HASH_STATISTICS
++table->deletions;
#endif
-
- *list = p->next;
-
- if (freeme)
- obstack_free (&table->memory, p);
-
- return p->data;
+ abort();
+ return NULL;
}
/* Traverse a hash table. Call the function on every entry in the
@@ -360,10 +461,8 @@ hash_traverse (struct hash_control *table,
for (i = 0; i < table->size; ++i)
{
- struct hash_entry *p;
-
- for (p = table->table[i]; p != NULL; p = p->next)
- (*pfn) (p->string, p->data);
+ if ( table->table[i].string )
+ (*pfn) (table->table[i].string, table->table[i].data);
}
}
@@ -410,7 +509,7 @@ hash_print_statistics (FILE *f ATTRIBUTE_UNUSED,
#ifdef TEST
-/* This test program is left over from the old hash table code. */
+/* This test program is left over from the old hash table code. */
/* Number of hash tables to maintain (at once) in any testing. */
#define TABLES (6)
--
2.7.4