7 ms·

>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 unders

>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.
    - loeg 1y ago
      It's true that the array approach cannot suffer from type confusion.
  - loeg 1y ago
    Non-UB data structure corruption and other incorrect behavior isn't like, super obviously better than UB corruption and other incorrect behavior.
    - conradludgate 1y ago
      The obvious upside is that it's so much easier to debug when there's no UB. Debugging UB is never enjoyable.
      - deleted 1y ago
        [deleted]
      - jpc0 1y ago
        It’s pretty common to implement graphs in terms of arrays, not because of indices but because of cache locality. So your “UB” and “non-UB” code would look effectively identical to the CPU and would take the same amount of debugging. The reality is whether an index was tombstones and referenced or “deallocated” and referenced it is still a programmer fault that is a bug that the compiler could not catch
        IshKebab 1y ago
        > So your “UB” and “non-UB” code would look effectively identical to the CPU and would take the same amount of debugging. Said the person who has never had to debug serious UB...
      - loeg 1y ago
        The practical ramifications are often similar, even if UB can in theory do anything.
      - nullc 1y ago
        not sure I agree. UB has the benefit that there are a lot of tools like valgrind, memcheck, and various compiler features to detect it both statically and at runtime. And when you hit UB it is certainly an error. Non-UB errors have no such powerful tools, only what application specific tests or assertions you create. I've seen plenty of cases where people went and turned signed types into unsigned because signed overflow is undefined, but it had the real effect of turning easily detected and diagnosed issues into much harder to find bugs.
- safercplusplus 1y ago
  Might I suggest that the scpptool-enforced safe subset of C++ has a better solution for such data structures with cyclic or complex reference graphs, which is run-time checked non-owning pointers [1] that impose no restrictions on how or where the target objects are allocated. Unlike indices, they are safe against use-after-destruction, and they don't require the additional level of indirection either. [1] https://github.com/duneroadrunner/SaferCPlusPlus#norad-pointers https://github.com/duneroadrunner/SaferCPlusPlus#norad-point...
- voidnap 1y ago
  This is well known to be solved by using generational indexes. Its not a big deal. The author's entire post is an overreaction/rage-bait. Basically any data structure like this where you want it relocatable in memory is going to use indirection like indexes or something instead of pointers. Its a very common use case outside of rust.
tptacek 1y ago
Whoah, hold on, the author isn't comparing writing graph structures in Rust to writing it in memory-unsafe languages --- they're comparing it to writing it in other memory-safe languages. You can't force a false dichotomy between Rust and C to rebut them.
- nemothekid 1y ago
  The comparison is contrived precisely because he's comparing it to other memory-safe languages. The borrow checker was introduced because the goal of the language was a memory safe language without a runtime. Falling back to indices isn't "ironic", its exactly how you would solve the problem in C/C++. If your argument is "well Rust should be like Julia and have a GC", well thats not Rust. That language also exists, its possibly called OCaml, but its not Rust.
  - oneshtein 1y ago
    Rust have few garbage collectors[1] to chose from. For example, rust-cc is simple to use, just put #[derive(Trace, Finalize)] on struct. [1]: https://crates.io/keywords/garbage-collector https://crates.io/keywords/garbage-collector
- conradludgate 1y ago
  I think it's reasonable enough. The author already argued that there are reasons for non GC languages to exist, even if the performance doesn't matter to them. One interpretation of the article is just the author doesn't personally like the borrow checker, but another interpretation is the author saying the borrow checker is just a bad abstraction. So under the assumption that we don't have a GC available, what else can we compare the borrow checker against?
  - jakobnissen 1y ago
    Author here. Yeah, I don't like the borrowchecker. But the motivation for me writing the article is the almost religious zeal with which many Rustaceans refuse to even acknowledge that the borrowchecker has a cost in terms of ergonomics, and that this translates to e.g. iteration speed. You encounter borrowchecker issues? Well, you're just a beginner or not skilled enough. Rust makes you jump through hoops? No it doesn't, it just makes you pay upfront what you otherwise would have. It slows development? No, studies show it doesn't, you must be imagining it. This is extremely annoying to be on the receiving end of. Even though it comes from a good place (mostly just excitement), it can feel like gaslighting.
blub 1y ago
C doesn’t have objects, which are great for encapsulating data structures, but in C++ it’s not at all hard to write a graph data structure. One wraps it behind a reliable interface, writes automated test and runs them under valgrind/sanitizers and that’s pretty much it. It’s normal for life and software development to have a certain degree of risk and to spend some effort solving problems. Too many HN comments make it sound like it’s a jungle out there and a use-after-free will chop your head clean off.
- nemothekid 1y ago
  I don't mean to imply that writing a graph in C++ is impossible. It's clearly possible in modern C++. My contention is treating indicies-based management as some tedious, manual workaround. Unity's ECS is written in C#, which has both a GC and the language expressiveness for an actual graph objects, but has adopted an indicies based system. It works, and is performant, so it isn't a mistake for the compiler to herd users down that path. In a similar vein, the Linux codebase is full of completely legitimate and readable uses of goto, but we are perfectly happy with languages that force us to use structured control flow.

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.
  - loeg 1y ago
    It's true that the array approach cannot suffer from type confusion.
- loeg 1y ago
  Non-UB data structure corruption and other incorrect behavior isn't like, super obviously better than UB corruption and other incorrect behavior.
  - conradludgate 1y ago
    The obvious upside is that it's so much easier to debug when there's no UB. Debugging UB is never enjoyable.
    - deleted 1y ago
      [deleted]
    - jpc0 1y ago
      It’s pretty common to implement graphs in terms of arrays, not because of indices but because of cache locality. So your “UB” and “non-UB” code would look effectively identical to the CPU and would take the same amount of debugging. The reality is whether an index was tombstones and referenced or “deallocated” and referenced it is still a programmer fault that is a bug that the compiler could not catch
      - IshKebab 1y ago
        > So your “UB” and “non-UB” code would look effectively identical to the CPU and would take the same amount of debugging. Said the person who has never had to debug serious UB...
    - loeg 1y ago
      The practical ramifications are often similar, even if UB can in theory do anything.
    - nullc 1y ago
      not sure I agree. UB has the benefit that there are a lot of tools like valgrind, memcheck, and various compiler features to detect it both statically and at runtime. And when you hit UB it is certainly an error. Non-UB errors have no such powerful tools, only what application specific tests or assertions you create. I've seen plenty of cases where people went and turned signed types into unsigned because signed overflow is undefined, but it had the real effect of turning easily detected and diagnosed issues into much harder to find bugs.
safercplusplus 1y ago
Might I suggest that the scpptool-enforced safe subset of C++ has a better solution for such data structures with cyclic or complex reference graphs, which is run-time checked non-owning pointers [1] that impose no restrictions on how or where the target objects are allocated. Unlike indices, they are safe against use-after-destruction, and they don't require the additional level of indirection either. [1] https://github.com/duneroadrunner/SaferCPlusPlus#norad-pointers https://github.com/duneroadrunner/SaferCPlusPlus#norad-point...
voidnap 1y ago
This is well known to be solved by using generational indexes. Its not a big deal. The author's entire post is an overreaction/rage-bait. Basically any data structure like this where you want it relocatable in memory is going to use indirection like indexes or something instead of pointers. Its a very common use case outside of rust.

tptacek 1y ago

Whoah, hold on, the author isn't comparing writing graph structures in Rust to writing it in memory-unsafe languages --- they're comparing it to writing it in other memory-safe languages. You can't force a false dichotomy between Rust and C to rebut them.

nemothekid 1y ago
The comparison is contrived precisely because he's comparing it to other memory-safe languages. The borrow checker was introduced because the goal of the language was a memory safe language without a runtime. Falling back to indices isn't "ironic", its exactly how you would solve the problem in C/C++. If your argument is "well Rust should be like Julia and have a GC", well thats not Rust. That language also exists, its possibly called OCaml, but its not Rust.
- oneshtein 1y ago
  Rust have few garbage collectors[1] to chose from. For example, rust-cc is simple to use, just put #[derive(Trace, Finalize)] on struct. [1]: https://crates.io/keywords/garbage-collector https://crates.io/keywords/garbage-collector
conradludgate 1y ago
I think it's reasonable enough. The author already argued that there are reasons for non GC languages to exist, even if the performance doesn't matter to them. One interpretation of the article is just the author doesn't personally like the borrow checker, but another interpretation is the author saying the borrow checker is just a bad abstraction. So under the assumption that we don't have a GC available, what else can we compare the borrow checker against?
- jakobnissen 1y ago
  Author here. Yeah, I don't like the borrowchecker. But the motivation for me writing the article is the almost religious zeal with which many Rustaceans refuse to even acknowledge that the borrowchecker has a cost in terms of ergonomics, and that this translates to e.g. iteration speed. You encounter borrowchecker issues? Well, you're just a beginner or not skilled enough. Rust makes you jump through hoops? No it doesn't, it just makes you pay upfront what you otherwise would have. It slows development? No, studies show it doesn't, you must be imagining it. This is extremely annoying to be on the receiving end of. Even though it comes from a good place (mostly just excitement), it can feel like gaslighting.

blub 1y ago

C doesn’t have objects, which are great for encapsulating data structures, but in C++ it’s not at all hard to write a graph data structure. One wraps it behind a reliable interface, writes automated test and runs them under valgrind/sanitizers and that’s pretty much it. It’s normal for life and software development to have a certain degree of risk and to spend some effort solving problems. Too many HN comments make it sound like it’s a jungle out there and a use-after-free will chop your head clean off.

nemothekid 1y ago
I don't mean to imply that writing a graph in C++ is impossible. It's clearly possible in modern C++. My contention is treating indicies-based management as some tedious, manual workaround. Unity's ECS is written in C#, which has both a GC and the language expressiveness for an actual graph objects, but has adopted an indicies based system. It works, and is performant, so it isn't a mistake for the compiler to herd users down that path. In a similar vein, the Linux codebase is full of completely legitimate and readable uses of goto, but we are perfectly happy with languages that force us to use structured control flow.