code::dive conference 2015 - Andrei Alexandrescu - Writing Fast Code I
Why Stack Overflow recommends it
Stack Overflow users link it when discussing C++ micro-optimizations and benchmarking technique, especially the differential timing method and the fast digit-counting routine.
Recommended by 3 people across 3 different months, 2016 to 2022.
What it is
A conference talk from code::dive 2015 in which Andrei Alexandrescu presents practical techniques for writing fast C++ code. It covers benchmarking pitfalls, differential timing, and low-level optimizations such as faster integer-to-digit counting and avoiding branches and data dependencies.
What people said
Recommends llllllllll · 2018-02 · Stack Overflow · on “Most efficient way to get an integer type id in a family of common base types”
I'm afraid you have to write vtable manually. A talk by Andrei Alexandrescu [this video] also uses some kind of manual vtable for better performance.
Recommends Gabriel · 2019-06 · Stack Overflow · on “Efficient way to determine number of digits in an integer”
If faster is more efficient, this is a improvement on andrei alexandrescu's improvement [this video] . His version was already faster than the naive way (dividing by 10 at every digit). The version below is constant time and faster at least on x86-64 and ARM for all sizes, but occupies twice as much binary code, so it is not as cache-friendly. Benchmarks for this version vs alexandrescu's version on my PR on facebook folly [LINK] . Works on unsigned , not signed . inline uint32_t digits10(uint64_t v) { return 1 + (std::uint32_t)(v>=10) + (std::uint32_t)(v>=100) + (std::uint32_t)(v>=1000) + (std::uint32_t)(v>=10000) + (std::uint32_t)(v>=100000) + (std::uint32_t)(v>=1000000) + (std::uint32_t)(v>=10
Recommends Gabriel · 2019-06 · Stack Overflow · on “What's the best way to get the length of the decimal representation of an int in C++?”
Since the goal is to be fast, this is a improvement on andrei alexandrescu's improvement [this video] . His version was already faster than the naive way (dividing by 10 at every digit). The version below is faster at least on x86-64 and ARM for most sizes. Benchmarks for this version vs alexandrescu's version on my PR on facebook folly [LINK] . inline uint32_t digits10(uint64_t v) { std::uint32_t result = 0; for (;;) { result += 1 + (std::uint32_t)(v>=10) + (std::uint32_t)(v>=100) + (std::uint32_t)(v>=1000) + (std::uint32_t)(v>=10000) + (std::uint32_t)(v>=100000); if (v < 1000000) return result; v /= 1000000U; } }
Recommends user2693780 · 2019-09 · Stack Overflow · on “What is 'differential timing' technique for doing benchmarks?”
Alexsandrescu's slide [this video] is rather trivial to pour into code: auto start = clock::now(); for( int i = 0; i < 2*n; i++ ) baseline(); auto t2a = clock::now() - start; start = clock::now(); for( int i = 0; i < n; i++ ) baseline(); // * for( int i = 0; i < n; i++ ) contender(); auto taplusb = clock::now() - start; double r = t2a / (2 * taplusb - t2a) // relative speedup * Synchronization point which prevents optimization across the last two loops. I would be more interested in the mathematical reasoning behind measuring the relative speed up this way as opposed to simply tBaseline / tContender as I've been doing for ever. He only vaguely hints at '...overhead noise (being) cancelled (out)',
Cites fen · 2016-02 · Stack Overflow · on “What is 'differential timing' technique for doing benchmarks?”
At around 39 minute of "Writing Fast Code I" by Andrei Alexandrescu ( link here to youtube [this video] ) there is a slide of how to use differential timing... can someone show me some basic code with this approach? It was only mentioned for a second, but I think that's an interesting idea. Run baseline 2n times (t 2a ) vs. baseline n times + contender n times (t a+b ). Relative improvement = "t 2a / (2t a+b - t 2a )" some overhead noises canceled
Cites Gabriel · 2019-06 · Stack Overflow · on “C/C++ counting the number of decimals?”
If the decimal part of your number is stored in a separate int , you can just count the its decimal digits. This is a improvement on andrei alexandrescu's improvement [this video] . His version was already faster than the naive way (dividing by 10 at every digit). The version below is constant time and faster at least on x86-64 and ARM for all sizes, but occupies twice as much binary code, so it is not as cache-friendly. Benchmarks for this version vs alexandrescu's version on my PR on facebook folly [LINK] . Works on unsigned , not signed . inline uint32_t digits10(uint64_t v) { return 1 + (std::uint32_t)(v>=10) + (std::uint32_t)(v>=100) + (std::uint32_t)(v>=1000) + (std::uint32_t)(v>=10000) + (
Cites Peter Cordes · 2019-09 · Stack Overflow · on “What is 'differential timing' technique for doing benchmarks?”
If you keep watching until 41:40 or so, he mentions it again when warning about the pitfall of first run vs. subsequent (allocators warmed up, etc.) The best solution for that is doing warm-up runs before the first timed region. I think he's picturing that 2n baseline vs. n baseline + n contender in separate invocations of the benchmark program. So instead of doing some warmup runs before the timed region, he's using the baseline as a controlled warmup inside the timed region . This might make it possible to just time the whole program, e.g. perf stat , instead of calling a time function inside the program. Depending on how much process startup overhead your OS has vs. how long you make your
Cites user2693780 · 2019-09 · Stack Overflow · on “What is 'differential timing' technique for doing benchmarks?”
WORKING LINK [this video] As opposed to the OP I would be more interested in some mathematical reasoning behind the 2nd approach -- I think it's rather trivial to pour into code..
Cites user79878 · 2021-07 · Stack Overflow · on “Why does coded version of std::all_of() benchmark differently than call to std::all_of()?”
I've been inspired the 2015 code::dive conference "Writing Fast Code" talk by Andrei Alexandrescu: [this video] I took the llvm std::all_of code and benchmarked it against a direct call to std::all_of(). I used google benchmark, and a range of 0 - 65535 elements (that all satisfy the predicate): #include <benchmark/benchmark.h> #include <algorithm> // LLVM std::all_of copied from [LINK] Benchmarking this against a direct call to std::all_of(). template <class _InputIterator, class _Predicate> inline bool all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) { for (; __first != __last; ++__first) if (!__pred(*__first)) return false; return true; } static bool equals_42(int i) {
Cites glades · 2022-10 · Stack Overflow · on “Is there a performance difference between i++ and ++i in C++?”
i++ is sometimes faster than ++i! For x86-architectures that use ILP (instruction level paralellism) i++ might in some situations outperform ++i. Why? Because of data dependencies. Modern CPUs parallelise a lot of stuff. If the next few CPU cycles don't have any direct dependency on the incremented value of i, the CPU might omit microcode to delay the increment of i and shove it in a "free slot". This means that you essentially get a "free" increment. I don't know how far ILE goes in this case but I suppose if the iterator becomes too complicated and does pointer dereferencing this might not work. Here's a talk by Andrei Alexandrescu explaining the concept: [this video]