mesa: Convert the hash table for GL object ids to the open-addressing hash.

The previous 1023-entry chaining hash table never resized, so it was very
inefficient when there were many objects live.  While one could have an even
more efficient implementation than this (keep an array for genned names with
packed IDs, or take advantage of the fact that key == hash or key ==
*(uint32_t *)data to store less data), this is fairly fast, and I want a nice
replacement hash table for other parts of Mesa, too.

It improves Minecraft performance 12.3% +/- 1.4% (n=9), dropping hash lookups
from 8% of the profile to 0.5%.

I also tested cairo-gl, which should be a pessimal workload for this hash
table: around 247000 FBOs created and destroyed, only around 65 live at any
time, and few lookups of them between creation and destruction.  No
statistically significant performance difference at n=76 (mean 20.3/20.4
seconds, sd 2.8/3.2 seconds).  If I remove the >20 seconds outliers that
appear to be due to thermal throttling, there's possibly a .97% +/- 0.31%
performance win (n=61/59).  The choice of cutoff for outliers feels a lot like
cooking the data, but I've gone through this process 3 times for minor
iterations of the code with the same conclusion each time.

Reviewed-by: Brian Paul <[email protected]>
Acked-by: Chad Versace <[email protected]>
Acked-by: Kenneth Graunke <[email protected]> (v1)

2 files changed, 113 insertions, 262 deletions

diff --git a/src/mesa/main/hash.c b/src/mesa/main/hash.c
index 61c369a80cd..8c763e20a90 100644
--- a/src/mesa/main/hash.c
+++ b/src/mesa/main/hash.c
@@ -34,40 +34,75 @@
  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  */
 
-
 #include "glheader.h"
 #include "imports.h"
 #include "glapi/glthread.h"
 #include "hash.h"
-
-
-#define TABLE_SIZE 1023  /**< Size of lookup table/array */
-
-#define HASH_FUNC(K)  ((K) % TABLE_SIZE)
-
+#include "hash_table.h"
 
 /**
- * An entry in the hash table.  
+ * Magic GLuint object name that gets stored outside of the struct hash_table.
+ *
+ * The hash table needs a particular pointer to be the marker for a key that
+ * was deleted from the table, along with NULL for the "never allocated in the
+ * table" marker.  Legacy GL allows any GLuint to be used as a GL object name,
+ * and we use a 1:1 mapping from GLuints to key pointers, so we need to be
+ * able to track a GLuint that happens to match the deleted key outside of
+ * struct hash_table.  We tell the hash table to use "1" as the deleted key
+ * value, so that we test the deleted-key-in-the-table path as best we can.
  */
-struct HashEntry {
-   GLuint Key;             /**< the entry's key */
-   void *Data;             /**< the entry's data */
-   struct HashEntry *Next; /**< pointer to next entry */
-};
-
+#define DELETED_KEY_VALUE 1
 
 /**
  * The hash table data structure.  
  */
 struct _mesa_HashTable {
-   struct HashEntry *Table[TABLE_SIZE];  /**< the lookup table */
+   struct hash_table *ht;
    GLuint MaxKey;                        /**< highest key inserted so far */
    _glthread_Mutex Mutex;                /**< mutual exclusion lock */
    _glthread_Mutex WalkMutex;            /**< for _mesa_HashWalk() */
    GLboolean InDeleteAll;                /**< Debug check */
+   /** Value that would be in the table for DELETED_KEY_VALUE. */
+   void *deleted_key_data;
 };
 
+/** @{
+ * Mapping from our use of GLuint as both the key and the hash value to the
+ * hash_table.h API
+ *
+ * There exist many integer hash functions, designed to avoid collisions when
+ * the integers are spread across key space with some patterns.  In GL, the
+ * pattern (in the case of glGen*()ed object IDs) is that the keys are unique
+ * contiguous integers starting from 1.  Because of that, we just use the key
+ * as the hash value, to minimize the cost of the hash function.  If objects
+ * are never deleted, we will never see a collision in the table, because the
+ * table resizes itself when it approaches full, and thus key % table_size ==
+ * key.
+ *
+ * The case where we could have collisions for genned objects would be
+ * something like: glGenBuffers(&a, 100); glDeleteBuffers(&a + 50, 50);
+ * glGenBuffers(&b, 100), because objects 1-50 and 101-200 are allocated at
+ * the end of that sequence, instead of 1-150.  So far it doesn't appear to be
+ * a problem.
+ */
+static bool
+uint_key_compare(const void *a, const void *b)
+{
+   return a == b;
+}
+
+static uint32_t
+uint_hash(GLuint id)
+{
+   return id;
+}
 
+static void *
+uint_key(GLuint id)
+{
+   return (void *)(uintptr_t) id;
+}
+/** @} */
 
 /**
  * Create a new hash table.
@@ -78,6 +113,9 @@ struct _mesa_HashTable *
 _mesa_NewHashTable(void)
 {
    struct _mesa_HashTable *table = CALLOC_STRUCT(_mesa_HashTable);
+
+   table->ht = _mesa_hash_table_create(NULL, uint_key_compare);
+   _mesa_hash_table_set_deleted_key(table->ht, uint_key(DELETED_KEY_VALUE));
    if (table) {
       _glthread_INIT_MUTEX(table->Mutex);
       _glthread_INIT_MUTEX(table->WalkMutex);
@@ -98,20 +136,14 @@ _mesa_NewHashTable(void)
 void
 _mesa_DeleteHashTable(struct _mesa_HashTable *table)
 {
-   GLuint pos;
    assert(table);
-   for (pos = 0; pos < TABLE_SIZE; pos++) {
-      struct HashEntry *entry = table->Table[pos];
-      while (entry) {
-	 struct HashEntry *next = entry->Next;
-         if (entry->Data) {
-            _mesa_problem(NULL,
-                          "In _mesa_DeleteHashTable, found non-freed data");
-         }
-	 free(entry);
-	 entry = next;
-      }
+
+   if (_mesa_hash_table_next_entry(table->ht, NULL) != NULL) {
+      _mesa_problem(NULL, "In _mesa_DeleteHashTable, found non-freed data");
    }
+
+   _mesa_hash_table_destroy(table->ht, NULL);
+
    _glthread_DESTROY_MUTEX(table->Mutex);
    _glthread_DESTROY_MUTEX(table->WalkMutex);
    free(table);
@@ -126,21 +158,19 @@ _mesa_DeleteHashTable(struct _mesa_HashTable *table)
 static inline void *
 _mesa_HashLookup_unlocked(struct _mesa_HashTable *table, GLuint key)
 {
-   GLuint pos;
-   const struct HashEntry *entry;
+   const struct hash_entry *entry;
 
    assert(table);
    assert(key);
 
-   pos = HASH_FUNC(key);
-   entry = table->Table[pos];
-   while (entry) {
-      if (entry->Key == key) {
-         return entry->Data;
-      }
-      entry = entry->Next;
-   }
-   return NULL;
+   if (key == DELETED_KEY_VALUE)
+      return table->deleted_key_data;
+
+   entry = _mesa_hash_table_search(table->ht, uint_hash(key), uint_key(key));
+   if (!entry)
+      return NULL;
+
+   return entry->data;
 }
 
 
@@ -175,9 +205,8 @@ _mesa_HashLookup(struct _mesa_HashTable *table, GLuint key)
 void
 _mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data)
 {
-   /* search for existing entry with this key */
-   GLuint pos;
-   struct HashEntry *entry;
+   uint32_t hash = uint_hash(key);
+   struct hash_entry *entry;
 
    assert(table);
    assert(key);
@@ -187,32 +216,17 @@ _mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data)
    if (key > table->MaxKey)
       table->MaxKey = key;
 
-   pos = HASH_FUNC(key);
-
-   /* check if replacing an existing entry with same key */
-   for (entry = table->Table[pos]; entry; entry = entry->Next) {
-      if (entry->Key == key) {
-         /* replace entry's data */
-#if 0 /* not sure this check is always valid */
-         if (entry->Data) {
-            _mesa_problem(NULL, "Memory leak detected in _mesa_HashInsert");
-         }
-#endif
-	 entry->Data = data;
-         _glthread_UNLOCK_MUTEX(table->Mutex);
-	 return;
+   if (key == DELETED_KEY_VALUE) {
+      table->deleted_key_data = data;
+   } else {
+      entry = _mesa_hash_table_search(table->ht, hash, uint_key(key));
+      if (entry) {
+         entry->data = data;
+      } else {
+         _mesa_hash_table_insert(table->ht, hash, uint_key(key), data);
       }
    }
 
-   /* alloc and insert new table entry */
-   entry = MALLOC_STRUCT(HashEntry);
-   if (entry) {
-      entry->Key = key;
-      entry->Data = data;
-      entry->Next = table->Table[pos];
-      table->Table[pos] = entry;
-   }
-
    _glthread_UNLOCK_MUTEX(table->Mutex);
 }
 
@@ -230,8 +244,7 @@ _mesa_HashInsert(struct _mesa_HashTable *table, GLuint key, void *data)
 void
 _mesa_HashRemove(struct _mesa_HashTable *table, GLuint key)
 {
-   GLuint pos;
-   struct HashEntry *entry, *prev;
+   struct hash_entry *entry;
 
    assert(table);
    assert(key);
@@ -244,27 +257,12 @@ _mesa_HashRemove(struct _mesa_HashTable *table, GLuint key)
    }
 
    _glthread_LOCK_MUTEX(table->Mutex);
-
-   pos = HASH_FUNC(key);
-   prev = NULL;
-   entry = table->Table[pos];
-   while (entry) {
-      if (entry->Key == key) {
-         /* found it! */
-         if (prev) {
-            prev->Next = entry->Next;
-         }
-         else {
-            table->Table[pos] = entry->Next;
-         }
-         free(entry);
-         _glthread_UNLOCK_MUTEX(table->Mutex);
-	 return;
-      }
-      prev = entry;
-      entry = entry->Next;
+   if (key == DELETED_KEY_VALUE) {
+      table->deleted_key_data = NULL;
+   } else {
+      entry = _mesa_hash_table_search(table->ht, uint_hash(key), uint_key(key));
+      _mesa_hash_table_remove(table->ht, entry);
    }
-
    _glthread_UNLOCK_MUTEX(table->Mutex);
 }
 
@@ -284,19 +282,19 @@ _mesa_HashDeleteAll(struct _mesa_HashTable *table,
                     void (*callback)(GLuint key, void *data, void *userData),
                     void *userData)
 {
-   GLuint pos;
+   struct hash_entry *entry;
+
    ASSERT(table);
    ASSERT(callback);
    _glthread_LOCK_MUTEX(table->Mutex);
    table->InDeleteAll = GL_TRUE;
-   for (pos = 0; pos < TABLE_SIZE; pos++) {
-      struct HashEntry *entry, *next;
-      for (entry = table->Table[pos]; entry; entry = next) {
-         callback(entry->Key, entry->Data, userData);
-         next = entry->Next;
-         free(entry);
-      }
-      table->Table[pos] = NULL;
+   hash_table_foreach(table->ht, entry) {
+      callback((uintptr_t)entry->key, entry->data, userData);
+      _mesa_hash_table_remove(table->ht, entry);
+   }
+   if (table->deleted_key_data) {
+      callback(DELETED_KEY_VALUE, table->deleted_key_data, userData);
+      table->deleted_key_data = NULL;
    }
    table->InDeleteAll = GL_FALSE;
    _glthread_UNLOCK_MUTEX(table->Mutex);
@@ -322,93 +320,25 @@ _mesa_HashWalk(const struct _mesa_HashTable *table,
 {
    /* cast-away const */
    struct _mesa_HashTable *table2 = (struct _mesa_HashTable *) table;
-   GLuint pos;
+   struct hash_entry *entry;
+
    ASSERT(table);
    ASSERT(callback);
    _glthread_LOCK_MUTEX(table2->WalkMutex);
-   for (pos = 0; pos < TABLE_SIZE; pos++) {
-      struct HashEntry *entry, *next;
-      for (entry = table->Table[pos]; entry; entry = next) {
-         /* save 'next' pointer now in case the callback deletes the entry */
-         next = entry->Next;
-         callback(entry->Key, entry->Data, userData);
-      }
+   hash_table_foreach(table->ht, entry) {
+      callback((uintptr_t)entry->key, entry->data, userData);
    }
+   if (table->deleted_key_data)
+      callback(DELETED_KEY_VALUE, table->deleted_key_data, userData);
    _glthread_UNLOCK_MUTEX(table2->WalkMutex);
 }
 
-
-/**
- * Return the key of the "first" entry in the hash table.
- * While holding the lock, walks through all table positions until finding
- * the first entry of the first non-empty one.
- * 
- * \param table  the hash table
- * \return key for the "first" entry in the hash table.
- */
-GLuint
-_mesa_HashFirstEntry(struct _mesa_HashTable *table)
-{
-   GLuint pos;
-   assert(table);
-   _glthread_LOCK_MUTEX(table->Mutex);
-   for (pos = 0; pos < TABLE_SIZE; pos++) {
-      if (table->Table[pos]) {
-         _glthread_UNLOCK_MUTEX(table->Mutex);
-         return table->Table[pos]->Key;
-      }
-   }
-   _glthread_UNLOCK_MUTEX(table->Mutex);
-   return 0;
-}
-
-
-/**
- * Given a hash table key, return the next key.  This is used to walk
- * over all entries in the table.  Note that the keys returned during
- * walking won't be in any particular order.
- * \return next hash key or 0 if end of table.
- */
-GLuint
-_mesa_HashNextEntry(const struct _mesa_HashTable *table, GLuint key)
+static void
+debug_print_entry(GLuint key, void *data, void *userData)
 {
-   const struct HashEntry *entry;
-   GLuint pos;
-
-   assert(table);
-   assert(key);
-
-   /* Find the entry with given key */
-   pos = HASH_FUNC(key);
-   for (entry = table->Table[pos]; entry ; entry = entry->Next) {
-      if (entry->Key == key) {
-         break;
-      }
-   }
-
-   if (!entry) {
-      /* the given key was not found, so we can't find the next entry */
-      return 0;
-   }
-
-   if (entry->Next) {
-      /* return next in linked list */
-      return entry->Next->Key;
-   }
-   else {
-      /* look for next non-empty table slot */
-      pos++;
-      while (pos < TABLE_SIZE) {
-         if (table->Table[pos]) {
-            return table->Table[pos]->Key;
-         }
-         pos++;
-      }
-      return 0;
-   }
+   _mesa_debug(NULL, "%u %p\n", key, data);
 }
 
-
 /**
  * Dump contents of hash table for debugging.
  * 
@@ -417,19 +347,12 @@ _mesa_HashNextEntry(const struct _mesa_HashTable *table, GLuint key)
 void
 _mesa_HashPrint(const struct _mesa_HashTable *table)
 {
-   GLuint pos;
-   assert(table);
-   for (pos = 0; pos < TABLE_SIZE; pos++) {
-      const struct HashEntry *entry = table->Table[pos];
-      while (entry) {
-	 _mesa_debug(NULL, "%u %p\n", entry->Key, entry->Data);
-	 entry = entry->Next;
-      }
-   }
+   if (table->deleted_key_data)
+      debug_print_entry(DELETED_KEY_VALUE, table->deleted_key_data, NULL);
+   _mesa_HashWalk(table, debug_print_entry, NULL);
 }
 
 
-
 /**
  * Find a block of adjacent unused hash keys.
  * 
@@ -446,7 +369,7 @@ _mesa_HashPrint(const struct _mesa_HashTable *table)
 GLuint
 _mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys)
 {
-   const GLuint maxKey = ~((GLuint) 0);
+   const GLuint maxKey = ~((GLuint) 0) - 1;
    _glthread_LOCK_MUTEX(table->Mutex);
    if (maxKey - numKeys > table->MaxKey) {
       /* the quick solution */
@@ -486,82 +409,14 @@ _mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys)
 GLuint
 _mesa_HashNumEntries(const struct _mesa_HashTable *table)
 {
-   GLuint pos, count = 0;
+   struct hash_entry *entry;
+   GLuint count = 0;
 
-   for (pos = 0; pos < TABLE_SIZE; pos++) {
-      const struct HashEntry *entry;
-      for (entry = table->Table[pos]; entry; entry = entry->Next) {
-         count++;
-      }
-   }
+   if (table->deleted_key_data)
+      count++;
 
-   return count;
-}
-
-
-
-#if 0 /* debug only */
+   hash_table_foreach(table->ht, entry)
+      count++;
 
-/**
- * Test walking over all the entries in a hash table.
- */
-static void
-test_hash_walking(void)
-{
-   struct _mesa_HashTable *t = _mesa_NewHashTable();
-   const GLuint limit = 50000;
-   GLuint i;
-
-   /* create some entries */
-   for (i = 0; i < limit; i++) {
-      GLuint dummy;
-      GLuint k = (rand() % (limit * 10)) + 1;
-      while (_mesa_HashLookup(t, k)) {
-         /* id already in use, try another */
-         k = (rand() % (limit * 10)) + 1;
-      }
-      _mesa_HashInsert(t, k, &dummy);
-   }
-
-   /* walk over all entries */
-   {
-      GLuint k = _mesa_HashFirstEntry(t);
-      GLuint count = 0;
-      while (k) {
-         GLuint knext = _mesa_HashNextEntry(t, k);
-         assert(knext != k);
-         _mesa_HashRemove(t, k);
-         count++;
-         k = knext;
-      }
-      assert(count == limit);
-      k = _mesa_HashFirstEntry(t);
-      assert(k==0);
-   }
-
-   _mesa_DeleteHashTable(t);
-}
-
-
-void
-_mesa_test_hash_functions(void)
-{
-   int a, b, c;
-   struct _mesa_HashTable *t;
-
-   t = _mesa_NewHashTable();
-   _mesa_HashInsert(t, 501, &a);
-   _mesa_HashInsert(t, 10, &c);
-   _mesa_HashInsert(t, 0xfffffff8, &b);
-   /*_mesa_HashPrint(t);*/
-
-   assert(_mesa_HashLookup(t,501));
-   assert(!_mesa_HashLookup(t,1313));
-   assert(_mesa_HashFindFreeKeyBlock(t, 100));
-
-   _mesa_DeleteHashTable(t);
-
-   test_hash_walking();
+   return count;
 }
-
-#endif
diff --git a/src/mesa/main/hash.h b/src/mesa/main/hash.h
index e935f8d3984..cdaa7669ae8 100644
--- a/src/mesa/main/hash.h
+++ b/src/mesa/main/hash.h
@@ -55,10 +55,6 @@ _mesa_HashWalk(const struct _mesa_HashTable *table,
                void (*callback)(GLuint key, void *data, void *userData),
                void *userData);
 
-extern GLuint _mesa_HashFirstEntry(struct _mesa_HashTable *table);
-
-extern GLuint _mesa_HashNextEntry(const struct _mesa_HashTable *table, GLuint key);
-
 extern void _mesa_HashPrint(const struct _mesa_HashTable *table);
 
 extern GLuint _mesa_HashFindFreeKeyBlock(struct _mesa_HashTable *table, GLuint numKeys);