On Mon, Feb 2, 2015 at 11:59 AM, Thomas Helland <thomashellan...@gmail.com> wrote: > 2015-02-02 19:18 GMT+01:00 Jason Ekstrand <ja...@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@lists.freedesktop.org > http://lists.freedesktop.org/mailman/listinfo/mesa-dev _______________________________________________ mesa-dev mailing list mesa-dev@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/mesa-dev
