3 ms·
Hmm, I can't think of a way to use the mathematical structure of those numbers to speed up checking. However, the reason I said AVX is because it can be used f
by vortico 7y ago
Hmm, I can't think of a way to use the mathematical structure of those numbers to speed up checking.
However, the reason I said AVX is because it can be used for checking equality of 5 (well, 8) numbers simultaneously. This solution requires AVX2 and is probably faster than the optimized reference code.
// Copy x to all 8 elements.
__m256i a = _mm256_set1_epi32(x);
// Duplicate 6 because we need to fill all 8 elements.
__m256i b = _mm256_set_epi32(6, 28, 496, 8128, 33550336, 6, 6, 6);
// Check for element-wise equality.
__m256i c = _mm256_cmpeq_epi32(a, b);
// Check if any bytes are nonzero.
return _mm256_movemask_epi8(c) != 0;
https://godbolt.org/z/6W8rZy https://godbolt.org/z/6W8rZy
- saagarjha 7y agoI’d benchmark that before being sure.
- vortico 7y agoIt might not be faster, but unfortunately the computer I'm typing this on doesn't support AVX2. :(
- deleted 7y ago[deleted]
- x0 7y agoSeems to be faster, did a crappy shell benchmark. It takes 5.7 seconds to run that SIMD function INT_MAX times, compared to 6.6 seconds for the original. MacBook Air, late 2014, clang, -O3 -mavx2
- OskarS 7y agoI have a hunch that the actually fastest version is to change all those "||" to "|" in the original version. Short-circuiting and adding branches probably just slows the whole thing down compared to just running the comparisons, which will probably pipeline really well. Interestingly the compiler doesn't do this optimization, even though it could. So maybe I'm wrong. No real way to know without benchmarking, though.
- vortico 7y agoGood idea. This does change the optimized assembly, but it doesn't seem to make a measureable difference in performance on my machine.