4 ms·

This is a very specific problem that lends itself to some fantastically cpu-friendly optimizations. Doing a single hash-map lookup here on the hot path would ki

This is a very specific problem that lends itself to some fantastically cpu-friendly optimizations. Doing a single hash-map lookup here on the hot path would kill performance, and let's not even get started on any serious I/O (disk or network) as that would be multiple orders of magnitude slower. Not many problems are just "cat something extremely predictable into /dev/null".

samhw 5y ago
And so what? That's what this code does, and so a compiler should be able to generate the optimal assembly. Why would a compiler need to consider something that the code in question is not doing?
- anthony_r 5y ago
  Yeah you could optimize GCC to work really well for those problems, there's a great ROI for the "write something trivial really quickly into /dev/null" class of problems. Let us know how this goes if you embark on this adventure.
  - samhw 5y ago
    If you genuinely understood me as saying that, then I should clarify, to be absolutely foolproof: That is not what I'm saying. I'm talking about having a compiler which could produce more optimal code in any given case, or most given cases. I obviously am not suggesting that compilers optimise this and only this case.
    - anthony_r 5y ago
      > I'm talking about having a compiler which could produce more optimal code in any given case, or most given cases Funny coincidence, that's exactly what the vast majority of compiler code is for, with tens (or hundreds) of thousands of man-years of work spent on that.
      - samhw 5y ago
        My point, again, is about having a compiler that can produce more optimal code than existing compilers (and whether there's a theoretical upper bound preventing them from more closely approaching the handwritten assembly in this case). I'm not quite sure what else you could have thought the word 'more' was referring to?
- bawolff 5y ago
  How would the compiler know that? This code for example is only optimal if you are piping it somewhere instead of displaying on the terminal. There is no way, even in principle, for the compiler to know that this program is always run with stdout connected to a pipe. Moreover, if you mean optimal in the absolute sense, pretty sure that is equivalent to solving the halting problem. If what your asking is: why can't computers take all surounding fuzzy context into account and do precisely the right thing, the answer is: because we haven't invented strong AI yet.
  - samhw 5y ago
    Ah, sorry, I misunderstood you. I thought you were placing the emphasis on what the code was doing, rather than where it was being piped. But why do you think that most of the possible optimisations would only be relevant if the output were being piped to somewhere other than a terminal? Also, why would making it absolutely optimal be "equivalent to solving the halting problem"? (Though either way, no, I'm not talking about producing 100.0000% optimal code - clearly there's plenty of daylight between the current degree of optimality and that one.)
    - bawolff 5y ago
      > Ah, sorry, I misunderstood you. I thought you were placing the emphasis on what the code was doing, rather than where it was being piped. But why do you think that most of the possible optimisations would only be relevant if the output were being piped to somewhere other than a terminal? One of the primary optimizations is using vm_splice to avoid memory copies. vm_splice only works if the file descriptor is a pipe. > Also, why would making it absolutely optimal be "equivalent to solving the halting problem"? https://en.m.wikipedia.org/wiki/Rice%27s_theorem https://en.m.wikipedia.org/wiki/Rice%27s_theorem Or more specificly, if a program always halts (without outputting things) then the best optimization would be to have it halt immediately but to know that you have to have solved the halting problem. You're right of course, absolutes are a bit of a distraction we just need something good for 99% of programs. However that's still really hard, and an optimization applied in the wrong context will slow down a program. There's still lots of room for compilers to grow, but the types of optimizations in use in this example are at best probably NP-complete to determine if they apply (i dont have any evidence for that though)
londons_explore 5y ago
But nearly all problems boil down to nearly zero actual work... Take booting up a computer for example. All that actually needs to be done is to display the login screen on the screen. And we know from 60 fps video playback, that the hardware is capable of displaying a frame inside 16 milliseconds.
- anthony_r 5y ago
  You can create an operating system that just displays a static image within milliseconds yourself (shouldn't take you more than a few weeks), it would work even when compiled at -O0.

samhw 5y ago

And so what? That's what this code does, and so a compiler should be able to generate the optimal assembly. Why would a compiler need to consider something that the code in question is not doing?

anthony_r 5y ago
Yeah you could optimize GCC to work really well for those problems, there's a great ROI for the "write something trivial really quickly into /dev/null" class of problems. Let us know how this goes if you embark on this adventure.
- samhw 5y ago
  If you genuinely understood me as saying that, then I should clarify, to be absolutely foolproof: That is not what I'm saying. I'm talking about having a compiler which could produce more optimal code in any given case, or most given cases. I obviously am not suggesting that compilers optimise this and only this case.
  - anthony_r 5y ago
    > I'm talking about having a compiler which could produce more optimal code in any given case, or most given cases Funny coincidence, that's exactly what the vast majority of compiler code is for, with tens (or hundreds) of thousands of man-years of work spent on that.
    - samhw 5y ago
      My point, again, is about having a compiler that can produce more optimal code than existing compilers (and whether there's a theoretical upper bound preventing them from more closely approaching the handwritten assembly in this case). I'm not quite sure what else you could have thought the word 'more' was referring to?
bawolff 5y ago
How would the compiler know that? This code for example is only optimal if you are piping it somewhere instead of displaying on the terminal. There is no way, even in principle, for the compiler to know that this program is always run with stdout connected to a pipe. Moreover, if you mean optimal in the absolute sense, pretty sure that is equivalent to solving the halting problem. If what your asking is: why can't computers take all surounding fuzzy context into account and do precisely the right thing, the answer is: because we haven't invented strong AI yet.
- samhw 5y ago
  Ah, sorry, I misunderstood you. I thought you were placing the emphasis on what the code was doing, rather than where it was being piped. But why do you think that most of the possible optimisations would only be relevant if the output were being piped to somewhere other than a terminal? Also, why would making it absolutely optimal be "equivalent to solving the halting problem"? (Though either way, no, I'm not talking about producing 100.0000% optimal code - clearly there's plenty of daylight between the current degree of optimality and that one.)
  - bawolff 5y ago
    > Ah, sorry, I misunderstood you. I thought you were placing the emphasis on what the code was doing, rather than where it was being piped. But why do you think that most of the possible optimisations would only be relevant if the output were being piped to somewhere other than a terminal? One of the primary optimizations is using vm_splice to avoid memory copies. vm_splice only works if the file descriptor is a pipe. > Also, why would making it absolutely optimal be "equivalent to solving the halting problem"? https://en.m.wikipedia.org/wiki/Rice%27s_theorem https://en.m.wikipedia.org/wiki/Rice%27s_theorem Or more specificly, if a program always halts (without outputting things) then the best optimization would be to have it halt immediately but to know that you have to have solved the halting problem. You're right of course, absolutes are a bit of a distraction we just need something good for 99% of programs. However that's still really hard, and an optimization applied in the wrong context will slow down a program. There's still lots of room for compilers to grow, but the types of optimizations in use in this example are at best probably NP-complete to determine if they apply (i dont have any evidence for that though)

londons_explore 5y ago

But nearly all problems boil down to nearly zero actual work... Take booting up a computer for example. All that actually needs to be done is to display the login screen on the screen. And we know from 60 fps video playback, that the hardware is capable of displaying a frame inside 16 milliseconds.

anthony_r 5y ago
You can create an operating system that just displays a static image within milliseconds yourself (shouldn't take you more than a few weeks), it would work even when compiled at -O0.