On Fri, 25 Mar 2022 at 13:31, Jan Sikorski jsikorski@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.