5 ms·

>if people really want zero cost abstraction That one "if" is (by definition) not zero-cost.

by dhsjxhx 10y ago

steveklabnik 10y ago
It is by definition a "zero-cost abstraction." Let's ask Stroustrup, who coined the term: > C++ implementations obey the zero-overhead principle: What you don’t use, you don’t pay for. And further: What you do use, you couldn’t hand code any better. Two points: What you don't use, you don't pay for: if you don't use array indexing, you won't get a bounds check. In addition, you can call an access method without a bounds check as well, so it truly is only if you use the checked version. What you do use, you couldn't hand-code any better: that bounds check is written the exact same way you'd write it in C. Therefore, this is a zero-cost abstraction.
- aduffy 10y ago
  This is actually a very helpful comment. I used to think "zero-cost" meant "at compile-time", as in `newtype` in Haskell, etc. I'm guessing that's what the parent commenter thought as well, and I'd guess is what most people think when they hear the phrase.
  - steveklabnik 10y ago
    Thanks! It can definitely be a bit unintuitive at first. After all, everything has _some_ cost...
  - kqr 10y ago
    Well, you can still sort of view it that way. You can imagine the bounds check being a "compile time generation of the C code you'd write to check the bounds anyway".
    - aduffy 10y ago
      The difference is that it's not dealt with entirely in the compile phase. i.e. language features that are checked at compilation and known to be true that are not needed at runtime. The Haskell `newtype` example I gave was meant to illustrate this, as newtype's are respected by the type system and then are treated as the underlying type at runtime.
  - gcatlin 10y ago
    I think that's why Stroustrup says "zero overhead" instead of "zero cost". There are costs to many of these abstractions; some at compile time and some at run time. For me, "zero overhead" conveys this a little better.
- Veedrac 10y ago
  This is a misrepresentation of his comment. By your interpretation, you could call GC zero-cost! Most code doesn't use bounds checking, because the branch is a safety net you should never hit, even in theory. Any code that does hit it is already broken. Correct programs using bounds checked indexing will in general be slower than but equivalent to a program where indexing instead results in undefined behaviour.
  - steveklabnik 10y ago
    Most GCs would violate the "What you don't use, you don't pay for". That is, they add runtime cost (and "the size of the runtime" size) to code, even code that doesn't allocate. "You couldn't hand-code any better", well, I won't argue on that point, as it sounds contentious. ;) _Should_ never hit is very different than will never hit...
    - Veedrac 10y ago
      If you never allocate, there's nothing stopping the compiler from optimizing the GC out. Then you get your first property back, in the sense you originally gave. My point is that Bjarne Stroustrup wasn't comparing against writing the exact same program the exact same way. He was comparing against what you'd get if you dropped down to ye olde C or Assembly and wrote the same algorithm there, without redundant work or waste. The comparison shouldn't be the language's GC versus SteveGC, it should be the language's GC versus an ideal, manually implemented allocator. Equally it shouldn't be built-in bounds checked indexing versus manual bounds checked indexing, it should be built-in bounds checked indexing versus an ideal, manually implemented indexing scheme. If you want safety against out-of-bounds, it seems to me the ideal method would be a proof, not runtime overhead.
      - steveklabnik 10y ago
        > there's nothing stopping the compiler from optimizing the GC out. I don't know of a single language that comes with a GC that does this, do you? > He was comparing against what you'd get if you dropped down to ye olde C or Assembly and wrote the same algorithm there, without redundant work or waste. Right. I agree with this. But basically, we are arguing over an extremely fine semantic, which is "should you even want bounds checks in the first place." If you don't, then don't use a method that has bounds checks. The one that does will have them. They'll both cost the exact same as writing it in C or assembly.

>if people really want zero cost abstraction That one "if" is (by definition) not zero-cost.

by dhsjxhx 10y ago

>if people really want zero cost abstraction That one "if" is (by definition) not zero-cost.

It is by definition a "zero-cost abstraction." Let's ask Stroustrup, who coined the term: > C++ implementations obey the zero-overhead principle: What you don’t use, you don’t pay for. And further: What you do use, you couldn’t hand code any better. Two points: What you don't use, you don't pay for: if you don't use array indexing, you won't get a bounds check. In addition, you can call an access method without a bounds check as well, so it truly is only if you use the checked version. What you do use, you couldn't hand-code any better: that bounds check is written the exact same way you'd write it in C. Therefore, this is a zero-cost abstraction.

aduffy 10y ago
This is actually a very helpful comment. I used to think "zero-cost" meant "at compile-time", as in `newtype` in Haskell, etc. I'm guessing that's what the parent commenter thought as well, and I'd guess is what most people think when they hear the phrase.
- steveklabnik 10y ago
  Thanks! It can definitely be a bit unintuitive at first. After all, everything has _some_ cost...
- kqr 10y ago
  Well, you can still sort of view it that way. You can imagine the bounds check being a "compile time generation of the C code you'd write to check the bounds anyway".
  - aduffy 10y ago
    The difference is that it's not dealt with entirely in the compile phase. i.e. language features that are checked at compilation and known to be true that are not needed at runtime. The Haskell `newtype` example I gave was meant to illustrate this, as newtype's are respected by the type system and then are treated as the underlying type at runtime.
- gcatlin 10y ago
  I think that's why Stroustrup says "zero overhead" instead of "zero cost". There are costs to many of these abstractions; some at compile time and some at run time. For me, "zero overhead" conveys this a little better.
Veedrac 10y ago
This is a misrepresentation of his comment. By your interpretation, you could call GC zero-cost! Most code doesn't use bounds checking, because the branch is a safety net you should never hit, even in theory. Any code that does hit it is already broken. Correct programs using bounds checked indexing will in general be slower than but equivalent to a program where indexing instead results in undefined behaviour.
- steveklabnik 10y ago
  Most GCs would violate the "What you don't use, you don't pay for". That is, they add runtime cost (and "the size of the runtime" size) to code, even code that doesn't allocate. "You couldn't hand-code any better", well, I won't argue on that point, as it sounds contentious. ;) _Should_ never hit is very different than will never hit...
  - Veedrac 10y ago
    If you never allocate, there's nothing stopping the compiler from optimizing the GC out. Then you get your first property back, in the sense you originally gave. My point is that Bjarne Stroustrup wasn't comparing against writing the exact same program the exact same way. He was comparing against what you'd get if you dropped down to ye olde C or Assembly and wrote the same algorithm there, without redundant work or waste. The comparison shouldn't be the language's GC versus SteveGC, it should be the language's GC versus an ideal, manually implemented allocator. Equally it shouldn't be built-in bounds checked indexing versus manual bounds checked indexing, it should be built-in bounds checked indexing versus an ideal, manually implemented indexing scheme. If you want safety against out-of-bounds, it seems to me the ideal method would be a proof, not runtime overhead.
    - steveklabnik 10y ago
      > there's nothing stopping the compiler from optimizing the GC out. I don't know of a single language that comes with a GC that does this, do you? > He was comparing against what you'd get if you dropped down to ye olde C or Assembly and wrote the same algorithm there, without redundant work or waste. Right. I agree with this. But basically, we are arguing over an extremely fine semantic, which is "should you even want bounds checks in the first place." If you don't, then don't use a method that has bounds checks. The one that does will have them. They'll both cost the exact same as writing it in C or assembly.