Lecture 2: Bentley Rules for Optimizing Work

What this lecture covers

This lecture defines "work" as the total number of operations a program executes, and argues that reducing work is a useful, though imperfect, heuristic for reducing running time. Julian Shun works through 22 optimization rules organized into four categories: data structures, logic, loops, and functions, named after Jon Bentley's 1982 book Writing Efficient Programs. Unlike architecture-specific tricks covered later in the course, these rules apply broadly across languages and machines.

After watching, you should recognize opportunities to reduce redundant computation in your own code, know when the compiler already handles an optimization automatically, and understand why some of these techniques trade memory for speed or vice versa. The lecture builds on Lecture 1's framing of performance as something worth budgeting deliberately, but stays at the level of source code rather than hardware.

Key ideas

• Work: the sum of all operations a program executes on a given input; reducing it is a heuristic for reducing running time, not a guarantee, since hardware effects like caching and branch prediction aren't captured by the count.
• Packing and encoding: storing multiple values in one machine word, or using fewer bits per value, cuts the memory traffic needed to move data around.
• Precomputation and compile-time initialization: computing results like binomial coefficient tables once, ideally at compile time via generated source code, avoids repeating the work at every run.
• Caching: storing recently computed results (such as an expensive square root) so repeated calls with the same inputs skip recomputation.
• Sparsity (compressed sparse row): a matrix or graph representation that stores only nonzero entries, cutting both memory and the number of operations needed for operations like matrix-vector multiply.
• Short-circuiting and fast paths: stopping a series of tests as soon as the answer is known, and ordering tests so cheap or frequently-true checks run first.
• Loop optimizations: hoisting invariant computation out of a loop, unrolling loops to reduce control overhead, and fusing loops over the same index range to improve cache reuse.
• Inlining: replacing a function call with its body to avoid call overhead, which the compiler often does automatically for functions declared static inline.

Walkthrough

Defining work and the Bentley rules (0:01)

Shun defines work as the total operations executed and distinguishes it from running time, since instruction-level parallelism, caching, and vectorization affect actual speed. He introduces Jon Bentley's original rules and previews today's updated set of 22, grouped into data structures, logic, loops, and functions.

Data structure optimizations (4:02)

The lecture covers packing and encoding (representing a date in 22 bits instead of 18 bytes, or using C bit fields for fast field access), data structure augmentation (adding a tail pointer to a singly linked list to make list append constant time instead of requiring a full traversal), precomputation of Pascal's triangle for binomial coefficients, compile-time table initialization via meta-programming, caching of expensive results such as square roots, and the compressed sparse row (CSR) format for sparse matrices and graphs, which stores only nonzero entries using offset and index arrays.

Logic optimizations (38:30)

Shun demonstrates constant folding and propagation (evaluating fixed expressions like orrery dimensions at compile time), common subexpression elimination (computing a - d once instead of twice when its value hasn't changed), and algebraic identities (comparing squared distances instead of taking a square root in a ball-collision test, since sqrt(u) <= v is equivalent to u <= v^2). He also covers short-circuiting logical tests, ordering tests from most-frequent to least-frequent and cheapest to most expensive, building a fast path that avoids expensive tests when a cheap check already rules out the expensive case (checking bounding-box overlap before the exact collision formula), and combining multiple if/else branches into a single switch statement or table lookup.

Loop optimizations (1:00:50)

The lecture covers hoisting (moving loop-invariant computation, such as a constant exponential, outside the loop body), using sentinel values to collapse two per-iteration checks into one when testing for integer overflow, full and partial loop unrolling (partial unrolling mainly helps by giving the compiler more code to optimize within, not just by cutting loop-control overhead), loop fusion (merging two loops over the same index range to improve cache reuse of shared data), and eliminating wasted iterations, illustrated with a matrix transpose that only loops over the entries actually needing a swap.

Function optimizations and closing advice (1:16:15)

Shun explains inlining, where a function's body replaces its call site to avoid call overhead, noting that modern compilers usually do this automatically and that inline functions are safer than macros because macros can re-evaluate expensive arguments multiple times through textual substitution. Two further techniques, tail recursion elimination and recursion removal, are mentioned but left for self-study. The lecture closes by cautioning against premature optimization: correctness comes first, regression tests should guard against optimization-introduced bugs, and reducing work is only a heuristic for reducing running time.

Before you watch

• Watch Lecture 1 first for the framing of performance as a currency and the context for why these optimizations matter.
• Familiarity with basic data structures (linked lists, arrays, matrices) and C syntax (structs, bit fields) is assumed.
• Basic algorithms background (sorting, recursion) helps but isn't required.

Check your understanding

1. Why does reducing the work of a program not always reduce its running time?
2. How does the compressed sparse row format reduce both memory usage and the number of operations for matrix-vector multiplication?
3. Explain why comparing squared distances instead of taking a square root is a valid optimization for the ball-collision test.
4. What is the main benefit of partial loop unrolling beyond reducing the number of loop-control checks?
5. Why can loop fusion improve cache locality compared to running two separate loops over the same range?