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

[Thomas Helland]

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.

-Thomas Helland