On Mon Jan 8 13:48:50 2024 +0000, Conor McCarthy wrote:
An ideal 64-bit hash has a 50% collision probability on about 5 billion entries. I think we should aim for a collision to never occur once, and 64 bits is not enough. Ideally a memcmp() of the entire key would be done in the comparison function after a hash match is found. I'm not sure of the performance of the moltenvk hash, but a simple prime multiplication hash like [FNV-1a](https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function) probably has fewer collisions.
The idea behind the separate *payload allocation is to load it on demand and free it when the cache grows beyond the application-specified memory size. The rbtree search callback may not have the entire key available.
There are certainly ways to deal with that: Load the contents from disk from the search callback (which means passing the cache or rbtree pointer somehow), or load it from the caller and re-run the search, and compare the full tree only if *payload is allocated. Though I guess Microsoft created DXGI_ERROR_CACHE_HASH_COLLISION for some reason.