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