[Mesa-dev] [PATCH 4/5] mesa: Convert the hash table for GL object ids to the open-addressing hash.

[Eric Anholt]

Brian Paul <brianp at vmware.com> writes:

> 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?

37000 out of the 148000 objects were OQs.  I think most of the rest are
display lists.

>> +#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.

Zero is the value for nothing-was-ever-present, as opposed to
something-was-present-but-was-deleted.  This kind of hash table uses the
second value to tell you when you need to keep reprobing for a
collision.  It lets you avoid linked lists and get excellent cache
behavior.

Given that id=1 is the first thing allocated and this passes piglit, I'm
pretty confident in the ugly hack to avoid id == 1 (it's why I chose
that instead of ~0, which would have made more sense to me).

Both the old program hash table and the new hash table have reserved
values -- the old one had a data value of NULL reserved, and the new one
has a key value of NULL and a key value of either some miscellanous
pointer or a value of your choice reserved.  I wrote it with reserved
key values instead of data values thinking of the program/ usage where
we're mapping a char * key to an integer 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.

I'll try to rewrite that text a bit.

Currently, genned object names are *almost* reasonable to handle using
just an array of pointers from 0-MaxKey.  It was something I was
thinking about doing instead of this patch series -- genned objects go
in the array, and just leave the old hash table around to handle
non-genned, ridiculously large ids.

But right now if you gen 100 objects, then delete the last 50, then gen
another 100 objects, you end up with objects named 1-50 and 100-199,
rather than 1-150.  We need a hash table to look them up so that memory
scales with number of live objects, not number of objects allocated over
the course of the program.

I'm still really tempted to pack genned objects so that you end up with
names 1-150 so that we can use an array.  If we end up with a workload
that's hurt by the hash function we're using, I'll probably give it a shot.

>>  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?

Nope, table size is dictated by number of entries in the table.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: not available
URL: <http://lists.freedesktop.org/archives/mesa-dev/attachments/20121105/cbfe3740/attachment.pgp>