11 ms·

> Borrow checking is incompatible with some useful patterns and optimizations (described later on), and its infectious constraints can have trouble coexisting w

> Borrow checking is incompatible with some useful patterns and optimizations (described later on), and its infectious constraints can have trouble coexisting with non-borrow-checked code. Not that this isn't true, but the rest of the article introduces a system with a superset of those limitations, gradually decreasing over time but never becoming a subset. In fact the pattern described in the article is a common pattern in Rust and I make use of it all the time; the library for making use of it is `slotmap`.

mr_00ff00 3y ago
I would really love a definitive answer on whether the borrow checker and rust’s rules do really limit optimizations and such. It seems like I see this opinion often and every time there are tons of people on both sides who seem sure they are correct. What are the limitations for optimization? Does unsafe rust really force those?
- apendleton 3y ago
  Without directly answering your question, it's worth noting that there are also additional optimizations made available by Rust that are not easily accessible in C/C++ (mostly around stronger guarantees the Rust compiler is able to make about aliasing).
- steveklabnik 3y ago
  The question is far too broad, and contextual. You're never going to get an answer to that question. Sometimes, the rules add more optimization potential. (like how restrict technically exists in C but is on every (okay almost every) reference in Rust) Sometimes, the rules let you be more confident that a trickier and faster design will be maintainable over time, so even if it is possible without these rules, you may not be able to do that in practice. (Stylo) Sometimes, they may result in slower things. Maybe while you could use Rust's type system to help you with a design, it's too tough for you, or simply not worth the effort, so you make a copy instead of using a reference. Maybe the compiler isn't fantastic at compiling away an abstraction, and you end up with slower code than you otherwise would. And that's before you get into complexities like "I see Rc<RefCell<T>> all the time in Rust code" "that doesn't make sense, I never see that pattern in code".
- bluGill 3y ago
  There can be no answer. Research is ongoing, smart people are actively trying to make optimizer better, so even if I gave a 100% correct answer now (which would be pages long), a new commit 1 minute latter will change the rules. Sometimes someone discovers what we thought was safe isn't safe in some obscure case and so we are forced to no longer apply some optimization. sometimes optimization is a compromise and we decide that the using a couple extra CPU cycles is worth it because of some other gain (a CPU cycle is often impossible to measure in the real world as things like caches tend to dominate benchmarks, so you can make this comprise many times when suddenly the total adds up to something you can measure.). The short answer for those who don't want details: it is unlikely you can measure a difference in real world code assuming good clean code with the right algorithm.
- amelius 3y ago
  Difficult to answer. However, what you can say is that the borrow-checker works like a straight-jacket for the programmer, making them less capable to focus on other things like performance issues, high-level data leaks (e.g. a map that is filled with values without removing them eventually), or high-level safety issues.
  - steveklabnik 3y ago
    You can also say that the borrow checker works like a helpful editor, double checking your work, so that you can focus on the important details of performance issues, safety issues, and such, without needing to waste brain power on the low-level details.
    - amelius 3y ago
      This would be true if code using the borrow checker was easier to read than to write.
      - steveklabnik 3y ago
        The point is that the compiler helps you “read” it. This takes mental effort off of you. I agree that not everyone thinks this is true, but this is my experience. I do not relate to the compiler as a straight jacket. I relate to it as a helpful assistant.
        jjnoakes 3y ago
        This is my experience as well. I find it much easier to work faster when the compiler is helping me, and I don't consider it a "straitjacket" at all.
      - SubjectToChange 3y ago
        I think it’s generally accepted that writing code is nearly universally easier than reading code, in any language. That aside, getting a mechanical check on memory safety for the price of some extra language verbosity is obviously worth it IMO. By the same token, it is common to see criticisms of the complexity of templates in C++, but templates are the cornerstone of “Modern C++” and many libraries could not exist without them.
- verdagon 3y ago
  I'd say it mostly applies to manual optimization, when we're restructuring our program. If the situation calls for a B-tree, the borrow checker loves that. If the situation calls for some sort of intrusive or self-referential data structure (like in https://lwn.net/Articles/907876/ https://lwn.net/Articles/907876/), then you might have to retreat to a different data structure which could incur more bounds checking, hasher costs, or expansion costs. It's probably not worth worrying about most the time, unless you're in a very performance-sensitive situation.
deleted 3y ago
[deleted]
dxhdr 3y ago
> In fact the pattern described in the article is a common pattern in Rust and I make use of it all the time; the library for making use of it is `slotmap`. Slotmap uses unsafe everywhere, it's a memory usage pattern not supported by the borrow checker. It's basically hand-implementing use-after-free and double-free checks, which is what the borrow checker is supposed to do. Is that really a common pattern in Rust?
- dralley 3y ago
  > Slotmap uses unsafe everywhere, it's a memory usage pattern not supported by the borrow checker. Is disabling the borrow checker really a common pattern in Rust? Wrapping "unsafe" code in a safe interface is a common pattern in Rust, yes. There is absolutely nothing wrong with using "unsafe" so long as you are diligent about checking invariants, and keep it contained as much as possible. Obviously the standard library uses some "unsafe" as well, for instance. "unsafe" just means "safe but the compiler cannot verify it". Unsafe does not disable the borrow checker, though. All of the restrictions of safe Rust still apply. All "unsafe" does is unlock the ability to use raw pointers and a few other constructs. https://doc.rust-lang.org/book/ch19-01-unsafe-rust.html#unsafe-superpowers https://doc.rust-lang.org/book/ch19-01-unsafe-rust.html#unsa...
  - dxhdr 3y ago
    It's essentially a "user-space" memory allocator with it's own use-after-free and double-free checks, apparently because the language implementation isn't adequate. If anything it just reinforces the articles point that "borrow checking is incompatible with some useful patterns and optimizations."
    - junon 3y ago
      Eh? This is a wild take. How do you draw the conclusion the default implementation is inadequate?
      - dymk 3y ago
verdagon 3y ago
Later on, it adds generational references and constraint references to relax the restrictions. These are both more flexible than SlotMap because they don't require a new parameter to be passed in from the callers (and callers' callers etc), which can cause problems when an indirect caller's signature can't change (trait method override, public API, drop, etc.)
Animats 3y ago
> Borrow checking is incompatible with some useful patterns. The main problem is back references, as in doubly linked lists. In Rust, you can do that sort of thing using Rc and the weak/strong reference mechanism. Forward references own, and are strong. Back references are weak. I've been toying with the idea of some generic types which allow strong forward references which you can't copy or clone, and weak back references which you can't make strong outside a contained scope. This can be implemented with the existing Rc system, and potentially could be proven, with a static analyzer, to not require the reference counts. It's worth a try to see if one can effectively program under those restrictions. If it's not too much of a pain to use, this might be an effective way out of Rust's back-reference problem.

mr_00ff00 3y ago

I would really love a definitive answer on whether the borrow checker and rust’s rules do really limit optimizations and such. It seems like I see this opinion often and every time there are tons of people on both sides who seem sure they are correct. What are the limitations for optimization? Does unsafe rust really force those?

apendleton 3y ago
Without directly answering your question, it's worth noting that there are also additional optimizations made available by Rust that are not easily accessible in C/C++ (mostly around stronger guarantees the Rust compiler is able to make about aliasing).
steveklabnik 3y ago
The question is far too broad, and contextual. You're never going to get an answer to that question. Sometimes, the rules add more optimization potential. (like how restrict technically exists in C but is on every (okay almost every) reference in Rust) Sometimes, the rules let you be more confident that a trickier and faster design will be maintainable over time, so even if it is possible without these rules, you may not be able to do that in practice. (Stylo) Sometimes, they may result in slower things. Maybe while you could use Rust's type system to help you with a design, it's too tough for you, or simply not worth the effort, so you make a copy instead of using a reference. Maybe the compiler isn't fantastic at compiling away an abstraction, and you end up with slower code than you otherwise would. And that's before you get into complexities like "I see Rc<RefCell<T>> all the time in Rust code" "that doesn't make sense, I never see that pattern in code".
bluGill 3y ago
There can be no answer. Research is ongoing, smart people are actively trying to make optimizer better, so even if I gave a 100% correct answer now (which would be pages long), a new commit 1 minute latter will change the rules. Sometimes someone discovers what we thought was safe isn't safe in some obscure case and so we are forced to no longer apply some optimization. sometimes optimization is a compromise and we decide that the using a couple extra CPU cycles is worth it because of some other gain (a CPU cycle is often impossible to measure in the real world as things like caches tend to dominate benchmarks, so you can make this comprise many times when suddenly the total adds up to something you can measure.). The short answer for those who don't want details: it is unlikely you can measure a difference in real world code assuming good clean code with the right algorithm.
amelius 3y ago
Difficult to answer. However, what you can say is that the borrow-checker works like a straight-jacket for the programmer, making them less capable to focus on other things like performance issues, high-level data leaks (e.g. a map that is filled with values without removing them eventually), or high-level safety issues.
- steveklabnik 3y ago
  You can also say that the borrow checker works like a helpful editor, double checking your work, so that you can focus on the important details of performance issues, safety issues, and such, without needing to waste brain power on the low-level details.
  - amelius 3y ago
    This would be true if code using the borrow checker was easier to read than to write.
    - steveklabnik 3y ago
      The point is that the compiler helps you “read” it. This takes mental effort off of you. I agree that not everyone thinks this is true, but this is my experience. I do not relate to the compiler as a straight jacket. I relate to it as a helpful assistant.
      - jjnoakes 3y ago
        This is my experience as well. I find it much easier to work faster when the compiler is helping me, and I don't consider it a "straitjacket" at all.
    - SubjectToChange 3y ago
      I think it’s generally accepted that writing code is nearly universally easier than reading code, in any language. That aside, getting a mechanical check on memory safety for the price of some extra language verbosity is obviously worth it IMO. By the same token, it is common to see criticisms of the complexity of templates in C++, but templates are the cornerstone of “Modern C++” and many libraries could not exist without them.
verdagon 3y ago
I'd say it mostly applies to manual optimization, when we're restructuring our program. If the situation calls for a B-tree, the borrow checker loves that. If the situation calls for some sort of intrusive or self-referential data structure (like in https://lwn.net/Articles/907876/ https://lwn.net/Articles/907876/), then you might have to retreat to a different data structure which could incur more bounds checking, hasher costs, or expansion costs. It's probably not worth worrying about most the time, unless you're in a very performance-sensitive situation.

deleted 3y ago

[deleted]

dxhdr 3y ago

> In fact the pattern described in the article is a common pattern in Rust and I make use of it all the time; the library for making use of it is `slotmap`. Slotmap uses unsafe everywhere, it's a memory usage pattern not supported by the borrow checker. It's basically hand-implementing use-after-free and double-free checks, which is what the borrow checker is supposed to do. Is that really a common pattern in Rust?

dralley 3y ago
> Slotmap uses unsafe everywhere, it's a memory usage pattern not supported by the borrow checker. Is disabling the borrow checker really a common pattern in Rust? Wrapping "unsafe" code in a safe interface is a common pattern in Rust, yes. There is absolutely nothing wrong with using "unsafe" so long as you are diligent about checking invariants, and keep it contained as much as possible. Obviously the standard library uses some "unsafe" as well, for instance. "unsafe" just means "safe but the compiler cannot verify it". Unsafe does not disable the borrow checker, though. All of the restrictions of safe Rust still apply. All "unsafe" does is unlock the ability to use raw pointers and a few other constructs. https://doc.rust-lang.org/book/ch19-01-unsafe-rust.html#unsafe-superpowers https://doc.rust-lang.org/book/ch19-01-unsafe-rust.html#unsa...
- dxhdr 3y ago
  It's essentially a "user-space" memory allocator with it's own use-after-free and double-free checks, apparently because the language implementation isn't adequate. If anything it just reinforces the articles point that "borrow checking is incompatible with some useful patterns and optimizations."
  - junon 3y ago
    Eh? This is a wild take. How do you draw the conclusion the default implementation is inadequate?
    - dymk 3y ago

verdagon 3y ago

Later on, it adds generational references and constraint references to relax the restrictions. These are both more flexible than SlotMap because they don't require a new parameter to be passed in from the callers (and callers' callers etc), which can cause problems when an indirect caller's signature can't change (trait method override, public API, drop, etc.)

Animats 3y ago

> Borrow checking is incompatible with some useful patterns. The main problem is back references, as in doubly linked lists. In Rust, you can do that sort of thing using Rc and the weak/strong reference mechanism. Forward references own, and are strong. Back references are weak. I've been toying with the idea of some generic types which allow strong forward references which you can't copy or clone, and weak back references which you can't make strong outside a contained scope. This can be implemented with the existing Rc system, and potentially could be proven, with a static analyzer, to not require the reference counts. It's worth a try to see if one can effectively program under those restrictions. If it's not too much of a pain to use, this might be an effective way out of Rust's back-reference problem.