bpo-37295: Use constant-time comb() for larger n depending on k#30305
Conversation
|
Code changes look good to me (modulo the compiler warnings on Windows). I'm running some timings. |
Running the same timings scripts that are posted to the issue, I see roughly a 5% slowdown for small |
That's really hard to swallow, Mark. At. e.g., Related: it may or may not be a timing win to set |
I'm comparing this branch with the main branch. (Sorry, I said "master" above, but I meant "main".) The main branch already has the fast mod-2**64 + popcount code in it. This branch has the same, but with some extra up-front indirection, so it's a bit slower. |
Ah, that explains it - sorry for the noise! 😃 |
| /* Maps k to the maximal n so that 2*k-1 <= n <= 127 and C(n, k)*k | ||
| * fits into a long long (which is at least 64 bit). Only contains | ||
| * items larger than in fast_comb_limits1. */ | ||
| static const unsigned long long fast_comb_limits2[] = { |
There was a problem hiding this comment.
which is at least 64 bit
C99 provides types like uint_least64_t that express such comments explicitly. So I think it will be better to #include <stdint.h> and use it:
| /* Maps k to the maximal n so that 2*k-1 <= n <= 127 and C(n, k)*k | |
| * fits into a long long (which is at least 64 bit). Only contains | |
| * items larger than in fast_comb_limits1. */ | |
| static const unsigned long long fast_comb_limits2[] = { | |
| /* Maps k to the maximal n so that 2*k-1 <= n <= 127 and C(n, k)*k | |
| * fits into a long long. Only contains | |
| * items larger than in fast_comb_limits1. */ | |
| static const uint_least64_t fast_comb_limits2[] = { |
There was a problem hiding this comment.
It should contain at least LLONG_MAX. There is no guarantee that uint_least64_t is at least so large as positive long long.
https://bugs.python.org/issue37295