如何优化计算Collatz猜想迭代次数的x86汇编子程序运行效率？

Problem Description #

I'm trying to optimize my hand-written x86 assembly code that calculates the number of iterations needed for a value to reach 1 in the Collatz conjecture. Here's my pseudocode:

int threexplusone(int x){
 if(x == 1){ return 0; }else{
 if(x % 2 == 0){ return (threexplusone(x/2)+1); }else{ return (threexplusone(3*x+1)+1); }
 }
}

And here's my current x86 assembly implementation:

threexplusone:
 push rbx ;store the rbx to stack
 mov rax, 0 ;store the base case
 cmp rdi, 1 ;compare the input with 1
 je done ;finished the loop if equal to 1
 jmp threexplusone_recursive ;jump to the recursion
threexplusone_recursive:
 push rax
 mov rdx,0
 mov rax,rdi
 mov rbx,2
 idiv rbx
 cmp rdx, 0 ;compare to check if the remainder is 0
 mov rbx, rax
 pop rax
 je even ;start the even instruction
odd:
 imul rdi,3 ;multiply x by 3
 add rdi, 1 ;add x by 1
 xor rax, rax
 call threexplusone ;do the recursion
 inc rax ;add the result by one
 jmp done
even:
 sar rdi,1 ;divided the input by 2
 xor rax,rax
 call threexplusone ;do the recursion
 inc rax ;add the result by one
 jmp done
done:
 pop rbx
 ret

What are some feasible optimization strategies for this code?

Optimization Strategies #

Let's walk through practical, impactful optimizations you can apply to speed up this Collatz implementation:

• Replace slow parity checks with bit testing
  Your current code uses idiv to check if a number is even/odd—this is one of the slowest integer instructions. Instead, use the test instruction to check the least significant bit (LSB), which tells you immediately if the number is odd (LSB = 1) or even (LSB = 0):

  ; Replace the entire division-based parity check block with this:
  test rdi, 1
  jnz odd ; Jump to odd handling if LSB is set
  

  This eliminates the push rax/pop rax pair and the expensive division, cutting down on both instruction count and execution time. You can also remove the push rbx/pop rbx since we no longer use rbx for division.

• Simplify recursive result handling
  Right now, you zero out rax before each recursive call, then increment it afterward. Since the recursive call returns the count directly, you can skip the zeroing step entirely:

  even:
    sar rdi, 1
    call threexplusone
    inc rax ; Add 1 directly to the recursive result
    jmp done
  

  This saves an unnecessary xor rax, rax instruction per recursive call.

• Convert recursion to iteration (tail recursion elimination)
  Recursion adds overhead from call/ret instructions and stack frame management. For Collatz sequences, we can easily rewrite the logic into a loop to eliminate this overhead entirely—this is the biggest performance win for large input values:

  threexplusone:
    mov rax, 0 ; Initialize iteration count
  loop_start:
    cmp rdi, 1
    je done
    test rdi, 1
    jnz handle_odd
  handle_even:
    sar rdi, 1
    inc rax
    jmp loop_start
  handle_odd:
    lea rdi, [rdi*2 + rdi] ; Equivalent to 3*rdi, faster than imul
    inc rdi ; Add 1 to get 3x+1
    inc rax
    jmp loop_start
  done:
    ret
  

  This iterative version avoids all recursive call overhead, making it significantly faster for deep sequences.

• Optimize arithmetic instructions
  Replace imul rdi,3 with lea rdi, [rdi*2 + rdi]—lea uses the CPU's address generation unit and is often faster than imul because it doesn't modify arithmetic flags. Also, use inc rdi instead of add rdi,1 for the final +1 in the odd case; it's a smaller instruction with the same effect.

• Remove redundant jumps
  In your original code, after checking cmp rdi, 1, you use an explicit jmp threexplusone_recursive. You can instead just fall through to the parity check logic, eliminating one unnecessary branch.

• Add memoization for frequent values
  Small numbers (like 2,3,4) appear repeatedly in Collatz sequences. Precompute their iteration counts and store them in a lookup table. Before processing a value, check if it's in the table—if so, add the precomputed count to your total and skip the loop steps for that value. This reduces redundant calculations for common inputs.

• Improve branch prediction
  Modern CPUs rely on accurate branch prediction. Since even numbers are far more common in Collatz sequences (every odd step produces an even number), rearrange your code to handle even cases first. This helps the CPU predict branches more accurately, reducing pipeline stalls.

内容的提问来源于stack exchange，提问作者Hongyan Wu