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

[Erik Faye-Lund]

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.