[PATCH] wined3d: Use hashes of graphics pipeline keys for the pipeline cache.
Jan Sikorski
jsikorski at codeweavers.com
Fri Mar 25 07:31:17 CDT 2022
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
Signed-off-by: Jan Sikorski <jsikorski at codeweavers.com>
---
dlls/wined3d/context_vk.c | 128 ++++++++++++++++-----------------
dlls/wined3d/wined3d_private.h | 2 +-
2 files changed, 64 insertions(+), 66 deletions(-)
diff --git a/dlls/wined3d/context_vk.c b/dlls/wined3d/context_vk.c
index 436973fe76f..e853bd568e2 100644
--- a/dlls/wined3d/context_vk.c
+++ b/dlls/wined3d/context_vk.c
@@ -1844,82 +1844,78 @@ static int wined3d_pipeline_layout_vk_compare(const void *key, const struct wine
return memcmp(a->bindings, b->bindings, a->binding_count * sizeof(*a->bindings));
}
-static int wined3d_graphics_pipeline_vk_compare(const void *key, const struct wine_rb_entry *entry)
+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;
+ const uint64_t *qend = &qwords[length >> 3];
+ const uint8_t *bytes = (const uint8_t *)qend;
+ uint64_t hash = seed ^ (length * factor);
+ const int shift = 47;
- if ((ret = wined3d_uint32_compare(a->pipeline_desc.stageCount, b->pipeline_desc.stageCount)))
- return ret;
- for (i = 0; i < a->pipeline_desc.stageCount; ++i)
+ while (qwords != qend)
{
- if ((ret = wined3d_uint64_compare(a->stages[i].module, b->stages[i].module)))
- return ret;
- }
+ uint64_t value = *qwords++;
- if ((ret = wined3d_uint32_compare(a->divisor_desc.vertexBindingDivisorCount,
- b->divisor_desc.vertexBindingDivisorCount)))
- return ret;
- if ((ret = memcmp(a->divisors, b->divisors,
- a->divisor_desc.vertexBindingDivisorCount * sizeof(*a->divisors))))
- return ret;
+ value *= factor;
+ value ^= value >> shift;
+ value *= factor;
- if ((ret = wined3d_uint32_compare(a->input_desc.vertexAttributeDescriptionCount,
- b->input_desc.vertexAttributeDescriptionCount)))
- return ret;
- if ((ret = memcmp(a->attributes, b->attributes,
- a->input_desc.vertexAttributeDescriptionCount * sizeof(*a->attributes))))
- return ret;
- if ((ret = wined3d_uint32_compare(a->input_desc.vertexBindingDescriptionCount,
- b->input_desc.vertexBindingDescriptionCount)))
- return ret;
- if ((ret = memcmp(a->bindings, b->bindings,
- a->input_desc.vertexBindingDescriptionCount * sizeof(*a->bindings))))
- return ret;
-
- if ((ret = wined3d_uint32_compare(a->ia_desc.topology, b->ia_desc.topology)))
- return ret;
- if ((ret = wined3d_uint32_compare(a->ia_desc.primitiveRestartEnable, b->ia_desc.primitiveRestartEnable)))
- return ret;
-
- if ((ret = wined3d_uint32_compare(a->ts_desc.patchControlPoints, b->ts_desc.patchControlPoints)))
- return ret;
+ hash ^= value;
+ hash *= factor;
+ }
- if ((ret = memcmp(&a->viewport, &b->viewport, sizeof(a->viewport))))
- return ret;
+ switch (length & 7)
+ {
+ case 7: hash ^= (uint64_t)(bytes[6]) << 48;
+ case 6: hash ^= (uint64_t)(bytes[5]) << 40;
+ case 5: hash ^= (uint64_t)(bytes[4]) << 32;
+ case 4: hash ^= (uint64_t)(bytes[3]) << 24;
+ case 3: hash ^= (uint64_t)(bytes[2]) << 16;
+ case 2: hash ^= (uint64_t)(bytes[1]) << 8;
+ case 1: hash ^= (uint64_t)(bytes[0]);
- if ((ret = memcmp(&a->scissor, &b->scissor, sizeof(a->scissor))))
- return ret;
+ hash *= factor;
+ };
- if ((ret = memcmp(&a->rs_desc, &b->rs_desc, sizeof(a->rs_desc))))
- return ret;
+ hash ^= hash >> shift;
+ hash *= factor;
+ hash ^= hash >> shift;
- if ((ret = wined3d_uint32_compare(a->ms_desc.rasterizationSamples, b->ms_desc.rasterizationSamples)))
- return ret;
- if ((ret = wined3d_uint32_compare(a->ms_desc.alphaToCoverageEnable, b->ms_desc.alphaToCoverageEnable)))
- return ret;
- if ((ret = wined3d_uint32_compare(a->sample_mask, b->sample_mask)))
- return ret;
+ return hash;
+}
- if ((ret = memcmp(&a->ds_desc, &b->ds_desc, sizeof(a->ds_desc))))
- return ret;
+static uint64_t wined3d_graphics_pipeline_vk_key_hash(struct wined3d_graphics_pipeline_key_vk *key)
+{
+ uint64_t result = 0, i;
- if ((ret = wined3d_uint32_compare(a->blend_desc.attachmentCount, b->blend_desc.attachmentCount)))
- return ret;
- if ((ret = memcmp(a->blend_attachments, b->blend_attachments,
- a->blend_desc.attachmentCount * sizeof(*a->blend_attachments))))
- return ret;
+ for (i = 0; i < key->pipeline_desc.stageCount; ++i)
+ result = hash_murmur64a(&key->stages[i].module, sizeof(key->stages[i].module), result);
- if ((ret = wined3d_uint64_compare(a->pipeline_desc.layout, b->pipeline_desc.layout)))
- return ret;
+ result = hash_murmur64a(key->divisors, key->divisor_desc.vertexBindingDivisorCount * sizeof(*key->divisors), result);
+ result = hash_murmur64a(key->attributes, key->input_desc.vertexAttributeDescriptionCount * sizeof(*key->attributes), result);
+ result = hash_murmur64a(key->bindings, key->input_desc.vertexBindingDescriptionCount * sizeof(*key->bindings), result);
+ result = hash_murmur64a(&key->viewport, sizeof(key->viewport), result);
+ result = hash_murmur64a(&key->scissor, sizeof(key->scissor), result);
+ result = hash_murmur64a(&key->sample_mask, sizeof(key->sample_mask), result);
+ result = hash_murmur64a(key->blend_attachments, key->blend_desc.attachmentCount * sizeof(*key->blend_attachments), result);
+ result = hash_murmur64a(&key->ia_desc.topology, sizeof(key->ia_desc.topology), result);
+ result = hash_murmur64a(&key->ia_desc.primitiveRestartEnable, sizeof(key->ia_desc.primitiveRestartEnable), result);
+ result = hash_murmur64a(&key->ts_desc.patchControlPoints, sizeof(key->ts_desc.patchControlPoints), result);
+ result = hash_murmur64a(&key->rs_desc, sizeof(key->rs_desc), result);
+ result = hash_murmur64a(&key->ms_desc.rasterizationSamples, sizeof(key->ms_desc.rasterizationSamples), result);
+ result = hash_murmur64a(&key->ms_desc.alphaToCoverageEnable, sizeof(key->ms_desc.alphaToCoverageEnable), result);
+ result = hash_murmur64a(&key->ds_desc, sizeof(key->ds_desc), result);
+ result = hash_murmur64a(&key->pipeline_desc.layout, sizeof(key->pipeline_desc.layout), result);
+ result = hash_murmur64a(&key->pipeline_desc.renderPass, sizeof(key->pipeline_desc.renderPass), result);
- if ((ret = wined3d_uint64_compare(a->pipeline_desc.renderPass, b->pipeline_desc.renderPass)))
- return ret;
+ return result;
+}
- return 0;
+static int wined3d_graphics_pipeline_vk_compare(const void *hash, const struct wine_rb_entry *entry)
+{
+ return wined3d_uint64_compare(*(uint64_t *)hash,
+ WINE_RB_ENTRY_VALUE(entry, const struct wined3d_graphics_pipeline_vk, entry)->hash);
}
static int wined3d_bo_slab_vk_compare(const void *key, const struct wine_rb_entry *entry)
@@ -3120,15 +3116,17 @@ static VkPipeline wined3d_context_vk_get_graphics_pipeline(struct wined3d_contex
struct wined3d_graphics_pipeline_vk *pipeline_vk;
struct wined3d_graphics_pipeline_key_vk *key;
struct wine_rb_entry *entry;
+ uint64_t hash;
VkResult vr;
key = &context_vk->graphics.pipeline_key_vk;
- if ((entry = wine_rb_get(&context_vk->graphics_pipelines, key)))
+ hash = wined3d_graphics_pipeline_vk_key_hash(key);
+ if ((entry = wine_rb_get(&context_vk->graphics_pipelines, &hash)))
return WINE_RB_ENTRY_VALUE(entry, struct wined3d_graphics_pipeline_vk, entry)->vk_pipeline;
if (!(pipeline_vk = heap_alloc(sizeof(*pipeline_vk))))
return VK_NULL_HANDLE;
- pipeline_vk->key = *key;
+ pipeline_vk->hash = hash;
if ((vr = VK_CALL(vkCreateGraphicsPipelines(device_vk->vk_device,
VK_NULL_HANDLE, 1, &key->pipeline_desc, NULL, &pipeline_vk->vk_pipeline))) < 0)
@@ -3138,7 +3136,7 @@ static VkPipeline wined3d_context_vk_get_graphics_pipeline(struct wined3d_contex
return VK_NULL_HANDLE;
}
- if (wine_rb_put(&context_vk->graphics_pipelines, &pipeline_vk->key, &pipeline_vk->entry) == -1)
+ if (wine_rb_put(&context_vk->graphics_pipelines, &pipeline_vk->hash, &pipeline_vk->entry) == -1)
ERR("Failed to insert pipeline.\n");
return pipeline_vk->vk_pipeline;
diff --git a/dlls/wined3d/wined3d_private.h b/dlls/wined3d/wined3d_private.h
index 5b3eb0136b0..34b7c9eab29 100644
--- a/dlls/wined3d/wined3d_private.h
+++ b/dlls/wined3d/wined3d_private.h
@@ -2521,7 +2521,7 @@ struct wined3d_graphics_pipeline_key_vk
struct wined3d_graphics_pipeline_vk
{
struct wine_rb_entry entry;
- struct wined3d_graphics_pipeline_key_vk key;
+ uint64_t hash;
VkPipeline vk_pipeline;
};
--
2.32.0
More information about the wine-devel
mailing list