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@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; };