[PATCH] wined3d: Use hashes of graphics pipeline keys for the pipeline cache.

[Henri Verbeet]

On Fri, 25 Mar 2022 at 13:31, Jan Sikorski <jsikorski at codeweavers.com> wrote:
>
> Avoid doing full comparisons, which are expensive. There's some
> possible improvements that can be made if necessary:
>  - Select a better hash function. Murmur64A was picked mainly because
>    it's small and simple.
>  - Don't always hash the entire pipeline key, hash incrementally.
>  - Use an actual hash table instead of a tree, or at least allocate the
>    nodes more contiguously.
> Note that it is assumed that no hash collision will happen. The
> probability of one is low (under an assumption that the hash function is
> good), but we could reasonably use a 128 bit hash to make it even less
> probable.
>
> Hash function implementation based on the one published in SMHasher.
> https://github.com/aappleby/smhasher/blob/master/src/MurmurHash2.cpp
>

I think the first part of this, including a hash of the pipeline key
for easy rejection, is uncontroversial, although it would be helpful
to include some performance information. I.e., how much does this
actually help?

Skipping the full compare entirely seems quite a bit more
questionable. I know from our earlier conversation on IRC that the
impact of that was significant, although it wasn't immediately clear
why that's the case. I.e., is the issue excessive pipeline
invalidation, or is this simply about the size of the key, or is it
e.g. about chasing the pointers contained in the key? Those are
potentially all issues we could mitigate. For example, instead of
including e.g. a VkPipelineColorBlendStateCreateInfo structure in the
key, we could include a pointer to one and then deduplicate those.
That would mean introducing a lookup for "blend_desc" in
wined3d_context_vk_update_blend_state(), but would allows us to do a
simple pointer comparison in wined3d_graphics_pipeline_vk_compare(),
reducing the size of the pipeline key, and potentially helping the
cases where STATE_BLEND and STATE_FRAMEBUFFER weren't invalidated.

Somewhat similarly, wined3d state objects like wined3d_blend_state are
effectively unique. In the case of d3d9 and earlier that's because of
the way we do state tracking there (i.e., see
wined3d_device_apply_stateblock()), and in the case of d3d10+ that's
because state objects are already deduplicated on that level. That
means it may be advantageous to use the D3D state as key instead of
the Vulkan state in some cases, because we could simply use pointer
compares for the D3D state.

> +uint64_t hash_murmur64a(const void *key, int length, uint64_t seed)
>  {
> -    const struct wined3d_graphics_pipeline_key_vk *a = key;
> -    const struct wined3d_graphics_pipeline_key_vk *b = &WINE_RB_ENTRY_VALUE(entry,
> -            const struct wined3d_graphics_pipeline_vk, entry)->key;
> -    unsigned int i;
> -    int ret;
> +    const uint64_t *qwords = (const uint64_t *)key;
> +    const uint64_t factor = 0xc6a4a7935bd1e995LLU;

We tend to use the lowercase type suffixes.