4 ms·
It seems there's a huge gap between what machine code compilers can generate and hand written optimized assembler. There's a lot of room left for compilers to b
by DeathArrow 5y ago
It seems there's a huge gap between what machine code compilers can generate and hand written optimized assembler. There's a lot of room left for compilers to be improved.
- bawolff 5y agoMost programs aren't fizzbuzz. This is basically hand optimizing a microbenchmark. While i'm sure compilers can always be better i'm not sure this particular example generalizes.
- londons_explore 5y agoBut hand optimizing a few microbenchmarks like this tells us how far we might be able to improve compilers. And from the looks of it, at least 100x is possible. It's a shame therefore that even a 1% performance increase in a compiler release is considered pretty noteworthy.
- anthony_r 5y agoThis 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 agoAnd 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?
- bawolff 5y agoHow 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 agoAh, 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 agoBut 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 agoYou 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.
- bonzini 5y agoThe top 3 entries use completely different algorithms. The use of assembly might help a bit, but not as much as the raw numbers suggest.
- andrewaylett 5y agoBack when I was employed to work on a compiler, our approach to such things was to implement our run-time libraries in C and fix the compiler so it was able to produce the desired output. In this case, though, the biggest differences aren't coming from C vs assembler but from walking away from platform conventions -- ABI, memory layout, CPU compatibility. It might be easier to write assembly than to teach the compiler how to generate code that does this, but that's largely because you don't need these optimisations in most cases. If the methods used provided a general speedup, it would be worth implementing them in compilers.
- pjc50 5y agoProducing this solution requires not merely a clever compiler but an extraordinary amount of creative intelligence.
- btilly 5y agoI suspect that a compiler which produced code that will crash when you attempt to write to a file would be declared buggy and unusable. And yet, that is one of the optimizations that helps get this one the speed crown.