This patch refactors 'hashtab.h' from a prime-sized double-hash
map to a power of two Robin Hood hashing regime. This enables
one to use masking rather than the modulus operator, or more
complex machinery meant to otherwise derive equivalence mod
some prime. Branching in 'htab_find_slot' was also reduced by
splitting the insert/no insert paths, alongside the insertion path
now making a stronger promise by actually inserting.
On top of these changes from v1, we additionally refine the
'hash_pointer' function to take the high bits after multiplying
the xorshifted value against an odd constant from RC5. This
tempered the benchmarks of the map both ways. cutting some of
the highs from the previous implementation whilst also mitigating
some of the lows on the same microbenchmark set as described
in v1. For reference, the tests are insertion of 20,000,000 elements,
erasing 1,000 elements from a table with 20,000,000 elements,
lookup of 1,000 elements in a table with 20,000,000 elements, both
in the case of elements existing and not existing, and lookup of
different slots that exist 1,000 times in a table of 20,000,000
elements. As with the previous time, the microbenchmarks were
performed on an AMD Ryzen 9 9950X3D 50 times each, with the
average time over all runs considered for each.
With the new map, we find insertion goes from 1468ms to 1100ms,
lookup for elements that exist ('htab_find') goes from 14989ns
to 9734ns, and lookup for slots that exist ('htab_find_slot_no_insert')
goes from 21944 to 9914ns. We do lose on deletion, going from 26us
to 28us, and fairly severely with find when the element does not
exist ('htab_find'), 1634ns to 4993ns. While the upper ends are not
as good as the v1, we do reduce the offense of the worse-performing
cases as well, and given that the change was to do with hashing,
I suspect the conjecture about probe chains from v1 to still be the
case. While obviously microbenchmarks have their limits and
Amdahl's law applies, the gains should hopefully compound over
time in larger workloads.
As additional changes from v1, the issues Thomas found regarding
the 32 bit build fail and the indirect clause should now be resolved,
via the preprocessor over trying to rely on DCE for the former and
by forcing alignment on the 'rh_entry' struct for the latter.
Built/tested x86_64-linux-gnu.
From 04ee22f0cc05de7c2e2b11126a6d090b50651c83 Mon Sep 17 00:00:00 2001
From: supers1ngular <[email protected]>
Date: Thu, 12 Nov 2026 20:38:44 -0800
Subject: [PATCH] libgomp: Refactor Hashtab
This patch refactors the libgomp hashmap from a prime sized double
hashing map into a power of two sized map utilizing Robin Hood
hashing. It additionally tweaks the API to decouple the insertion
and lookup codepaths, and handles integration where relevant.
libgomp/ChangeLog:
* config/accel/target-indirect.c (GOMP_target_map_indirect_ptr):
Whitespace fix.
(build_indirect_map): Support new API.
* hashtab.h (htab_hash): Re-declare.
(htab_eq): Ditto.
(HTAB_EMPTY_ENTRY): Defined to 0.
(HTAB_DELETED_ENTRY): Removed.
(struct htab): Remove prime and deleted members.
(enum insert_option): Removed.
(struct prime_ent): Removed.
(struct rh_entry): New Robin Hood entry struct.
(RH_EMPTY): Defined to 0.
(higher_prime_index): Removed.
(htab_expand): Adapt to account for no more tombstones.
(htab_size): Add comment.
(htab_mod_1): Removed.
(htab_mod): Ditto.
(htab_mod_m2): Ditto.
(rup2): New helper.
(htab_clear): Adjust memset for new size.
(htab_create): Adapt for power of 2. Now minimum 32 elements.
(find_empty_slot_for_expand): Remove.
(htab_find): Adapt for RH strategy.
(htab_find_slot_insert): Separate insert path out, and adapt for
RH strategy.
(htab_find_slot): Remove.
(htab_find_slot_no_insert): Separate lookup path out, and adapt
for RH strategy.
(htab_clear_slot): Adapt for RH paradigm and no more tombstones.
(hash_pointer): Add a new multiplication constant for better
distribution.
* plugin/build-target-indirect-htab.h (create_target_indirect_map):
Adapt for new API and size.
* target.c (gomp_increment_refcount): Adapt for new API.
(gomp_decrement_refcount): Adapt for new API.
* task.c (gomp_task_handle_depend): Adapt for new RH struct.
(gomp_task_run_post_handle_depend_hash): Adapt for new API.
(gomp_task_maybe_wait_for_dependencies): Adapt for new RH
struct.
(gomp_reduction_register): Adapt for new API and RH struct.
Co-Authored-By: Waffl3x <[email protected]>
---
libgomp/config/accel/target-indirect.c | 8 +-
libgomp/hashtab.h | 564 ++++++++------------
libgomp/plugin/build-target-indirect-htab.h | 6 +-
libgomp/target.c | 6 +-
libgomp/task.c | 100 ++--
5 files changed, 299 insertions(+), 385 deletions(-)
diff --git a/libgomp/config/accel/target-indirect.c b/libgomp/config/accel/target-indirect.c
index 475cd528a49..e9dac951cc9 100644
--- a/libgomp/config/accel/target-indirect.c
+++ b/libgomp/config/accel/target-indirect.c
@@ -82,7 +82,6 @@ GOMP_target_map_indirect_ptr (void *ptr)
return ptr;
assert (GOMP_INDIRECT_ADDR_HMAP);
-
hash_entry_type element;
SET_INDIRECT_HOST_ADDR (element, ptr);
hash_entry_type entry = htab_find ((htab_t) GOMP_INDIRECT_ADDR_HMAP, element);
@@ -113,9 +112,10 @@ build_indirect_map (void)
{
hash_entry_type element;
SET_INDIRECT_ADDRS (element, *map_entry, *(map_entry + 1));
- hash_entry_type *slot = htab_find_slot (&indirect_htab, element,
- INSERT);
- *slot = element;
+ struct rh_entry *ret = htab_find_slot_no_insert (&indirect_htab, element);
+ if (ret != NULL)
+ htab_clear_slot (indirect_htab, ret);
+ htab_find_slot_insert (&indirect_htab, element);
}
}
diff --git a/libgomp/hashtab.h b/libgomp/hashtab.h
index b3462aa09e8..86e15295a85 100644
--- a/libgomp/hashtab.h
+++ b/libgomp/hashtab.h
@@ -24,433 +24,317 @@
see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
<http://www.gnu.org/licenses/>. */
-/* The hash table code copied from include/hashtab.[hc] and adjusted,
- so that the hash table entries are in the flexible array at the end
- of the control structure, no callbacks are used and the elements in the
- table are of the hash_entry_type type.
- Before including this file, define hash_entry_type type and
- htab_alloc and htab_free functions. After including it, define
- htab_hash and htab_eq inline functions. */
+/* The hash map here is an adaption of the previous libgomp version, itself
+ an iteration of an implementation from libiberty, made to retain a
+ similar interface and modernize the internals. Previously used was a
+ prime-sized double hash table. Now, we use a power of two sized table
+ using linear probing and Robin Hood hashing.
-/* This package implements basic hash table functionality. It is possible
- to search for an entry, create an entry and destroy an entry.
+ This header implements basic hash table functionality. One can search
+ for an entry, create an entry, and delete an entry.
Elements in the table are generic pointers.
- The size of the table is not fixed; if the occupancy of the table
- grows too high the hash table will be expanded.
+ The size of the table is variant, but will always be a power of two.
+ The table will appropriately grow according to the defined policy of:
- The abstract data implementation is based on generalized Algorithm D
- from Knuth's book "The art of computer programming". Hash table is
- expanded by creation of new hash table and transferring elements from
- the old table to the new table. */
+ If the table is at over half occupancy, expand.
-/* The type for a hash code. */
-typedef unsigned int hashval_t;
-
-static inline hashval_t htab_hash (hash_entry_type);
-static inline bool htab_eq (hash_entry_type, hash_entry_type);
-
-/* This macro defines reserved value for empty table entry. */
-
-#define HTAB_EMPTY_ENTRY ((hash_entry_type) 0)
+ The table will always maintain the "Robin Hood" invariant, that is:
-/* This macro defines reserved value for table entry which contained
- a deleted element. */
+ If a slot is found during probing that has a smaller distance from
+ home than the current probe, it is safe to return, since if the key
+ did exist, it would have a probe distance of at most the probed
+ entries.
-#define HTAB_DELETED_ENTRY ((hash_entry_type) 1)
+ This was done to minimize probe chains and enforce consistency in
+ lookups. Further, it improves expected probe chain lengths in the
+ worst case to theta (logn) when paired with a distance check.
-/* Hash tables are of the following type. The structure
- (implementation) of this type is not needed for using the hash
- tables. All work with hash table should be executed only through
- functions mentioned below. The size of this structure is subject to
- change. */
+ Do note, however, that we do not necessarily always observe this
+ early exit in practice, as the additional branch can impact performance
+ negatively. As such, we have a hybrid design here, in which we preserve
+ the Robin Hood invariant, but rather use typical linear probing without
+ checking for the case of an early return. This, in theory, returns us
+ back to the typical worst case, but in practice, we still usually get the
+ benefit. */
-struct htab {
- /* Current size (in entries) of the hash table. */
- size_t size;
+/* In order to properly use the map, we inherit the same requirements
+ as the previous map.
- /* Current number of elements including also deleted elements. */
- size_t n_elements;
+ Prior to including the header:
+ 1. You must define the type of hash_entry_type
+ 2. You must define the htab_alloc inline function
+ 3. You must define the htab_free inline function
- /* Current number of deleted elements in the table. */
- size_t n_deleted;
+ After including the header:
+ 1. You must define the htab_hash inline function
+ 2. You must define the htab_eq inline function. */
- /* Current size (in entries) of the hash table, as an index into the
- table of primes. */
- unsigned int size_prime_index;
-
- /* Table itself. */
- hash_entry_type entries[];
-};
-
-typedef struct htab *htab_t;
-
-/* An enum saying whether we insert into the hash table or not. */
-enum insert_option {NO_INSERT, INSERT};
+/* The type for the hash code. */
+typedef unsigned int hashval_t;
-/* Table of primes and multiplicative inverses.
- Note that these are not minimally reduced inverses. Unlike when generating
- code to divide by a constant, we want to be able to use the same algorithm
- all the time. All of these inverses (are implied to) have bit 32 set.
+static inline hashval_t htab_hash (hash_entry_type);
+static inline bool htab_eq (hash_entry_type, hash_entry_type);
- For the record, the function that computed the table is in
- libiberty/hashtab.c. */
+/* Reserves 0 to define empty table entry. */
+#define HTAB_EMPTY_ENTRY ((hash_entry_type) 0)
-struct prime_ent
+/* Struct that contains the actual entry and Robin Hood metadata. */
+struct __attribute__ ((aligned (16))) rh_entry
{
- hashval_t prime;
- hashval_t inv;
- hashval_t inv_m2; /* inverse of prime-2 */
- hashval_t shift;
-};
-
-static struct prime_ent const prime_tab[] = {
- { 7, 0x24924925, 0x9999999b, 2 },
- { 13, 0x3b13b13c, 0x745d1747, 3 },
- { 31, 0x08421085, 0x1a7b9612, 4 },
- { 61, 0x0c9714fc, 0x15b1e5f8, 5 },
- { 127, 0x02040811, 0x0624dd30, 6 },
- { 251, 0x05197f7e, 0x073260a5, 7 },
- { 509, 0x01824366, 0x02864fc8, 8 },
- { 1021, 0x00c0906d, 0x014191f7, 9 },
- { 2039, 0x0121456f, 0x0161e69e, 10 },
- { 4093, 0x00300902, 0x00501908, 11 },
- { 8191, 0x00080041, 0x00180241, 12 },
- { 16381, 0x000c0091, 0x00140191, 13 },
- { 32749, 0x002605a5, 0x002a06e6, 14 },
- { 65521, 0x000f00e2, 0x00110122, 15 },
- { 131071, 0x00008001, 0x00018003, 16 },
- { 262139, 0x00014002, 0x0001c004, 17 },
- { 524287, 0x00002001, 0x00006001, 18 },
- { 1048573, 0x00003001, 0x00005001, 19 },
- { 2097143, 0x00004801, 0x00005801, 20 },
- { 4194301, 0x00000c01, 0x00001401, 21 },
- { 8388593, 0x00001e01, 0x00002201, 22 },
- { 16777213, 0x00000301, 0x00000501, 23 },
- { 33554393, 0x00001381, 0x00001481, 24 },
- { 67108859, 0x00000141, 0x000001c1, 25 },
- { 134217689, 0x000004e1, 0x00000521, 26 },
- { 268435399, 0x00000391, 0x000003b1, 27 },
- { 536870909, 0x00000019, 0x00000029, 28 },
- { 1073741789, 0x0000008d, 0x00000095, 29 },
- { 2147483647, 0x00000003, 0x00000007, 30 },
- /* Avoid "decimal constant so large it is unsigned" for 4294967291. */
- { 0xfffffffb, 0x00000006, 0x00000008, 31 }
+ hash_entry_type entry;
+ uint32_t dist;
};
-/* The following function returns an index into the above table of the
- nearest prime number which is greater than N, and near a power of two. */
+/* Defines RH_EMPTY to 0. */
+#define RH_EMPTY HTAB_EMPTY_ENTRY
-static unsigned int
-higher_prime_index (unsigned long n)
+/* Struct containing table and associated metadata.
+ size: Current table size.
+ n_elements: Number of elements that have been inserted.
+ entries: Table. */
+struct htab
{
- unsigned int low = 0;
- unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]);
-
- while (low != high)
- {
- unsigned int mid = low + (high - low) / 2;
- if (n > prime_tab[mid].prime)
- low = mid + 1;
- else
- high = mid;
- }
-
- /* If we've run out of primes, abort. */
- if (n > prime_tab[low].prime)
- abort ();
+ size_t size;
+ size_t n_elements;
+ struct rh_entry entries[];
+};
- return low;
-}
-/* Return the current size of given hash table. */
+typedef struct htab *htab_t;
+/* Forward declaration. */
+static htab_t htab_expand (htab_t htab);
+/* Return current table size. */
static inline size_t
htab_size (htab_t htab)
{
return htab->size;
}
-/* Return the current number of elements in given hash table. */
-
+/* Return current number of elements in the table. */
static inline size_t
htab_elements (htab_t htab)
{
- return htab->n_elements - htab->n_deleted;
-}
-
-/* Return X % Y. */
-
-static inline hashval_t
-htab_mod_1 (hashval_t x, hashval_t y, hashval_t inv, int shift)
-{
- /* The multiplicative inverses computed above are for 32-bit types, and
- requires that we be able to compute a highpart multiply. */
- if (sizeof (hashval_t) * __CHAR_BIT__ <= 32)
- {
- hashval_t t1, t2, t3, t4, q, r;
-
- t1 = ((unsigned long long)x * inv) >> 32;
- t2 = x - t1;
- t3 = t2 >> 1;
- t4 = t1 + t3;
- q = t4 >> shift;
- r = x - (q * y);
-
- return r;
- }
-
- /* Otherwise just use the native division routines. */
- return x % y;
-}
-
-/* Compute the primary hash for HASH given HTAB's current size. */
-
-static inline hashval_t
-htab_mod (hashval_t hash, htab_t htab)
-{
- const struct prime_ent *p = &prime_tab[htab->size_prime_index];
- return htab_mod_1 (hash, p->prime, p->inv, p->shift);
+ return htab->n_elements;
}
-/* Compute the secondary hash for HASH given HTAB's current size. */
-
-static inline hashval_t
-htab_mod_m2 (hashval_t hash, htab_t htab)
+/* Helper function to determine the next largest power of two
+ from an unknown, non-zero value of an unsigned integral type. */
+static inline size_t
+rup2 (size_t num)
{
- const struct prime_ent *p = &prime_tab[htab->size_prime_index];
- return 1 + htab_mod_1 (hash, p->prime - 2, p->inv_m2, p->shift);
+ num -= 1;
+ num |= (num >> 1);
+ num |= (num >> 2);
+ num |= (num >> 4);
+ num |= (num >> 8);
+ num |= (num >> 16);
+#if SIZE_MAX == UINT64_MAX
+ num |= (num >> 32);
+#endif
+ return num + 1;
}
+/* Clears the table. */
static inline htab_t
htab_clear (htab_t htab)
{
htab->n_elements = 0;
- htab->n_deleted = 0;
- memset (htab->entries, 0, htab->size * sizeof (hash_entry_type));
+ memset (htab->entries, 0, htab->size * sizeof (struct rh_entry));
return htab;
}
-/* Create hash table of size SIZE. */
-
+/* Creates a new table of power of two size not less than 32.
+ This was done to preclude very early grow calls, while still
+ choosing a number that allows quick traversals. */
static htab_t
htab_create (size_t size)
{
- htab_t result;
- unsigned int size_prime_index;
-
- size_prime_index = higher_prime_index (size);
- size = prime_tab[size_prime_index].prime;
-
- result = (htab_t) htab_alloc (sizeof (struct htab)
- + size * sizeof (hash_entry_type));
+ size = (size < 32) ? 32 : rup2 (size);
+ htab_t result = (htab_t) htab_alloc (sizeof (struct htab)
+ + (size * sizeof (struct rh_entry)));
result->size = size;
- result->size_prime_index = size_prime_index;
return htab_clear (result);
}
-/* Similar to htab_find_slot, but without several unwanted side effects:
- - Does not call htab_eq when it finds an existing entry.
- - Does not change the count of elements in the hash table.
- This function also assumes there are no deleted entries in the table.
- HASH is the hash value for the element to be inserted. */
-
-static hash_entry_type *
-find_empty_slot_for_expand (htab_t htab, hashval_t hash)
+/* Find an element, if it is in the table. */
+static hash_entry_type
+htab_find (htab_t htab, const hash_entry_type elem)
{
- hashval_t index = htab_mod (hash, htab);
- size_t size = htab_size (htab);
- hash_entry_type *slot = htab->entries + index;
- hashval_t hash2;
-
- if (*slot == HTAB_EMPTY_ENTRY)
- return slot;
- else if (*slot == HTAB_DELETED_ENTRY)
- abort ();
+ size_t mask = htab->size - 1;
+ hashval_t idx = htab_hash (elem) & mask;
+ struct rh_entry *slot = &htab->entries[idx];
+ size_t dist = 0;
- hash2 = htab_mod_m2 (hash, htab);
- for (;;)
+ while (1)
{
- index += hash2;
- if (index >= size)
- index -= size;
-
- slot = htab->entries + index;
- if (*slot == HTAB_EMPTY_ENTRY)
- return slot;
- else if (*slot == HTAB_DELETED_ENTRY)
- abort ();
+ if (!slot->entry || htab_eq (slot->entry, elem))
+ return slot->entry;
+ if (slot->entry && dist > slot->dist)
+ return HTAB_EMPTY_ENTRY;
+ idx = (idx + 1) & mask;
+ slot = &htab->entries[idx];
}
}
-/* The following function changes size of memory allocated for the
- entries and repeatedly inserts the table elements. The occupancy
- of the table after the call will be about 50%. Naturally the hash
- table must already exist. Remember also that the place of the
- table entries is changed. */
-
-static htab_t
-htab_expand (htab_t htab)
-{
- htab_t nhtab;
- hash_entry_type *olimit;
- hash_entry_type *p;
- size_t osize, elts;
-
- osize = htab->size;
- olimit = htab->entries + osize;
- elts = htab_elements (htab);
-
- /* Resize only when table after removal of unused elements is either
- too full or too empty. */
- if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
- nhtab = htab_create (elts * 2);
- else
- nhtab = htab_create (osize - 1);
- nhtab->n_elements = htab->n_elements - htab->n_deleted;
-
- p = htab->entries;
- do
- {
- hash_entry_type x = *p;
-
- if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
- *find_empty_slot_for_expand (nhtab, htab_hash (x)) = x;
-
- p++;
- }
- while (p < olimit);
-
- htab_free (htab);
- return nhtab;
-}
-
-/* This function searches for a hash table entry equal to the given
- element. It cannot be used to insert or delete an element. */
-
-static hash_entry_type
-htab_find (htab_t htab, const hash_entry_type element)
+/* The insertion codepath. Inserts an element while maintaining
+ the Robin Hood invariant. */
+static struct rh_entry *
+htab_find_slot_insert (htab_t *htabp, const hash_entry_type elem)
{
- hashval_t index, hash2, hash = htab_hash (element);
- size_t size;
- hash_entry_type entry;
-
- size = htab_size (htab);
- index = htab_mod (hash, htab);
+ htab_t htab = *htabp;
+ if (htab->n_elements * 2 >= htab->size)
+ htab = *htabp = htab_expand (htab);
+ const size_t mask = htab->size - 1;
+ hashval_t idx = htab_hash (elem) & mask;
- entry = htab->entries[index];
- if (entry == HTAB_EMPTY_ENTRY
- || (entry != HTAB_DELETED_ENTRY && htab_eq (entry, element)))
- return entry;
+ struct rh_entry cur;
+ cur.entry = elem;
+ cur.dist = 0;
- hash2 = htab_mod_m2 (hash, htab);
- for (;;)
+ while (1)
{
- index += hash2;
- if (index >= size)
- index -= size;
-
- entry = htab->entries[index];
- if (entry == HTAB_EMPTY_ENTRY
- || (entry != HTAB_DELETED_ENTRY && htab_eq (entry, element)))
- return entry;
+ struct rh_entry *slot = &htab->entries[idx];
+ uint32_t slot_dist = slot->dist;
+
+ if (!slot->entry)
+ {
+ *slot = cur;
+ htab->n_elements++;
+ return slot;
+ }
+ if (htab_eq (slot->entry, elem))
+ return slot;
+ if (slot_dist < cur.dist)
+ {
+ struct rh_entry tmp = *slot;
+ *slot = cur;
+ cur = tmp;
+ struct rh_entry *ret = slot;
+ idx = (idx + 1) & mask;
+ ++cur.dist;
+ while (1)
+ {
+ slot = &htab->entries[idx];
+ if (slot->entry == RH_EMPTY)
+ {
+ *slot = cur;
+ htab->n_elements++;
+ return ret;
+ }
+ if (slot->dist < cur.dist)
+ {
+ struct rh_entry tmp = *slot;
+ *slot = cur;
+ cur = tmp;
+ }
+ idx = (idx + 1) & mask;
+ ++cur.dist;
+ }
+ }
+ idx = (idx + 1) & mask;
+ ++cur.dist;
}
}
-/* This function searches for a hash table slot containing an entry
- equal to the given element. To delete an entry, call this with
- insert=NO_INSERT, then call htab_clear_slot on the slot returned
- (possibly after doing some checks). To insert an entry, call this
- with insert=INSERT, then write the value you want into the returned
- slot. */
+/* The codepaths are entirely different for the NO_INSERT and for the
+ INSERT cases, and as such, they were made into separate functions
+ to mitigate unnecessary logic/branching.
+
+ We do presume that the caller knows the element to be within the map,
+ as this is the use case in libgomp thus far. Otherwise, this does not
+ maintain the RH invariant, so probing may continue longer than
+ one would anticipate. For other uses, consider htab_find.
-static hash_entry_type *
-htab_find_slot (htab_t *htabp, const hash_entry_type element,
- enum insert_option insert)
+ Unused attribute applied for target.c. */
+__attribute__ ((unused))
+static struct rh_entry *
+htab_find_slot_no_insert (htab_t *htabp, const hash_entry_type elem)
{
- hash_entry_type *first_deleted_slot;
- hashval_t index, hash2, hash = htab_hash (element);
- size_t size;
- hash_entry_type entry;
htab_t htab = *htabp;
+ const size_t mask = htab->size - 1;
+ hashval_t idx = htab_hash (elem) & mask;
- size = htab_size (htab);
- if (insert == INSERT && size * 3 <= htab->n_elements * 4)
- {
- htab = *htabp = htab_expand (htab);
- size = htab_size (htab);
- }
-
- index = htab_mod (hash, htab);
-
- first_deleted_slot = NULL;
-
- entry = htab->entries[index];
- if (entry == HTAB_EMPTY_ENTRY)
- goto empty_entry;
- else if (entry == HTAB_DELETED_ENTRY)
- first_deleted_slot = &htab->entries[index];
- else if (htab_eq (entry, element))
- return &htab->entries[index];
-
- hash2 = htab_mod_m2 (hash, htab);
- for (;;)
+ struct rh_entry *slot = &htab->entries[idx];
+ while (slot->entry != RH_EMPTY)
{
- index += hash2;
- if (index >= size)
- index -= size;
-
- entry = htab->entries[index];
- if (entry == HTAB_EMPTY_ENTRY)
- goto empty_entry;
- else if (entry == HTAB_DELETED_ENTRY)
- {
- if (!first_deleted_slot)
- first_deleted_slot = &htab->entries[index];
- }
- else if (htab_eq (entry, element))
- return &htab->entries[index];
+ if (htab_eq (slot->entry, elem))
+ return slot;
+ idx = (idx + 1) & mask;
+ slot = &htab->entries[idx];
}
+ return NULL;
+}
- empty_entry:
- if (insert == NO_INSERT)
- return NULL;
- if (first_deleted_slot)
+/* Handles expansion/shrink logic
+ Allocates a new map of the appropriate size, then
+ populates it by iterating through the previous.
+ Shrink/growth policy are defined by doubling or
+ halving. Meant to be an internal helper. */
+static htab_t
+htab_expand (htab_t htab)
+{
+ size_t osize = htab->size;
+ /* We only ever call to grow. */
+ htab_t nhtab = htab_create (osize * 2);
+ for (size_t i = 0; i < osize; ++i)
{
- htab->n_deleted--;
- *first_deleted_slot = HTAB_EMPTY_ENTRY;
- return first_deleted_slot;
+ struct rh_entry *exp = &htab->entries[i];
+ if (exp->entry)
+ htab_find_slot_insert (&nhtab, exp->entry);
}
-
- htab->n_elements++;
- return &htab->entries[index];
+ htab_free (htab);
+ return nhtab;
}
-/* This function clears a specified slot in a hash table. It is
- useful when you've already done the lookup and don't want to do it
- again. */
-
+/* Deletion logic. To be called on a rh_entry slot.
+ Performs deletion whilst maintaining the Robin
+ Hood invariant. */
static inline void
-htab_clear_slot (htab_t htab, hash_entry_type *slot)
+htab_clear_slot (htab_t htab, struct rh_entry *slot)
{
- if (slot < htab->entries || slot >= htab->entries + htab_size (htab)
- || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
+ size_t idx = slot - htab->entries;
+ if (idx >= htab->size || slot->entry == RH_EMPTY)
abort ();
-
- *slot = HTAB_DELETED_ENTRY;
- htab->n_deleted++;
+ size_t mask = htab->size - 1;
+ while (1)
+ {
+ size_t next = (idx + 1) & mask;
+ struct rh_entry *nentry = &htab->entries[next];
+ if (nentry->entry == RH_EMPTY || nentry->dist == 0)
+ {
+ htab->entries[idx].entry = RH_EMPTY;
+ htab->entries[idx].dist = 0;
+ break;
+ }
+ htab->entries[idx] = *nentry;
+ --(htab->entries[idx].dist);
+ idx = next;
+ }
+ --(htab->n_elements);
}
-/* Returns a hash code for pointer P. Simplified version of evahash */
-
+/* Default pointer hash function. */
+/* Microbenchmarking reveals that this variant of the
+ pointer hash from the previous implementation seems
+ to temper performance, in both ways. While we become
+ marginally slower on lookups than with the old pointer
+ hash, we also tend to erase faster, so we get more
+ balanced behavior. */
static inline hashval_t
hash_pointer (const void *p)
{
uintptr_t v = (uintptr_t) p;
if (sizeof (v) > sizeof (hashval_t))
- v ^= v >> (sizeof (uintptr_t) / 2 * __CHAR_BIT__);
+ {
+ v ^= v >> (sizeof (uintptr_t) / 2 * __CHAR_BIT__);
+ /* From RC5. */
+ v *= 0x9E3779B97F4A7C15;
+ v = v >> (sizeof (uintptr_t) / 2 * __CHAR_BIT__);
+ }
return v;
}
diff --git a/libgomp/plugin/build-target-indirect-htab.h b/libgomp/plugin/build-target-indirect-htab.h
index a13f9717bf7..3a5bb77dda8 100644
--- a/libgomp/plugin/build-target-indirect-htab.h
+++ b/libgomp/plugin/build-target-indirect-htab.h
@@ -73,11 +73,9 @@ create_target_indirect_map (size_t *h_size, size_t count,
for (int i = 0; i < count; i++)
{
SET_INDIRECT_ADDRS (element, host_addrs[i], device_addrs[i]);
- hash_entry_type *slot = htab_find_slot (&indirect_htab, element,
- INSERT);
- *slot = element;
+ htab_find_slot_insert (&indirect_htab, element);
}
*h_size = (sizeof (struct htab)
- + htab_size (indirect_htab) * sizeof (hash_entry_type));
+ + htab_size (indirect_htab) * sizeof (struct rh_entry));
return (void*) indirect_htab;
}
diff --git a/libgomp/target.c b/libgomp/target.c
index 2bd1d573de4..76cd6d0f57f 100644
--- a/libgomp/target.c
+++ b/libgomp/target.c
@@ -513,8 +513,7 @@ gomp_increment_refcount (splay_tree_key k, htab_t *refcount_set)
{
if (htab_find (*refcount_set, refcount_ptr))
return;
- uintptr_t **slot = htab_find_slot (refcount_set, refcount_ptr, INSERT);
- *slot = refcount_ptr;
+ htab_find_slot_insert (refcount_set, refcount_ptr);
}
*refcount_ptr += 1;
@@ -572,8 +571,7 @@ gomp_decrement_refcount (splay_tree_key k, htab_t *refcount_set, bool delete_p,
goto end;
}
- uintptr_t **slot = htab_find_slot (refcount_set, refcount_ptr, INSERT);
- *slot = refcount_ptr;
+ htab_find_slot_insert (refcount_set, refcount_ptr);
new_encountered_refcount = true;
}
else
diff --git a/libgomp/task.c b/libgomp/task.c
index 9ff300d576a..fdc48209194 100644
--- a/libgomp/task.c
+++ b/libgomp/task.c
@@ -280,19 +280,20 @@ gomp_task_handle_depend (struct gomp_task *task, struct gomp_task *parent,
task->depend[0].redundant_out = false;
if (parent->depend_hash)
{
- /* Inlined htab_traverse + htab_clear. All newer siblings can
- just depend on this task. Add dependencies on all previous
+ /* Inlined traversal of the hashmap + htab_clear. All newer siblings
+ can just depend on this task. Add dependencies on all previous
sibling tasks with dependencies and make them redundant and
clear the hash table. */
- hash_entry_type *slot = &parent->depend_hash->entries[0];
- hash_entry_type *end = slot + htab_size (parent->depend_hash);
+ struct rh_entry *slot = &parent->depend_hash->entries[0];
+ struct rh_entry *end = slot + htab_size (parent->depend_hash);
for (; slot != end; ++slot)
{
- if (*slot == HTAB_EMPTY_ENTRY)
+ /* If the slot is empty, just skip it. */
+ if (slot->entry == HTAB_EMPTY_ENTRY)
continue;
- if (*slot != HTAB_DELETED_ENTRY)
+ else
{
- for (ent = *slot; ent; ent = ent->next)
+ for (ent = slot->entry; ent; ent = ent->next)
{
struct gomp_task *tsk = ent->task;
@@ -327,6 +328,8 @@ gomp_task_handle_depend (struct gomp_task *task, struct gomp_task *parent,
sizeof (struct gomp_dependers_vec)
+ (tsk->dependers->allocated
* sizeof (struct gomp_task *)));
+ /* gomp_realloc will fatally error on fail, no need
+ to check for NULL. */
}
tsk->dependers->elem[tsk->dependers->n_elem++] = task;
task->num_dependees++;
@@ -337,20 +340,24 @@ gomp_task_handle_depend (struct gomp_task *task, struct gomp_task *parent,
ent = ent->next;
}
}
- *slot = HTAB_EMPTY_ENTRY;
+ /* We can still keep the inline deletion, as we are traversing
+ the whole map, and clearing it unconditionally. So,
+ maintenance of the Robin Hood invariant is overhead in this
+ case. Similarly, we don't have to worry about the size
+ of the table changing and thus thrashing the references,
+ since we aren't modifying n_elements. */
+ slot->entry = HTAB_EMPTY_ENTRY;
+ slot->dist = 0;
}
if (htab_size (parent->depend_hash) <= 32)
- {
- parent->depend_hash->n_elements = 0;
- parent->depend_hash->n_deleted = 0;
- }
+ parent->depend_hash->n_elements = 0;
else
{
/* Shrink the hash table if it would be too large.
We don't want to walk e.g. megabytes of empty hash
table for every depend(inout: omp_all_memory). */
- free (parent->depend_hash);
- parent->depend_hash = htab_create (12);
+ htab_free (parent->depend_hash);
+ parent->depend_hash = htab_create (31);
}
}
parent->depend_all_memory = task;
@@ -358,7 +365,7 @@ gomp_task_handle_depend (struct gomp_task *task, struct gomp_task *parent,
}
task->depend_count = ndepend;
if (parent->depend_hash == NULL)
- parent->depend_hash = htab_create (2 * ndepend > 12 ? 2 * ndepend : 12);
+ parent->depend_hash = htab_create (2 * ndepend > 32 ? 2 * ndepend : 31);
for (i = 0; i < ndepend; i++)
{
task->depend[i].next = NULL;
@@ -367,8 +374,23 @@ gomp_task_handle_depend (struct gomp_task *task, struct gomp_task *parent,
task->depend[i].redundant = false;
task->depend[i].redundant_out = false;
- hash_entry_type *slot = htab_find_slot (&parent->depend_hash,
- &task->depend[i], INSERT);
+ /* Below is a bit of a kludge in order to preserve semantics despite
+ API differences. Previously, using the insert option would not
+ actually guarantee insertion, trusting the caller to
+ manually assign the element afterwards. The new API automatically
+ performs the insertion. Since actual insertion was delayed
+ previously, we need to first check to see if the element exists,
+ and if it doesn't, then we insert it and set it to null, then keep
+ track of the entry reference and assign later. */
+ struct rh_entry *entry = htab_find_slot_no_insert (&parent->depend_hash,
+ &task->depend[i]);
+ if (!entry)
+ {
+ entry = htab_find_slot_insert (&parent->depend_hash,
+ &task->depend[i]);
+ entry->entry = NULL;
+ }
+ hash_entry_type *slot = &entry->entry;
hash_entry_type out = NULL, last = NULL;
if (*slot)
{
@@ -1360,15 +1382,16 @@ gomp_task_run_post_handle_depend_hash (struct gomp_task *child_task)
child_task->depend[i].prev->next = child_task->depend[i].next;
else
{
- hash_entry_type *slot
- = htab_find_slot (&parent->depend_hash, &child_task->depend[i],
- NO_INSERT);
+ struct rh_entry *entry = htab_find_slot_no_insert (
+ &parent->depend_hash,
+ &child_task->depend[i]);
+ hash_entry_type *slot = &entry->entry;
if (*slot != &child_task->depend[i])
abort ();
if (child_task->depend[i].next)
*slot = child_task->depend[i].next;
else
- htab_clear_slot (parent->depend_hash, slot);
+ htab_clear_slot (parent->depend_hash, entry);
}
}
}
@@ -2048,17 +2071,17 @@ gomp_task_maybe_wait_for_dependencies (void **depend)
if (__builtin_expect (elem.addr == NULL && !elem.is_in, false))
{
size_t size = htab_size (task->depend_hash);
- if (htab_elements (task->depend_hash) * 8 < size && size > 32)
+ if (htab_elements (task->depend_hash) * 8 > size && size > 32)
htab_expand (task->depend_hash);
-
/* depend(inout: omp_all_memory) - depend on all previous
sibling tasks that do have dependencies. Inlined
htab_traverse. */
- hash_entry_type *slot = &task->depend_hash->entries[0];
- hash_entry_type *end = slot + htab_size (task->depend_hash);
- for (; slot != end; ++slot)
+ struct rh_entry *entry = &task->depend_hash->entries[0];
+ struct rh_entry *end = entry + htab_size (task->depend_hash);
+ for (; entry != end; ++entry)
{
- if (*slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
+ hash_entry_type *slot = &entry->entry;
+ if (*slot == HTAB_EMPTY_ENTRY)
continue;
for (ent = *slot; ent; ent = ent->next)
{
@@ -2493,16 +2516,27 @@ gomp_reduction_register (uintptr_t *data, uintptr_t *old, uintptr_t *orig,
new_htab = htab_create (total_cnt);
if (old_htab)
{
- /* Copy old hash table, like in htab_expand. */
- hash_entry_type *p, *olimit;
+ /* Copy old hash table. We intentionally copy over the number of
+ elements from the old table, such as to not need to repeatedly
+ expand by setting it to zero and reinserting. We manage the
+ increment done in 'htab_find_slot_insert' by decrementing before
+ insertion. Since we never shrink the map, only expand it, this
+ prevents growing it mid-copy in the case of being on the
+ boundary. */
+ struct rh_entry *p, *olimit;
new_htab->n_elements = htab_elements (old_htab);
olimit = old_htab->entries + old_htab->size;
p = old_htab->entries;
do
{
- hash_entry_type x = *p;
- if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
- *find_empty_slot_for_expand (new_htab, htab_hash (x)) = x;
+ struct rh_entry x = *p;
+ if (x.entry)
+ {
+ /* This will never wrap, since it is only triggered if an
+ entry exists. Thus, 'n_elements' is necessarily >= 1. */
+ new_htab->n_elements = new_htab->n_elements - 1;
+ htab_find_slot_insert (&new_htab, x.entry);
+ }
p++;
}
while (p < olimit);
@@ -2521,7 +2555,7 @@ gomp_reduction_register (uintptr_t *data, uintptr_t *old, uintptr_t *orig,
a pointer. Hide the cast from the compiler. */
hash_entry_type n;
__asm ("" : "=g" (n) : "0" (p));
- *htab_find_slot (&new_htab, n, INSERT) = n;
+ htab_find_slot_insert (&new_htab, n);
}
if (d[4] == (uintptr_t) old)
break;
--
2.55.0
