search

potassco / clingo

🤔 A grounder and solver for logic programs.
https://potassco.org/clingo
MIT License
599 stars 79 forks source link

rework hash_combine and hash_mix for performance #441

Closed trws closed 1 year ago

trws commented 1 year ago

This ended up being a small change, tweaking the hash_combine function to work more like the boost version and selecting hash_mix based on size of size_t rather than the argument. The end result is that for spack inputs 5.6.2 performs almost exactly as well as 5.5.2, which is a 30%+ speedup in some tests.

rkaminsk commented 1 year ago

This ended up being a small change, tweaking the hash_combine function to work more like the boost version and selecting hash_mix based on size of size_t rather than the argument. The end result is that for spack inputs 5.6.2 performs almost exactly as well as 5.5.2, which is a 30%+ speedup in some tests.

I am puzzled. As far as I understand hash functions, this should be a really bad one. Now hash_combine is even commutative. I'll have to dig a little deeper to see what is actually happening here.

rkaminsk commented 1 year ago

I just played around a bit and the key element of this patch seems to be applying the hash_mix function in hash_combine. With this we can also get the same speed up with a small twist to the original implementation. I'll commit a suggestion also cleaning up the mess with the templates I introduced a bit. :wink:

EDIT: Sorry for the noise. Compilation on MacOS has to be fixed.

rkaminsk commented 1 year ago

If this works for you, I would merge it like this. And thanks for digging into this. I don't think I would have found it myself.