Speeding Up Collatz Iteration With Inline Assembly

I’ve recently had the terrible idea to start looking at the Collatz Conjecture on a hunch there may be an interesting equivalent statement in proof theory. While looking though the Wikipedia article I found an elegant algorithm that finds Collatz sequences for odd numbers represented as binary strings. The part about repeatedly dividing by two caught my eye, and the whole thing looked like a fun optimization exercise to see if I could beat a C compiler for once.

Collatz Iteration Link to heading

The following is a simple Collatz iteration function that given any number n will return the length of n’s Collatz sequence. The actual number of iterations is irrelevant, we really just care that n eventually reaches 1, and how quickly this happens (faster is better). If n did not reach 1 the program would enter an infinite loop and we would have successfully solved the Collatz conjecture. This is however impossible as every single unsigned long (64 bit representable) number has already been experimentally verified to reach 1.

int collatzBasic(unsigned long n){
    int rv = 0;
    for(;n!=1; rv++){
        n = n % 2 ? 3 * n + 1 : n / 2; 
    }
    return rv;
}

One common optimization is to use a a shortcut version of the Collatz function based on parity results that converges faster by immediately dividing the odd case by 2.

int collatzShortcut(unsigned long n){
    int rv = 0;
    for(;n!=1; rv++){
        n = n % 2 ? (3 * n + 1) / 2 : n / 2; 
    }
    return rv;
}

Now for a bad implementation of Wikipedia algorithm for odd numbers. Why divide by two once when you can spam it until you cant any more?

int collatzLoopCut(unsigned long n){
    int rv = 0;
    for(;n!=1; rv++){
        n = 3 * n + 1;
        while(n % 2 == 0){
            n = n / 2;
        }
    }
    return rv;
}

The insight here is that this repeated division by two is actually just throwing out all tailing zeros on the binary representation of n and that this can be done extremely efficiently with the right x86 assembly instructions. In particular BSF: the Bit Scan Forward instruction, which counts the number of trailing zeros, into a SHR : Shift Logical Right instruction to remove the trailing zeros.

int collatzLoopCutAsm(unsigned long n){
    unsigned long rv = 0;
    for(;n!=1; rv++){
        n = 3 * n + 1;
        asm(
            "bsfq %0, %%rcx \n"
            "shrq %%cl, %0 \n"
            : "=r"(n)
            : "r"(n)
            : "%rcx"
        );
    }
    return rv; 
}

Finally its time to test how much of an improvement this is. I add some benchmarking boilerplate where we count how long it takes to sum the lengths of the first half million Collatz sequences generated by odd numbers.

#define BENCH(C){\
    unsigned long cycles = 0;\
    clock_t s = clock();\
    for(unsigned long i = 1; i < 1000000; i+=2)\
        cycles += C(i);\
    double e = (double)(clock() - s) / CLOCKS_PER_SEC;\
    printf("%s, %ld cycles, %lf secs\n", #C, cycles, e);\
}

int main(){
    BENCH(collatzBasic)
    BENCH(collatzShortcut)
    BENCH(collatzLoopCut)
    BENCH(collatzLoopCutAsm)
}

Compiling on my hardware using GCC at various optimization levels, I did 5 runs and took the lowest run-time for each value.

It should be clear that using the inline assembly substantially outperforms not using it even when the compiler is trying as hard as it can to optimize.