[Mesa-dev] [PATCH 00/18] [RFC] Pointer specific data structures

[Eric Anholt]

Erik Faye-Lund <kusmabite at gmail.com> writes:

> On Wed, Apr 11, 2018 at 8:48 PM, Thomas Helland
> <thomashelland90 at gmail.com> wrote:
>> This series came about when I saw a talk online, while simultaneously
>> being annoyd about the needless waste of memory in our set as reported
>> by pahole. I have previously made some patches that changed our hash
>> table from a reprobing one to a quadratic probing one, in the name of
>> lower overhead and better cache locality, but I was not quite satisfied.
>>
>> I'm sending this series out now, as it seems like an ideal time since
>> Timothy is working at reducing our compile times. Further details about
>> the implementation and its advantages are described in the patches.
>> I've found this to give a reduction in shader-db runtime of about 2%,
>> but I have to do some more testing on my main computer, as my laptop
>> is showing its age with some terrible thermal issues.
>>
>> This special cases on pointers, as that is a very common usecase.
>> This allows us to drop some comparisons, and reduce the total size
>> of our hash table to 70% or our current and the set to 50%. It uses
>> linear probing and power-of-two table sizes to get good cache locality.
>> In the pointer_map caes it moves the stored hashes out into it's own
>> array for even better cache locality.
>>
>> I'm not sure if we want another set and map amongst our utils,
>> but the patch series is simple enough, and complete enough,
>> that I thought I could share it for some inital comments.
>
> This approach gives me a bad feeling. Using memory addresses for
> storage ordering in a compiler is not quite nice; it can easily mask
> spurious bugs, and have a compiler produce different result each run.
> Such compilers are not nice to work with. I've seen *exactly* this
> use-case go wrong in the past.

I've got bad news for you about what we're already doing in
_mesa_hash_pointer().

I'm generally interested in this series, though a completely new
implementation without unit tests is less interesting to me.  How much
do we get from just having a pointer map forked off of hash_table.c with
the ->hash removed?
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 832 bytes
Desc: not available
URL: <https://lists.freedesktop.org/archives/mesa-dev/attachments/20180412/7f5ca9c5/attachment.sig>