4 ms·

It's not just about the compiler being smart. There is nothing more you can do with x -> 2 + x other than compile it as is. Now if I somehow prove that x will n

It's not just about the compiler being smart. There is nothing more you can do with x -> 2 + x other than compile it as is. Now if I somehow prove that x will never be greater than 10 then all of a sudden the compiler can in theory just turn that addition into a lookup table or do all sorts of other things I couldn't think of. So it's more than just sufficient cleverness. It is also about the language providing you the tools to express certain invariants that the compiler can mechanically verify and then use in an optimization pipeline. Edit: This is mostly out of context now and can be ignored.

lomnakkus 10y ago
> There is nothing more you can do with x -> 2 + x other than compile it as is. You can often inline it. Now that may or not yield improvements in speed, but more to the point: It's quite possible that it's used in a context where x is bounded sensibly, and you can optimize further from there.
- dkarapetyan 10y ago
  At which point you are hoping the black box known as the compiler is "sufficiently smart". It's nice to hope but not in the context of compilers.
  - Rusky 10y ago
    That kind of optimization is well outside the bounds of "sufficiently smart." It happens routinely.
  - DannyBee 10y ago
    Uh? This happens all the time.
    - dkarapetyan 10y ago
      We must be using different compilers then. Last time I checked there are some heuristics about what gets inlined and when exactly those heuristics are triggered. Something about compilers being terminating programs and stack depth not being an unbounded resource. I don't know though. Maybe I was reading the wrong literature. What are your sources?
      - DannyBee 10y ago
        Now you are changing arguments. You said: "There is nothing more you can do with x -> 2 + x other than compile it as is." That is factually false. People called you on it. Rather than say "yeah, i was wrong, but i meant that in general, one doesn't get a guarantee that it will always turn out fast" or something, you seem to be just dodging it. So please, can you start with exactly what you would like to talk about? If it's about inlining, yes, those are heuristics in a lot of compilers, but they also do make guarantees a lot of the time (particularly around tail calling), and in fact, provide the ability to guarantee inlining happens to users. Fact: If always_inline doesn't always inline, the linux kernel fails to compile and link. So people rely on it in real software.
        dkarapetyan 10y ago
        Oh, `always_inline` looks like a programmer annotation to me? Am I correct? I don't know. You're the compiler writer who knows about these "sufficiently smart" compilers that should have filled all of that in for me.
wfunction 10y ago
> It's not just about the compiler being smart. There is nothing more you can do with x -> 2 + x other than compile it as is. > It is also about the language providing you the tools to express certain invariants that the compiler can use. Compiled code is useless if it is never called. The moment it's called, whether the caller is known during compilation or not, the caller can pass down any additional information it has, whether for that call or to help the callee optimize future calls. Heck, if it really wants to, the compiler could simply let the "compiled" code be the AST or source code itself (plus a JITter), and make the program generate code on the fly when the caller calls it, optimized using whatever information the caller is willing to provide. Again, nothing fundamentally in a language preventing this. It a tradeoff between implementation difficulty, execution latency, program size, and the like.
- dkarapetyan 10y ago
  That language with your described properties already exists and is called SBCL (http://www.sbcl.org/ http://www.sbcl.org/). I'm not sure what you're arguing at this point though and don't quite get what point you're making. Compilers, optimizations, type systems, and proof systems are all very closely related and if you want correct optimizations then you must annotate your code with types that the compiler can verify and use as assumptions in an optimization pipeline. These things are not easy to engineer. Saying just JIT it doesn't make much sense.
- kybernetikos 10y ago
  But doing the optimization at runtime will slow down at least one run (and probably more) compared to doing the optimization at compile time.
DannyBee 10y ago
"It's not just about the compiler being smart. There is nothing more you can do with x -> 2 + x other than compile it as is. " This is just trivially wrong. You can always add checks that it is a thing that lets you optimize better. You can always just JIT in addition to static compilation.
- dkarapetyan 10y ago
  Really? It's that simple? I wonder then why all these compiler writers spend so much time on getting the type system right if all they need to do is just add some if statements and then add a JIT. Guess I can also solve all pointer aliasing problems by just adding "if p != q {...}".
  - wfunction 10y ago
    > Really? It's that simple? Yeah. > I wonder then why all these compiler writers spend so much time on getting the type system right if all they need to do is just add some if statements then add a JIT. Because (1) JIT has a latency hit users like to avoid, and (2) you still have to solve the same problem during JIT time, it doesn't magically go away.
  - DannyBee 10y ago
    Yes. Actually, it kind of is. Note: I'm one of these compiler writers. In fact, i'm one of the compiler writers who wrote the current aliasing implementations for the two major compilers everyone uses, among other things. If you are going to disagree, please be concrete. I'm stating that good enough aliasing algorithms exist to do what you want, and where you can't, you can do runtime checks. People who truly care about performance hand the compiler the whole program, and want it to do a great job. It can and will. Your counter argument is what, exactly. That because people spend time getting type systems right, this must be false? If so, that's just silly. People spend time on getting type systems right to make it easier to reason about for people. Not because it's impossible at the compiler level. But because they'd rather not have to do it if they can avoid it. That doesn't mean it can't be done, and isn't done.
zurn 10y ago
If you forget about the static concepts of compilers, input data, and program source code, you see that it's all just inputs to a computation process and it's possible to specialize the program to the input. (See also: partial evaluation, Futamura projection)
dang 10y ago
Since this subthread degenerated so badly we detached it from https://news.ycombinator.com/item?id=14040109 https://news.ycombinator.com/item?id=14040109 and demoted it. Please don't do flamewars on HN.
- dkarapetyan 10y ago
  I don't know what detached means. If it is still visible it's kinda out of context now but I can't delete or edit so can it be detached further to not be visible at all? Oh, nm. I can edit.
  - steveklabnik 10y ago
    (not a mod) It means that it's not a reply anymore, it's at the top level, on its own, usually at the bottom of the page. Think of comments as a tree: this was a leaf, then was detached from its sub-tree.

lomnakkus 10y ago

> There is nothing more you can do with x -> 2 + x other than compile it as is. You can often inline it. Now that may or not yield improvements in speed, but more to the point: It's quite possible that it's used in a context where x is bounded sensibly, and you can optimize further from there.

dkarapetyan 10y ago
At which point you are hoping the black box known as the compiler is "sufficiently smart". It's nice to hope but not in the context of compilers.
- Rusky 10y ago
  That kind of optimization is well outside the bounds of "sufficiently smart." It happens routinely.
- DannyBee 10y ago
  Uh? This happens all the time.
  - dkarapetyan 10y ago
    We must be using different compilers then. Last time I checked there are some heuristics about what gets inlined and when exactly those heuristics are triggered. Something about compilers being terminating programs and stack depth not being an unbounded resource. I don't know though. Maybe I was reading the wrong literature. What are your sources?
    - DannyBee 10y ago
      Now you are changing arguments. You said: "There is nothing more you can do with x -> 2 + x other than compile it as is." That is factually false. People called you on it. Rather than say "yeah, i was wrong, but i meant that in general, one doesn't get a guarantee that it will always turn out fast" or something, you seem to be just dodging it. So please, can you start with exactly what you would like to talk about? If it's about inlining, yes, those are heuristics in a lot of compilers, but they also do make guarantees a lot of the time (particularly around tail calling), and in fact, provide the ability to guarantee inlining happens to users. Fact: If always_inline doesn't always inline, the linux kernel fails to compile and link. So people rely on it in real software.
      - dkarapetyan 10y ago
        Oh, `always_inline` looks like a programmer annotation to me? Am I correct? I don't know. You're the compiler writer who knows about these "sufficiently smart" compilers that should have filled all of that in for me.

wfunction 10y ago

> It's not just about the compiler being smart. There is nothing more you can do with x -> 2 + x other than compile it as is. > It is also about the language providing you the tools to express certain invariants that the compiler can use. Compiled code is useless if it is never called. The moment it's called, whether the caller is known during compilation or not, the caller can pass down any additional information it has, whether for that call or to help the callee optimize future calls. Heck, if it really wants to, the compiler could simply let the "compiled" code be the AST or source code itself (plus a JITter), and make the program generate code on the fly when the caller calls it, optimized using whatever information the caller is willing to provide. Again, nothing fundamentally in a language preventing this. It a tradeoff between implementation difficulty, execution latency, program size, and the like.

dkarapetyan 10y ago
That language with your described properties already exists and is called SBCL (http://www.sbcl.org/ http://www.sbcl.org/). I'm not sure what you're arguing at this point though and don't quite get what point you're making. Compilers, optimizations, type systems, and proof systems are all very closely related and if you want correct optimizations then you must annotate your code with types that the compiler can verify and use as assumptions in an optimization pipeline. These things are not easy to engineer. Saying just JIT it doesn't make much sense.
kybernetikos 10y ago
But doing the optimization at runtime will slow down at least one run (and probably more) compared to doing the optimization at compile time.

DannyBee 10y ago

"It's not just about the compiler being smart. There is nothing more you can do with x -> 2 + x other than compile it as is. " This is just trivially wrong. You can always add checks that it is a thing that lets you optimize better. You can always just JIT in addition to static compilation.

dkarapetyan 10y ago
Really? It's that simple? I wonder then why all these compiler writers spend so much time on getting the type system right if all they need to do is just add some if statements and then add a JIT. Guess I can also solve all pointer aliasing problems by just adding "if p != q {...}".
- wfunction 10y ago
  > Really? It's that simple? Yeah. > I wonder then why all these compiler writers spend so much time on getting the type system right if all they need to do is just add some if statements then add a JIT. Because (1) JIT has a latency hit users like to avoid, and (2) you still have to solve the same problem during JIT time, it doesn't magically go away.
- DannyBee 10y ago
  Yes. Actually, it kind of is. Note: I'm one of these compiler writers. In fact, i'm one of the compiler writers who wrote the current aliasing implementations for the two major compilers everyone uses, among other things. If you are going to disagree, please be concrete. I'm stating that good enough aliasing algorithms exist to do what you want, and where you can't, you can do runtime checks. People who truly care about performance hand the compiler the whole program, and want it to do a great job. It can and will. Your counter argument is what, exactly. That because people spend time getting type systems right, this must be false? If so, that's just silly. People spend time on getting type systems right to make it easier to reason about for people. Not because it's impossible at the compiler level. But because they'd rather not have to do it if they can avoid it. That doesn't mean it can't be done, and isn't done.

zurn 10y ago

If you forget about the static concepts of compilers, input data, and program source code, you see that it's all just inputs to a computation process and it's possible to specialize the program to the input. (See also: partial evaluation, Futamura projection)

dang 10y ago

Since this subthread degenerated so badly we detached it from https://news.ycombinator.com/item?id=14040109 https://news.ycombinator.com/item?id=14040109 and demoted it. Please don't do flamewars on HN.

dkarapetyan 10y ago
I don't know what detached means. If it is still visible it's kinda out of context now but I can't delete or edit so can it be detached further to not be visible at all? Oh, nm. I can edit.
- steveklabnik 10y ago
  (not a mod) It means that it's not a reply anymore, it's at the top level, on its own, usually at the bottom of the page. Think of comments as a tree: this was a leaf, then was detached from its sub-tree.