34

I came across this term when exploring Rust.

I saw different kinds of explanations regarding this and still don't quite get the ideas.

In The Embedded Rust Book, it said

Type states are also an excellent example of Zero Cost Abstractions

  • the ability to move certain behaviors to compile time execution or analysis.

These type states contain no actual data, and are instead used as markers.

Since they contain no data, they have no actual representation in memory at runtime:

Does it mean the runtime is faster because there is no memory in runtime?

Appreciate it if anyone can explain it in an easy to understand way.

1
  • 12
    Zero Cost Abstractions don't make anything faster, rather they (hopefully) make the runtime exactly the same as if you wrote the lower level unabstracted version (usually at the expense of compile time). The idea is generally adding a convenience abstraction layer, but without incurring any runtime penalties. Sep 14, 2021 at 13:11

4 Answers 4

69

Zero Cost Abstractions means adding higher-level programming concepts, like generics, collections and so on do not come with a run-time cost, only compile time cost (the code will be slower to compile). Any operation on zero-cost abstractions is as fast as you would write out matching functionality by hand using lower-level programming concepts like for loops, counters, ifs and using raw pointers.

Or another way to view this is that using zero-cost abstraction tools, functions, templates, classes and such come with "zero cost" for the performance of your code.

16

Zero cost abstractions are ones that bear no runtime costs in execution speed or memory usage.

By contrast, virtual methods are a good example of a costly abstraction: in many OO languages the type of the method's caller is determined at runtime which requires maintaining a lookup table (runtime memory usage) and then actually performing the lookup (runtime overhead per method call, likely at least an extra pointer dereference) with the runtime type to determine which version of the method to call. Another good example would be garbage collection: in return for being able to not worry about the details of memory allocation you pay with GC pauses.

Rust though mostly tries to have zero cost abstractions: ones that let you have your cake and eat it too. Ones that compiler can safely and correctly convert to forms that bear no extra indirection/memory usage. In fact, the only thing that I'm aware of (somebody more knowledgeable correct me if I'm wrong) that you really pay for at runtime in Rust is bounds checking and dyn (see the bit about virtual methods above).

15
  • 4
    Rust has traits which provide runtime virtual function behaviour, for one (see e.g. this)
    – rubenvb
    Sep 14, 2021 at 13:52
  • 2
    Well, it seems Rust is "smart" in the sense that it will "devirtualize" trait usage when possible (at least that's how I read this blog post with my C++ glasses). I think it comes down to Rust providing unified syntax for static and dynamic dispatching.
    – rubenvb
    Sep 15, 2021 at 7:07
  • 4
    Traits may be dispatched at runtime or compile time. If you have a struct Foo: Bar and a variable let foo = Foo{} then calling a method from Bar will be dispatched at compile-time (zero-cost). However if your variable is a Bar reference: let bar = &foo as &Bar, then dispatching will be done at runtime using the same kind of lookup table as most OO languages (unless the optimizer is able to go back to the Foo type, which some OO languages can do too).
    – Jmb
    Sep 15, 2021 at 7:39
  • 1
    @Jmb Rust only uses dynamic dyspatch when you use dyn, as in &dyn Trait. Otherwise it always uses compile-time dispatch, even for references.
    – Dev
    May 27, 2022 at 17:44
  • 1
    @Dev if you look at the assembly for this playground, you will notice that the call to bar.bar() is actually inlined without using the &dyn Bar vtable because the compiler was smart enough to recognize that bar always refers to a Foo instance even though it's a trait object.
    – Jmb
    May 30, 2022 at 6:38
6

The concept of zero cost abstractions originally came from the functional world. However, the terminology comes from C++. According to Bjarne Stroustrup,

In general, 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.

This quote along with most answers fail to deliver the idea in its entirety because the context in which these were said isn't explicitly stated.

If there was only one programming language in the world: be it Rust or C++, zero-cost abstractions would be indistinguishable from most other compiler optimizations. The implication here is that there are countless other languages that let you do the same things as Rust or C++, but with a nonzero and often runtime-specific cost.

4
  • Do you have a reference supporting that this originates from functional programming?
    – mkrieger1
    Aug 28, 2022 at 13:15
  • 2
    @mkrieger1 no need for references, it's clear that functional programming, which is a style of programming that emphasizes the use of pure functions, immutable data, and declarative constructs to create programs that are easy to reason about and maintain, are the perfect example Zero-cost abstraction. Dec 12, 2022 at 23:55
  • 2
    @JulianoSilva depends on what you are comparing the abstraction to. Immutable data means that you will do a copy-on-write instead of inplace operation (hence why games and matrix computing is expensive in FP). It also requires GC (or some other automated memory management) to clean up unused data (although technically, Haskell's gc "saves used data" instead of "collecting garbage")
    – gust
    Mar 10 at 18:02
  • 1
    @gust you are correct, let me fix my comment: zero-cost abstraction is not particular from functional paradigms, which often requires memoizing data in order to be eficient, as opposite: it is how entities with data and behavior together are used in higher levels implementation that makes zero-cost abstractions useful, such as OOP, Metaprogramming and Generics Programming Mar 13 at 0:20
-1

Zero-cost abstraction refers to the concept of using abstractions in code that are both expressive and efficient, without incurring any additional runtime overhead. This concept is particularly associated with the C++ programming language, which was one of the first languages to pioneer metaprogramming, generic programming, and object-oriented programming, all of which can be used to achieve zero-cost abstractions.

On the other hand we have functional programming, while it can also make use of abstractions, is not typically associated with zero-cost abstraction, as its emphasis on immutability can require additional memory allocation and copy-on-write operations (following gust comment), which can impact performance in certain use cases, such as real-time game programming or matrix computing.

7
  • Please delete you answer chatGPT answers are not allowed
    – Ahmed Sbai
    Mar 13 at 1:00
  • @AhmedSbai what makes you think of that? I crafted this based on the previous knowledge in this post Mar 13 at 1:23
  • Bro it is the same answer that chatGPT gives
    – Ahmed Sbai
    Mar 13 at 1:24
  • it may be identical for sure, it's because I use it a lot and my language may be mimicking it, but this doesn't necessarily mean that I literally copied, it's based on my knowledge, the concept of difference of in place operation vs copy-on-write was good to make it known in a good answer for this question. Mar 13 at 1:31
  • AI detector thinks this is a real text, not AI-generated. But, you say "I use it a lot and my language may be mimicking it" and here's a friendly tip: you should not do that. It will only cause you issues. And this is not a good style to copy anyway. If you imitate GPT's style you will likely have problems in the future.
    – Eric Aya
    Mar 13 at 9:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.