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

[Brian Paul]

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 <brianp at vmware.com>