People generally don’t get very excited over 5-10% performance improvements in some databases. Yes, this is what software engineers are paid for, but these types of optimizations tend to be too intricate and system-specific to be readily generalized to other software.
Instead, the most fascinating showcases of performance engineering are multifold improvements of textbook algorithms: the kinds that everybody knows and deemed so simple that it would never even occur to try to optimize them in the first place. These optimizations are simple and instructive and can very much be adopted elsewhere — and they are surprisingly not as rare as you would think.
In this talk, we will focus on one such fundamental algorithm — binary search — and discuss several ways of making it faster using branchless programming, memory layout optimization, and SIMD instructions, and eventually develop an algorithm that is up to ~15x faster than std::lower_bound.
---
Sergey Slotin
Sergey Slotin is the author of Algorithms for Modern Hardware (en.algorithmica.org/hpc).
---
Videos Streamed & Edited by Digital Medium: http://online.digital-medium.co.uk
The Dark Corner of STL in Cpp : MinMax Algorithms - Šimon Tóth - CppCon 2022
https://github.com/CppCon/CppCon2022
How many problems could one possibly run into when calling a simple algorithm such as std::min?
In this talk, we will take a deep dive into the ergonomics of min-max algorithms and explore several language features in the process:
• reference semantics and lifetime issues
• const correctness and use of const_cast
• costs of using the std::initializer_list
We will finish by exploring the options for addressing these issues when implementing functions with similar semantics.
---
Šimon Tóth
Currently on a mission to share my 20 years' worth of Software Engineering experience with the world.
__
Videos Streamed & Edited by Digital Medium: http://online.digital-medium.co.uk
The Most Important Optimizations to Apply in Your C++ Programs - Jan Bielak - CppCon 2022
https://github.com/CppCon/CppCon2022
Writing efficient programs is hard. This is because it requires a lot of knowledge, experience and strategic thinking. There have been many talks on optimization and often each addresses a single concept. Being able to achieve a bird’s eye view of factors affecting performance often requires many hours of researching the topic. To lessen the mental burden of optimizing programs, I have picked out the techniques, I believe are most important. During the talk, I will present them in an organized manner and provide practical examples of how they can be applied.
I will first discuss what I believe are the main goals efficient programs strive to achieve. Then, I will present the general methods of achieving those goals. Then, for the majority of the talk, we will discuss a few dozen performance opportunities. For each of them, I will explain the underlying mechanism of how the optimisation works. I will avoid bluntly giving guidelines to follow without explanation. Each of the techniques naturally comes with its costs, and those will be discussed as well.
I will additionally discuss various performance pitfalls. These are sometimes called “premature pessimisations” in contrast to the often used term of “premature optimizations”. I will show examples of optimizations which do not incur any cost on program readability or maintainability and as such should be considered performance best practices. Avoiding their use doesn’t improve code in any manner, while making it slower.
This talk is intended for a diverse audience, as after all, probably most of the C++ community is interested in performance. It is appropriate for hobbyists and professionals alike, with varying experience with the language, due to the gradual increase in difficulty of examples. It will be a time productively spent.
---
Jan Bielak
Jan Bielak is a student at the Warsaw Staszic High School. His main areas of interest are physics and computer science. He is especially into advanced C++ cppcon.digital-medium.co.uk/tag/programming/">programming and physically based real-time rendering. He also hosts and educational YouTube channel. He is involved in the CyberDuck project and in the PaSh project. In free time, he likes to create renders in Blender.
Graph Algorithms and Data Structures in C++20 - Phil Ratzloff, Andrew Lumsdaine - CppCon 2022
https://github.com/CppCon/CppCon2022
The C++ Standard Library is a valuable collection of generic algorithms and data structures that improves the usability and reliability of C++ software. Graph algorithms and data structures are notably absent from the standard library, and previous attempts to fill this gap have not gained widespread adoption.
This session presents an approach for expressing graph algorithms in a modern, composable, and extensible, aka generic, fashion. Concepts provide a means for a systematic organization of the type requirements for graph algorithms to operate correctly and efficiently. Remarkably, these type requirements can be expressed not in graph-specific terms, but rather in terms of existing sets of requirements already in place for basic containers in C++, i.e., ranges. Using this conceptual framework, we develop several generic algorithms and concrete data structures as well as the emerging proposal for a standard graph library.
---
Phil Ratzloff
Phil Ratzloff is a Distinguished Software Developer and C++ advocate at SAS Institute. He has used C++ for 27 years on applications using graphs for business cost analysis and fraud detection.
---
Andrew Lumsdaine
Andrew Lumsdaine is an internationally recognized expert in the area of high-performance computing who has made important contributions in many of the constitutive areas of HPC, including systems, programming languages, software libraries, and performance modeling. His work in HPC has been motivated by data-driven problems (e.g., large-scale graph analytics), as well as more traditional computational science problems. He has been an active participant in multiple standardization efforts, including the MPI Forum, the BLAS Technical Forum, the ISO C++ standardization committee, the oneAPI Technical Advisory Board, and the SYCL Advisory Panel. Open source software projects resulting from his work include the Matrix Template Library, the Boost Graph Library, and Open MPI.
---
Videos Filmed & Edited by Bash Films: http://www.BashFilms.com
YouTube Channel Managed by Digital Medium Ltd https://events.digital-medium.co.uk
