optimization_and_hardware.md

Optimization

Table of contents

• Optimizations
  • Branch prediction
    • [[likely]] / [[unlikely]] attributes
    • likely / unlikely Linux kernel macros
  • Memory
    • Memory copying
    • Memory allocation
    • Memory relocation
    • Memory access
    • Nested std::vectors
    • Aliasing
  • Floating-point arithmetic
  • Integral arithmetic
    • Integral multiplication
    • Integeral division
  • Empty base class optimization (EBO)
  • Return value optimization and copy elision
  • Tail call optimisation
  • Devirtualization
  • Undefined behavior
    • Infinite loops
    • Strict aliasing rule
• Benchmarking
• Profiling

---

Optimizations

See also Optimizations – Compilers.

🔗

• Optimizing C++ – WikiBooks
• A.O’Dwyer. [[trivial_abi]] 101

❔

• Can const-correctness improve performance? – Stack Overflow
• Why does this loop produce “warning: iteration 3u invokes undefined behavior” and output more than 4 lines? – Stack Overflow
• What is tail call optimization? – Stack Overflow
• Is premature optimization really the root of all evil? – Software Engineering

🎥

• A.Lachmish. Algorithmic complexity, data locality, parallelism, and compiler optimizations, seasoned with some concurrency – CppCon (2022)
• J.Bielak. The most important otimizations to apply in your C++ programs – CppCon (2022)
• A.Alexandrescu. Speed is found in the minds of people – CppCon (2019)
• H.Matthews. Optimising a small real-world C++ application – ACCU (2019)
• H.Matthews. Optimising a small real-world C++ application – NDC (2018)
• H.Matthews. C++ performance and optimisation – NDC (2017)
• F.Pikus. Design for performance – CppCon (2018)
• C.Bay. The CPU cache: Instruction re-ordering made obvious – C++Now (2016)
• C.Carruth. Understanding compiler optimization – code::dive (2016)
• C.Cook. The speed game: Automated trading systems in C++ – Meeting C++ (2016)
• T.Doumler. Want fast C++? Know your hardware! – CppCon (2016)
• A.Alexandrescu. Optimization tips – CppCon (2014)
• M.Godbolt. x86 internals for fun & profit – GOTO (2014)
• S.Meyers. CPU caches and why you care – code::dive (2014)

📖

• Col. 9: Code tuning – J.Bentley. Programming pearls (1999)

⚓

• Intel 64 and IA-32 architectures optimization reference manual

Branch prediction

🔗

• Branch predictor – Wikipedia

[[likely]] / [[unlikely]] attributes

These attributes allow the compiler to optimize for the case where paths of execution are more or less likely than any alternative path of execution.

❔

• How to use C++20’s likely/unlikely attributes in if-else statement – Stack Overflow

⚓

• C++ attribute: likely, unlikely – C++ reference

likely / unlikely Linux kernel macros

❔

• How do the likely/unlikely macros in the Linux kernel work and what is their benefit? – Stack Overflow

Memory

🔗

• J.Müller. malloc() and free() are a bad API (2022)

Memory copying

🔗

• Time to revisit REP MOVS – Intel Developer Zone (2006)

❔

• Enhanced REP MOVSB for memcpy – Stack Overflow
• What setup does REP do? – Stack Overflow
• Why are complicated memcpy/memset superior? – Stack Overflow

Memory allocation

See also Allocators – The standard library and proposals.

🔗

• N.Fitzgerald. Always bump downwards (2019)

❔

• Is the compiler allowed to optimize out heap memory allocations? – Stack Overflow

🎥

• S.Al Bahra, H.Sowa, P.Khuong. What programmers should know about memory allocation – CppCon (2019)
• J.Lakos. Local (“arena”) memory allocators. Part I, Part II – CppCon (2017)
• J.Lakos. Local (“arena”) memory allocators – ACCU (2017)
• A.Alexandrescu. std::allocator is to allocation what std::vector is to vexation – CppCon (2015)

Memory relocation

🔗

• A.O’Dwyer. Announcing “trivially relocatable” (2018)

🎥

• A.O’Dwyer. Trivially relocatable – C++Now (2019)

⚓

• A.O’Dwyer. Object relocation in terms of move plus destroy – WG21/P1144

Memory access

❔

• Why is transposing a matrix of 512x512 much slower than transposing a matrix of 513x513? – Stack Overflow
• Why are elementwise additions much faster in separate loops than in a combined loop? – Stack Overflow
• Why don’t C++ compilers optimize this conditional boolean assignment as an unconditional assignment? – Stack Overflow

Nested std::vectors

❔

• Is it a good idea to use vector<vector<double>> to form a matrix class for high performance scientific computing code? – Computational Science
• Performance impact of nested vectors vs. contiguous arrays – Stack Overflow
• Using nested vectors vs a flatten vector wrapper, strange behaviour – Stack Overflow

Aliasing

See also Type-punning – Core language.

🎥

• R.Barkan. Aliasing: Risks, opportunities and techniques – CppCon (2022)
• R.Barkan. Aliasing: Risks, opportunities and techniques – C++ on Sea (2022)

Floating-point arithmetic

🔗

• K.Walfridsson. Optimizations enabled by -ffast-math (2021)

❔

• What does gcc’s ffast-math actually do? – Stack Overflow

⚓

• Bug 323: Optimized code gives strange floating point results – GCC Bugzilla

Integral arithmetic

❔

• What is the performance impact of using int64_t instead of int32_t on 32-bit systems? – Stack Overflow

Integral multiplication

❔

• Why is imul used for multiplying unsigned numbers? – Stack Overflow

Integeral division

🔗

• D.W.Jones. Reciprocal multiplication, a tutorial (1999)
• T.Granlund, P.L.Montgomery. Division by invariant integers using multiplication (1994)

❔

• Why does GCC use multiplication by a strange number in implementing integer division? – Stack Overflow
• Why does the compiler generate a right-shift by 31 bits when dividing by 2? – Stack Overflow

Empty base class optimization (EBO)

Empty base class optimization allows the size of an empty base subobject to be zero. Empty base optimization is required for standard layout types.

struct Empty {};
static_assert(sizeof(Empty) >= 1);

struct Derived : Empty {
    T i;
};
static_assert(sizeof(Derived) == sizeof(T));

🔗

• N.C.Myers. The “empty member” C++ optimization (mirror) – Dr.Dobb’s Journal (1997)
• Empty base optimization – WikiBooks
• boost::compressed_pair
• boost::empty_value

🎥

• J.Berg. Empty objects – Sweden C++ (2023)

📖

• Sec. 21.1: The empty base class optimization, Sec. 25.5.1: Tuples and the EBCO – D.Vandevoorde, N.M.Josuttis, D.Gregor. C++ templates: The complete guide – Addison-Wesley (2017)

⚓

• Empty base optimization – C++ reference

Return value optimization and copy elision

🔗

• R.Chen. On harmful overuse of std::move (2023)
• A.Fertig. Why you should use std::move only rarely (2022)

🎥

• A.O’Dwyer. The complete guide to return x; – C++Now (2021)
• J.Kalb. Copy elision – C++Now (2018)

⚓

• Copy elision – C++ reference

Tail call optimisation

🔗

• A.O’Dwyer. It’s not always obvious when tail-call optimization is allowed (2021)
• A.Balaam. Tail call optimisation in C++ – Overload 109 (2012)

Devirtualization

🔗

• A.O’Dwyer. When can the C++ compiler devirtualize a call? (2021)

Undefined behavior

🔗

• T.Chatzigiannakis. Undefined behavior can literally erase your hard disk (2017)
• K.Walfridsson. How undefined signed overflow enables optimizations in GCC (2016)
• K.Walfridsson. Dangling pointers and undefined behavior (2016)
• K.Walfridsson. Pointer comparison — an invalid optimization in GCC (2016)
• J.Regehr. Finding undefined behavior bugs by finding dead code (2013)
• C.Lattner. What every C programmer should know about undefined behavior. Part I, Part II, Part III – LLVM project (2013)
• O.Maudel. Demons may fly out of your nose – Overload 115 (2013)
• M.Shroyer. Both true and false: A Zen moment with C (2012)

🎥

• F.Pikus. Undefined behavior in C++: What every programmer should know and fear – CppCon (2023)
• A.Meredith. Removing needless undefined behavior for a safer C++ – ACCU (2023)
• A.Sermersheim, B.Geller. Back to basics: Undefined behavior – CppCon (2021)
• J.Regehr. Undefined behavior and compiler optimizations – C++Now (2018)
• B.Geller, A.Sermersheim. Undefined behavior is not an error – CppCon (2018)
• P.Padlewski. Undefined behaviour is awesome! – CppCon (2017)
• M.Spencer. My little optimizer: Undefined behavior is magic – CppCon (2016)

Infinite loops

See also Infinite loop – Patterns, idioms, and design principles.

❔

• Optimizing away a while(1); in C++0x – Stack Overflow

🎥

• O.Giroux. Forward progress in C++ – CppNorth (2022)

⚓

• H.-J. Boehm. Why undefined behavior for infinite loops? – WG14/N1528
• JF.Bastien. Trivial infinite loops are not Undefined Behavior – WG14/P2809

Strict aliasing rule

See Type-punning – Core language.

---

Benchmarking

🔗

• D.Ferenc. Contractual loopholes – Overload 138 (2017)

---

Profiling

🎥

• M.Ropert. The basics of profiling – CppCon (2021)