Hacker News Reader

Comment by steveklabnik | Hacker News Reader

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.

View on HN

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.

Thanks! It can definitely be a bit unintuitive at first. After all, everything has _some_ cost...

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

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.

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.

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.

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

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.

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

I'm not arguing about whether bounds checks are good, but about whether it's correct to call them zero-cost in the canonical sense. Doing so just devalues the term, and IMO feels like misdirection.

To put it another way, let's say I was a C++ developer on the fence about Rust. If I read this conversation, I'd see that indexing gets called "zero-cost" despite the overhead. Since tons of things in Rust are "zero-cost", like traits, closures, borrowing, etc., all of those things now have doubt cast on them. How can I really trust that these things are actually getting compiled efficiently?

If instead the conversation pointed out that this was one of a few cases where safety took priority over truly being zero cost, but that there were tools in place to mitigate the cost (iterators, unsafe indexing, LLVM), I'd have a much more positive outlook that focussed on what Rust did right.

I would suspect that a C++ programmer would be more familiar with that actual definition I mentioned originally, and so would understand the subtleties here.

That said, I can appreciate focusing on other things when talking about the principle; I only brought them up here because we were literally discussing them. I think there's much better examples when actually attemping to convince someone.

I think you have a good point. It makes more sense to think and talk about as Rust's implementation of bounds checked indexing syntax as being a zero cost abstraction for writing `if` statements everywhere. I.e. Assuming you want bounds checking, you can't do better than what Rust does despite having nice syntax etc.

I think something like this actually happened with one of the first scheme implementations, but that was because they wrote the GC in scheme so they had to do it that way for a very small subset of the system (is the GC code). But yeah other than that I can't think of any examples (and my example is kind of the exception that proves the rule).

> I don't know of a single language that comes with a GC that does this, do you?

Java, .NET, Go, ML and Lisp compilers.

Escape analysis allows to do that, even if just in certain special cases.

Plus the more one uses value types and less heap, the GC needs to work less, specially if we take languages like Modula-3 into this mix.

This is more than escape analysis, this is removing the GC and associated runtime bits entirely.

Escape analysis may not use the GC for those variables, but it is still a pervasive runtime cost in both senses unless it's totally gone.

Yes, but making it run less also helps reducing the cost.

IIUC there's always some tagging or bit depth loss due to the use of GC ?

If you never allocate, escape analysis doesn't have anything to do.

Reply on news.ycombinator.com