12 ms·

Going faster by duplicating code

158 points by voidstarcpp 3y ago

voidstarcpp 3y ago
TL;DR: If you copy paste the same implementation code in different branches, you give the compiler opportunities to generate faster code for each case it wouldn't have otherwise generated, without you having to do any manual optimization work.
- spiritplumber 3y ago
  thank you
- resonious 3y ago
  If that's the case, then I imagine the inline keyword would have the same effect?
  - lionkor 3y ago
    yeah, languages which can do inking optimizations do this for you, sometimes even without you knowing.
  - swatcoder 3y ago
    This isn’t an optimization you should consider without insight into your actual bottlenecks, but compilers can be even more aggressive with code that’s strictly local to one translation unit (i.e. inside an anonymous namespace in a cpp file) than they typically would be when seeing an inline hint elsewhere. It’s not quite the same. Plus, another benefit of duplication is that you can more freely hand-tune your implementation once you’ve decided its private. Memory alignment, pointer aliasing hints, clever loop structures, SSE stuff, etc can all be used more freely when you know nothing else needs to use this version. The article is a good teaser around how unintuitive optimization can be, but it only scratches the surface.
  - voidstarcpp 3y ago
    You need to use a compiler specific "always inline" directive if you want macro-like functionality of actually inlining code. On its own, the C++ "inline" keyword does not cause inlining to happen, although compilers may treat it like a hint depending on optimization level. GCC does not inline an "inline" function on O0. "Inline" in the C++ standard means "multiple definitions permitted" so the same entity can exist in multiple translation units without upsetting the linker. This is why C++17 added "inline" variables, which can be initialized in a header that's included in multiple places, even though the inlining concept has no applicability to a variable. The keyword was adopted for this purpose because of the primary association with affecting linkage behavior.
- jrumbut 3y ago
  This is really an excellent programming technique article. I think what makes it so great is that your examples hit a sweet spot of simplicity while still being motivating and you show how to get a "good enough" solution very quickly.
drmikeando 3y ago
IMO the reason the compiler doesn't add special cases for the simplest version is that it doesn't know which of its _many_ special cases to use. If you actually use the unoptimised version of the code like void withSwitch(vector<int>& Values, bool v) { if (v) { multiply1(Values, 2.0); } else { multiply1(Values, 3.0); } } Then it actually inlines the code and optimises each one correctly, as it has context about which special cases are available. (Doesn't even need the `inline` keyword for this at `-O2`) You can see the code here: https://godbolt.org/z/5beeYe77a https://godbolt.org/z/5beeYe77a
- voidstarcpp 3y ago
  This is possible if the call site can see the implementation, but you can't count on it for separate translation units or larger functions. My goal was to not rely on site-specific optimization and instead have one separately compiled function body that can be improved for common cases. Certainly, once the compiler has a full view of everything it can take advantage of information as it pleases but this is less controllable. If I were really picky about optimizing for each use I would make it a template. >Doesn't even need the `inline` keyword for this at `-O2` The inline keyword means little in terms of actually causing inlining to happen. I would expect the majority of inlining compilers do happens automatically on functions that lack the "inline" keyword. Conversely, programmers probably add "inline" as an incantation all over the place not knowing that compilers often ignore it.
  - chii 3y ago
    would it have made a difference if the function was static? The compiler would then be able to deduce that it isn't used anywhere else, and thus could do this inline optimization.
    - thesnide 3y ago
      Gcc actually totally does that. Even doing it while not static by copy/pasting the function and enabling further optims. to me modern compilers are like voodoo magic
swatcoder 3y ago
OP — If this comp_nearest is still a hot path for you or if you want to generate more articles, consider testing: 1. using `restrict` to tell that compiler that src and dest are sure not to overlap 2. Converting your two increment and test blocks to add+mod to allow for uninterrupted pipelining Neither might make a difference, but either could.
- voidstarcpp 3y ago
  Addressing the aliasing concern would be the easiest improvement. I observed in the assembly that the source pixel is being re-read all four times it is used, which could be fixed. Writing an optimal composite function is of course not really the goal, nor of much educational/entertainment value. For any additional speed I already have a function which slices up compositing tasks into chunks and puts them on a thread pool.
ape4 3y ago
Honest question, would `V *= Factor` be faster?
- crote 3y ago
  In almost all cases: no. "A compound assignment of the form E1 op= E2 differs from the simple assignment expression E1 = E1 op (E2) only in that the lvalue E1 is evaluated only once." (C99, 6.5.16.2p3) It only matters when evaluating E1 has side effects. For example, `a[i++] += 1;` which is equivalent to `a[i] = a[i] + 1; i++;` rather than `a[i++] = a[i++] + 1;`.
  - vardump 3y ago
    > `a[i++] = a[i++] + 1;` This is probably not what you want, as "i" is increased twice.
    - jrumbut 3y ago
      That's why it matters in that situation, because it changes what actually happens (not just the performance).
lifthrasiir 3y ago
> Compilers try to hoist constant conditions outside of loops but they're bad at it. Even in the trivial example above, on -O2 gcc does a redundant check with every loop iteration. GCC is actually good at that, -O3 has no issue recognizing it. In fact there even is a very explicit option (-funswitch-loops) responsible for extracting loop invariants. It is not enabled on -O2 because it has a space-speed tradeoff. If this optimization is truly desirable even on -O2, `#pragma GCC optimize("-funswitch-loops")` can be used to force it.
- msla 3y ago
  I don't know why people are so reluctant to just use -O3
  - lifthrasiir 3y ago
    Because i) not all programs benefit tremendously from -O3 and ii) it adds to the compile time and binary size? It would be great to have some optimization level between -O2 and -O3 so that only portions that have a potential to be improved more than, say, 5% are compiled using -O3. In fact the existence of `#pragma GCC optimize` does suggest that this might be possible today with some heuristics... (Or use PGO, which will have the same effect. But PGO is still a novelty in 2023.)
    - glandium 3y ago
      Also, in practice, -O3 doesn't necessarily lead to faster code. https://people.cs.umass.edu/~emery/pubs/stabilizer-asplos13.pdf https://people.cs.umass.edu/~emery/pubs/stabilizer-asplos13.... https://m.youtube.com/watch?v=r-TLSBdHe1A https://m.youtube.com/watch?v=r-TLSBdHe1A
    - KeplerBoy 3y ago
      you can manually set the optimizations (and order of optimizations) you want. -O3 ist just a predefined set of optimizations.
      - 3y ago
andersa 3y ago
> This function doesn't know the value being multiplied until it is called. The compiler (gcc, O2) emits a generic integer multiply instruction in its loop body. Well, that's because they did it wrong. Tiny math function like this should be defined in the header file and force-inlined, problem solved. No need for that template monstrosity suggested at the end.
- voidstarcpp 3y ago
  The "tiny math function" is used for expository purposes of the generic application, to fit a trivial example on one page. Obviously it's not how you would literally write a function that transforms elements in a vector.
pif 3y ago
As @andersa correctly pointed it out, put the function in a header file and refrain from inventing useless complications. How could this post get to the front page of Hacker News?
- exabrial 3y ago
  My guess is it's the combination of: 1. A pushback against code standards a lot of organizations have 2. The ego a lot of individuals have that is incompatible with #1 again, just guessing
denton-scratch 3y ago
So, by making your code harder to read ("Duh - both these branches do the same thing, so I'll refactor it"), you can give the optimiser actionable information. But it's not explicit in the code; you'd need a comment in the code to explain your reasons. Comments rot. And your tuned "high-level" code (yeah, C++ isn't generally considered a high-level language) is now dependent on some specific optimizer, which might change in the future; code that appears to be portable, and compiles on multiple compilers, only performs properly if you use the right optimizer. I don't like this advice; but I'm not a C++ programmer. I don't like macros, and I'm not at all keen on the merciless optimizers that are shipped with modern compilers.
- bunderbunder 3y ago
  I'm generally opposed to unnecessary optimization, but I'm also opposed to this tendency to start flaming as soon as people even talk about optimization. Because sometimes this kind of careful performance tuning, even at the cost of readability, is necessary and desirable. And, for the times when that happens, this kind of information needs to be out there, available, and being discussed, so that people can learn the techniques and understand how to use them properly and responsibly. Yes, that does include knowing that a change to the compiler's optimizer could mean that things that used to make the code faster now make it slower. For that matter, changing the CPU microarchitecture could have the same effect. But that's something we all learn in Optimizing 101. It's so well-known that the very first setting on Godbolt's output pane is a toggle to select which compiler and version it should use to generate said output.
  - denton-scratch 3y ago
    > this kind of information needs to be out there Agreed; I think TFA is a useful article. Highly-tuned code is going to be hard to read (it used to be written in assembler, which is at least explicit). I was simply commenting on the opacity of having two branches in the source that appear to do the same thing, and rely on something outside the code (or the language specification) to achieve the desired performance.
    - 3y ago
JTbane 3y ago
I'm reminded of http://number-none.com/blow/john_carmack_on_inlined_code.html http://number-none.com/blow/john_carmack_on_inlined_code.htm... Sometimes it really is faster just to do what a rookie would, dump all the work in a single function.
krupan 3y ago
"Programmers often put in speed hacks based on performance knowledge which is outdated or inapplicable to the target platform. Separating cases lets the programmer supply their high-level knowledge about what values are likely to be encountered, which the compiler can optimize to the platform based on its low-level information." But if our performance knowledge is outdated, how do we know which cases to separate the code into? Using the toy example here, how do we know that multiplying by 2 is a special case we should add a branch for? What about multiplying by 3 or 4 or 5? It seems like you still need to use up-to-date performance knowledge for this technique to work, and in that case just write the left shift into your code so that when this code gets read later it will be more clear why it's there.
- dahart 3y ago
  > how do you know which cases to separate the code into? It takes practice. For this you really just have to read the assembly, and profile the code. Then try separating it one way and see if it helps, and if not then another. In my experience, it takes many tries to update your perf knowledge, and optimizations sometimes don’t work even when your knowledge is current. All this is why the article noted people should be “Giving the compiler an opportunity to do something is useful, but measure carefully before forcing it.”
- bunderbunder 3y ago
  Reminds me of a point in the interview with Donald Knuth in Coders at Work where he criticized overuse of abstraction in code, and said that he thinks it's more important for code to be easy to read and edit than for it to be easy to reuse. He didn't say it explicitly, but the implication that I took was that things that are meant, in essence, to make code more configurable can sometimes (often?) do more harm than good. (SOLID, I'm looking at you.) Using them successfully often requires oracular knowledge about how the code might evolve in the future. I've found that doing my job got a lot easier after I started following this idea. The code might be more repetitive and boilerplate-y, but there's actually less of it, so it's still easier to read, understand, and maintain.
  - thesnide 3y ago
ladberg 3y ago
I've used this before for memcpy with arbitrary values that are likely to be one of a small set of known small sizes. Calling memcpy with an arbitrary value always has to call out to libc but a specific value can be inlined into a single instruction or two for smaller values, so you can have an if-else chain or switch with a few common ones for your program and it's a noticeable speedup.
logdahl 3y ago
I kind of wish we had a form of preconditions/hints for the C compiler. There are lots of attributes, but those all look weird. Imagine annotating a calculation that 1 is a common value for example. or that a function is never called with a null-pointer.
- variadix 3y ago
  With GCC/clang you can write an ASSERT/ASSUME macro that does this. Basically: if (!cond) __builtin_unreachable();
mortallywounded 3y ago
In summary, programming in a staticly compiled language is really about giving your compiler hints as to what you want to happen. Sometimes it listens, sometimes it doesn't. Sometimes you can force it with some kind words, and sometimes you need to use beat it into submission.
DannyBee 3y ago
This is well known and I thought GCC did it already. This is a form of ipcp with cloning. Whether it is worth it is hard to determine without profiling info, except in the case where an argument is always constant vs partially constant

158 points by voidstarcpp 3y ago

TL;DR: If you copy paste the same implementation code in different branches, you give the compiler opportunities to generate faster code for each case it wouldn't have otherwise generated, without you having to do any manual optimization work.

spiritplumber 3y ago
thank you
resonious 3y ago
If that's the case, then I imagine the inline keyword would have the same effect?
- lionkor 3y ago
  yeah, languages which can do inking optimizations do this for you, sometimes even without you knowing.
- swatcoder 3y ago
  This isn’t an optimization you should consider without insight into your actual bottlenecks, but compilers can be even more aggressive with code that’s strictly local to one translation unit (i.e. inside an anonymous namespace in a cpp file) than they typically would be when seeing an inline hint elsewhere. It’s not quite the same. Plus, another benefit of duplication is that you can more freely hand-tune your implementation once you’ve decided its private. Memory alignment, pointer aliasing hints, clever loop structures, SSE stuff, etc can all be used more freely when you know nothing else needs to use this version. The article is a good teaser around how unintuitive optimization can be, but it only scratches the surface.
- voidstarcpp 3y ago
  You need to use a compiler specific "always inline" directive if you want macro-like functionality of actually inlining code. On its own, the C++ "inline" keyword does not cause inlining to happen, although compilers may treat it like a hint depending on optimization level. GCC does not inline an "inline" function on O0. "Inline" in the C++ standard means "multiple definitions permitted" so the same entity can exist in multiple translation units without upsetting the linker. This is why C++17 added "inline" variables, which can be initialized in a header that's included in multiple places, even though the inlining concept has no applicability to a variable. The keyword was adopted for this purpose because of the primary association with affecting linkage behavior.
jrumbut 3y ago
This is really an excellent programming technique article. I think what makes it so great is that your examples hit a sweet spot of simplicity while still being motivating and you show how to get a "good enough" solution very quickly.

drmikeando 3y ago

IMO the reason the compiler doesn't add special cases for the simplest version is that it doesn't know which of its _many_ special cases to use. If you actually use the unoptimised version of the code like void withSwitch(vector<int>& Values, bool v) { if (v) { multiply1(Values, 2.0); } else { multiply1(Values, 3.0); } } Then it actually inlines the code and optimises each one correctly, as it has context about which special cases are available. (Doesn't even need the `inline` keyword for this at `-O2`) You can see the code here: https://godbolt.org/z/5beeYe77a https://godbolt.org/z/5beeYe77a

voidstarcpp 3y ago
This is possible if the call site can see the implementation, but you can't count on it for separate translation units or larger functions. My goal was to not rely on site-specific optimization and instead have one separately compiled function body that can be improved for common cases. Certainly, once the compiler has a full view of everything it can take advantage of information as it pleases but this is less controllable. If I were really picky about optimizing for each use I would make it a template. >Doesn't even need the `inline` keyword for this at `-O2` The inline keyword means little in terms of actually causing inlining to happen. I would expect the majority of inlining compilers do happens automatically on functions that lack the "inline" keyword. Conversely, programmers probably add "inline" as an incantation all over the place not knowing that compilers often ignore it.
- chii 3y ago
  would it have made a difference if the function was static? The compiler would then be able to deduce that it isn't used anywhere else, and thus could do this inline optimization.
  - thesnide 3y ago
    Gcc actually totally does that. Even doing it while not static by copy/pasting the function and enabling further optims. to me modern compilers are like voodoo magic

swatcoder 3y ago

OP — If this comp_nearest is still a hot path for you or if you want to generate more articles, consider testing: 1. using `restrict` to tell that compiler that src and dest are sure not to overlap 2. Converting your two increment and test blocks to add+mod to allow for uninterrupted pipelining Neither might make a difference, but either could.

voidstarcpp 3y ago
Addressing the aliasing concern would be the easiest improvement. I observed in the assembly that the source pixel is being re-read all four times it is used, which could be fixed. Writing an optimal composite function is of course not really the goal, nor of much educational/entertainment value. For any additional speed I already have a function which slices up compositing tasks into chunks and puts them on a thread pool.

ape4 3y ago

Honest question, would `V *= Factor` be faster?

crote 3y ago
In almost all cases: no. "A compound assignment of the form E1 op= E2 differs from the simple assignment expression E1 = E1 op (E2) only in that the lvalue E1 is evaluated only once." (C99, 6.5.16.2p3) It only matters when evaluating E1 has side effects. For example, `a[i++] += 1;` which is equivalent to `a[i] = a[i] + 1; i++;` rather than `a[i++] = a[i++] + 1;`.
- vardump 3y ago
  > `a[i++] = a[i++] + 1;` This is probably not what you want, as "i" is increased twice.
  - jrumbut 3y ago
    That's why it matters in that situation, because it changes what actually happens (not just the performance).

lifthrasiir 3y ago

> Compilers try to hoist constant conditions outside of loops but they're bad at it. Even in the trivial example above, on -O2 gcc does a redundant check with every loop iteration. GCC is actually good at that, -O3 has no issue recognizing it. In fact there even is a very explicit option (-funswitch-loops) responsible for extracting loop invariants. It is not enabled on -O2 because it has a space-speed tradeoff. If this optimization is truly desirable even on -O2, `#pragma GCC optimize("-funswitch-loops")` can be used to force it.

msla 3y ago
I don't know why people are so reluctant to just use -O3
- lifthrasiir 3y ago
  Because i) not all programs benefit tremendously from -O3 and ii) it adds to the compile time and binary size? It would be great to have some optimization level between -O2 and -O3 so that only portions that have a potential to be improved more than, say, 5% are compiled using -O3. In fact the existence of `#pragma GCC optimize` does suggest that this might be possible today with some heuristics... (Or use PGO, which will have the same effect. But PGO is still a novelty in 2023.)
  - glandium 3y ago
    Also, in practice, -O3 doesn't necessarily lead to faster code. https://people.cs.umass.edu/~emery/pubs/stabilizer-asplos13.pdf https://people.cs.umass.edu/~emery/pubs/stabilizer-asplos13.... https://m.youtube.com/watch?v=r-TLSBdHe1A https://m.youtube.com/watch?v=r-TLSBdHe1A
  - KeplerBoy 3y ago
    you can manually set the optimizations (and order of optimizations) you want. -O3 ist just a predefined set of optimizations.
    - 3y ago

andersa 3y ago

> This function doesn't know the value being multiplied until it is called. The compiler (gcc, O2) emits a generic integer multiply instruction in its loop body. Well, that's because they did it wrong. Tiny math function like this should be defined in the header file and force-inlined, problem solved. No need for that template monstrosity suggested at the end.

voidstarcpp 3y ago
The "tiny math function" is used for expository purposes of the generic application, to fit a trivial example on one page. Obviously it's not how you would literally write a function that transforms elements in a vector.

pif 3y ago

As @andersa correctly pointed it out, put the function in a header file and refrain from inventing useless complications. How could this post get to the front page of Hacker News?

exabrial 3y ago
My guess is it's the combination of: 1. A pushback against code standards a lot of organizations have 2. The ego a lot of individuals have that is incompatible with #1 again, just guessing

denton-scratch 3y ago

So, by making your code harder to read ("Duh - both these branches do the same thing, so I'll refactor it"), you can give the optimiser actionable information. But it's not explicit in the code; you'd need a comment in the code to explain your reasons. Comments rot. And your tuned "high-level" code (yeah, C++ isn't generally considered a high-level language) is now dependent on some specific optimizer, which might change in the future; code that appears to be portable, and compiles on multiple compilers, only performs properly if you use the right optimizer. I don't like this advice; but I'm not a C++ programmer. I don't like macros, and I'm not at all keen on the merciless optimizers that are shipped with modern compilers.

bunderbunder 3y ago
I'm generally opposed to unnecessary optimization, but I'm also opposed to this tendency to start flaming as soon as people even talk about optimization. Because sometimes this kind of careful performance tuning, even at the cost of readability, is necessary and desirable. And, for the times when that happens, this kind of information needs to be out there, available, and being discussed, so that people can learn the techniques and understand how to use them properly and responsibly. Yes, that does include knowing that a change to the compiler's optimizer could mean that things that used to make the code faster now make it slower. For that matter, changing the CPU microarchitecture could have the same effect. But that's something we all learn in Optimizing 101. It's so well-known that the very first setting on Godbolt's output pane is a toggle to select which compiler and version it should use to generate said output.
- denton-scratch 3y ago
  > this kind of information needs to be out there Agreed; I think TFA is a useful article. Highly-tuned code is going to be hard to read (it used to be written in assembler, which is at least explicit). I was simply commenting on the opacity of having two branches in the source that appear to do the same thing, and rely on something outside the code (or the language specification) to achieve the desired performance.
  - 3y ago

JTbane 3y ago

I'm reminded of http://number-none.com/blow/john_carmack_on_inlined_code.html http://number-none.com/blow/john_carmack_on_inlined_code.htm... Sometimes it really is faster just to do what a rookie would, dump all the work in a single function.

krupan 3y ago

"Programmers often put in speed hacks based on performance knowledge which is outdated or inapplicable to the target platform. Separating cases lets the programmer supply their high-level knowledge about what values are likely to be encountered, which the compiler can optimize to the platform based on its low-level information." But if our performance knowledge is outdated, how do we know which cases to separate the code into? Using the toy example here, how do we know that multiplying by 2 is a special case we should add a branch for? What about multiplying by 3 or 4 or 5? It seems like you still need to use up-to-date performance knowledge for this technique to work, and in that case just write the left shift into your code so that when this code gets read later it will be more clear why it's there.

dahart 3y ago
> how do you know which cases to separate the code into? It takes practice. For this you really just have to read the assembly, and profile the code. Then try separating it one way and see if it helps, and if not then another. In my experience, it takes many tries to update your perf knowledge, and optimizations sometimes don’t work even when your knowledge is current. All this is why the article noted people should be “Giving the compiler an opportunity to do something is useful, but measure carefully before forcing it.”
bunderbunder 3y ago
Reminds me of a point in the interview with Donald Knuth in Coders at Work where he criticized overuse of abstraction in code, and said that he thinks it's more important for code to be easy to read and edit than for it to be easy to reuse. He didn't say it explicitly, but the implication that I took was that things that are meant, in essence, to make code more configurable can sometimes (often?) do more harm than good. (SOLID, I'm looking at you.) Using them successfully often requires oracular knowledge about how the code might evolve in the future. I've found that doing my job got a lot easier after I started following this idea. The code might be more repetitive and boilerplate-y, but there's actually less of it, so it's still easier to read, understand, and maintain.
- thesnide 3y ago

ladberg 3y ago

I've used this before for memcpy with arbitrary values that are likely to be one of a small set of known small sizes. Calling memcpy with an arbitrary value always has to call out to libc but a specific value can be inlined into a single instruction or two for smaller values, so you can have an if-else chain or switch with a few common ones for your program and it's a noticeable speedup.

logdahl 3y ago

I kind of wish we had a form of preconditions/hints for the C compiler. There are lots of attributes, but those all look weird. Imagine annotating a calculation that 1 is a common value for example. or that a function is never called with a null-pointer.

variadix 3y ago
With GCC/clang you can write an ASSERT/ASSUME macro that does this. Basically: if (!cond) __builtin_unreachable();

mortallywounded 3y ago

In summary, programming in a staticly compiled language is really about giving your compiler hints as to what you want to happen. Sometimes it listens, sometimes it doesn't. Sometimes you can force it with some kind words, and sometimes you need to use beat it into submission.

DannyBee 3y ago

This is well known and I thought GCC did it already. This is a form of ipcp with cloning. Whether it is worth it is hard to determine without profiling info, except in the case where an argument is always constant vs partially constant