Hacker News Reader

Comment by vortico | Hacker News Reader

#1 got me and I had a good laugh. I wonder if there's a faster method for #2 using AVX and bit tiddling, or if the optimizer is smart enough to find the most efficient code for a particular architecture.

View on HN

These are the five numbers in binary, to give some inspiration for a bit twiddling algorithm:

                          110
                        11100
                    111110000
                1111111000000
    1111111111111000000000000

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

I 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.

Good idea. This does change the optimized assembly, but it doesn't seem to make a measureable difference in performance on my machine.

I’d benchmark that before being sure.

It might not be faster, but unfortunately the computer I'm typing this on doesn't support AVX2. :(

Seems 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

The even perfect numbers all have the formula

    2^(p - 1)(2^p - 1)

for some prime `p`. In code that's

    ((1 << p) - 1) << (p - 1)

for `p` = 2, 3, 5, 7 and 13, which is why you're seeing that interesting pattern of bits.

(There are no odd perfect numbers in the range under consideration.)

You should also note that there are no known odd perfect numbers, period. Any that do exist must exceed 10^1500.

One things that comes to mind: popcnt(x^(x>>1))==2 for all 5 numbers. Maybe the checking function could start with that condition, then fall back to the slower one-by-one check when that evaluates to two. For most numbers the popcnt check would fail.

edit: Not to mention that all 5 numbers are even, so a parity check could also help for odd number inputs (but it makes it slower for even numbers). I do not think that AVX has anything to offer here though.

It might matter then what cases you need to optimize for, which statistics are most important, and what instruction set you are using.

Sure, my tricks are mostly aimed for improving the average performance for uniform inputs between 0 and 2^32-1.

Edit: And yeah, you need a fast popcnt here.

Assuming arguments will be uniformly picked an extra check would speed things up on many architectures:

  return (x & 0xFE0000001 == 0) &&
    (x == 6 || x == 28 || x == 496 || x == 8128 || x == 33550336):

The original code does about 5 comparisons in each call. The improvement always does a binary ‘and’ and 1 comparison, and only does the original 5 in 1/256 of the calls.

Although unlike the original code it will be trickier to refactor for >5000 bit architectures once we encounter an odd perfect number.

Here's a version that at least for 64 bit might be faster:

  bool isPerfect(uint64_t x) {
        int ctz = __builtin_ctzll(x);
        return ((0x40051056 >> ctz) & 1) && ((x >> ctz) + 1) == (uint64_t(1) << (ctz + 1));
  }

Got me to laugh too! I thought I was clever with my O(n) solution. Let A be the original array and let B be the sorted array. Just loop through A and assign B[A[i]] = A[i].

But this is still dumb! lol.

It says from 1 to N inclusive, so each offset would need to have 1 subtracted from it.

(Yes I realize it would just be an iota function in c++)

Reply on news.ycombinator.com