On 10/25/2012 10:13 AM, Eric Anholt wrote:
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%.
That's pretty good! What kind of object (texture, VBO, etc) is
stressing the hash table in Minecraft?
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.
---
src/mesa/main/hash.c | 365 +++++++++++++++-----------------------------------
src/mesa/main/hash.h | 4 -
2 files changed, 107 insertions(+), 262 deletions(-)
diff --git a/src/mesa/main/hash.c b/src/mesa/main/hash.c
index 61c369a..be332a6 100644
--- a/src/mesa/main/hash.c
+++ b/src/mesa/main/hash.c
@@ -34,40 +34,69 @@
* 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
Why not use zero? IIRC, I don't think any user-defined GL object can
have ID=0.
As-is, does ID=1 work as expected? It's a little hard to tell from
the code and comments.
/**
* 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, with very few skipped (would happen
+ * due to deletion but us continuing to allocate from MaxKey).
I can't quite parse that last part.
In that case,
+ * if we just use the key as the hash value, we will never see a collision in
+ * the table, because the table resizes itself when it approaches full, and
+ * key % table_size == key.
+ */
What happens if some app gens its own IDs and happens to use some
really large GLuint values? Does that imply a really large table?
The rest looks OK, AFAICT.
For the series:
Reviewed-by: Brian Paul <bri...@vmware.com>
_______________________________________________
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/mesa-dev
