search

skarupke / flat_hash_map

A very fast hashtable
1.69k stars 186 forks source link

Test for optimizable prime numbers #1

Closed tobia closed 7 years ago

tobia commented 7 years ago

I really enjoyed your article. Here is an idea for a further improvement (for lack of a better place to post it.)

For each prime_index you could automatically test several prime numbers around the ideal value, to see which one can be optimized best by the compiler.

For example, what if the integer modulo operation using one of the other primes near 14480561146010017169ll, let's say among the ones that are less than 1% off from the ideal value—which will be a lot of primes—what if one of them can be compiled into x64 assembly code that is twice as fast? 10 times faster? Wouldn't it make sense to pick that as the compile-time default?

Considering the black magic that goes on in these kinds of compiler optimizations, it wouldn't surprise me to see a huge variation in the assembly code generated for different primes (and by different compilers too.)

skarupke commented 7 years ago

I like the idea, but looking at the assembly that gets generated, the code for the prime numbers starts to look pretty similar once you're at numbers over 200. For small numbers there seems to be a lot of variety in the generated assembly, but for larger numbers the compiler always generates very similar assembly, just with different magic numbers.

So I could try to do this optimization for small numbers, but unfortunately I also don't have a lot of options when it comes to small prime numbers.

It might still be worth doing, but I don't expect big gains so I won't invest time in pursuing this idea.