4 ms·

This reminds me of something that was popular in some bioinformatics circles years ago. People claimed that Java was faster than C++. To "prove" that, they wrot

This reminds me of something that was popular in some bioinformatics circles years ago. People claimed that Java was faster than C++. To "prove" that, they wrote reasonably efficient Java code for some task, and then rewrote it in C++. Using std::shared_ptr extensively to get something resembling garbage collection. No wonder the real Java code was faster than the Java code written in C++. I've been writing C++ for almost 30 years, and a few years of Rust. I sometimes struggle with the Rust borrow checker, and it's almost always my fault. I keep trying to write C++ in Rust, because I'm thinking in C++ instead of Rust. The lesson is always the same. If you want to use language X, you must learn to write X, instead of writing language Y in X. Using indexes (or node ids or opaque handles) in graph/tree implementations is a good idea both in C++ and in Rust. It makes serialization easier and faster. It allows you to use data structures where you can't have a pointer to a node. And it can also save memory, as pointers and separate memory allocations take a lot of space when you have billions of them. Like when working with human genomes.

timmytokyo 1y ago
If using indices is going to be your answer, then it seems to me you should at least contend with the OP's argument that this approach violates the very reason the borrowchecker was introduced in the first place. From the post: "The Rust community's whole thing is commitment to compiler-enforced correctness, and they built the borrowchecker on the premise that humans can't be trusted to handle references manually. When the same borrowchecker makes references unworkable, their solution is to... recommend that I manually manage them, with zero safety and zero language support?!? The irony is unreal."
- mmoskal 1y ago
  I think this is like unsafe - most of your code won’t have it, so you get the benefits of borrow checker (memory safety and race freedom) elsewhere.
  - sundarurfriend 1y ago
    An important saving grace that `unsafe` has is that it's local and clearly demarcated. If a core data structure of your program can be compared to `unsafe` and has to be manually managed for correctness, it's very valid to ask whether the hoops Rust makes you jump through are actually gaining you anything.
- nemothekid 1y ago
  >OP's argument that this approach violates the very reason the borrowchecker was introduced in the first place. No it doesn't. I just don't think author understands the pitfalls of implementing something like a graph structure in a memory unsafe language. The author doesn't write C so I don't believe he has struggled with the pain of chasing a dangling pointer with valgrind. There are plenty of libraries in C that eventually decided to use indexes instead of juggling pointers around because it's much harder to eventually introduce a use-after-free when dereferencing nodes this way. Entity component systems were invented in 1998 which essentially implement this pattern. I don't find it ironic that the Rust compiler herds people towards a safe design that has been rediscovered again and again. The borrow checker was introduced to statically verify memory safety. Using indices into graphs has been a memory safe option in languages like C for decades. I find his argument as valid as if someone said "I can't use goto? you expect me to manually run my cleanup code before I return?" Just because I took away your goto to make control flow easier it doesn't make it "ironic" if certain legitimate uses of goto are harder. Surely you wouldn't accept his argument for someone arguing for the return of goto in mainstream languages?
  - loeg 1y ago
    Indices can be dangling in almost exactly the same way as pointers. Worse, it's easier to accidentally use-after-free clobber some other item in the same structure, because allocations are "dense." (Pointer designs on systems where malloc/free is ~LIFO experience similar problems.)
    - burntsushi 1y ago
      Except for the fact that one leads to undefined behavior and the other doesn't. This is a massive difference.
      - bombela 1y ago
        This might not seem obvious. So allow me an attempt at expanding a bit. The difference is that a dangling raw pointer to the heap will point to anything that can be modified at any time. But indexing a dynamic array guarantees that every elements is always well formed and safe to use.
- burntsushi 1y ago
  The OP's argument is bunk. It's been said many times too over the years. The fact is that the index approach does not give up everything. The obvious thing it doesn't give up is safety. It's true you can still get bugs via out of bounds accesses, but it won't result in undefined behavior. You get a panic instead. This is how the regex crate works internally and uses almost no `unsafe`.
- Groxx 1y ago
  That seems rather easy? There's still plenty of safety. It's not an `unsafe` trick or worse, you still have bounds checking and safe concurrency and well-defined behavior, and you can trivially guarantee that (while mutating the vec) it cannot be changed unexpectedly while you hold ownership of the vec. The extreme ease of making that guarantee is kinda the core of their complaint. The dangling-pointer equivalent is an issue, but it's still safe (unlike in C-like langs) and there are ways to mitigate the risk of accidental misbehavior (e.g. generational pointers, or simply an ID check if you have a convenient ID). That's quite a bit different than what you get in almost any other widely-used language - e.g. some will at best be able to claim "concurrent access won't lead to undefined behavior" via e.g. the GIL, but not prevent unexpected modification (e.g. "freeze" doesn't deep-freeze in the vast majority of languages).
ninetyninenine 1y ago
There is such a thing of languages that align with human intuition. C++ and Rust are not these languages so you have to really learn these languages in depth. Languages like typescript or python or go align more with intuition and you don't really need to learn as much about the details or patterns as these just naturally flow from your intuition. This is a huge huge thing as it makes the language literally take about a week to develop proficiency and two weeks to develop mastery. A language like C++... you can't even develop mastery in a year. That is not to say these languages are better. Intuition is just one trade off.
- fpoling 1y ago
  Typescript is not a language that matches intuition. Typing complex code while avoiding the any hatch resembles fighting limitations of the borrow checker in Rust.
  - ninetyninenine 1y ago
    I find it highly highly intuitive. But my background is haskell like languages. I feel with practice basic type checking is something that helps you rather then hinders you. It can be learned easily imo. People coming from js tend to have a hard time but that's understandable. The borrow checker is not easily learned imo. It's always me running into a wall.
    - fpoling 1y ago
      For me the problem with TypeScript or Flow when the latter was a thing was that the syntax/semantics of the sub language of types was extremely ad-hoc with so many idiosyncrasies. Maybe if I programmed it all the time I would learned it. But I had to change the relevant code only occasionally and typing helpers to access DOM required constant look at the spec and StackOverflow. With Rust the rules at least are simple. While following them can be a struggle the compiler errors at least are much more helpful and points to the problem with the design or the checker limitations.

timmytokyo 1y ago

If using indices is going to be your answer, then it seems to me you should at least contend with the OP's argument that this approach violates the very reason the borrowchecker was introduced in the first place. From the post: "The Rust community's whole thing is commitment to compiler-enforced correctness, and they built the borrowchecker on the premise that humans can't be trusted to handle references manually. When the same borrowchecker makes references unworkable, their solution is to... recommend that I manually manage them, with zero safety and zero language support?!? The irony is unreal."

mmoskal 1y ago
I think this is like unsafe - most of your code won’t have it, so you get the benefits of borrow checker (memory safety and race freedom) elsewhere.
- sundarurfriend 1y ago
  An important saving grace that `unsafe` has is that it's local and clearly demarcated. If a core data structure of your program can be compared to `unsafe` and has to be manually managed for correctness, it's very valid to ask whether the hoops Rust makes you jump through are actually gaining you anything.
nemothekid 1y ago
>OP's argument that this approach violates the very reason the borrowchecker was introduced in the first place. No it doesn't. I just don't think author understands the pitfalls of implementing something like a graph structure in a memory unsafe language. The author doesn't write C so I don't believe he has struggled with the pain of chasing a dangling pointer with valgrind. There are plenty of libraries in C that eventually decided to use indexes instead of juggling pointers around because it's much harder to eventually introduce a use-after-free when dereferencing nodes this way. Entity component systems were invented in 1998 which essentially implement this pattern. I don't find it ironic that the Rust compiler herds people towards a safe design that has been rediscovered again and again. The borrow checker was introduced to statically verify memory safety. Using indices into graphs has been a memory safe option in languages like C for decades. I find his argument as valid as if someone said "I can't use goto? you expect me to manually run my cleanup code before I return?" Just because I took away your goto to make control flow easier it doesn't make it "ironic" if certain legitimate uses of goto are harder. Surely you wouldn't accept his argument for someone arguing for the return of goto in mainstream languages?
- loeg 1y ago
  Indices can be dangling in almost exactly the same way as pointers. Worse, it's easier to accidentally use-after-free clobber some other item in the same structure, because allocations are "dense." (Pointer designs on systems where malloc/free is ~LIFO experience similar problems.)
  - burntsushi 1y ago
    Except for the fact that one leads to undefined behavior and the other doesn't. This is a massive difference.
    - bombela 1y ago
      This might not seem obvious. So allow me an attempt at expanding a bit. The difference is that a dangling raw pointer to the heap will point to anything that can be modified at any time. But indexing a dynamic array guarantees that every elements is always well formed and safe to use.
burntsushi 1y ago
The OP's argument is bunk. It's been said many times too over the years. The fact is that the index approach does not give up everything. The obvious thing it doesn't give up is safety. It's true you can still get bugs via out of bounds accesses, but it won't result in undefined behavior. You get a panic instead. This is how the regex crate works internally and uses almost no `unsafe`.
Groxx 1y ago
That seems rather easy? There's still plenty of safety. It's not an `unsafe` trick or worse, you still have bounds checking and safe concurrency and well-defined behavior, and you can trivially guarantee that (while mutating the vec) it cannot be changed unexpectedly while you hold ownership of the vec. The extreme ease of making that guarantee is kinda the core of their complaint. The dangling-pointer equivalent is an issue, but it's still safe (unlike in C-like langs) and there are ways to mitigate the risk of accidental misbehavior (e.g. generational pointers, or simply an ID check if you have a convenient ID). That's quite a bit different than what you get in almost any other widely-used language - e.g. some will at best be able to claim "concurrent access won't lead to undefined behavior" via e.g. the GIL, but not prevent unexpected modification (e.g. "freeze" doesn't deep-freeze in the vast majority of languages).

ninetyninenine 1y ago

There is such a thing of languages that align with human intuition. C++ and Rust are not these languages so you have to really learn these languages in depth. Languages like typescript or python or go align more with intuition and you don't really need to learn as much about the details or patterns as these just naturally flow from your intuition. This is a huge huge thing as it makes the language literally take about a week to develop proficiency and two weeks to develop mastery. A language like C++... you can't even develop mastery in a year. That is not to say these languages are better. Intuition is just one trade off.

fpoling 1y ago
Typescript is not a language that matches intuition. Typing complex code while avoiding the any hatch resembles fighting limitations of the borrow checker in Rust.
- ninetyninenine 1y ago
  I find it highly highly intuitive. But my background is haskell like languages. I feel with practice basic type checking is something that helps you rather then hinders you. It can be learned easily imo. People coming from js tend to have a hard time but that's understandable. The borrow checker is not easily learned imo. It's always me running into a wall.
  - fpoling 1y ago
    For me the problem with TypeScript or Flow when the latter was a thing was that the syntax/semantics of the sub language of types was extremely ad-hoc with so many idiosyncrasies. Maybe if I programmed it all the time I would learned it. But I had to change the relevant code only occasionally and typing helpers to access DOM required constant look at the spec and StackOverflow. With Rust the rules at least are simple. While following them can be a struggle the compiler errors at least are much more helpful and points to the problem with the design or the checker limitations.