[Mesa-dev] [PATCH 1/6] glsl: Prehash in refcount hash table to reduce hashing

[Thomas Helland]

2017-05-22 21:44 GMT+02:00 Thomas Helland <thomashelland90 at gmail.com>:
> 2017-05-22 21:19 GMT+02:00 Ian Romanick <idr at freedesktop.org>:
>> On 05/22/2017 11:55 AM, Thomas Helland wrote:
>>> _mesa_hash_table_search is one of our hottest function according to perf.
>>> Callgrind shows the refcounting as one of the major users of the
>>> searching functions. We can reduce the pain by prehashing, so that we
>>> avoid hashing two times when inserting in the table.
>>>
>>> On a short shader-db run (with validation disabled) it makes
>>> 1.2 million of 4.5 million calls to _hash_table_insert come from
>>> the pre-hashed path.
>>
>> Did this have any measurable impact on the run time?
>>
>
> Not as I can tell. I believe it is mostly just accumulating a slight
> gain from each patch. However, coming to think of it, the big one
> here might actually be string_to_uint_map, as that one has to hash
> strings instead of just pointers. I guess the pointer hashing is now
> so fast that it doesn't really matter.
>
> However, this is all a bit hard to measure. I would probably have
> to instrument this, and run it on my desktop, maybe with
> GALLIUM_NOOP set, in order to get conclusive results. My poor
> old ivy-bridge ultrabook has seen better days and is giving me
> quite hard-to-conlude-on results. What I can tell for sure though,
> is that the number of executed instructions drops by about 0.1%
> for this patch only.
>
> I can do some tests on my desktop tomorrow, if you'd like that.
> Then I would probably be able to get more conclusive results.
>

Thinking about this some more, I believe this approach is really
only beneficial in nir's instr_set, and in hash tables with other
longer data as keys, like strings. With the speed of the new
pointer hashing function there is little to no gain. However,
sysprof reports that the hash_instr part of the set_insert
function in nir_opt_cse is a cumulative 0.25% of overall overhead.
So with the patch to the instr_set we should see a 0.25%
drop in nir_opt_cse's part of the total picture. I'll do some tests
and see if I can confirm this.

>>> ---
>>>  src/compiler/glsl/ir_variable_refcount.cpp | 7 +++++--
>>>  1 file changed, 5 insertions(+), 2 deletions(-)
>>>
>>> diff --git a/src/compiler/glsl/ir_variable_refcount.cpp b/src/compiler/glsl/ir_variable_refcount.cpp
>>> index 8306be10b9..bbb4c0ddd7 100644
>>> --- a/src/compiler/glsl/ir_variable_refcount.cpp
>>> +++ b/src/compiler/glsl/ir_variable_refcount.cpp
>>> @@ -79,13 +79,16 @@ ir_variable_refcount_visitor::get_variable_entry(ir_variable *var)
>>>  {
>>>     assert(var);
>>>
>>> -   struct hash_entry *e = _mesa_hash_table_search(this->ht, var);
>>> +   uint32_t hash = this->ht->key_hash_function(var);
>>> +
>>> +   struct hash_entry *e =
>>> +      _mesa_hash_table_search_pre_hashed(this->ht, hash, var);
>>>     if (e)
>>>        return (ir_variable_refcount_entry *)e->data;
>>>
>>>     ir_variable_refcount_entry *entry = new ir_variable_refcount_entry(var);
>>>     assert(entry->referenced_count == 0);
>>> -   _mesa_hash_table_insert(this->ht, var, entry);
>>> +   _mesa_hash_table_insert_pre_hashed(this->ht, hash, var, entry);
>>>
>>>     return entry;
>>>  }
>>>
>>