비트연산 최적화

if문을 사용하면 느려진다. 비트연산으로 최적화했다.

pub fn calculation(i: u128) ->bool{
    let mut n = i;
    // while n >= i{
    //     if n % 2 == 0 {
    //         n = n >> 1;
    //     } else {
    //         n = (n << 1) + n + 1;
    //     }
    // }
    while n >= i {
        let odd = n & 1; // 1 = odd, 0 = even

        // (n >> 1) * (1 - odd) + ((n << 1) + n + 1) * odd
        n = ((n >> 1) & (!odd).wrapping_neg()) | (((n << 1) + n + 1) & odd.wrapping_neg());
    }
    true
}

주석이 원래 코드, 활성화된게 이후 코드이다.
홀짝을 구분해 2의 보수로 00000../11111.. 마스크를 만들고 홀수/짝수일 때 둘 다 계산하고 비트마스크 후 더한다.
예를 들어 홀수라면, /2계산을 0000...과 and연산하여 0으로 만드는 식이다.
컴퓨터가 비트연산을 하는 기계이므로, 기계에 맞춰주면 더 빠르다.

(.venv) Collatz_Conjecture/parallel [ cargo run --release -- para         main * ] 5:43 PM
   Compiling parallel v0.1.0 (/Users/Taery/Collatz_Conjecture/parallel)
    Finished `release` profile [optimized] target(s) in 0.59s
     Running `target/release/parallel para`
parallel start
end 1073741824 numbers
걸린 시간: 449.726167ms
(.venv) Collatz_Conjecture/parallel [ cargo run --release -- para         main * ] 5:43 PM
   Compiling parallel v0.1.0 (/Users/Taery/Collatz_Conjecture/parallel)
    Finished `release` profile [optimized] target(s) in 0.41s
     Running `target/release/parallel para`
parallel start
end 1073741824 numbers
걸린 시간: 1.577015666s 

M2 맥북에어이다. 2^30까지 계산했다. 위가 비트연산, 아래가 if문이다. 3배 빨라졌다.

cpu에서는 3배이지만 gpu에서는 효과가 훨씬 클 것이다.

(.venv) Collatz_Conjecture/parallel [ cargo run --release -- para
   Compiling parallel v0.1.0 (/Users/Taery/Collatz_Conjecture/parallel)
    Finished `release` profile [optimized] target(s) in 0.16s
     Running `target/release/parallel para`
parallel start
end 1073741824 numbers
걸린 시간: 303.282084ms
(.venv) Collatz_Conjecture/parallel [ cargo run --release -- para
   Compiling parallel v0.1.0 (/Users/Taery/Collatz_Conjecture/parallel)
    Finished `release` profile [optimized] target(s) in 0.38s
     Running `target/release/parallel para`
parallel start
end 1073741824 numbers
걸린 시간: 440.417µs 

위가 인라인금지, 아래가 인라인금지 뺀 코드이다. 인라인된 코드가 1000배 더 빠르다. 뭔가 최적화(아니면 dead code?) 가 이루어진 것 같다. 어셈블리를 더 봐야겠다.