Skip to content
  • Neutron3529's avatar
    Rearrange the pipeline of `pow` to gain efficiency · ef74e508
    Neutron3529 authored
    The check of the `exp` parameter seems useless if we execute the while-loop more than once.
    The original implementation of `pow` function using one more comparison if the `exp==0` and may break the pipeline of the cpu, which may generate a slower code.
    The performance gap between the old and the new implementation may be small, but IMO, at least the newer one looks more beautiful.
    
    ---
    
    bench prog:
    ```
    extern crate test;
    ($a:expr)=>{let time=std::time::Instant::now();{$a;}print!("{:?} ",time.elapsed())};
    ($a:expr,$b:literal)=>{let time=std::time::Instant::now();let mut a=0;for _ in 0..$b{a^=$a;}print!("{:?} {} ",time.elapsed(),a)}
    }
    pub fn pow_rust(x:i64, mut exp: u32) -> i64 {
        let mut base = x;
        let mut acc = 1;
        while exp > 1 {
            if (exp & 1) == 1 {
                acc = acc * base;
            }
            exp /= 2;
            base = base * base;
        }
        if exp == 1 {
            acc = acc * base;
        }
        acc
    }
    pub fn pow_new(x:i64, mut exp: u32) -> i64 {
        if exp==0{
            1
        }else{
            let mut base = x;
            let mut acc = 1;
            while exp > 1 {
                if (exp & 1) == 1 {
                    acc = acc * base;
                }
                exp >>= 1;
                base = base * base;
            }
            acc * base
        }
    }
    
    fn main(){
    let a=2i64;
    let b=1_u32;
    println!();
    timing!(test::black_box(a).pow(test::black_box(b)),100000000);
    timing!(pow_new(test::black_box(a),test::black_box(b)),100000000);
    timing!(pow_rust(test::black_box(a),test::black_box(b)),100000000);
    println!();
    timing!(test::black_box(a).pow(test::black_box(b)),100000000);
    timing!(pow_new(test::black_box(a),test::black_box(b)),100000000);
    timing!(pow_rust(test::black_box(a),test::black_box(b)),100000000);
    println!();
    timing!(test::black_box(a).pow(test::black_box(b)),100000000);
    timing!(pow_new(test::black_box(a),test::black_box(b)),100000000);
    timing!(pow_rust(test::black_box(a),test::black_box(b)),100000000);
    println!();
    timing!(test::black_box(a).pow(test::black_box(b)),100000000);
    timing!(pow_new(test::black_box(a),test::black_box(b)),100000000);
    timing!(pow_rust(test::black_box(a),test::black_box(b)),100000000);
    println!();
    timing!(test::black_box(a).pow(test::black_box(b)),100000000);
    timing!(pow_new(test::black_box(a),test::black_box(b)),100000000);
    timing!(pow_rust(test::black_box(a),test::black_box(b)),100000000);
    println!();
    timing!(test::black_box(a).pow(test::black_box(b)),100000000);
    timing!(pow_new(test::black_box(a),test::black_box(b)),100000000);
    timing!(pow_rust(test::black_box(a),test::black_box(b)),100000000);
    println!();
    timing!(test::black_box(a).pow(test::black_box(b)),100000000);
    timing!(pow_new(test::black_box(a),test::black_box(b)),100000000);
    timing!(pow_rust(test::black_box(a),test::black_box(b)),100000000);
    println!();
    timing!(test::black_box(a).pow(test::black_box(b)),100000000);
    timing!(pow_new(test::black_box(a),test::black_box(b)),100000000);
    timing!(pow_rust(test::black_box(a),test::black_box(b)),100000000);
    println!();
    }
    ```
    bench in my laptop:
    ```
    neutron@Neutron:/me/rust$ rc commit.rs
    rustc commit.rs  && ./commit
    
    3.978419716s 0 4.079765171s 0 3.964630622s 0
    3.997127013s 0 4.260304804s 0 3.997638211s 0
    3.963195544s 0 4.11657718s 0 4.176054164s 0
    3.830128579s 0 3.980396122s 0 3.937258567s 0
    3.986055948s 0 4.127804162s 0 4.018943411s 0
    4.185568857s 0 4.217512517s 0 3.98313603s 0
    3.863018225s 0 4.030447988s 0 3.694878237s 0
    4.206987927s 0 4.137608047s 0 4.115564664s 0
    neutron@Neutron:/me/rust$ rc commit.rs -O
    rustc commit.rs -O && ./commit
    
    162.111993ms 0 165.107125ms 0 166.26924ms 0
    175.20479ms 0 205.062565ms 0 176.278791ms 0
    174.408975ms 0 166.526899ms 0 201.857604ms 0
    146.190062ms 0 168.592821ms 0 154.61411ms 0
    199.678912ms 0 168.411598ms 0 162.129996ms 0
    147.420765ms 0 209.759326ms 0 154.807907ms 0
    165.507134ms 0 188.476239ms 0 157.351524ms 0
    121.320123ms 0 126.401229ms 0 114.86428ms 0
    ```
    
    delete an unnecessary semicolon...
    
    Sorry for the typo.
    
    delete trailing whitespace
    
    Sorry, too..
    
    Sorry for the missing...
    
    I checked all the implementations, and finally found that there is one function that does not check whether `exp == 0`
    
    add extra tests
    
    add extra tests.
    
    finished adding the extra tests to prevent further typo
    
    add pow(2) to negative exp
    
    add whitespace.
    
    add whitespace
    
    add whitespace
    
    delete extra line
    ef74e508