When zero cost abstractions aren't zero cost
blog.polybdenum.com
blog.polybdenum.com
I'm not really sure it follows, though, that you should ever expect more than that. It's nice if you can get it but the presence of a very specific optimization shouldn't be taken as the new "zero cost" baseline, and I don't think it should be taken as given that a newtype will inherit all possible optimizations of its enclosed type.
[0]: https://github.com/rust-lang/rust/blob/master/library/alloc/...
[1]: https://github.com/rust-lang/rust/blob/master/library/alloc/...
However, if the type is Copy and all the bytes are zeros, then you know it can be calloc
https://crates.io/crates/misfortunate
However, Rust does have two other tricks up its sleeve:
1. Unsafe traits. You can declare a trait to be "unsafe". Implementations of this trait likewise need that "unsafe" keyword and it alerts the programmer that, as with unsafe function calls, they are responsible for actually getting the implementation details correct. Not many standard library traits are unsafe because that's a considerable burden, but a few are, including Send and Sync.
You wouldn't learn much by implementing unsafe traits wrongly in a library like misfortunate, it's the same lesson as a C++ library that scribbles on random memory addresses.
2. Rust knows whether you implemented a trait by hand or merely derived it. In a few cases it can be reasonable for the language to distinguish these cases for built-in traits, since in the former case it knows the derived trait does what is needed even though a manual implementation may not.
It is possible that future improvements to Const Generics will rely on this latter idea. So long as you derive Eq rather than implementing it, Rust can reason that your type really is suitable as a constant type parameter whereas misfortunate::Always is not suitable (it would cause mayhem if permitted because of its idea of what "equality" is) despite claiming to be Eq.
unsafe trait IsZero: Copy {
fn is_zero(&self) -> bool;
}
#[derive(Copy, IsZero)]
struct Foo {
a: u8,
b: u16,
}
unsafe impl IsZero for Foo {
fn is_zero(&self) -> bool {
true
&& self.a.is_zero()
&& self.b.is_zero()
}
}[1]: https://rust-lang.github.io/rfcs/3107-derive-enum-default.ht...
enum E<T> {
Empty = 42,
Some(NonFortyTwo<T>),
}
enum E<T> {
Empty = 0,
Some(NonZero<T>),
}
Still the existing tricks get a lot done for relatively little work. I have used Option<NonZeroUsize> to do roughly what I'd use a single integer for in C, but making explicit that zero isn't just zero, but "I dunno, invalid". Would I have done that even if it cost more space? Probably, but it was cool that I didn't even need to consider that, "Zero cost abstraction".
Too late to edit. This should clearly have said, in the latter case not the former case. In the hand implemented case the compiler has no idea whether your implementation has the desired properties.
That's not as easy to check as one would think since Copy types can still contain uninitialized bytes.
Especially in a case like in the article, where the type is very small (one byte), and the obstacle is that the author is using a newtype.
Surely baseline is that it does something correct. Reasonable (or just "not pathologically stupid" if you separate the two, with reasonable next) comes after. To my mind an optimising compiler is a compiler first, an optimiser second.
This feels like a recurring pattern in Rust's design whether we're talking about performance, what's accepted by the compiler, etc. I'm not sure it's a bad thing exactly, but it leads to a lot of unintuitive footguns. Of course the consequence of these footguns is de-optimization or a compiler error, instead of a runtime exception or a memory error. But nevertheless it can make for a confusing landscape of behavior to navigate.
Should they not try and spot-optimize common cases where they can, just for the sake of predictability? No, I don't think so. And so I don't know what the answer is. I just often (and even more so when I was new to it) find myself surprised by Rust's general-rules-that-actually-have-notable-exceptions. Though who knows, maybe it's just not possible to make a language this powerful that doesn't run into this problem.
I meant they "shouldn't not", as in I don't think it would make sense to do otherwise from what they're doing
I think the industry as a whole has already accepted "try to optimize common cases on a best-effort basis, at the cost of unpredictable performance cliffs in unusual cases" as the default paradigm.
From multi-tiers JITs, auto-vectorizing, all the way down to branch prediction, source code is a leaky abstraction. If you don't care about performance, you still get the benefits most of the time. If you do care, then you need to peel back the abstraction and have a good understanding of what the compiler/JIT/CPU does behind the scenes.
https://old.reddit.com/r/rust/comments/p0ul6b/when_zero_cost...
// 1st-way
vec![0; len];
// 2nd-way
std::iter::repeat(0).take(len).collect::<Vec<_>>();
godbolt: https://godbolt.org/z/8bM7zz4E7
the specific specialization: https://github.com/rust-lang/rust/blob/master/library/alloc/...
vec![0u8; len]
.into_iter()
.map(|x| WrappedByte(x))
.collect::<Vec<_>>()
Godbolt: https://godbolt.org/z/hxnnPcjvG
[In Rust the standard library provides count_ones() on integer types, and that's actually safely wrapping an intrinsic pop count feature]
Sure, I can see how the code doesn't immediately tell you the difference but after you understood it, isn't it completely logical?
The title seems clickbaity and not accurate when you dig into the article.
Do you think the title is still inaccurate even from that point of view?
And IMO the title is still inaccurate because it attacks a general promised/desired property of Rust (and other languages) and I honestly don't see the connection. Looks like the observed behaviour is an unfortunate side effect of the `newtype` thing and is very prone to fixing and optimization in future versions. It's not a failure of the "zero-cost abstraction" ideal which is being chased after every day and is still in flux.
The second example doesn't seem compelling to me either...is a newtype of a reference type a common application?
This paragraph is worth highlighting. Say yes to everything and vision becomes meaningless. Can't move in one direction when you're pulled by an infinite number of stakeholders on all sides.
1. Turns out that zeroing u8 is a special case so if you allocate 17 GB of your custom structure Rust is gonna init that for you.
2. Okay, so you don't understand how RefCell works? The caller to this function should be holding r, not passing it into the function. Of course that will just correctly Panic, so it's not wonderful. But that is the point of RefCell.
Generally more stuff runs fast in Rust than in other languages, but you can always find bad counterexamples in any language.
That’s not the interesting part. The point is that rust won’t optimize a lifetime inside a struct the same way it will optimize an actual reference. It can’t assume that the lifetime will be valid for the whole function (as it can with ref). This limits the amount of reordering you can do in the optimizer.
The example you were looking at was explaining why that is the case.
Ultimately I'm happy for Rust to only be so smart, of course there are going to be limitations. But you are right, the author was making a clear example and my comment doesn't make sense in that context.
[1]: https://github.com/rust-lang/rfcs/blob/master/text/2094-nll....
Arguably the WrapperType, i.e. any arbitrary type is the general case and thus the baseline performance. `u8` is the special case (hence specialization) that performs the alloc_zeroed optimization. So it's not really that the abstraction adds a cost. It's just that the special case removes a cost paid by everything else.
In the future the vec initialization might be fixable, but this requires turning potentially undefined values into some valid if arbitrary bit patterns (i.e. llvm's freeze) to compare it against zero.
Zero-cost abstraction is what you get when your abstraction gets compiled away to nothing. Like properly written value wrappers in C++, or (presumably) newtype in Rust. These things disappear from final assembly.
In that regard, exceptions are interesting as if you're on the happy path (which should be 99.999% of the time - a normal program that uses exceptions as error handling method should not encounter any exception if you do a `catch throw` on an average run of the software), they can cost less than return-value-based error handling (https://nibblestew.blogspot.com/2017/01/measuring-execution-...). If you're on a "sad path", though, they will cost more.
What is pretty sure is that since compilers learned to put the "sad" path in .cold section, the code size issue has become a 100% non-issue, the "sad" path won't bloat the hot, exception-less path ; in my experience, exceptions are in cases that matter a negative-cost abstraction.
struct Error* create_error(const char *msg) {
struct Error *e = malloc(sizeof(struct Error));
e->msg = strdup(msg);
return e;
}
It’s also disingenuous to pretend there isn’t some downside to not using the abstraction. Obviously you need to evaluate the tradeoffs.
High level code itself is a sort of abstraction. We could write raw assembly all the time to remove that abstraction and associated costs, but clearly that’s not very productive.
Not specializing at all would make your code awful slow (as you would need some quite complicated and costly treatment of generics at runtime).
"Specializing by hand" is not realistically doable besides toy programs.
And not having generics in the language at all will result in "solutions" like in Go…
I see no way around (semi-)automatic specialization done by the compiler.
I do not think wrapped types are so advertised.
That's an extremely ignorant and incorrect take on Rust, and your phrasing makes me believe that you're doing this intentionally.
There's a reason a lot of the complaints about C++ mention bloat or the difficulty of practically choosing a safe subset (you could use a subset, but you're very likely dependent on coworkers, existing codebases and library authors which may not share your subset). A lot of people added 'zero cost' stuff, and all of that has a cost.
For example, lets say Rust's newtype pattern worked perfectly everywhere, and all of the author's examples run fine as u8 with no runtime cost. There would likely still be a small cognitive cost to learn this, a small cost to unwrap the types (for other programmers reading the code), and a tiny cost in compile time. Typedefs are worth it, and it's all very reasonable to pay this!
But there's still a cost, and when people never believe there's a cost a language ends up like C++.
For example, C++'s template language as originally implemented was technically 'zero cost', but C++ programmers paid for it a lot for a long time, in inscrutable error messages and slow compile times (this was fixed to a large degree with modern implementations and standards).
In contrast, the benefits of Zero Cost Abstraction are quite subtle. "Why would I want that? Ever heard of Moore's law? Caring about perf is so 1990s!" goes the immediate thinking. If you never have to write high-perf code, that reasoning is even correct! Of course, there are still many places where performance does matter, and being able to use high level language features on the very innermost loops, the places that halve or quarter the throughput of your $6000 graphics card(s) if you carelessly toss in even a single call of overhead, is quite something to those in a position to take advantage.
Since the caveats of ZCA are obvious and the benefits are subtle, I think it's perfectly fair to use the term as a way to draw attention to the latter.
> You still pay, often in something that you didn't bother to measure, which (in C++) is usually compile time or programmer productivity or programmer cognitive cost or compiler complexity.
Obviously everything is about tradeoffs. If an abstraction is making everything worse for you, then don’t use it. I don’t think it’s fair to try to list every possible downside of an abstraction, as there are obviously also downsides to not using abstractions otherwise we wouldn’t have these options.
Zero cost refers to the compiled code and runtime performance.
Now, I did say this option was worth it. And there are cases of being too conservative (Golang?). But when designing and programming, one should look at the tradeoff. Abstraction is not always worth its costs [EDIT: and sometimes you can have less costs by a better abstraction, but being aware of the costs helps to think about the better abstraction].
type Tiny = u8;
The compiler knows a "Tiny" is just a u8 anyway and exactly the same code is produced.
The wrapper type is a distinct type, which is why you'd want one because it can have different properties from whatever it's wrapping.
Using/typedef declarations in c++ only introduce a new name, not a new type.
Why wouldn't I just use C? Because of improved programmer productivity and readability of the code.
The reason C++ exists as a language today (and why Rust is it's direct competitor) is because of zero-cost abstractions. Because in many situations programmer productivity and compiler complexity is second to performance.
You're basically just arguing that C++ shouldn't be C++ (and Rust shouldn't be Rust). We already have plenty of languages that provide high-level "costly" abstractions. The reason we need C/C++/Rust is for that zero-cost aspect.
Historically, there were much fewer choices for languages and arguably C++ has been used for building applications that didn't need zero-cost features. But now we have plenty of alternatives and C++ still exists for that valuable niche that it provides. This is the reason Rust was created -- to provide this level of control without the baggage of C++.
This is worth bookmarking.
It's a bit strange to say that before the u8 specialization this was not a problem and it's suddenly a problem now.
The intention of the newtype pattern is to specifically create a new type without the behaviour of the wrapped type, so if there's a special case just for u8, I would expect it not to be on the newtype.
One version initializes the memory and the other one doesn't. There's a lot of subtle ways to cause that in different languages.
If you actually use the memory, both cases work out the same. There are too many languages where you can easily make the mistake of reading uninitialized memory, and that can't happen here, if you ask to sum() the vector you'll get a zero answer in both cases... and both programs will be similarly slow.
u8 turns into "Hey, Linux kernel, zero these pages if I ever read them" (and then never reading them) whereas the opaque type turns into memset() zeroing all the pages.
Not doing any work is in fact a million times faster but your real program would have needed to do work, otherwise why bother having the vector? Whereupon the benefit disappears.
Where possible design your benchmarks to really do the thing you think you're measuring. If what you're measuring is nothing then be sceptical about supposed "performance" measured for that, since it's nothing, you're probably exploring the same space as the people who wanted to find out how much the human soul weighs (trick question, there is no such thing, but they put a lot of effort into trying to measure it anyway).
it might be optimized to a memset, but it's the clone codepath, as opposed to the u8 specialization codepath as discussed in the article
But the original commenter is talking about how the benchmark isn't useful because it doesn't touch memory, but you get similar results even if you do touch memory.
It's just an example to show that zero cost abstractions are actually not zero cost at all.
The language would have you believe the abstraction is zero cost. If you were to really believe it, you would never think about whether you need to allocate a vector of u8 or your custom byte type. They should be one and the same. That's the point of the promise of zero cost abstractions.
By the way, pre-allocating a lot of virtual memory upfront is not unheard of.
In this situation, to avoid paying the cost of the abstraction, you would have to stop and think "I can't allocate _my_ byte type! I must allocate u8, then cast the result to a vector of my custom byte type. Maybe the compiler will not like the cast so I have to create an "unsafe" block and do some pointer casting? (I don't know if that's what you would need to do in rust, or if it would have been something else).
No, this is premature optimization. Rather, you would write the code in the most obvious way, and then profile it to figure out which optimizations are worth doing. At that point you can comment your code explaining why it looks all wonky :)
It's doing different things: In the first case it's not doing anything and it will request memory dynamically. In the second case it's zeroing 16gb of RAM.
The explanation linked at the end explains it better.
It’s basically competing abstractions. Letting the kernel reserve pages and only zeroing them when used will hide the cost and amortize it across access.
It’s worth knowing about but it’s also an artificial problem revealed by benchmarks.