[Mesa-dev] Naming conventions, DSA, and meta

[Kristian Høgsberg]

On Mon, Feb 2, 2015 at 11:59 AM, Thomas Helland
<thomashelland90 at gmail.com> wrote:
> 2015-02-02 19:18 GMT+01:00 Jason Ekstrand <jason at jlekstrand.net>:
>> Hi all,
>> I wanted to send out a quick message about naming conventions for mesa
>> entrypoints and dd table fallbacks.  There has been some confusion and
>> disagreement about this with some of the stuff Laura has been doing to
>> implement DSA.  Instead of side-track one of those patches for this
>> discussion, I thought it was worth its own e-mail.
>>
>> When Laura started working on DSA, I suggested that, since we're refactoring
>> everything anyway, we refactor the guts of the entrypoint into a DSA-style
>> "internal entrypoint".  This internal entrypoint takes a gl_context pointer,
>> does less error checking, and actual mesa object pointers instead of GLuint
>> names.  I'll get to why in a minute here.  However, that leaves us needing a
>> naming convention for three things:
>>
>>  1) The entrypoint itself (currently _mesa_EntryPoint)
>>  2) the internal entrypoint (Laura chose _mesa_entry_point)
>>  3) the software fallback for the DD table entry (Laura chose
>> _mesa_TableEntry_sw)
>>
>> I think we can all agree on not changing (1).  Previously we had something
>> of a convention of _mesa_entry_point for (3) but it wasn't perfectly
>> consistent.  Since we didn't have DSA, we didn't have anything for (2).
>> Personally, I'm OK with what Laura chose, but I understand that it's a
>> change of convention.  Another option, would be to do _mesa_main_TableEntry
>> or _mesa_main_table_entry for the standard DD fallback.  Or we can come up
>> with a different convention for the internal entry points.  I don't care
>> much.
>>
>> Why the internal entrypoints?
>>
>> The first reason is that we have to do the refactor anyway, and that seems
>> reasonable.  The more important reason is meta.  This is something that
>> Kristian, Ken and I have talked about a good bit lately.  I've done some
>> traces with meta lately and meta_begin/end show up a lot and what shows up
>> more is hash table lookups and, in particular, the mutex lock/unlock that's
>> involved.  Inside meta, we do all sorts of stupidity like
>
> Kind of off-topic, but since you're mentioning overhead of hash tables:
> I've been doing some work on util/hash_table that is yet to be sent to the list.
> Thought I could share my experience if someone happens to be
> working on other improvements to the hash-tables.
>
> TLDR of approach:
> Power-of-two sized table instead of prime size.
> -> We can replace the modulo with bitmasking to fit keys in the table.
> -> Reduced overhead on insert, search, resize, etc.
> -> FNV-1a has good avalanche properties -> collisions is a no-issue.
>
> Changing to quadratic probing removes the rehash-stuff.
> -> Less code, simpler, seems to do a better job.
> -> Reduced memory usage and better cache locality?
>
> Preliminary oprofile results of a shader-db run with NIR:
>
> hash_table_insert:   4.13 %   -->   2.13 %
> hash_table_search: 4.12 %   -->   2.29 %
>
> To be done:
> Do the same for hash set.
> Change some hash table uses to the one in util.
> Similar treatment for the other tables.
> Test on something that is actually CPU bound.

Yeah, I was never convinced that the prime size hashtables provided
any benefit. Sounds good to me looking forward to seeing the patches.

Kristian

> -Thomas Helland
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/mesa-dev