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)

1 files changed, 0 insertions, 4 deletions

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);