5 ms·

Will It Optimize?

132 points by DallaRosa 15y ago

udp 15y ago
Previous submission and discussion: http://news.ycombinator.com/item?id=1540567 http://news.ycombinator.com/item?id=1540567
deleted 15y ago
[deleted]
samth 15y ago
The comment about tail calls is wrong -- it's not an optimization, it's a guarantee about semantics of your program. Not optimizing tail calls is like making array dereference run in linear time instead of constant: it changes the programs you can write.
- barrkel 15y ago
  Irrespective of how it changes the semantics of (mostly functional) languages that rely on it for iteration, tail calling is also an optimization in languages that don't need to rely on it for this, and it is not wrong to describe it as such.
  - samth 15y ago
    There are two things here: an optimization, and a semantics guarantee. Obviously, if your language provides the guarantee, then implementing it correctly isn't just an optimization. But the original article claims that the transformation proves that proper tail calling is "just an optimization", which it doesn't prove at all. It's still an important semantic guarantee which increases the expressiveness of a language. This is true regardless of whether it is the only means of expressing iteration in a language.
    - ridiculous_fish 15y ago
      What the factorial example proves is that the set of recursive functions that can run in constant space is larger than just tail-recursive functions. You're right to say that TCO guarantees increase the expressiveness of a language. If we could provide the same guarantees for an even larger class of recursive functions, it stands to reason our expressiveness would increase even further!
- lukesandberg 15y ago
  In a language that requires TCO then you are right, it's not about optimization it's about correctness. In a language (like c) that has no such semantics it is 'just' an optimization. In scheme however it is a correctness issue.
alecco 15y ago
Oh, I remember getting upset last time with this "test". For example: 3. Multiplication by 2 to addition - integer Will GCC transform an integer multiplication by 2 to addition? The statement (not function) x * 2 is shift x left 1 bit on almost all compilers. Shift has a lot less dependencies than ADD/LEA and has better reciprocal throughput. Meh.
- DarkShikari 15y ago
  Shift has a lot less dependencies than ADD/LEA and has better reciprocal throughput. Nope. Usually it's the reverse: Atom, for example, can only do one shift per cycle, but it can dual-issue adds.
  - ajross 15y ago
    This surprises a lot of programmers. A barrel shifter is a big circuit for an ALU. Smaller than a multiplier obviously, but much larger than a ripple carry adder and somewhat larger even than the fancy pipelined adders used in fast CPUs. It's the kind of thing that got skimped on in Atom. Lots of stuff runs surprisingly slow on Atom. Another one I find striking is that there are two pipes for ADD/SUB instructions, but ADC/SBB (the carry/borrow variants) are not just single-issue, but apparently unpipelined. Intel lists their throughput at 3 instead of 0.5!
    - psykotic 15y ago
      > Intel lists their throughput at 3 instead of 0.5! Agner Fog lists ADC/SBB on Atom as having latency 2 and throughput 1/2. I guess Intel could have made them run with ADD/SUB-level performance in cases where there are no intra-pair dependencies on the carry/borrow flag, but the extra interlocks for handling that were probably not worth the cost.
  - alecco 15y ago
    My big mouth. I stand corrected.
Roritharr 15y ago
I remember learning about compiler optimization at university. Sadly all my colleagues knew(and were taught) was Java and the Sun JVM we used at the time didn't even do most of the stuff we learned, not even the tail-recursion optimization, therefor the opinion of most of the students was that the professor should stop babbling about things that have no application in real life. This was the one time i was on the side of academia...
- iam 15y ago
  Thankfully since then the HotSpot JVM has become one of the most advanced VMs in terms of JIT optimization, doing things that are so wild and crazy that other JITs can only dream of.
merraksh 15y ago
I have a little doubt about number 6. A switch() without a "default:" label has undefined behavior if x is negative or above 5, while nothing would happen in the cascading if's. Wouldn't a correct optimization of that be void function(int x) { switch (x) { case 0: f0(); break; case 1: f1(); break; case 2: f2(); break; case 3: f3(); break; case 4: f4(); break; case 5: f5(); break; default: } }
- dchest 15y ago
  Why does it have undefined behavior? Switch statement with no match and without the default case has defined behavior: the switch statement does nothing.
  - rcfox 15y ago
    "If no converted case constant expression matches and there is no default label, no part of the switch body is executed." Section 6.8.4.2, item 5 of http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf (page 134)
    - cbr 15y ago
      how is this different from "does nothing"?
      - rcfox 15y ago
        ... it's not? I was just providing an authoritative reference for the parent's claim. (Pedantic note: It's technically incorrect to say that the switch statement does nothing. switch(FunctionThatDoesSomethingAndReturns1()) { case 2: // foo } The switch body does nothing, but the actual statement does something.)
- thefre 15y ago
  are you high?
ajross 15y ago
Quibbles: the strlen() example is poorly explained. It doesn't hoist it because it's "built-in", it hoists it because strlen() is marked "pure" (i.e. without side effects) in the declaration. Any function can get that attribute.
- wzdd 15y ago
  There must be more to it than that. For example, if something in the loop body writes to s, then the result of "strlen" could change and the optimisation will be wrong. So, it must know a bit about what strlen() does, mustn't it -- otherwise it wouldn't know that it has to ensure that \0 isn't written to s inside the loop body.
  - saucetenuto 15y ago
    GCC can statically prove that `s` isn't changed at all in the loop body, just accessed. Thus the analysis goes: `strlen()` is pure, and its argument never changes, so its result never changes, so I can hoist it.
    - ssp 15y ago
      No, there is more to it than that. It has to perform an aliasing analysis to prove that nothing that s points to changes. Consider this code: unsigned sum(const unsigned char *s, char *t) { unsigned result = 0; for (size_t i=0; i < strlen(s); i++) { result += s[i]; *t = 'x'; } return result; } gcc can't hoist strlen() in this case, because *t = 'x' could potentially overwrite the null termination of s.
      - JoachimSchipper 15y ago
        Note that C99 has added "restrict" for such cases, which essentially promises that the restricted pointer (and any pointers derived from it) is the only pointer to that chunk of memory.
      - sausagefeet 15y ago

132 points by DallaRosa 15y ago

udp 15y ago

Previous submission and discussion: http://news.ycombinator.com/item?id=1540567 http://news.ycombinator.com/item?id=1540567

deleted 15y ago

[deleted]

samth 15y ago

The comment about tail calls is wrong -- it's not an optimization, it's a guarantee about semantics of your program. Not optimizing tail calls is like making array dereference run in linear time instead of constant: it changes the programs you can write.

barrkel 15y ago
Irrespective of how it changes the semantics of (mostly functional) languages that rely on it for iteration, tail calling is also an optimization in languages that don't need to rely on it for this, and it is not wrong to describe it as such.
- samth 15y ago
  There are two things here: an optimization, and a semantics guarantee. Obviously, if your language provides the guarantee, then implementing it correctly isn't just an optimization. But the original article claims that the transformation proves that proper tail calling is "just an optimization", which it doesn't prove at all. It's still an important semantic guarantee which increases the expressiveness of a language. This is true regardless of whether it is the only means of expressing iteration in a language.
  - ridiculous_fish 15y ago
    What the factorial example proves is that the set of recursive functions that can run in constant space is larger than just tail-recursive functions. You're right to say that TCO guarantees increase the expressiveness of a language. If we could provide the same guarantees for an even larger class of recursive functions, it stands to reason our expressiveness would increase even further!
lukesandberg 15y ago
In a language that requires TCO then you are right, it's not about optimization it's about correctness. In a language (like c) that has no such semantics it is 'just' an optimization. In scheme however it is a correctness issue.

alecco 15y ago

Oh, I remember getting upset last time with this "test". For example: 3. Multiplication by 2 to addition - integer Will GCC transform an integer multiplication by 2 to addition? The statement (not function) x * 2 is shift x left 1 bit on almost all compilers. Shift has a lot less dependencies than ADD/LEA and has better reciprocal throughput. Meh.

DarkShikari 15y ago
Shift has a lot less dependencies than ADD/LEA and has better reciprocal throughput. Nope. Usually it's the reverse: Atom, for example, can only do one shift per cycle, but it can dual-issue adds.
- ajross 15y ago
  This surprises a lot of programmers. A barrel shifter is a big circuit for an ALU. Smaller than a multiplier obviously, but much larger than a ripple carry adder and somewhat larger even than the fancy pipelined adders used in fast CPUs. It's the kind of thing that got skimped on in Atom. Lots of stuff runs surprisingly slow on Atom. Another one I find striking is that there are two pipes for ADD/SUB instructions, but ADC/SBB (the carry/borrow variants) are not just single-issue, but apparently unpipelined. Intel lists their throughput at 3 instead of 0.5!
  - psykotic 15y ago
    > Intel lists their throughput at 3 instead of 0.5! Agner Fog lists ADC/SBB on Atom as having latency 2 and throughput 1/2. I guess Intel could have made them run with ADD/SUB-level performance in cases where there are no intra-pair dependencies on the carry/borrow flag, but the extra interlocks for handling that were probably not worth the cost.
- alecco 15y ago
  My big mouth. I stand corrected.

Roritharr 15y ago

I remember learning about compiler optimization at university. Sadly all my colleagues knew(and were taught) was Java and the Sun JVM we used at the time didn't even do most of the stuff we learned, not even the tail-recursion optimization, therefor the opinion of most of the students was that the professor should stop babbling about things that have no application in real life. This was the one time i was on the side of academia...

iam 15y ago
Thankfully since then the HotSpot JVM has become one of the most advanced VMs in terms of JIT optimization, doing things that are so wild and crazy that other JITs can only dream of.

merraksh 15y ago

I have a little doubt about number 6. A switch() without a "default:" label has undefined behavior if x is negative or above 5, while nothing would happen in the cascading if's. Wouldn't a correct optimization of that be void function(int x) { switch (x) { case 0: f0(); break; case 1: f1(); break; case 2: f2(); break; case 3: f3(); break; case 4: f4(); break; case 5: f5(); break; default: } }

dchest 15y ago
Why does it have undefined behavior? Switch statement with no match and without the default case has defined behavior: the switch statement does nothing.
- rcfox 15y ago
  "If no converted case constant expression matches and there is no default label, no part of the switch body is executed." Section 6.8.4.2, item 5 of http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf (page 134)
  - cbr 15y ago
    how is this different from "does nothing"?
    - rcfox 15y ago
      ... it's not? I was just providing an authoritative reference for the parent's claim. (Pedantic note: It's technically incorrect to say that the switch statement does nothing. switch(FunctionThatDoesSomethingAndReturns1()) { case 2: // foo } The switch body does nothing, but the actual statement does something.)
thefre 15y ago
are you high?

ajross 15y ago

Quibbles: the strlen() example is poorly explained. It doesn't hoist it because it's "built-in", it hoists it because strlen() is marked "pure" (i.e. without side effects) in the declaration. Any function can get that attribute.

wzdd 15y ago
There must be more to it than that. For example, if something in the loop body writes to s, then the result of "strlen" could change and the optimisation will be wrong. So, it must know a bit about what strlen() does, mustn't it -- otherwise it wouldn't know that it has to ensure that \0 isn't written to s inside the loop body.
- saucetenuto 15y ago
  GCC can statically prove that `s` isn't changed at all in the loop body, just accessed. Thus the analysis goes: `strlen()` is pure, and its argument never changes, so its result never changes, so I can hoist it.
  - ssp 15y ago
    No, there is more to it than that. It has to perform an aliasing analysis to prove that nothing that s points to changes. Consider this code: unsigned sum(const unsigned char *s, char *t) { unsigned result = 0; for (size_t i=0; i < strlen(s); i++) { result += s[i]; *t = 'x'; } return result; } gcc can't hoist strlen() in this case, because *t = 'x' could potentially overwrite the null termination of s.
    - JoachimSchipper 15y ago
      Note that C99 has added "restrict" for such cases, which essentially promises that the restricted pointer (and any pointers derived from it) is the only pointer to that chunk of memory.
    - sausagefeet 15y ago