4 ms·

Optimizing compilers have been able to recognize pretty complicated patterns for many years. For instance if you're making a loop to count the bits that are se

by tux3 2y ago

Optimizing compilers have been able to recognize pretty complicated patterns for many years. For instance if you're making a loop to count the bits that are set in a number, the compiler can recognize the entire loop and turn it into a single popcnt instruction (e.g. https://lemire.me/blog/2016/05/23/the-surprising-cleverness-of-modern-compilers/ https://lemire.me/blog/2016/05/23/the-surprising-cleverness-... )

dietr1ch 2y ago
I feel that the compiler is doing too much work here. I know they are thinking about special cases on generated code, but at some point it feels that it just adds compile time for no good reason. Look at this --beauty-- eww, thing, should compilers really spend time trying to figure out how to optimise insane code? def is_even(n): return str(n)[len(str(n))-1] in [str(2*n) for n in range(5)]
- ajross 2y ago
  These optimizations are very useful. Consider the only slightly less contrived case where you want to mod an index by the size of an array. And the compiler expands the inline function around a context where the array is a fixed power of two size at compile time. Poof, no division/modulus needed, magically. Lots and lots of code looks like this: general algorithms expressed in simple implementation that has a faster implementation in the specific instance that gets generated.
- refulgentis 2y ago
  Maybe one day there will be compilers that can choose what to optimize based on their aesthetic judgement of the code. I could see that as a novel feedback mechanism for software engineers. As it stands, I'm glad they design optimizations abstractly, even if that means code I don't like gets the benefits
  - dietr1ch 2y ago
    It's not about aesthetics, but about the sort of hit-rate of the optimisations as if they need to be too smart to figure things out, then it also means that they'd more rarely be used and necessary.
    - refulgentis 2y ago
      I'm not quite sure what you're visualizing for compilers, if I understand correctly, what I'd say is: tl;dr: there are general optimizations for "this function in a for loop is a constant expression, we dont need to call it 500 times" or "this obscure combination of asm instructions is optimal on pentium iii 350 mhz dual core" not "we need to turn this unholy CS101 student spaghetti code where they do a 500 branch-if into a for loop" comment over here is attempting to communicate that as well https://news.ycombinator.com/item?id=42705758 https://news.ycombinator.com/item?id=42705758 I've never, ever, heard the idea that compilers are burdened by the workload of maintaining thousands of type-specific optimizations for hilariously bad code, until today. I've been here since 2009, so it is puzzling to me to see it referred to off hand, in a "this is water" manner https://en.wikipedia.org/wiki/This_Is_Water https://en.wikipedia.org/wiki/This_Is_Water
      - dietr1ch 2y ago
        > I've never, ever, heard the idea that compilers are burdened by the workload of maintaining thousands of type-specific optimizations for hilariously bad code, until today. I've heard tons of people complain about slow compilers, so even if compiler devs find it easy architect their compilers to do multiple kinds of optimisations there's a cost to it that devs running the compilers pay. Also, if you think about it, optimising code has to follow diminishing returns, so at some point we are putting too much CPU time into little to no gains, and it's also possible to get slower code with more optimisations if they interact poorly, or at least not better code even if spending more CPU time. This is why there's -O3 in gcc and it's not the default, there's a cost to it that's likely not worth paying.
        refulgentis 2y ago
- matt_daemon 2y ago
  Or even: def is_even(n): return str(n)[-1] in "02468"
eichin 2y ago
They've been able to recognize this pattern since the 1960s (popcount is a very historically special case and not really a sign of complexity, since traditionally it was "if you write this exact code from the documentation, you'll get the machine instruction" and didn't imply any more general cleverness.)
- LegionMammal978 2y ago
  Yeah, once I tried writing out a dumber popcount loop (checking each bit) for better readability, and was annoyed to find that GCC and Clang didn't recognize it. I ended up looking into the source of both compilers to find that they only transform the more 'idiomatic' version.
- cperciva 2y ago
  popcount is a very historically special case To elaborate a bit on the specialness of popcount: It is a generally accepted belief in the computer architecture community that several systems included a popcount iNstruction Solely due to A request from a single "very good customer".

by tux3 2y ago

dietr1ch 2y ago

I feel that the compiler is doing too much work here. I know they are thinking about special cases on generated code, but at some point it feels that it just adds compile time for no good reason. Look at this --beauty-- eww, thing, should compilers really spend time trying to figure out how to optimise insane code? def is_even(n): return str(n)[len(str(n))-1] in [str(2*n) for n in range(5)]

ajross 2y ago
These optimizations are very useful. Consider the only slightly less contrived case where you want to mod an index by the size of an array. And the compiler expands the inline function around a context where the array is a fixed power of two size at compile time. Poof, no division/modulus needed, magically. Lots and lots of code looks like this: general algorithms expressed in simple implementation that has a faster implementation in the specific instance that gets generated.
refulgentis 2y ago
Maybe one day there will be compilers that can choose what to optimize based on their aesthetic judgement of the code. I could see that as a novel feedback mechanism for software engineers. As it stands, I'm glad they design optimizations abstractly, even if that means code I don't like gets the benefits
- dietr1ch 2y ago
  It's not about aesthetics, but about the sort of hit-rate of the optimisations as if they need to be too smart to figure things out, then it also means that they'd more rarely be used and necessary.
  - refulgentis 2y ago
    I'm not quite sure what you're visualizing for compilers, if I understand correctly, what I'd say is: tl;dr: there are general optimizations for "this function in a for loop is a constant expression, we dont need to call it 500 times" or "this obscure combination of asm instructions is optimal on pentium iii 350 mhz dual core" not "we need to turn this unholy CS101 student spaghetti code where they do a 500 branch-if into a for loop" comment over here is attempting to communicate that as well https://news.ycombinator.com/item?id=42705758 https://news.ycombinator.com/item?id=42705758 I've never, ever, heard the idea that compilers are burdened by the workload of maintaining thousands of type-specific optimizations for hilariously bad code, until today. I've been here since 2009, so it is puzzling to me to see it referred to off hand, in a "this is water" manner https://en.wikipedia.org/wiki/This_Is_Water https://en.wikipedia.org/wiki/This_Is_Water
    - dietr1ch 2y ago
      > I've never, ever, heard the idea that compilers are burdened by the workload of maintaining thousands of type-specific optimizations for hilariously bad code, until today. I've heard tons of people complain about slow compilers, so even if compiler devs find it easy architect their compilers to do multiple kinds of optimisations there's a cost to it that devs running the compilers pay. Also, if you think about it, optimising code has to follow diminishing returns, so at some point we are putting too much CPU time into little to no gains, and it's also possible to get slower code with more optimisations if they interact poorly, or at least not better code even if spending more CPU time. This is why there's -O3 in gcc and it's not the default, there's a cost to it that's likely not worth paying.
      - refulgentis 2y ago
matt_daemon 2y ago
Or even: def is_even(n): return str(n)[-1] in "02468"

eichin 2y ago

They've been able to recognize this pattern since the 1960s (popcount is a very historically special case and not really a sign of complexity, since traditionally it was "if you write this exact code from the documentation, you'll get the machine instruction" and didn't imply any more general cleverness.)

LegionMammal978 2y ago
Yeah, once I tried writing out a dumber popcount loop (checking each bit) for better readability, and was annoyed to find that GCC and Clang didn't recognize it. I ended up looking into the source of both compilers to find that they only transform the more 'idiomatic' version.
cperciva 2y ago
popcount is a very historically special case To elaborate a bit on the specialness of popcount: It is a generally accepted belief in the computer architecture community that several systems included a popcount iNstruction Solely due to A request from a single "very good customer".