5 ms·

> And zero runtime overhead. Please show me an implementation of binary decision diagrams [1] (ideally multi-threaded) where Rust has zero runtime overhead. R

> And zero runtime overhead. Please show me an implementation of binary decision diagrams [1] (ideally multi-threaded) where Rust has zero runtime overhead. Rust has zero runtime overhead only in some cases. [1] https://en.wikipedia.org/wiki/Binary_decision_diagram https://en.wikipedia.org/wiki/Binary_decision_diagram

naasking 9y ago
I made a claim of zero runtime overhead after directly quoting the context of automatic memory management. So are you suggesting that claim in such a context is false, citing BDDs as some example, or are you taking my claim to be more broad than the context warrants, and so are arguing a strawman?
- rbehrends 9y ago
  > I made a claim of zero runtime overhead after directly quoting the context of automatic memory management. And that's what I was referring to. BDDs inherently require Rc<T>/Arc<T> (as long as you want to be memory-safe, at least) and therefore incur significant overhead (reference counting is one of the most expensive forms of automatic memory management). I use BDDs as an example, because there's no way to work around the structural sharing, as it's a requirement for an implementation. In addition, aiming for zero-cost abstractions is hardly a Rust-only thing. That's more of a Java problem because it only has polymorphic methods and no value types. Outside functional languages, lack of zero-cost abstractions is not a particularly common issue.
  - naasking 9y ago
    Even if your claim is correct, the existence of some programs that cannot be expressed with memory-safe zero overhead abstractions still doesn't entail your original claim. As you just said, you can use Rust's unsafe escape hatch to preserve your desired performance where it's critical and you haven't lost anything from C/C++, but you can still enjoy the safety benefits where unsafety is not needed. And BDDs expose a safe API behind which you can hide the unsafety, so only a fragment of your system would dependent on unsafe Rust. So we come full circle to your claim that Rust is not "at all attractive", despite being able to express programs more compactly, more elegantly, and more safely than in C/C++, without losing the performance. So I still don't see the case for this claim. > Outside functional languages, lack of zero-cost abstractions is not a particularly common issue. Pretty much only Ada and C++ can provide the zero cost abstractions, and they do so only with heavy syntactic and semantic costs (templates for C++, packages and wordy instantiation for Ada). The Rust language does this as part of polymorphic elaboration, which is a natural and compositional language feature, not some ad-hoc secondary language or restricted module system. I'm frankly finding it hard to believe you think there are serious alternatives. Certainly MLTon if you want the same specialization done, but you then have the unavoidable GC cost, so you're still back to non-zero runtime overhead.
    - rbehrends 9y ago
      > Even if your claim is correct, the existence of some programs that cannot be expressed with memory-safe zero overhead abstractions still doesn't entail your original claim. As you just said, you can use Rust's unsafe escape hatch to preserve your desired performance where it's critical and you haven't lost anything from C/C++, but you can still enjoy the safety benefits where unsafety is not needed. I'm not comparing to C/C++. I'm comparing to other memory-safe languages. The more general problem is that Rust cannot offer zero-cost abstractions for shared ownership as a result of how it is designed. This is the really killer issue. It's a problem for pretty much any persistent data structure, for example. > And BDDs expose a safe API behind which you can hide the unsafety, so only a fragment of your system would dependent on unsafe Rust. The unsafe approach would be to do use an array representation, use indices instead of pointers, and roll your own garbage collector. Or manually remove unnecessary reference count updates whenever you can prove that they are unnecessary. Both of which cannot be easily hidden behind a safe zero-cost API. > Pretty much only Ada and C++ can provide the zero cost abstractions, and they do so only with heavy syntactic and semantic costs (templates for C++, packages and wordy instantiation for Ada). The Rust language does this as part of polymorphica elaboration, which is a natural and compositional language feature, not some ad-hoc secondary language or restricted module system. The entire Wirth family of languages qualifies, too. Or Eiffel. Or Fortran. Or Modula-3. As do more recent languages such as Nim and D. Honestly, off the top of my head I can't think of an imperative language with native compilation that doesn't and isn't totally obscure, other than Swift and Go (and even they only some of the time). Note that zero-cost abstractions need to only exist, not that they have to be the only option. Languages can and do provide both expressive constructs that come with overhead and less expressive constructs that are overhead-free. 90:10 rule, premature optimization, and all that. In addition, parametric polymorphism cannot ever have a zero-cost abstraction (or rather, the term has no meaningful definition in this context), because you pay for it either in runtime overhead (shared generics) or code size (specialization). I also wouldn't bring up syntactic and semantic costs; that's throwing stones while sitting inside a glass house. Rust is probably one of the worst offenders in this regard.
      - naasking 9y ago
        > The unsafe approach would be to do use an array representation, use indices instead of pointers, and roll your own garbage collector. Or manually remove unnecessary reference count updates whenever you can prove that they are unnecessary. Both of which cannot be easily hidden behind a safe zero-cost API. There are potentially many unsafe approaches, and possibly even some safe ones. > The entire Wirth family of languages qualifies, too. Or Eiffel [1]. Or Fortran [2]. Or Modula-3 [3]. As do more recent languages such as Nim [4] and D [5]. [1] Doesn't support expressing stack allocation patterns, which are essentially to achieving true zero-cost abstractions. [2] Oh yeah, that'll be easy and maintainable to program. [3] Doesn't support 64-bit Windows. Verbose like Ada. Abstraction is weak compared to Rust. Also doesn't support expressing stack allocation. [4] Nim requires a GC, so not zero cost. It also has surprising runtime semantics. For instance, fields that are are guarded by a clause raise runtime exceptions. These would require different cases which are checked for exhaustiveness statically in Rust. [5] D is not memory safe for non-trivial programs if you're not using the GC. Clearly you and I have a different understanding of zero-cost abstraction. > In addition, parametric polymorphism cannot ever have a zero-cost abstraction (or rather, the term has no meaningful definition in this context), because you pay for it either in runtime overhead (shared generics) or code size (specialization). Code size is not a problem when discussing zero-cost abstractions. Honestly, it just seems like you're grasping for something to nitpick on. > I also wouldn't bring up syntactic and semantic costs; that's throwing stones while sitting inside a glass house. Rust is probably one of the worst offenders in this regard. I have no idea what you're talking about. Once they removed all the special syntax for pointer types years back, Rust is very readable to anyone from a brace-based language tradition.
  - steveklabnik 9y ago
    > BDDs inherently require Rc<T>/Arc<T> "Zero-cost abstraction" means "You couldn't have coded it any better yourself." If the problem requires a certain amount of overhead, than an implementation of that solution is considered zero-cost. Rust can't change the laws of math. Maybe Bjarne should have called it the "Zero additional-cost abstraction" instead; I think it'd clear the principle up a lot.
    - naasking 9y ago
      > If the problem requires a certain amount of overhead, than an implementation of that solution is considered zero-cost. Rust can't change the laws of math. His contention is that languages with GC don't require reference count updates, and so manipulating the BDD graph is much cheaper in these languages since the resource accounting overhead is deferred by some non-deterministic time.
      - steveklabnik 9y ago
        You can still write a GC in Rust and use it for those types.
        rbehrends 9y ago
        First, "you can write a GC" in Rust is not seriously an answer. You can't do it without unsafe code, it would be a lot of effort to just purposely avoid using a GCed language. And the existing efforts to do a GC in Rust are very simple mark-sweep designs that (unsurprisingly) don't even support generational collection. Second, the reason why I use the BDD example (or, more generally, persistent data structures) is that it's the simplest way for online discussions, because (unlike simpler examples), it's not amenable to pseudo-solutions that don't resolve the underlying problem and that you don't have the space and time for. The underlying problem is that Rust doesn't really do safe zero-cost abstractions for multiple ownership, and multiple ownership crops up more often in actual Rust code than people like to admit (global caches and memoization often end up with using cloning). You have to deal with it either through Rc<T>, Arc<T>, or cloning, of which cloning is the most common solution, because you don't have the footprints of shared ownership all over your code.

naasking 9y ago

I made a claim of zero runtime overhead after directly quoting the context of automatic memory management. So are you suggesting that claim in such a context is false, citing BDDs as some example, or are you taking my claim to be more broad than the context warrants, and so are arguing a strawman?

rbehrends 9y ago
> I made a claim of zero runtime overhead after directly quoting the context of automatic memory management. And that's what I was referring to. BDDs inherently require Rc<T>/Arc<T> (as long as you want to be memory-safe, at least) and therefore incur significant overhead (reference counting is one of the most expensive forms of automatic memory management). I use BDDs as an example, because there's no way to work around the structural sharing, as it's a requirement for an implementation. In addition, aiming for zero-cost abstractions is hardly a Rust-only thing. That's more of a Java problem because it only has polymorphic methods and no value types. Outside functional languages, lack of zero-cost abstractions is not a particularly common issue.
- naasking 9y ago
  Even if your claim is correct, the existence of some programs that cannot be expressed with memory-safe zero overhead abstractions still doesn't entail your original claim. As you just said, you can use Rust's unsafe escape hatch to preserve your desired performance where it's critical and you haven't lost anything from C/C++, but you can still enjoy the safety benefits where unsafety is not needed. And BDDs expose a safe API behind which you can hide the unsafety, so only a fragment of your system would dependent on unsafe Rust. So we come full circle to your claim that Rust is not "at all attractive", despite being able to express programs more compactly, more elegantly, and more safely than in C/C++, without losing the performance. So I still don't see the case for this claim. > Outside functional languages, lack of zero-cost abstractions is not a particularly common issue. Pretty much only Ada and C++ can provide the zero cost abstractions, and they do so only with heavy syntactic and semantic costs (templates for C++, packages and wordy instantiation for Ada). The Rust language does this as part of polymorphic elaboration, which is a natural and compositional language feature, not some ad-hoc secondary language or restricted module system. I'm frankly finding it hard to believe you think there are serious alternatives. Certainly MLTon if you want the same specialization done, but you then have the unavoidable GC cost, so you're still back to non-zero runtime overhead.
  - rbehrends 9y ago
    > Even if your claim is correct, the existence of some programs that cannot be expressed with memory-safe zero overhead abstractions still doesn't entail your original claim. As you just said, you can use Rust's unsafe escape hatch to preserve your desired performance where it's critical and you haven't lost anything from C/C++, but you can still enjoy the safety benefits where unsafety is not needed. I'm not comparing to C/C++. I'm comparing to other memory-safe languages. The more general problem is that Rust cannot offer zero-cost abstractions for shared ownership as a result of how it is designed. This is the really killer issue. It's a problem for pretty much any persistent data structure, for example. > And BDDs expose a safe API behind which you can hide the unsafety, so only a fragment of your system would dependent on unsafe Rust. The unsafe approach would be to do use an array representation, use indices instead of pointers, and roll your own garbage collector. Or manually remove unnecessary reference count updates whenever you can prove that they are unnecessary. Both of which cannot be easily hidden behind a safe zero-cost API. > Pretty much only Ada and C++ can provide the zero cost abstractions, and they do so only with heavy syntactic and semantic costs (templates for C++, packages and wordy instantiation for Ada). The Rust language does this as part of polymorphica elaboration, which is a natural and compositional language feature, not some ad-hoc secondary language or restricted module system. The entire Wirth family of languages qualifies, too. Or Eiffel. Or Fortran. Or Modula-3. As do more recent languages such as Nim and D. Honestly, off the top of my head I can't think of an imperative language with native compilation that doesn't and isn't totally obscure, other than Swift and Go (and even they only some of the time). Note that zero-cost abstractions need to only exist, not that they have to be the only option. Languages can and do provide both expressive constructs that come with overhead and less expressive constructs that are overhead-free. 90:10 rule, premature optimization, and all that. In addition, parametric polymorphism cannot ever have a zero-cost abstraction (or rather, the term has no meaningful definition in this context), because you pay for it either in runtime overhead (shared generics) or code size (specialization). I also wouldn't bring up syntactic and semantic costs; that's throwing stones while sitting inside a glass house. Rust is probably one of the worst offenders in this regard.
    - naasking 9y ago
      > The unsafe approach would be to do use an array representation, use indices instead of pointers, and roll your own garbage collector. Or manually remove unnecessary reference count updates whenever you can prove that they are unnecessary. Both of which cannot be easily hidden behind a safe zero-cost API. There are potentially many unsafe approaches, and possibly even some safe ones. > The entire Wirth family of languages qualifies, too. Or Eiffel [1]. Or Fortran [2]. Or Modula-3 [3]. As do more recent languages such as Nim [4] and D [5]. [1] Doesn't support expressing stack allocation patterns, which are essentially to achieving true zero-cost abstractions. [2] Oh yeah, that'll be easy and maintainable to program. [3] Doesn't support 64-bit Windows. Verbose like Ada. Abstraction is weak compared to Rust. Also doesn't support expressing stack allocation. [4] Nim requires a GC, so not zero cost. It also has surprising runtime semantics. For instance, fields that are are guarded by a clause raise runtime exceptions. These would require different cases which are checked for exhaustiveness statically in Rust. [5] D is not memory safe for non-trivial programs if you're not using the GC. Clearly you and I have a different understanding of zero-cost abstraction. > In addition, parametric polymorphism cannot ever have a zero-cost abstraction (or rather, the term has no meaningful definition in this context), because you pay for it either in runtime overhead (shared generics) or code size (specialization). Code size is not a problem when discussing zero-cost abstractions. Honestly, it just seems like you're grasping for something to nitpick on. > I also wouldn't bring up syntactic and semantic costs; that's throwing stones while sitting inside a glass house. Rust is probably one of the worst offenders in this regard. I have no idea what you're talking about. Once they removed all the special syntax for pointer types years back, Rust is very readable to anyone from a brace-based language tradition.
- steveklabnik 9y ago
  > BDDs inherently require Rc<T>/Arc<T> "Zero-cost abstraction" means "You couldn't have coded it any better yourself." If the problem requires a certain amount of overhead, than an implementation of that solution is considered zero-cost. Rust can't change the laws of math. Maybe Bjarne should have called it the "Zero additional-cost abstraction" instead; I think it'd clear the principle up a lot.
  - naasking 9y ago
    > If the problem requires a certain amount of overhead, than an implementation of that solution is considered zero-cost. Rust can't change the laws of math. His contention is that languages with GC don't require reference count updates, and so manipulating the BDD graph is much cheaper in these languages since the resource accounting overhead is deferred by some non-deterministic time.
    - steveklabnik 9y ago
      You can still write a GC in Rust and use it for those types.
      - rbehrends 9y ago
        First, "you can write a GC" in Rust is not seriously an answer. You can't do it without unsafe code, it would be a lot of effort to just purposely avoid using a GCed language. And the existing efforts to do a GC in Rust are very simple mark-sweep designs that (unsurprisingly) don't even support generational collection. Second, the reason why I use the BDD example (or, more generally, persistent data structures) is that it's the simplest way for online discussions, because (unlike simpler examples), it's not amenable to pseudo-solutions that don't resolve the underlying problem and that you don't have the space and time for. The underlying problem is that Rust doesn't really do safe zero-cost abstractions for multiple ownership, and multiple ownership crops up more often in actual Rust code than people like to admit (global caches and memoization often end up with using cloning). You have to deal with it either through Rc<T>, Arc<T>, or cloning, of which cloning is the most common solution, because you don't have the footprints of shared ownership all over your code.