Bentley Rules for Optimizing Work


Agenda

  • Data structures
    • Packing and encoding
    • Augmentation
    • Precomputation
    • Compile-time initialization
    • Caching
    • Lazy evaluation
    • Sparsity
  • Loops
    • Hoisting
    • Sentinels
    • Loop unrolling
    • Loop fusion
    • Eliminating wasted iterations
  • Logic
    • Constant folding and propagation
    • Common-subexpression elimination
    • Algebraic identities
    • Short-circuiting
    • Ordering tests
    • Creating a fast path
    • Combining tests
  • Functions
    • Inlining
    • Tail-recursion elimination
    • Coarsening recursion

Data Structures

Packing and Encoding

The idea of packing is to store more than one data value in a machine word. The related idea of encoding is to convert data values into a representation requiring fewer bits.

Augmentation

The idea of data-structure augmentation is to add information to a data structure to make common operations do less work.

Example: Appending singly linked lists

  • Appending one list to another requires walking the length of the first list to set its null pointer to the start of the second.
  • AUgmenting the list with a tail pointer allows appending to operate in a constant time.

Precomputation

The idea of precomputation is to perform calculations in advance so as to avoid doing them at “mission-critical” times.

Compile-time initialization

The idea of **compile-time initalization is to store the values of constants during compilation, saving work at execution time.

Idea: Creat large static tables by metaprogramming.

Sparsity

THe idea of exploting sparsity is to avoid storing and computing on zeros. “The fastest way to compute is not to compute at all”.

Logic

Constant Folding and Propagation

The idea of constant folding and propagation is to evaluate constant expressions and substitue the result into further expressions, all during compilation.

void orrery() {
    const double x = 1;
    const doube y = 2 * x;
    const double z = M_PI * y;
    //...
}

With a sufficiently high optimization level, all the expressions are evaluated at compile-time.

Common-Subexpression Elimination

The idea of common-subexpression elimination is to avoid computing the same expression multiple times by evaluating the expression once and storing the result for later use.

Algebraic Identities

The idea of exploiting algebraic identities is to preplace expensive algebraic expressions with algebraic equivalents that require less work.

Short-Circuiting

WHen performing a series of tests, the idea of short-circuiting is to stop evaluating as soon as you know the answer.

Functions

Inlining

The idea of inlining is to avoid the overhead of a function call by replacing a call to the function with the body of the function itself.

double square(doube x) {
    return x*x;
}

double sum_of_squares(double* A, int n) {
    double sum = 0.0f;
    for (int i=0; i<n; ++i){
        sum += square(A[i]);
    }
    return sum;
}

We can inline the square function to reduce the overhead (stack expend). To do that, we can simply mark fucntion using static inline keywords. It turns out for some modern compilers, the functions can be inlined without declaring “static inline”.