optimization_and_hardware.md

Optimization and hardware

Table of contents

• Introduction and overview
• Compiler optimizations
  • Floating-point arithmetic
  • Heap allocation
  • Integeral division
  • Memory access
  • Return value optimization and copy elision
  • Undefined behavior
    • Strict aliasing rule
• CPU
• Memory and cache
  • Access
    • Copying
    • Nested std::vectors
  • Allocation
  • Relocation

---

Introduction and overview

🔗

• Optimizing C++ – WikiBooks

🎥

• H.Matthews. Optimising a small real-world C++ application – ACCU (2019)
• A.Alexandrescu. Speed is found in the minds of people – CppCon (2019)
• F.Pikus. Design for performance – CppCon (2018)
• H.Matthews. Optimising a small real-world C++ application – NDC (2018)
• H.Matthews. C++ performance and optimisation – NDC (2017)
• C.Cook. The speed game: Automated trading systems in C++ – Meeting C++ (2016)
• A.Alexandrescu. Optimization tips – CppCon (2014)

⚓

• Intel 64 and IA-32 architectures optimization reference manual

---

Compiler optimizations

:link

• 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

🎥

• C.Carruth. Understanding compiler optimization – code::dive (2016)

Floating-point arithmetic

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

Heap allocation

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

Integeral division

🔗

• Why does GCC use multiplication by a strange number in implementing integer division? – Stack Overflow
• D.W.Jones. Reciprocal multiplication, a tutorial (1999)
• T.Granlund, P.L.Montgomery. Division by invariant integers using multiplication (1994)

Memory access

🔗

• Why don’t C++ compilers optimize this conditional boolean assignment as an unconditional assignment? – Stack Overflow

Return value optimization and copy elision

📷

• J.Kalb. Copy elision – C++Now (2018)

⚓

• Copy elision – C++ reference

Undefined behavior

:link

• K.Walfridsson. How undefined signed overflow enables optimizations 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)

🎥

• J.Regehr. Undefined behavior and compiler optimizations – C++Now (2018)

Strict aliasing rule

See Type-punning – Core language.

---

CPU

🎥

• C.Bay. The CPU cache: Instruction re-ordering made obvious – C++Now (2016)
• M.Godbolt. x86 internals for fun & profit – GOTO (2014)

Memory and cache

🔗

• U.Drepper. What every programmer should know about memory (2007)
• D.A.Rusling. Ch. 3: Memory management – The Linux kernel
• Simple benchmark for memory throughput and latency
• L.Maranget, S.Sarkar, P.Sewell. A tutorial introduction to the ARM and POWER relaxed memory models (2012)

🎥

• T.Doumler. Want fast C++? Know your hardware! – CppCon (2016)
• S.Meyers. CPU caches and why you care – code::dive (2014)
• C.Terman. Virtual memory. Part I, Part II – MIT 6.004: Computation structures (2013)

Access

🔗

• Why is transposing a matrix of 512x512 much slower than transposing a matrix of 513x513? – Stack Overflow

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

Nested std::vectors

🔗

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

Allocation

🔗

• N.Fitzgerald. Always bump downwards (2019)

🎥

• A.Alexandrescu std::allocator is to allocation what std::vector is to vexation – CppCon (2015)

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/P1144R2 (2019)