Fastware - Andrei Alexandrescu (2017)

Simple principles:

Strength Reduction

Try to reduce strong operation in lesser operation. eg a /=2 replaced with a »= 1 Speed hierarchy: -comparisons -(u)int add substract, bitops, bitshift -FP add, sub -(u)int mul; FP mul -FP division, reminder -(u)int division, reminder (compiler transform integer div to multiply already)

Strength reduction example:

int digits10( int64 v) {
    result = 0;
    do {
        ++result;
        v /= 10;
    } while( v)
    return result;
}

Transform /= to comparison and addition. This is not loop unrolling.

int digits10( int64 v) {
    result = 1;
    for(;;){
        if( v <     10) return result;
        if( v <    100) return result + 1;
        if( v <  1'000) return result + 2;
        if( v < 10'000) return result + 3;
        v /= 10'000;
        result += 4;
    } 
}

Gives x2 to x6 speed improvement

Minimize indirect writes (through a pointer)

• impossible to put in register
• is really a read and write (because of cache line)

• make cache dirty

• fewer data dependencies (gives instruction parallelism)
• associative mean parallelizable

leads to 2x factor improvement faceboook/folly