notes

Personal notes
git clone git://git.laack.co/notes.git
Log | Files | Refs

BentleyRules.md (2636B)


      1 # Bentley Rules for Optimizing Work
      2 
      3 **Source:** MIT 6.172 Performance Engineering of Software Systems, Fall 2018
      4 
      5 **Definition:** Bentley rules are rules for optimizing the work performed by computer programs, from his book "Writing Efficient Programs".
      6 
      7 Some of the original rules are no longer applicable due to computer architecture changes, but these won't be included in these notes.
      8 
      9 ## Rules
     10 
     11 - Datastructures
     12     1. Packing and encoding
     13         - Compressed representations increase the likelihood for cache hits
     14     2. Augmentation
     15         - Augment data structures to make specific operations perform less work
     16             - Ex. reference to tail for singly linked lists
     17     3. Precomputation / compile-time initialization
     18         - Perform calculations in advanced to decrease work during critical sections
     19             - Ex. Meta-programming to precompute tables at compile-time
     20     4. Caching
     21         - Store previous results to decrease repeated work
     22     5. Lazy evaluation
     23         - Sparsity
     24         - Compress representations of data
     25             - Ex. compressed sparse row matrix representation
     26 - Logic
     27     1. Constant folding an propagation
     28         - Evaluate constant expressions and substitute their results into further expressions at compile time
     29     2. Common-subexpression elimination
     30         - Evaluate an expression and store it for reuse
     31             - This is a specific case of caching
     32     3. Algebraic identities
     33         - Using identities to replace more costly operations with equivalent cheaper ones
     34     4. Short-circuiting
     35         - When performing a series of tests, stop evaluating once an answer is found
     36     5. Creating a fast path
     37         - Perform cheaper tests before performing full tests to evaluate invariants
     38             - Ex. Before checking euclidean distance check Manhattan distance
     39     6. Combining tests
     40         - Replace a sequence of tests with one test or switch
     41 - Loops
     42     1. Hoisting
     43         - Avoid recomputing loop-invariant code
     44     2. Sentinels
     45         - Dummy values to simplify logic of boundary conditions
     46     3. Loop unrolling
     47         - Combining consecutive iterations of the loop into a single iteration
     48             - Partial unrolling
     49                 - Decreased number of loop iterations
     50             - Full unrolling
     51                 - No loop
     52     4. Loop fusion
     53         - Combine multiple loops when they have the same index ranges
     54     5. Eliminate wasted iterations
     55 - Functions
     56     1. Inlining
     57         - Replaces the overhead of a function call
     58     2. Tail recursion elimination
     59     3. Coarsening recursion
     60         - Make base case larger to decrease recursion depth