4 ms·

Actually compilers are much better at register allocation than humans and have been for many years; the fact that it is NP complete is irrelevant, because NP co

Actually compilers are much better at register allocation than humans and have been for many years; the fact that it is NP complete is irrelevant, because NP completeness is just as difficult for humans to deal with. Other than taking advantage of special instructions that are hard for compilers to use, there are few cases where the performance of hand-written assembly is better than compiler-generated code. Compilers cannot assume pre/post conditions, but they can analyze much larger amounts of code than humans and will often detect things that humans miss -- which constants that can be propagated, expressions that can be reduced, etc. Compilers are a lot better at deciding which of two equivalent instruction sequences will be faster on a given CPU architecture.

gizmo 9y ago
And yet the most efficient programs are written in the low level languages, and the slowest programs are written in high level languages where optimization is the responsibility of the compiler. Compilers can definitely do better than humans in some situations, but you can also use an optimizing assembler that helps with register allocation (not as important for x64) and all sorts of peephole optimizations. The compiler doesn't reason about the data, which means the compiler has to make worst-case assumptions that the programmer knows won't occur. This is a big source of inefficiency. Compilers will never be able to make strategic optimizations because the compiler doesn't understand what it's compiling. Like with chess, computer + human is the winning combination.
- tyingq 9y ago
  "Like with chess, computer + human is the winning combination." Curious what you mean here. My layman's observation is that computers have far surpassed humans in that space.
  - Retric 9y ago
    Not starting from scratch. Modern chess programs leverage a lot of human design and analysis work.
    - fourthark 9y ago
      Are there any domains in which computers start from scratch?
      - Retric 9y ago
        There are various abstract learning systems that work just fine for simple 2d video games. The problem is they have a lot of overhead.
  - MiddleEndian 9y ago
    He's probably referring to Centaur Chess, where a team of a human assisted by a chess computer (or perhaps more accurately a computer assisted by a human) competes against another similar team. https://en.wikipedia.org/wiki/Advanced_Chess https://en.wikipedia.org/wiki/Advanced_Chess
  - Santosh83 9y ago
    They're probably saying that a human assisted by a chess program (during training, not during actual game) can on average do better than a human who has practised chess without any artificial analysis/help. They could also perhaps mean that a chess program that takes human input during processing can do better (on average) than one that doesn't. Essentially they imply human + AI is superior to either of them in isolation.
- betterunix2 9y ago
  I am not sure how you are defining the "compiler" here; the compiler back end that emits code is where register allocation and peephole optimizations happen. "The compiler doesn't reason about the data" It certainly can; it is hard in a language like C due to the deficiencies of the type system, but in other languages the programmer can more explicitly state constraints on values. Compilers can also make useful inferences about constraints based on e.g. conditional statements, loop bounds, etc. Where humans win is in designing more efficient algorithms. Compilers are great at reducing the constants but still cannot improve the asymptotics. In other words, human effort is better spent on the higher-level concerns, and yes, some languages are better than others for that task. "Like with chess, computer + human is the winning combination." Chess-playing programs are so much better than humans that it is not even interesting to compare them anymore.
  - davemp 9y ago
    Are you trying to make the “sufficiently smart compiler” argument here? The reality is that the fastest compilers for the fastest languages still require babysitting and hand written ASM for peak performance. > human effort is better spent on the higher-level concerns For most cases, yes I (and likely most people) agree. Although there are times when we do care and it is important to know that our tools are not infallible.
userbinator 9y ago
Actually compilers are much better at register allocation than humans and have been for many years Having inspected compiler output for many years, I very much disagree. They've gotten a little better, but I still see plenty of unnecessary data shuffling and other things no sane human Asm programmer would ever do. A human has a far better understanding of what he/she wants the program to do, and this also includes things like which variables should go in registers, and when. A compiler can analyse dataflow and somewhat understand, but especially when external functions are involved, the knowledge is still incomplete. Compilers are a lot better at deciding which of two equivalent instruction sequences will be faster on a given CPU architecture. This ironically makes them worse overall, since (when told to) they always attempt to optimise for speed, even at the expense of size. They don't know that making one part of the code smaller, although somewhat slower, could allow another more critical part to fit completely into cache and improve performance overall. Speaking as a long-time Asm programmer myself, rarely do we act like HLL compilers and literally transcribe statement-for-statement what the HLL (e.g. C or C++) source code does. We start with a high-level understanding of the algorithm; maybe pseudocode, maybe flowcharts, maybe something derived from HLL source. Then we think at the register and instruction level and decide how to implement it. It's a somewhat creative process, unlike the literal pattern-matching compilers do. Example: https://news.ycombinator.com/item?id=15423674 https://news.ycombinator.com/item?id=15423674
- betterunix2 9y ago
  "I still see plenty of unnecessary data shuffling and other things no sane human Asm programmer would ever do." OK, but in the general case, at scale, in a complex program, compilers are better able to make register allocation decisions than humans. Some compilers may not be as good as others, and I would love to see some examples, but it has been a long time since this debate was settled. "A compiler can analyse dataflow and somewhat understand, but especially when external functions are involved, the knowledge is still incomplete." https://en.wikipedia.org/wiki/Interprocedural_analysis https://en.wikipedia.org/wiki/Interprocedural_analysis Sure, dynamic linking throws a wrench into things, but equally true for humans who may not understand how the function they are calling really works. "making one part of the code smaller, although somewhat slower, could allow another more critical part to fit completely into cache and improve performance overall." I am sure it happens. It is far more common for that sort of optimization to be irrelevant due to the size and complexity of the system. Compilers are also capable of optimizing for code size, it is similar to optimizing for speed but not important in most cases.

gizmo 9y ago

And yet the most efficient programs are written in the low level languages, and the slowest programs are written in high level languages where optimization is the responsibility of the compiler. Compilers can definitely do better than humans in some situations, but you can also use an optimizing assembler that helps with register allocation (not as important for x64) and all sorts of peephole optimizations. The compiler doesn't reason about the data, which means the compiler has to make worst-case assumptions that the programmer knows won't occur. This is a big source of inefficiency. Compilers will never be able to make strategic optimizations because the compiler doesn't understand what it's compiling. Like with chess, computer + human is the winning combination.

tyingq 9y ago
"Like with chess, computer + human is the winning combination." Curious what you mean here. My layman's observation is that computers have far surpassed humans in that space.
- Retric 9y ago
  Not starting from scratch. Modern chess programs leverage a lot of human design and analysis work.
  - fourthark 9y ago
    Are there any domains in which computers start from scratch?
    - Retric 9y ago
      There are various abstract learning systems that work just fine for simple 2d video games. The problem is they have a lot of overhead.
- MiddleEndian 9y ago
  He's probably referring to Centaur Chess, where a team of a human assisted by a chess computer (or perhaps more accurately a computer assisted by a human) competes against another similar team. https://en.wikipedia.org/wiki/Advanced_Chess https://en.wikipedia.org/wiki/Advanced_Chess
- Santosh83 9y ago
  They're probably saying that a human assisted by a chess program (during training, not during actual game) can on average do better than a human who has practised chess without any artificial analysis/help. They could also perhaps mean that a chess program that takes human input during processing can do better (on average) than one that doesn't. Essentially they imply human + AI is superior to either of them in isolation.
betterunix2 9y ago
I am not sure how you are defining the "compiler" here; the compiler back end that emits code is where register allocation and peephole optimizations happen. "The compiler doesn't reason about the data" It certainly can; it is hard in a language like C due to the deficiencies of the type system, but in other languages the programmer can more explicitly state constraints on values. Compilers can also make useful inferences about constraints based on e.g. conditional statements, loop bounds, etc. Where humans win is in designing more efficient algorithms. Compilers are great at reducing the constants but still cannot improve the asymptotics. In other words, human effort is better spent on the higher-level concerns, and yes, some languages are better than others for that task. "Like with chess, computer + human is the winning combination." Chess-playing programs are so much better than humans that it is not even interesting to compare them anymore.
- davemp 9y ago
  Are you trying to make the “sufficiently smart compiler” argument here? The reality is that the fastest compilers for the fastest languages still require babysitting and hand written ASM for peak performance. > human effort is better spent on the higher-level concerns For most cases, yes I (and likely most people) agree. Although there are times when we do care and it is important to know that our tools are not infallible.

userbinator 9y ago

Actually compilers are much better at register allocation than humans and have been for many years Having inspected compiler output for many years, I very much disagree. They've gotten a little better, but I still see plenty of unnecessary data shuffling and other things no sane human Asm programmer would ever do. A human has a far better understanding of what he/she wants the program to do, and this also includes things like which variables should go in registers, and when. A compiler can analyse dataflow and somewhat understand, but especially when external functions are involved, the knowledge is still incomplete. Compilers are a lot better at deciding which of two equivalent instruction sequences will be faster on a given CPU architecture. This ironically makes them worse overall, since (when told to) they always attempt to optimise for speed, even at the expense of size. They don't know that making one part of the code smaller, although somewhat slower, could allow another more critical part to fit completely into cache and improve performance overall. Speaking as a long-time Asm programmer myself, rarely do we act like HLL compilers and literally transcribe statement-for-statement what the HLL (e.g. C or C++) source code does. We start with a high-level understanding of the algorithm; maybe pseudocode, maybe flowcharts, maybe something derived from HLL source. Then we think at the register and instruction level and decide how to implement it. It's a somewhat creative process, unlike the literal pattern-matching compilers do. Example: https://news.ycombinator.com/item?id=15423674 https://news.ycombinator.com/item?id=15423674

betterunix2 9y ago
"I still see plenty of unnecessary data shuffling and other things no sane human Asm programmer would ever do." OK, but in the general case, at scale, in a complex program, compilers are better able to make register allocation decisions than humans. Some compilers may not be as good as others, and I would love to see some examples, but it has been a long time since this debate was settled. "A compiler can analyse dataflow and somewhat understand, but especially when external functions are involved, the knowledge is still incomplete." https://en.wikipedia.org/wiki/Interprocedural_analysis https://en.wikipedia.org/wiki/Interprocedural_analysis Sure, dynamic linking throws a wrench into things, but equally true for humans who may not understand how the function they are calling really works. "making one part of the code smaller, although somewhat slower, could allow another more critical part to fit completely into cache and improve performance overall." I am sure it happens. It is far more common for that sort of optimization to be irrelevant due to the size and complexity of the system. Compilers are also capable of optimizing for code size, it is similar to optimizing for speed but not important in most cases.