david's pl notes

2024-07-10 • optimizations and gc

Sep 02, 20242 min read

Since this is a very general topic, this note serves both to track my readings for this week of prelim prep, but also as an index for resources on program optimization generally.

See also

This note borrows from Wikipedia.

Static optimization

There are a number of techniques we can make use of to optimize. The Dragon book provides an example of a number of these:

The principal sources of optimization

Using high-level languages often introduces redundant operations. For example, if you do array access via A[i][j], you’re doing pointer arithmetic under the hood, which might end up being duplicated. In this section, we provide some examples of semantics-preserving transformations/optimizations.

  • Global common subexpressions: if an expression was previously computed and the values of the variables in haven’t changed since the previous computation.
  • Copy propagation: If we have a copy statement x = v somewhere, wherever we use x afterwards, we should use v instead. This might not seem to change anything, but this helps improve dead-code elimination. Speaking of!
  • Dead-code elimination: if a statement computes values that are never used, it can just be removed. This is why copy propagation is important; if we have x = v; y = 2 * x, with copy propagation + dead-code elim we can remove x entirely!
  • Constant folding: deducing at compile time that an expression’s value is constant and using that constant value
  • Code motion: If an expression in a loop yields the same result on every iteration, it’s taken out of the loop ^9d6c9d
    • e.g., while (i <= x - 2) becomes t = x - 2; while (i <= t)
  • Induction variables & strength reduction: if a variable changes by a constant c on each reassignment, it’s an induction variable. Strength reduction is replacing an expensive op (e.g., multiplication) with a cheaper one (e.g., addition).
Link to original

I’ve taken notes on a few other things mentioned explicitly in the syllabus:

And I’ve noted a few other areas for optimization (from here and also this extremely useful Wikipedia page that has a big summary)

  • algebraic reductions (i.e., partial evaluation), like x + 0 -> x and 0 == 0 -> true
  • peephole optimizations, where we look at adjacent instructions in assembly and replace them with more efficient alternatives
  • register allocation: the most frequently used vars should be kept in processor registers for fastest access.
  • tail-call optimization: if we have a tail-call, we don’t need to keep pushing function frames! see also continuations
  • bounds-checking elimination
  • symbolic execution: see CS 264 Notes for now

Crucially, these optimizations all enable one another. Copy propagation, global value numbering, and common subexpression elimination make each other possible!

Runtime optimization

There are a few ways to optimize programs at runtime. Just-in-time (JIT) compilers produce customized machine code based on runtime data and input, at the cost of compilation overhead. Regex engines do this. Java HotSpot, JavaScript’s V8, and Julia are common examples of this now.

There are a few other important terms to know here:

  • Adaptive optimization does dynamic recompiling of portions of a program based on the current execution profile. This is a general term that encompasses a few techniques: choosing whether to JIT or not, choosing whether to inline at runtime, etc.
  • Profile-guided optimization is an ahead-of-time (AOT) strategy that uses runtime profiles to inform optimization. It’s the static version of adaptive optimiztation.
  • Self-modifying code can alter itself in response to runtime conditions.
  • CPUs do lots of runtime optimization: out-of-order execution, speculative execution, instruction pipelines (running multiple instructions at once by staggering instruction fetch, decode, etc.), and branch prediction.

Garbage collection

Graph View

Backlinks