5 ms·

I am working on an x86 code generator today for a small language I have been working on. This story seems very timely to re-read because it is so difficult to g

by timtadh 12y ago

I am working on an x86 code generator today for a small language I have been working on. This story seems very timely to re-read because it is so difficult to generate really good x86 code. Even though I basically know what I am doing when writing a code generator at this point, and I have previous ones to reference, there are so many edge cases it is hard to get it right.[1] It used to be said that a compiler would never beat a programmer at assembly. Now we say the compiler is usually going to "do the right thing." I think there are two things going on here: 1) Our code generators are much better than they were in the bad old days. 2) Most people don't understand the ins and outs of their machines like Mel did (I certainly don't). This means that the compiler has "institutional" knowledge from a few really knowledgeable people and the rest of us just use that knowledge. [1] see for simple example `imul` which has 5 different forms http://docs.oracle.com/cd/E19455-01/806-3773/instructionset-39/index.html http://docs.oracle.com/cd/E19455-01/806-3773/instructionset-... . According to the intel optimization manual[2] the 16 bit forms suffer from "false LCP" stalls. The recommendation is to cast to 32 bit before preforming the `imul`. [2] http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf http://www.intel.com/content/dam/www/public/us/en/documents/... page 103 in the PDF. See also 506 for timings on the Atom architecture and 517 for Silvermont.

mikeash 12y ago
An important addition/corollary/reason for (2) is that modern machines are so much more complex. It's no longer possible for any one person to have that level of understanding of their machine, because there's too much to it. There are probably orders of magnitude more transistors in a single Intel CPU today than had ever been produced in the entire world at the time Mel was doing his thing. It's overall a good thing. It's what lets us do so much and have machines that are so fast. But it does imply a lot of necessary abstraction to get stuff done.
CodeMage 12y ago
I find this trend slightly scary. The more certain bits of code are used, the more we tend to trust that they are good. Yet, the more time passes, the more complex systems get and the fewer people truly understand those core bits of code. I've been in a few situations where I've seen core bits of code with glaring inefficiencies, but nobody even bothered to check them before, because we all trusted the group of people in charge of writing and maintaining that code. Turns out, those are "mere humans", just like the rest of us, and they can make mistakes too.
- dclusin 12y ago
  I think you are right to be fearful. Trust isn't good enough. As our machines become more complicated, formal methods of verification & validation will become necessary for the daily programmer. We cannot trust that it is correct, we must know with certainty. We can already deliver software and hardware solutions that are formally verified to perform correctly and not kill anyone. The knowledge and know-how just isn't widespread largely due to prohibitive cost and arcane nature of the subject material. Increasing complexity and security consciousness will be the primary driver for the adoption of these technologies in the mainstream I believe. We are already starting to see the articles about formal methods appear more frequently on Hacker News, which is a more general programming and entrepreneurial audience.
NoMoreNicksLeft 12y ago
> It used to be said that a compiler would never beat a programmer at assembly. Probably still couldn't. But with gigs of ram, terabytes of hard drive space, and gazillions of flops of cpu time available, no one cares. No one can wait for Mel to optimize blackjack, your boss wants the new build 5-15 minutes after you've written the code, and that shouldn't take more than an hour itself. It's not that the compiler got better than programmers... it just because cheaper. Hell, how many Mels are there out there anyway? Surely the number of people that clever and devoted to the bare metal of a CPU has never exceeded a few thousand people out of the entire population of Earth. Rarity makes them expensive, but it also means that shitty software shop in St. Louis or Tampa could never have such a person. And since technology drives the economy, everything would crash if we had to rely on the availability of super-programmers. Optimizing compilers are slightly better than they were long ago... but this isn't because they're all that impressive. We've just had thousands of monkeys pounding away over decades, hammering out one little optimization or another, and the storage to allow compilers to grow big enough to have a library of those to rely on.
- dllthomas 12y ago
  It depends greatly on the programmer, and how much time you allot them. GCC will produce vastly better code than any human programmer, given a specification in C and a time bound of 1 second. Give them ten minutes? An hour? A week? At the extreme a sufficiently adept assembly programmer (which probably still exist) will still beat the compiler, given enough time, though that can be helped by the ability to reference the code the compiler is generating.
  - wolf550e 12y ago
    Not any human programmer, at least not for some tasks. The handcoded x86 SIMD code in x264 (the software video encoder used by everyone who cares about video quality per bitrate) beats the output of any compiler trying to compile the pure-C fallback function. Same for a bunch of other code you use (indirectly) like memcpy or strlen. But the optimized handcoded routines take weeks to develop while a compiler would be done in less than a second. For almost all code, a programmer's time would be better spent on something else.

by timtadh 12y ago

mikeash 12y ago

An important addition/corollary/reason for (2) is that modern machines are so much more complex. It's no longer possible for any one person to have that level of understanding of their machine, because there's too much to it. There are probably orders of magnitude more transistors in a single Intel CPU today than had ever been produced in the entire world at the time Mel was doing his thing. It's overall a good thing. It's what lets us do so much and have machines that are so fast. But it does imply a lot of necessary abstraction to get stuff done.

CodeMage 12y ago

I find this trend slightly scary. The more certain bits of code are used, the more we tend to trust that they are good. Yet, the more time passes, the more complex systems get and the fewer people truly understand those core bits of code. I've been in a few situations where I've seen core bits of code with glaring inefficiencies, but nobody even bothered to check them before, because we all trusted the group of people in charge of writing and maintaining that code. Turns out, those are "mere humans", just like the rest of us, and they can make mistakes too.

dclusin 12y ago
I think you are right to be fearful. Trust isn't good enough. As our machines become more complicated, formal methods of verification & validation will become necessary for the daily programmer. We cannot trust that it is correct, we must know with certainty. We can already deliver software and hardware solutions that are formally verified to perform correctly and not kill anyone. The knowledge and know-how just isn't widespread largely due to prohibitive cost and arcane nature of the subject material. Increasing complexity and security consciousness will be the primary driver for the adoption of these technologies in the mainstream I believe. We are already starting to see the articles about formal methods appear more frequently on Hacker News, which is a more general programming and entrepreneurial audience.

NoMoreNicksLeft 12y ago

> It used to be said that a compiler would never beat a programmer at assembly. Probably still couldn't. But with gigs of ram, terabytes of hard drive space, and gazillions of flops of cpu time available, no one cares. No one can wait for Mel to optimize blackjack, your boss wants the new build 5-15 minutes after you've written the code, and that shouldn't take more than an hour itself. It's not that the compiler got better than programmers... it just because cheaper. Hell, how many Mels are there out there anyway? Surely the number of people that clever and devoted to the bare metal of a CPU has never exceeded a few thousand people out of the entire population of Earth. Rarity makes them expensive, but it also means that shitty software shop in St. Louis or Tampa could never have such a person. And since technology drives the economy, everything would crash if we had to rely on the availability of super-programmers. Optimizing compilers are slightly better than they were long ago... but this isn't because they're all that impressive. We've just had thousands of monkeys pounding away over decades, hammering out one little optimization or another, and the storage to allow compilers to grow big enough to have a library of those to rely on.

dllthomas 12y ago
It depends greatly on the programmer, and how much time you allot them. GCC will produce vastly better code than any human programmer, given a specification in C and a time bound of 1 second. Give them ten minutes? An hour? A week? At the extreme a sufficiently adept assembly programmer (which probably still exist) will still beat the compiler, given enough time, though that can be helped by the ability to reference the code the compiler is generating.
- wolf550e 12y ago
  Not any human programmer, at least not for some tasks. The handcoded x86 SIMD code in x264 (the software video encoder used by everyone who cares about video quality per bitrate) beats the output of any compiler trying to compile the pure-C fallback function. Same for a bunch of other code you use (indirectly) like memcpy or strlen. But the optimized handcoded routines take weeks to develop while a compiler would be done in less than a second. For almost all code, a programmer's time would be better spent on something else.