10 ms·

Zero Cost Abstractions

366 points by Bognar 10y ago

etrain 10y ago
This is pretty awesome. One key bit of information that the compiler has is that the coefficients are a constant array of length 12, which makes the loop unrolling possible and also means that the register magic is in play - it's seriously awesome that the compiler does this. That said, I'd expect something similar to happen with a well-written C program. Would equivalent abstractions in C++1{1,4,7} be "costly"?
- Manishearth 10y ago
  All of the optimizations were done by llvm, so nothing stopping this from working in C++ with closures or C with functions annotated for inlining. With C the lack of generics means that writing composable iterators is hard, though.
  - adrianN 10y ago
    At least it's hard to write composable iterators that don't circumvent the type system completely.
- Veedrac 10y ago
  Since ranges are not yet standard, the "equivalent" abstractions would look to be std::algorithms, but those are not zero-cost as they are not iterator adaptors, but consumers. This is extremely inefficient. However, Boost offers iterator adapters, which although weaker than true iterator adapters (which C++ calls ranges), those will suffice in this case.
  - sqeaky 10y ago
    As for std::algorithms not being zero-cost. I have seen cases were std::foreach was noticably faster or much slower. I have seen it in benchmarks and it seems largely to be a quality of implementation issue. Good implementations can cheat and use knowledge my code shouldn't have about parts of the underlying system and bad ones do extra useless crap. Benchmarking and profiling seem to be the only real way to gain confidence in your results reliably.
forrestthewoods 10y ago
I'm not familiar with some of these operations. I don't know what a Rust "slice" is. Or what "Zip" does. Could someone show me the most straight forward equivalent in vanilla C? I assume there is no direct equivalent as temporary storage will be needed. But that's fine and would further serve the purpose of explaining why Rust is cool. Thanks.
- steveklabnik 10y ago
  A slice is a pointer + a length. Zip takes two iterators and gives an iterator that returns pairs of elements from each of them. For an imperative translation see https://www.reddit.com/r/programming/comments/5fpghn/zerocost_abstractions/dam19ax/?st=iw5lpml6&sh=4c17bb07 https://www.reddit.com/r/programming/comments/5fpghn/zerocos... Doing an exact translation to C is hard. The C that does the same thing, or C that demonstrates these abstractions that are boiling away?
  - kutkloon7 10y ago
    The thing with C is also that it's hard to do metaprogramming. Example, I have some finite element code that ideally, I would like to run for an arbitrary dimension. In C, this is practically impossible to code efficiently, while in C++ (and I suppose in Rust) I belive this can be done with templates (though I have not too much experience with this).
- thenewwazoo 10y ago
  Uh, the C equivalent might be something like uint32_t *buffer = ...; uint64_t coefficients[12] = {...}; uint16_t qlp_shift = ...; uint32_t *bufp = &buffer[...]; uint64_t sum; for (size_t i = 0; i < 12; i++) sum += coefficients[i] * bufp[i-12]; uint64_t prediction = sum >> qlp_shift; *bufp += (uint32_t)prediction; Edit: this is incorrect
  - kutkloon7 10y ago
    Which -in my opinion- is a lot clearer than the Rust code in the article.
kutkloon7 10y ago
I like the idea of zero-cost abstractions very much. I think that eventually, we will move to functionally proven code - which is, of course, also a zero-cost abstraction, since functional verification is normally done at compile-time. The snippet presented is completely unreadable to me though, and I think that in general, Rust is too hard to understand (and has some syntax which seems quite arbitrary).
- Manishearth 10y ago
  > The snippet presented is completely unreadable to me though I suspect this is just a matter of being used to things. For me, the corresponding imperative code is harder to disentangle. Whereas, knowing what zip/map/sum do, both the intent and the behavior of the code is abundantly clear to me.
  - khedoros1 10y ago
    I suspect that's right. I can describe what zip, map, and sum do, but I don't have an intuitive feel for what each one does or the patterns that they're usually used in because I haven't ever really done any functional programming. I've seen side-by-side imperative and functional comparisons, written in Rust. Reading through the functional version of the code always gave me a very rough idea of what was happening, and reading the imperative version was always immediately clear to me. I think that it's almost certainly a function of familiarity.
    - yazaddaruvala 10y ago
      Have you ever learned a new spoken language? At first, the learner understands by translating to primary language. Only later, with repeated experience does the learner stop doing so and become "fluent". Its very similar when learning the functional style of programming. Even today having most of this functional style be intuitive, when I see a complex iterator chain (usually only when constructing a `Map`), I need to mentally unfold it into a loop.
      - 10y ago
dfrey 10y ago
Why no constant for the value 12? :(
mpweiher 10y ago
>The only proper way to reason about the cost of these >abstractions is to inspect the generated machine code. To me, that's a big problem with a lot of these Heldencompilers. They may generate really optimal machine code. Then again, they may not, and the difference between optimizations working well and not working well in runtime efficiency is so great (I've measured 1000x for Swift) that they might as well be completely different languages. For reference, 1000x means that 1 second turns into 16 minutes, and having that type of difference in something that's completely opaque is not a useful performance tool for me, because predictability is at least half the game in performance. So something like Knuth's transformation systems that turn optimization into a dialogue between programmer, compiler and instrumentation seems like a better idea[1]. [1] https://www.cs.sjsu.edu/~mak/CS185C/KnuthStructuredProgrammingGoTo.pdf https://www.cs.sjsu.edu/~mak/CS185C/KnuthStructuredProgrammi...
- colordrops 10y ago
  Heldencompiler? Google is not turning up much.
  - stouset 10y ago
    Might be a typo of heisencompiler?
  - ben0x539 10y ago
    Heroic compiler?
  - hunterwerlla 10y ago
    Probably supposed to be Heisencompiler as a play on Heisenberg's uncertainty principal.
    - stcredzero 10y ago
      Is messing up branch prediction "Breaking Bad?"
      - 10y ago
a_c 10y ago
His snippet is very close to what one would do in scala. And I suspect it is very similar to other functional languages. I have always wanted to have a comparison between the generated code of different functional languages for a similar program. One day..
- k__ 10y ago
  Yes, Rust feels a bit like a mix of Scala and C. Especially match :)
  - hyperpape 10y ago
    I think ML is actually the strongest influence. Of course, Scala and Haskell both have ML influence, so there are things that look familiar from all three languages.
rawnlq 10y ago
> But in any case, a missed opportunity for vectorisation is just that: a missed opportunity. It is not abstraction overhead. Does the same code implemented in C manage to vectorize? If so isn't that an actual "cost" in comparison?
_lce0 10y ago
OT and not sure if you're the author.. but what a beautifully designed website!
- elmerland 10y ago
  That's exactly what I thought! One of best designed blogs I've ever seen. It has exactly what you need and nothing more. Looking at the HTML code its also incredibly simple and elegant! What a pleasure to read
- aban 10y ago
  Not the author (Ruud), but I've been in touch with him. The source code for his website is free software [0], so feel free to have a look or adopt it for yourself. Ruud uses a small static site generator he's written in Haskell, and in his own words it “includes a tiny templating engine, an html and css minifier, and an aggressive font subsetter.” [0]: https://github.com/ruuda/blog https://github.com/ruuda/blog
- sambe 10y ago
  Came here to say exactly this. It's rare for me to be so motivated by design to comment on it - I wanted to read more posts just because it was so beautiful to look at! Arguably missing a link the homepage/post overview at the top, perhaps I just expect this too much from convention.
- Ruud-v-A 10y ago
  Thank you!
fche 10y ago
Would be curious to see a good C++ translation of that, which a modern compiler can unroll/inline about as well.
- kibwen 10y ago
  Given that the Rust compiler uses LLVM as its backend, and given that Rust's closure implementation was inspired by C++'s (though with extra compile-time machinery to make them memory-safe), I'm certain that C++ is just as capable of boiling these abstractions away as Rust is. :) (But admittedly I don't know if iterator adaptors like map and zip are in C++'s stdlib.)
  - Karliss 10y ago
    Not part of stdlib, but it can be done using Boost. https://godbolt.org/g/QBN5zP https://godbolt.org/g/QBN5zP
sjolsen 10y ago
How difficult is it to add a "zero cost abstraction" like the ones used here? For example, what would it take to make this compile: for window in buffer.sliding_window(coefficients.len()) { let prediction = coefficients.iter() .zip(window) .map(|(&c, &s)| c * s as i64) .sum::<i64>() >> qlp_shift; let delta = buffer[i]; buffer[i] = prediction as i32 + delta; } with sliding_window returning an iterator over slices of the buffer?
- jstimpfle 10y ago
  "Zero cost abstraction" to me means a completely "static" abstraction, i.e. there are no runtime mechanisms necessary to implement the abstraction. Your sliding window is just a series of windows, so there is no reason why it couldn't be compiled in the "most" efficient way. In fact it probably does, just try it out by implementing the sliding_window as an iterable. However there's always this problem with cleverness: It gets harder and harder to read and maintain. Also http://wiki.c2.com/?SufficientlySmartCompiler http://wiki.c2.com/?SufficientlySmartCompiler
- Veedrac 10y ago
  There is a `windows` iterator. https://doc.rust-lang.org/std/primitive.slice.html#method.windows https://doc.rust-lang.org/std/primitive.slice.html#method.wi... However, your code would not work as-is, since the window borrows the buffer, so `buffer[i]` cannot be written to. Further, there is no `windows_mut` to let you write to the end of the window, because that would let you get multiple mutable references to a given element.
pron 10y ago
> Fortunately these structures are not allocated on the heap, as they would likely be in a language like Java or Python. At least in principle, escape analysis would be used to allocate them on the stack. In HotSpot, simple iterators are commonly allocated on the stack (and then optimized further). When you have a JIT (which means you can afford one), general abstractions become zero-cost based on their use-site. The upside is that you get a few, general and powerful abstractions that are then completely optimized based on how they're used. The downside is that it is not guaranteed, and a JIT requires more RAM and power (and in practice usually a warmup period, although that can be solved).
junke 10y ago
I don't know anything about FLAC, but is the implicit modular arithmetic the expected behavior here? What if a product or a sum overflows?
- jstimpfle 10y ago
  My assumption would be that the assumption was that 64-bit arithmetic is somehow more time efficient and 32-bit is more memory efficient while still large enough to hold the results.
- nkurz 10y ago
  I think the shift at the end (>> qlp_shift) takes care of this. The multiplication and sum are done in 64-bit, and then the sum is presumably shifted enough so as to fit in 32-bits.
  - junke 10y ago
    Thanks. Isn't it possible to give a "coefficients" vector with large enough values so that computations with 64 bits would overflow too? I don't doubt the code works in practice, because the range of values are reasonable. However this is not explicit, just looking at the code. I'd prefer if the actual domains were being made obvious. Right now, 12, 32 and 64 feel like magic numbers in the code.
- Ruud-v-A 10y ago
  Good question! It turns out that 64 bit arithmetic does not overflow (I explain this in a comment in the source code [1]) up to the shift. The shift amount must then be large enough to fit the result in 32 (or actually, 24 or usually 16) bits. For a valid FLAC file this will be the case. For an invalid FLAC file it might truncate, but an invalid file cannot be decoded properly anyway. The shift amount is a 5 bit signed number [2], so it is never possible to shift by the integer width or more. [1]: https://github.com/ruuda/claxon/blob/91b6af9/src/subframe.rs#L476-L481 https://github.com/ruuda/claxon/blob/91b6af9/src/subframe.rs... [2]: https://github.com/ruuda/claxon/blob/91b6af9/src/subframe.rs#L576-L579 https://github.com/ruuda/claxon/blob/91b6af9/src/subframe.rs...

366 points by Bognar 10y ago

This is pretty awesome. One key bit of information that the compiler has is that the coefficients are a constant array of length 12, which makes the loop unrolling possible and also means that the register magic is in play - it's seriously awesome that the compiler does this. That said, I'd expect something similar to happen with a well-written C program. Would equivalent abstractions in C++1{1,4,7} be "costly"?

Manishearth 10y ago
All of the optimizations were done by llvm, so nothing stopping this from working in C++ with closures or C with functions annotated for inlining. With C the lack of generics means that writing composable iterators is hard, though.
- adrianN 10y ago
  At least it's hard to write composable iterators that don't circumvent the type system completely.
Veedrac 10y ago
Since ranges are not yet standard, the "equivalent" abstractions would look to be std::algorithms, but those are not zero-cost as they are not iterator adaptors, but consumers. This is extremely inefficient. However, Boost offers iterator adapters, which although weaker than true iterator adapters (which C++ calls ranges), those will suffice in this case.
- sqeaky 10y ago
  As for std::algorithms not being zero-cost. I have seen cases were std::foreach was noticably faster or much slower. I have seen it in benchmarks and it seems largely to be a quality of implementation issue. Good implementations can cheat and use knowledge my code shouldn't have about parts of the underlying system and bad ones do extra useless crap. Benchmarking and profiling seem to be the only real way to gain confidence in your results reliably.

forrestthewoods 10y ago

I'm not familiar with some of these operations. I don't know what a Rust "slice" is. Or what "Zip" does. Could someone show me the most straight forward equivalent in vanilla C? I assume there is no direct equivalent as temporary storage will be needed. But that's fine and would further serve the purpose of explaining why Rust is cool. Thanks.

steveklabnik 10y ago
A slice is a pointer + a length. Zip takes two iterators and gives an iterator that returns pairs of elements from each of them. For an imperative translation see https://www.reddit.com/r/programming/comments/5fpghn/zerocost_abstractions/dam19ax/?st=iw5lpml6&sh=4c17bb07 https://www.reddit.com/r/programming/comments/5fpghn/zerocos... Doing an exact translation to C is hard. The C that does the same thing, or C that demonstrates these abstractions that are boiling away?
- kutkloon7 10y ago
  The thing with C is also that it's hard to do metaprogramming. Example, I have some finite element code that ideally, I would like to run for an arbitrary dimension. In C, this is practically impossible to code efficiently, while in C++ (and I suppose in Rust) I belive this can be done with templates (though I have not too much experience with this).
thenewwazoo 10y ago
Uh, the C equivalent might be something like uint32_t *buffer = ...; uint64_t coefficients[12] = {...}; uint16_t qlp_shift = ...; uint32_t *bufp = &buffer[...]; uint64_t sum; for (size_t i = 0; i < 12; i++) sum += coefficients[i] * bufp[i-12]; uint64_t prediction = sum >> qlp_shift; *bufp += (uint32_t)prediction; Edit: this is incorrect
- kutkloon7 10y ago
  Which -in my opinion- is a lot clearer than the Rust code in the article.

kutkloon7 10y ago

I like the idea of zero-cost abstractions very much. I think that eventually, we will move to functionally proven code - which is, of course, also a zero-cost abstraction, since functional verification is normally done at compile-time. The snippet presented is completely unreadable to me though, and I think that in general, Rust is too hard to understand (and has some syntax which seems quite arbitrary).

Manishearth 10y ago
> The snippet presented is completely unreadable to me though I suspect this is just a matter of being used to things. For me, the corresponding imperative code is harder to disentangle. Whereas, knowing what zip/map/sum do, both the intent and the behavior of the code is abundantly clear to me.
- khedoros1 10y ago
  I suspect that's right. I can describe what zip, map, and sum do, but I don't have an intuitive feel for what each one does or the patterns that they're usually used in because I haven't ever really done any functional programming. I've seen side-by-side imperative and functional comparisons, written in Rust. Reading through the functional version of the code always gave me a very rough idea of what was happening, and reading the imperative version was always immediately clear to me. I think that it's almost certainly a function of familiarity.
  - yazaddaruvala 10y ago
    Have you ever learned a new spoken language? At first, the learner understands by translating to primary language. Only later, with repeated experience does the learner stop doing so and become "fluent". Its very similar when learning the functional style of programming. Even today having most of this functional style be intuitive, when I see a complex iterator chain (usually only when constructing a `Map`), I need to mentally unfold it into a loop.
    - 10y ago

dfrey 10y ago

Why no constant for the value 12? :(

mpweiher 10y ago

>The only proper way to reason about the cost of these >abstractions is to inspect the generated machine code. To me, that's a big problem with a lot of these Heldencompilers. They may generate really optimal machine code. Then again, they may not, and the difference between optimizations working well and not working well in runtime efficiency is so great (I've measured 1000x for Swift) that they might as well be completely different languages. For reference, 1000x means that 1 second turns into 16 minutes, and having that type of difference in something that's completely opaque is not a useful performance tool for me, because predictability is at least half the game in performance. So something like Knuth's transformation systems that turn optimization into a dialogue between programmer, compiler and instrumentation seems like a better idea[1]. [1] https://www.cs.sjsu.edu/~mak/CS185C/KnuthStructuredProgrammingGoTo.pdf https://www.cs.sjsu.edu/~mak/CS185C/KnuthStructuredProgrammi...

colordrops 10y ago
Heldencompiler? Google is not turning up much.
- stouset 10y ago
  Might be a typo of heisencompiler?
- ben0x539 10y ago
  Heroic compiler?
- hunterwerlla 10y ago
  Probably supposed to be Heisencompiler as a play on Heisenberg's uncertainty principal.
  - stcredzero 10y ago
    Is messing up branch prediction "Breaking Bad?"
    - 10y ago

a_c 10y ago

His snippet is very close to what one would do in scala. And I suspect it is very similar to other functional languages. I have always wanted to have a comparison between the generated code of different functional languages for a similar program. One day..

k__ 10y ago
Yes, Rust feels a bit like a mix of Scala and C. Especially match :)
- hyperpape 10y ago
  I think ML is actually the strongest influence. Of course, Scala and Haskell both have ML influence, so there are things that look familiar from all three languages.

rawnlq 10y ago

> But in any case, a missed opportunity for vectorisation is just that: a missed opportunity. It is not abstraction overhead. Does the same code implemented in C manage to vectorize? If so isn't that an actual "cost" in comparison?

_lce0 10y ago

OT and not sure if you're the author.. but what a beautifully designed website!

elmerland 10y ago
That's exactly what I thought! One of best designed blogs I've ever seen. It has exactly what you need and nothing more. Looking at the HTML code its also incredibly simple and elegant! What a pleasure to read
aban 10y ago
Not the author (Ruud), but I've been in touch with him. The source code for his website is free software [0], so feel free to have a look or adopt it for yourself. Ruud uses a small static site generator he's written in Haskell, and in his own words it “includes a tiny templating engine, an html and css minifier, and an aggressive font subsetter.” [0]: https://github.com/ruuda/blog https://github.com/ruuda/blog
sambe 10y ago
Came here to say exactly this. It's rare for me to be so motivated by design to comment on it - I wanted to read more posts just because it was so beautiful to look at! Arguably missing a link the homepage/post overview at the top, perhaps I just expect this too much from convention.
Ruud-v-A 10y ago
Thank you!

fche 10y ago

Would be curious to see a good C++ translation of that, which a modern compiler can unroll/inline about as well.

kibwen 10y ago
Given that the Rust compiler uses LLVM as its backend, and given that Rust's closure implementation was inspired by C++'s (though with extra compile-time machinery to make them memory-safe), I'm certain that C++ is just as capable of boiling these abstractions away as Rust is. :) (But admittedly I don't know if iterator adaptors like map and zip are in C++'s stdlib.)
- Karliss 10y ago
  Not part of stdlib, but it can be done using Boost. https://godbolt.org/g/QBN5zP https://godbolt.org/g/QBN5zP

sjolsen 10y ago

How difficult is it to add a "zero cost abstraction" like the ones used here? For example, what would it take to make this compile: for window in buffer.sliding_window(coefficients.len()) { let prediction = coefficients.iter() .zip(window) .map(|(&c, &s)| c * s as i64) .sum::<i64>() >> qlp_shift; let delta = buffer[i]; buffer[i] = prediction as i32 + delta; } with sliding_window returning an iterator over slices of the buffer?

jstimpfle 10y ago
"Zero cost abstraction" to me means a completely "static" abstraction, i.e. there are no runtime mechanisms necessary to implement the abstraction. Your sliding window is just a series of windows, so there is no reason why it couldn't be compiled in the "most" efficient way. In fact it probably does, just try it out by implementing the sliding_window as an iterable. However there's always this problem with cleverness: It gets harder and harder to read and maintain. Also http://wiki.c2.com/?SufficientlySmartCompiler http://wiki.c2.com/?SufficientlySmartCompiler
Veedrac 10y ago
There is a `windows` iterator. https://doc.rust-lang.org/std/primitive.slice.html#method.windows https://doc.rust-lang.org/std/primitive.slice.html#method.wi... However, your code would not work as-is, since the window borrows the buffer, so `buffer[i]` cannot be written to. Further, there is no `windows_mut` to let you write to the end of the window, because that would let you get multiple mutable references to a given element.

pron 10y ago

> Fortunately these structures are not allocated on the heap, as they would likely be in a language like Java or Python. At least in principle, escape analysis would be used to allocate them on the stack. In HotSpot, simple iterators are commonly allocated on the stack (and then optimized further). When you have a JIT (which means you can afford one), general abstractions become zero-cost based on their use-site. The upside is that you get a few, general and powerful abstractions that are then completely optimized based on how they're used. The downside is that it is not guaranteed, and a JIT requires more RAM and power (and in practice usually a warmup period, although that can be solved).

junke 10y ago

I don't know anything about FLAC, but is the implicit modular arithmetic the expected behavior here? What if a product or a sum overflows?

jstimpfle 10y ago
My assumption would be that the assumption was that 64-bit arithmetic is somehow more time efficient and 32-bit is more memory efficient while still large enough to hold the results.
nkurz 10y ago
I think the shift at the end (>> qlp_shift) takes care of this. The multiplication and sum are done in 64-bit, and then the sum is presumably shifted enough so as to fit in 32-bits.
- junke 10y ago
  Thanks. Isn't it possible to give a "coefficients" vector with large enough values so that computations with 64 bits would overflow too? I don't doubt the code works in practice, because the range of values are reasonable. However this is not explicit, just looking at the code. I'd prefer if the actual domains were being made obvious. Right now, 12, 32 and 64 feel like magic numbers in the code.
Ruud-v-A 10y ago
Good question! It turns out that 64 bit arithmetic does not overflow (I explain this in a comment in the source code [1]) up to the shift. The shift amount must then be large enough to fit the result in 32 (or actually, 24 or usually 16) bits. For a valid FLAC file this will be the case. For an invalid FLAC file it might truncate, but an invalid file cannot be decoded properly anyway. The shift amount is a 5 bit signed number [2], so it is never possible to shift by the integer width or more. [1]: https://github.com/ruuda/claxon/blob/91b6af9/src/subframe.rs#L476-L481 https://github.com/ruuda/claxon/blob/91b6af9/src/subframe.rs... [2]: https://github.com/ruuda/claxon/blob/91b6af9/src/subframe.rs#L576-L579 https://github.com/ruuda/claxon/blob/91b6af9/src/subframe.rs...