5 ms·

Learning Rust with Entirely Too Many Linked Lists

56 points by xwvvvvwx 9y ago

PaulHoule 9y ago
Makes Rust look hard.
- steveklabnik 9y ago
  Getting this code right is hard in many languages in Rust's space; Rust just forces you to get it right, whereas they let you get it wrong.
gradschool 9y ago
An old school c programmer wants to know if there's a Rust idiom for recovering gracefully from failed allocations (i.e., when malloc returns NULL). Otherwise, what good is a type safe program that crashes due to a heap overflow? If this is the wrong kind of question, I'm listening.
- steveklabnik 9y ago
  Rust's standard library assumes that allocation will not fail. That's just a library; the language doesn't inherently know things about heap allocation. You can always call an alllocator directly and look at what it returns. Furthermore, we're working on an allocator interface that you could use with stdlib stuff that would let you handle it. The TL;DR is basically "if you want to, you can. It's going to be even easier in the future."
  - gpm 9y ago
    I'd also imagine that a allocator that returned a Result type would be quite ergonomic. Though you'd have to re-implement any datastructures that you wanted to use.
    - FreeFull 9y ago
      You would probably want to be really careful about avoiding any sort of allocation in the error case, though.
- bryanlarsen 9y ago
  Where are you using this? Embedded? By default Linux is set to over commit memory, so malloc always be succeeds even if you're out of memory.
  - jjnoakes 9y ago
    Not if process limits are set.
  - SeanDav 9y ago
    > " By default Linux is set to over commit memory, so malloc always be succeeds even if you're out of memory." How does Linux handle 1 trillion mallocs of 1MB, on a 8GB system with 500GB hard drive, without failing? There is nothing magic about Linux, it still cannot allocate and use memory which physically and virtually is simply not there.
    - steveklabnik 9y ago
      When overcommit is set, it's not malloc that fails; the OS kills your process. So, checking the result of your allocations will never let you handle this kind of error.
      - rcxdude 9y ago
        Though if the allocation is ludicrously oversized (not sure the threshold, but 2x present memory will do it) it will just straight up fail without over-committing.
  - dmpk2k 9y ago
    There are other *nix OSes out there (that don't make the mistake of overcommit by default).
- Animats 9y ago
  That's a legitimate criticism of a systems programming language. You'd like your OS kernel to never panic on an out of memory condition. (The serious end of the embedded world insists on this.) There are people working on this problem.[1] Core Rust avoids almost all implicit heap allocations that aren't triggered by operations the programmer sees as allocations.[2] But there are many library functions which allocate and panic if the allocation fails. [1] https://internals.rust-lang.org/t/notes-interviews-on-fallible-collection-allocations/5619 https://internals.rust-lang.org/t/notes-interviews-on-fallib... [2] https://www.reddit.com/r/rust/comments/69awhl/how_to_know_where_allocations_are/ https://www.reddit.com/r/rust/comments/69awhl/how_to_know_wh...
- jwatt 9y ago
  > what good is a type safe program that crashes due to a heap overflow Being "safe" is not about preventing any type of crash. It's about preventing exploitable crashes and behavior.
emerged 9y ago
I feel that Rust is something of a religion at this point. Curious how many downvotes I might accrue for expressing that perspective. Might be wrong, but my sense has been that challenges with Rust are written off in an off-hand way and its features exaggerated. Glad to see promising new languages pushing progress forward, though. I'm head high in C/C++/asm for decades so many of the complaints about those languages fall flat with me since I'm over the hurdles via sheer years of experience.
- xiphias 9y ago
  It's the first time since I'm alive a language that is higher level than C/C++ can compete with C/C++ in the benchmarks. If you have experienc with large C++ code bases you probably know how impossible it is to write safe code. Also after you use only unique/linear types, single inharitance (which is advised when working with a big code base), you are writing something that's easier to express in Rust than in C/C++. Inlined asm will stay of course, Rust doesn't try compete with it.
  - blub 9y ago
    Safety is many shades of grey instead of being black and white and it is intertwined with the concept of risk. The fact that large C and C++ code bases exist and the products they drive are successful proves that it is possible to write code in those languages that offers a good enough risk/reward balance. This is what many Rust fans are missing: you want to sell 100% memory safety, but you're assuming that everyone wants 100% instead of 80 or 90% and that they're willing to pay the price of switching.
    - steveklabnik 9y ago
      If you want to work in a memory-unsafe superset, you can; that's what unsafe is.
      - blub 9y ago
        It looks like you didn't understand what I meant. Each company/project/person needs to make a decision: * I can work in C and C++, which I can get to X% safe using the techniques and tools A, B, C at the cost of M. OR * I can invest in learning Rust and integrating it with my environment to get to 100% at the cost of N. Is the difference from X% to 100% big enough to pay N instead of M? How big of an X do I need? Is it even possible for me to use A, B and C? This is how an informed decision would look like, but Rust proponents just keep repeating that X < 100.
Animats 9y ago
Rust needs back pointers as a primitive. A back pointer and a forward pointer are locked in an invariant relationship (A points to B which points back to A). The borrow checker needs to know about that to check back pointers properly. Then you could do trees, doubly-linked lists, and various other graphs safely. (The two basic constructs that are hard to express safely in Rust are back pointers and partially initialized arrays. There's also some trouble with concurrency primitives. See [1]) [1] https://people.mpi-sws.org/~dreyer/papers/rustbelt/paper.pdf https://people.mpi-sws.org/~dreyer/papers/rustbelt/paper.pdf
- dbaupp 9y ago
  Do you have any thoughts on how it might even begin to be possible to do back pointers safely, in ways that don't already exist in Rust? I find it very confusing that you often complain about Rust's complexity, and then also complain that it isn't complex enough (i.e. doesn't have the features required statically reason about complex ownership graphs at compile time). It's fair that maybe there's complexity budget spent in places that you think aren't quite right, but I haven't picked up any reasonable plan for modelling back pointers (from anyone), nor many specific pain points that could be solved in your suggested way while maintaining the low-level nature of Rust.
  - Animats 9y ago
    Do you have any thoughts on how it might even begin to be possible to do back pointers safely, in ways that don't already exist in Rust? First, you need to be able to talk about them. A forward ref/back ref pair has to be identified with some form of declaration at compile time. The forward pointer is an ordinary owning pointer. The back pointer is special. So add a variable attribute "back", to be used like much like "mut", but only on a reference field of a struct. Let's see if that's enough. The invariants to be enforced are: - If b.bak points to a, a.fwd must point to b. - If a.fwd points to b, b.bak must be Option(None) or point to a. These can be enforced by some simple update checks when a.fwd or b.bak is updated. The normal sequence of events is something like: a.fwd = &mut b; b.bak = &back a; or, when breaking a link, b.bak = Option(None); a.fwd = None; // drop ownership of b, which deallocates it. You have to clear the back reference before dropping the object, to avoid a dangling pointer situation. The compiler might optimize that out, observing that b is dead at deallocation. If you try to change b.bak to anything but Option(None) or a, that's an error. If you try to change a.fwd while b.bak is not Option(None), that's an error. This can usually be checked at compile time. Open questions: - Can the compiler figure out which field of a is the forward ref? That's the ref that owns b. Or is syntax needed in the declaration of the a struct for that. - What about arrays of forward refs?
derefr 9y ago
Question: does a hash table with linked-list chaining count as a non-niche use-case for linked lists, or is the linked list just counted as an implementation detail rather than a separate data structure in that context? (Though, Rust's own std::collections::HashMap just does robin-hood hashing instead of separate chaining, and everyone's just going to use that, so "what data structure should a separately-chained hash-table use in Rust" is mostly a moot question.)

56 points by xwvvvvwx 9y ago

PaulHoule 9y ago

Makes Rust look hard.

steveklabnik 9y ago
Getting this code right is hard in many languages in Rust's space; Rust just forces you to get it right, whereas they let you get it wrong.

gradschool 9y ago

An old school c programmer wants to know if there's a Rust idiom for recovering gracefully from failed allocations (i.e., when malloc returns NULL). Otherwise, what good is a type safe program that crashes due to a heap overflow? If this is the wrong kind of question, I'm listening.

steveklabnik 9y ago
Rust's standard library assumes that allocation will not fail. That's just a library; the language doesn't inherently know things about heap allocation. You can always call an alllocator directly and look at what it returns. Furthermore, we're working on an allocator interface that you could use with stdlib stuff that would let you handle it. The TL;DR is basically "if you want to, you can. It's going to be even easier in the future."
- gpm 9y ago
  I'd also imagine that a allocator that returned a Result type would be quite ergonomic. Though you'd have to re-implement any datastructures that you wanted to use.
  - FreeFull 9y ago
    You would probably want to be really careful about avoiding any sort of allocation in the error case, though.
bryanlarsen 9y ago
Where are you using this? Embedded? By default Linux is set to over commit memory, so malloc always be succeeds even if you're out of memory.
- jjnoakes 9y ago
  Not if process limits are set.
- SeanDav 9y ago
  > " By default Linux is set to over commit memory, so malloc always be succeeds even if you're out of memory." How does Linux handle 1 trillion mallocs of 1MB, on a 8GB system with 500GB hard drive, without failing? There is nothing magic about Linux, it still cannot allocate and use memory which physically and virtually is simply not there.
  - steveklabnik 9y ago
    When overcommit is set, it's not malloc that fails; the OS kills your process. So, checking the result of your allocations will never let you handle this kind of error.
    - rcxdude 9y ago
      Though if the allocation is ludicrously oversized (not sure the threshold, but 2x present memory will do it) it will just straight up fail without over-committing.
- dmpk2k 9y ago
  There are other *nix OSes out there (that don't make the mistake of overcommit by default).
Animats 9y ago
That's a legitimate criticism of a systems programming language. You'd like your OS kernel to never panic on an out of memory condition. (The serious end of the embedded world insists on this.) There are people working on this problem.[1] Core Rust avoids almost all implicit heap allocations that aren't triggered by operations the programmer sees as allocations.[2] But there are many library functions which allocate and panic if the allocation fails. [1] https://internals.rust-lang.org/t/notes-interviews-on-fallible-collection-allocations/5619 https://internals.rust-lang.org/t/notes-interviews-on-fallib... [2] https://www.reddit.com/r/rust/comments/69awhl/how_to_know_where_allocations_are/ https://www.reddit.com/r/rust/comments/69awhl/how_to_know_wh...
jwatt 9y ago
> what good is a type safe program that crashes due to a heap overflow Being "safe" is not about preventing any type of crash. It's about preventing exploitable crashes and behavior.

emerged 9y ago

I feel that Rust is something of a religion at this point. Curious how many downvotes I might accrue for expressing that perspective. Might be wrong, but my sense has been that challenges with Rust are written off in an off-hand way and its features exaggerated. Glad to see promising new languages pushing progress forward, though. I'm head high in C/C++/asm for decades so many of the complaints about those languages fall flat with me since I'm over the hurdles via sheer years of experience.

xiphias 9y ago
It's the first time since I'm alive a language that is higher level than C/C++ can compete with C/C++ in the benchmarks. If you have experienc with large C++ code bases you probably know how impossible it is to write safe code. Also after you use only unique/linear types, single inharitance (which is advised when working with a big code base), you are writing something that's easier to express in Rust than in C/C++. Inlined asm will stay of course, Rust doesn't try compete with it.
- blub 9y ago
  Safety is many shades of grey instead of being black and white and it is intertwined with the concept of risk. The fact that large C and C++ code bases exist and the products they drive are successful proves that it is possible to write code in those languages that offers a good enough risk/reward balance. This is what many Rust fans are missing: you want to sell 100% memory safety, but you're assuming that everyone wants 100% instead of 80 or 90% and that they're willing to pay the price of switching.
  - steveklabnik 9y ago
    If you want to work in a memory-unsafe superset, you can; that's what unsafe is.
    - blub 9y ago
      It looks like you didn't understand what I meant. Each company/project/person needs to make a decision: * I can work in C and C++, which I can get to X% safe using the techniques and tools A, B, C at the cost of M. OR * I can invest in learning Rust and integrating it with my environment to get to 100% at the cost of N. Is the difference from X% to 100% big enough to pay N instead of M? How big of an X do I need? Is it even possible for me to use A, B and C? This is how an informed decision would look like, but Rust proponents just keep repeating that X < 100.

Animats 9y ago

Rust needs back pointers as a primitive. A back pointer and a forward pointer are locked in an invariant relationship (A points to B which points back to A). The borrow checker needs to know about that to check back pointers properly. Then you could do trees, doubly-linked lists, and various other graphs safely. (The two basic constructs that are hard to express safely in Rust are back pointers and partially initialized arrays. There's also some trouble with concurrency primitives. See [1]) [1] https://people.mpi-sws.org/~dreyer/papers/rustbelt/paper.pdf https://people.mpi-sws.org/~dreyer/papers/rustbelt/paper.pdf

dbaupp 9y ago
Do you have any thoughts on how it might even begin to be possible to do back pointers safely, in ways that don't already exist in Rust? I find it very confusing that you often complain about Rust's complexity, and then also complain that it isn't complex enough (i.e. doesn't have the features required statically reason about complex ownership graphs at compile time). It's fair that maybe there's complexity budget spent in places that you think aren't quite right, but I haven't picked up any reasonable plan for modelling back pointers (from anyone), nor many specific pain points that could be solved in your suggested way while maintaining the low-level nature of Rust.
- Animats 9y ago
  Do you have any thoughts on how it might even begin to be possible to do back pointers safely, in ways that don't already exist in Rust? First, you need to be able to talk about them. A forward ref/back ref pair has to be identified with some form of declaration at compile time. The forward pointer is an ordinary owning pointer. The back pointer is special. So add a variable attribute "back", to be used like much like "mut", but only on a reference field of a struct. Let's see if that's enough. The invariants to be enforced are: - If b.bak points to a, a.fwd must point to b. - If a.fwd points to b, b.bak must be Option(None) or point to a. These can be enforced by some simple update checks when a.fwd or b.bak is updated. The normal sequence of events is something like: a.fwd = &mut b; b.bak = &back a; or, when breaking a link, b.bak = Option(None); a.fwd = None; // drop ownership of b, which deallocates it. You have to clear the back reference before dropping the object, to avoid a dangling pointer situation. The compiler might optimize that out, observing that b is dead at deallocation. If you try to change b.bak to anything but Option(None) or a, that's an error. If you try to change a.fwd while b.bak is not Option(None), that's an error. This can usually be checked at compile time. Open questions: - Can the compiler figure out which field of a is the forward ref? That's the ref that owns b. Or is syntax needed in the declaration of the a struct for that. - What about arrays of forward refs?

derefr 9y ago

Question: does a hash table with linked-list chaining count as a non-niche use-case for linked lists, or is the linked list just counted as an implementation detail rather than a separate data structure in that context? (Though, Rust's own std::collections::HashMap just does robin-hood hashing instead of separate chaining, and everyone's just going to use that, so "what data structure should a separately-chained hash-table use in Rust" is mostly a moot question.)