4 ms·

> assembly does not make it faster It is still very possible to hand write assembly that’s faster than optimized C. The compiler can’t just magically assume th

by davemp 9y ago

> assembly does not make it faster It is still very possible to hand write assembly that’s faster than optimized C. The compiler can’t just magically assume the same pre/post conditions that you can. Also register allocation is an NP problem (graph coloring). Can a human keep that level of optimization up for the length of an OS? No idea. Would it even be worth it? Probably not.

betterunix2 9y ago
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
- 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.
dom0 9y ago
> Also register allocation is an NP problem (graph coloring). No, this strongly depends on the form of the program. SSA form permits polynomial solution of register allocation. (SSA is the most widely used form in compilers; LLVM, GCC and even MSVC use it, and many more.)
- andrewflnr 9y ago
  My understanding is that the number of colors is just the maximum number of live values at any point, which is easy to determine, so the theoretically NP-complete part of graph-coloring is solved before you even start trying to pick registers. After that, it gets tricky to even define optimality, because you have to trade off the likely runtime costs of different sets of moves (which in my mind includes which variables to spill to the stack when). If there's a formal framework that decisively handles that stuff, someone please let me know. OTOH, GP only actually said "NP problem", of which P is a subset, so they're not wrong. :)

by davemp 9y ago

betterunix2 9y ago

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
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.

dom0 9y ago

> Also register allocation is an NP problem (graph coloring). No, this strongly depends on the form of the program. SSA form permits polynomial solution of register allocation. (SSA is the most widely used form in compilers; LLVM, GCC and even MSVC use it, and many more.)

andrewflnr 9y ago
My understanding is that the number of colors is just the maximum number of live values at any point, which is easy to determine, so the theoretically NP-complete part of graph-coloring is solved before you even start trying to pick registers. After that, it gets tricky to even define optimality, because you have to trade off the likely runtime costs of different sets of moves (which in my mind includes which variables to spill to the stack when). If there's a formal framework that decisively handles that stuff, someone please let me know. OTOH, GP only actually said "NP problem", of which P is a subset, so they're not wrong. :)