4 ms·

So, I guess the lesson here is don't trust the compiler to inline something.. verify?

loeg 4y ago
That's a pretty reasonable takeaway. Measure your hot loops and ideally incorporate a benchmark into your CI (to avoid regression).
levodelellis 4y ago
I'm the author, although that's 100% true I was going for "our intuition of optimization is bad". Before writing a word I knew that compilers don't inline code that's not in the compile unit (unless `-flto` is specified and it's not guaranteed to work). Imagine my surprise when clang optimized away the call to itoa/strol. I believe it's a heuristic in clang because clang doesn't optimize away 6A
- dataflow 4y ago
  To be honest, I feel like your blog post was moreso entertainment (and a good one) than actual support for your thesis. While not every examples was bad, you picked some incredible edge cases for many of them that are at best rare in reality (fibonacci, dynamic_cast immediately following construction), and at worst nonsensical (always_inline with noinline?!) and then deduced people have bad intuition if they couldn't guess what optimizations occurred here. That's not really an accurate assessment of people's intuitions - for example, I'm around ~100% sure that hardly anyone who claims "I have good intuition for inlining" has the answer to "what happens if I combine always_inline to noinline" in their head when they say that - nor should they! Heck, I already forget what that does on each compiler even after reading your post. If anything, someone with a good intuition would know that they should check the compiler output for something like that. What you'd need to do for assessing intuition is finding some actual common/realistic cases, then seeing how accurately people perform on those - things that are useful, and which people might actually claim to have intuition about! Moreover, also note that someone with "good intuition" for inlining wouldn't necessarily know (or need to care) what happens at every call site - sometimes it doesn't really matter what specific level the inlining stops at, as long as most of the call chain is inlined, and that's what intuition often gets you.
  - levodelellis 4y ago
    Yes it's mostly for entertainment. I didn't want to stress anyone out with this. Round 2 was specifically to 1) Show people not to take this seriously 2) To serve as an example that some modifications doesn't mean earlier examples do/don't inline. So they wouldn't overthink. Outside of the first two rounds most of these were inspired by real code but simplified for reading. I think it'd be less entertaining if it was more serious and more had realistic code. A lot more people would tune out. If it was any longer I think it would have made more sense to explain why something was optimized or not. I don't work on clang or gcc so I may not be a good person to write that kind of article > someone with "good intuition" for inlining wouldn't necessarily know (or need to care) what happens at every call site Round 5 (the virtual function/dynamic cast round) was inspired by a person who claimed to have 20 years of experience. He suggested a way I could implement a feature in my compiler. I eventually wrote a test case to see if compilers would 'devirtualize' function calls as he claimed. They didn't. From memory he works on making servers preform so he wasn't a stranger to performance. I think "good intuition" is more about knowing what won't inline and having some tactics you can use in the first 5 minutes after looking at a flamegraph
    - dataflow 4y ago
      I'm not a compiler expert, but just a note regarding your last point, devirtualization of a function call and dynamic_cast are different beasts; in fact I've never heard of an optimization of the latter as being referred to as devirtualization. (Though perhaps this is just me?) From what I've seen, dynamic_cast is implemented as an opaque external function call (and quite a complicated one), so the compiler would need to explicitly make assumptions about its behavior before it can optimize it away. (Which it certainly could, but that's extra work for the compiler writer that would need to be worth the payoff, which in this case I imagine is probably debatable.) Virtual functions, on the other hand, don't involve an opaque call for mere target resolution, and their vtables have definitions available at compile time, so they're much more tame. So expecting devirtualization to come with dynamic_cast getting optimized away seems a bit of a non-sequitur IMO.
  - jesse__ 4y ago
    > at worst nonsensical (always_inline with noinline?!) I think this is actually great support for their thesis. If you came across actual code that looked like that (and god knows it probably exists if it's legal), who fucking knows what the compiler would do? My question is: why is it even legal to mark functions with both of these, in addition to the `inline` keyword? My guess is the C++ spec says something along the lines of "you can mark functions with as many attributes as you want .. something .. something .." ie compiler vendors get no choice but to (at best) emit a warning.
okanat 4y ago
Yes and no. While verifying you should benchmark too. Maybe the inline option is slower! Don't try to outclever or force compiler to do weird things and be knowledgeable about limitations due to compilation steps and the ABI limitations is the lesson. Most of the time using contexpr and defining inlineable functions in headers will get you the most optimal result. In the most of the remaining part the compiler is again right to not inline things because it probably knows more about the instruction caches etc than you. The remaining tiny part is basically PhD or very expert level experience which makes it your job to know more than the compiler because it is your job to write the compiler or discover its shortcomings.

loeg 4y ago

That's a pretty reasonable takeaway. Measure your hot loops and ideally incorporate a benchmark into your CI (to avoid regression).

levodelellis 4y ago

I'm the author, although that's 100% true I was going for "our intuition of optimization is bad". Before writing a word I knew that compilers don't inline code that's not in the compile unit (unless `-flto` is specified and it's not guaranteed to work). Imagine my surprise when clang optimized away the call to itoa/strol. I believe it's a heuristic in clang because clang doesn't optimize away 6A

dataflow 4y ago
To be honest, I feel like your blog post was moreso entertainment (and a good one) than actual support for your thesis. While not every examples was bad, you picked some incredible edge cases for many of them that are at best rare in reality (fibonacci, dynamic_cast immediately following construction), and at worst nonsensical (always_inline with noinline?!) and then deduced people have bad intuition if they couldn't guess what optimizations occurred here. That's not really an accurate assessment of people's intuitions - for example, I'm around ~100% sure that hardly anyone who claims "I have good intuition for inlining" has the answer to "what happens if I combine always_inline to noinline" in their head when they say that - nor should they! Heck, I already forget what that does on each compiler even after reading your post. If anything, someone with a good intuition would know that they should check the compiler output for something like that. What you'd need to do for assessing intuition is finding some actual common/realistic cases, then seeing how accurately people perform on those - things that are useful, and which people might actually claim to have intuition about! Moreover, also note that someone with "good intuition" for inlining wouldn't necessarily know (or need to care) what happens at every call site - sometimes it doesn't really matter what specific level the inlining stops at, as long as most of the call chain is inlined, and that's what intuition often gets you.
- levodelellis 4y ago
  Yes it's mostly for entertainment. I didn't want to stress anyone out with this. Round 2 was specifically to 1) Show people not to take this seriously 2) To serve as an example that some modifications doesn't mean earlier examples do/don't inline. So they wouldn't overthink. Outside of the first two rounds most of these were inspired by real code but simplified for reading. I think it'd be less entertaining if it was more serious and more had realistic code. A lot more people would tune out. If it was any longer I think it would have made more sense to explain why something was optimized or not. I don't work on clang or gcc so I may not be a good person to write that kind of article > someone with "good intuition" for inlining wouldn't necessarily know (or need to care) what happens at every call site Round 5 (the virtual function/dynamic cast round) was inspired by a person who claimed to have 20 years of experience. He suggested a way I could implement a feature in my compiler. I eventually wrote a test case to see if compilers would 'devirtualize' function calls as he claimed. They didn't. From memory he works on making servers preform so he wasn't a stranger to performance. I think "good intuition" is more about knowing what won't inline and having some tactics you can use in the first 5 minutes after looking at a flamegraph
  - dataflow 4y ago
    I'm not a compiler expert, but just a note regarding your last point, devirtualization of a function call and dynamic_cast are different beasts; in fact I've never heard of an optimization of the latter as being referred to as devirtualization. (Though perhaps this is just me?) From what I've seen, dynamic_cast is implemented as an opaque external function call (and quite a complicated one), so the compiler would need to explicitly make assumptions about its behavior before it can optimize it away. (Which it certainly could, but that's extra work for the compiler writer that would need to be worth the payoff, which in this case I imagine is probably debatable.) Virtual functions, on the other hand, don't involve an opaque call for mere target resolution, and their vtables have definitions available at compile time, so they're much more tame. So expecting devirtualization to come with dynamic_cast getting optimized away seems a bit of a non-sequitur IMO.
- jesse__ 4y ago
  > at worst nonsensical (always_inline with noinline?!) I think this is actually great support for their thesis. If you came across actual code that looked like that (and god knows it probably exists if it's legal), who fucking knows what the compiler would do? My question is: why is it even legal to mark functions with both of these, in addition to the `inline` keyword? My guess is the C++ spec says something along the lines of "you can mark functions with as many attributes as you want .. something .. something .." ie compiler vendors get no choice but to (at best) emit a warning.

okanat 4y ago

Yes and no. While verifying you should benchmark too. Maybe the inline option is slower! Don't try to outclever or force compiler to do weird things and be knowledgeable about limitations due to compilation steps and the ABI limitations is the lesson. Most of the time using contexpr and defining inlineable functions in headers will get you the most optimal result. In the most of the remaining part the compiler is again right to not inline things because it probably knows more about the instruction caches etc than you. The remaining tiny part is basically PhD or very expert level experience which makes it your job to know more than the compiler because it is your job to write the compiler or discover its shortcomings.