Program optimization

From David's Wiki
Revision as of 19:47, 21 June 2023 by David (talk | contribs) (Created page with "The most important aspect of optimizing your program is to continuosly perform benchmarks. Without any metrics, you risk complicating your code without any actual performance improvements. ==Memory Access== See [https://people.freebsd.org/~lstewart/articles/cpumemory.pdf What Every Programmer Should Know About Memory] and [https://www.forrestthewoods.com/blog/memory-bandwidth-napkin-math/ Memory Bandwidth Napkin Math]. In general, try to access memory sequentially to...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
\( \newcommand{\P}[]{\unicode{xB6}} \newcommand{\AA}[]{\unicode{x212B}} \newcommand{\empty}[]{\emptyset} \newcommand{\O}[]{\emptyset} \newcommand{\Alpha}[]{Α} \newcommand{\Beta}[]{Β} \newcommand{\Epsilon}[]{Ε} \newcommand{\Iota}[]{Ι} \newcommand{\Kappa}[]{Κ} \newcommand{\Rho}[]{Ρ} \newcommand{\Tau}[]{Τ} \newcommand{\Zeta}[]{Ζ} \newcommand{\Mu}[]{\unicode{x039C}} \newcommand{\Chi}[]{Χ} \newcommand{\Eta}[]{\unicode{x0397}} \newcommand{\Nu}[]{\unicode{x039D}} \newcommand{\Omicron}[]{\unicode{x039F}} \DeclareMathOperator{\sgn}{sgn} \def\oiint{\mathop{\vcenter{\mathchoice{\huge\unicode{x222F}\,}{\unicode{x222F}}{\unicode{x222F}}{\unicode{x222F}}}\,}\nolimits} \def\oiiint{\mathop{\vcenter{\mathchoice{\huge\unicode{x2230}\,}{\unicode{x2230}}{\unicode{x2230}}{\unicode{x2230}}}\,}\nolimits} \)

The most important aspect of optimizing your program is to continuosly perform benchmarks. Without any metrics, you risk complicating your code without any actual performance improvements.

Memory Access

See What Every Programmer Should Know About Memory and Memory Bandwidth Napkin Math.

In general, try to access memory sequentially to maximize the use of cache. Accessing memory can be 10x-100x slower than accessing cache. This means paying attention to ordering (i.e. row-major vs column-major) when iterating over arrays.

  1. For small amounts of data, it may be better to directly use an array instead of a fancy data structure which requires jumping around in memory.
  2. For variables used together, it may make sense to put them in a struct so they are close together in memory.
  3. Variables independently accessed by multiple threads can but put into thread-local storage (TLS).

Branchless Programming

Branchless programming is typically a micro-optimization since small branches are optimized by the compiler. However, if this fails to occur, you can consider manually removing branches in your code.