10 ms·

Note: If someone wants to learn Rust by implementing linked lists, then https://rust-unofficial.github.io/too-many-lists/ https://rust-unofficial.github.io/too-

by dbrgn 5y ago

Note: If someone wants to learn Rust by implementing linked lists, then https://rust-unofficial.github.io/too-many-lists/ https://rust-unofficial.github.io/too-many-lists/ is a must-read :)

volta83 5y ago
Arguably, that's just too hardcore. You can implement doubly-linked lists in safe Rust by using Rc and Weak, Option, and RefCell (or Arc and Mutex for a safe concurrent doubly-linked list). Learning about safe Rust is gentler and more useful for a beginner, than starting to learn Rust by learning about "unsafe code". You have to know what safe Rust allows so that you can appropriately know to which contract unsafe Rust must adhere to.
- quotemstr 5y ago
  > You can implement doubly-linked lists in safe Rust by using Rc and Weak, Option, and RefCell (or Arc and Mutex for a safe concurrent doubly-linked list). You can, but not without introducing runtime overhead relative to C and C++, e.g., by forcing reference-counting where none would be necessary in C. Rust's safety checks do in fact block some safe and zero-overhead abstractions familiar to people working in C and C++, and denying that isn't helpful. Stating that these techniques can be implemented in Rust with overhead is missing the point. Arguing that the added overhead is "minimal" (which is a meaningless word, since the word "minimal" just means "I don't care about your scenario") is still missing the point: it's overhead that's not present in unsafe languages. The reason people use languages like C++ and Rust is to get zero cost abstractions and explicit control over the machine. If you want good performance but don't care about precise control over the machine, write Java or C# or something high level like that. You'll be just as safe as you would be in Rust and more productive. I'm really tired of this motte and bailey stuff. Rust proponents say Rust gives you fine grained machine control and safety with no performance compromises, and then when you point out that the language doesn't quite live up to that promise, Rust proponents start telling you that you didn't really need that performance anyway. This argumentative tic is annoying.
  - volta83 5y ago
    > You can, but not without introducing runtime overhead relative to C and C++, e.g., by forcing reference-counting where none would be necessary in C. The runtime overhead is minimal. 96% of it comes from the pointer indirection in the linked list, and this you have either way. Last time I benchmarked, the checks made the list 4% slower, which is acceptable for many, since doubly-linked lists are already very slow. This 4% is buying you a correctness proof that your list API cannot introduce undefined behavior. If you write this doubly-linked list abstraction in safe Rust, and make a mistake, the resulting code will still not have undefined behavior. C and C++, even paying this 4% performance cost, do not provide this guarantee, which is valuable to many. Unsafe code that removes this 4% runtime overhead is an optimization. The fact that you can remove this overhead by providing a safe wrapper over unsafe code is a selling point of Rust, but learning how to write such optimized code without learning first what it takes to make it correct IMO completely misses the point of Rust. It is very easy to write broken safe Rust abstractions over broken unsafe code. At that point, you are in a worse place than C or C++, since you are paying many costs for introducing Rust in a project, but leaving the most valuable feature off the table (correctness, lack of segfaults, lack of data-races, etc.).
    - gpderetta 5y ago
      Reference counting also adds per-element space overhead. Also linked lists are often [1] used in C and C++ for intrusive chaining of nodes otherwise owned by other data structures and the reference counting would either impose overhead to those other datastrucutres or be pointless. [1] In fact I would say this is very common at least in C++ as linked lists make otherwise very poor datastructures by themselves.
      - volta83 5y ago
        I know. So? How does that change anything? A doubly-linked list is already space inefficient, it adds 2 pointers per element. Using Rc + Weak adds one extra word per element to store the two (strong and weak) refcounts. So for a 64-bit type, a Vec takes 1x space 1xN, a list takes 3xN, and a ref-counted list 4xN. Performance wise, the extra space doesn't change anything, since that word is allocated with the element in the same cache line and would have been read anyways (even if you don't access it, the hardware does access it). If you are using a doubly-linked list, you really don't care that much about any of this, and the only thing that makes a real difference, is the guarantee that your list implementation is correct.
mushishi 5y ago
I wonder if that's still relevant way to learn Rust as seems to written in 2018.
- ATsch 5y ago
  The changes since 2018 have been very minor
  - dbrgn 5y ago
    Yep, the core concepts did not change. It's still relevant.

by dbrgn 5y ago

Note: If someone wants to learn Rust by implementing linked lists, then https://rust-unofficial.github.io/too-many-lists/ https://rust-unofficial.github.io/too-many-lists/ is a must-read :)

volta83 5y ago

Arguably, that's just too hardcore. You can implement doubly-linked lists in safe Rust by using Rc and Weak, Option, and RefCell (or Arc and Mutex for a safe concurrent doubly-linked list). Learning about safe Rust is gentler and more useful for a beginner, than starting to learn Rust by learning about "unsafe code". You have to know what safe Rust allows so that you can appropriately know to which contract unsafe Rust must adhere to.

quotemstr 5y ago
> You can implement doubly-linked lists in safe Rust by using Rc and Weak, Option, and RefCell (or Arc and Mutex for a safe concurrent doubly-linked list). You can, but not without introducing runtime overhead relative to C and C++, e.g., by forcing reference-counting where none would be necessary in C. Rust's safety checks do in fact block some safe and zero-overhead abstractions familiar to people working in C and C++, and denying that isn't helpful. Stating that these techniques can be implemented in Rust with overhead is missing the point. Arguing that the added overhead is "minimal" (which is a meaningless word, since the word "minimal" just means "I don't care about your scenario") is still missing the point: it's overhead that's not present in unsafe languages. The reason people use languages like C++ and Rust is to get zero cost abstractions and explicit control over the machine. If you want good performance but don't care about precise control over the machine, write Java or C# or something high level like that. You'll be just as safe as you would be in Rust and more productive. I'm really tired of this motte and bailey stuff. Rust proponents say Rust gives you fine grained machine control and safety with no performance compromises, and then when you point out that the language doesn't quite live up to that promise, Rust proponents start telling you that you didn't really need that performance anyway. This argumentative tic is annoying.
- volta83 5y ago
  > You can, but not without introducing runtime overhead relative to C and C++, e.g., by forcing reference-counting where none would be necessary in C. The runtime overhead is minimal. 96% of it comes from the pointer indirection in the linked list, and this you have either way. Last time I benchmarked, the checks made the list 4% slower, which is acceptable for many, since doubly-linked lists are already very slow. This 4% is buying you a correctness proof that your list API cannot introduce undefined behavior. If you write this doubly-linked list abstraction in safe Rust, and make a mistake, the resulting code will still not have undefined behavior. C and C++, even paying this 4% performance cost, do not provide this guarantee, which is valuable to many. Unsafe code that removes this 4% runtime overhead is an optimization. The fact that you can remove this overhead by providing a safe wrapper over unsafe code is a selling point of Rust, but learning how to write such optimized code without learning first what it takes to make it correct IMO completely misses the point of Rust. It is very easy to write broken safe Rust abstractions over broken unsafe code. At that point, you are in a worse place than C or C++, since you are paying many costs for introducing Rust in a project, but leaving the most valuable feature off the table (correctness, lack of segfaults, lack of data-races, etc.).
  - gpderetta 5y ago
    Reference counting also adds per-element space overhead. Also linked lists are often [1] used in C and C++ for intrusive chaining of nodes otherwise owned by other data structures and the reference counting would either impose overhead to those other datastrucutres or be pointless. [1] In fact I would say this is very common at least in C++ as linked lists make otherwise very poor datastructures by themselves.
    - volta83 5y ago
      I know. So? How does that change anything? A doubly-linked list is already space inefficient, it adds 2 pointers per element. Using Rc + Weak adds one extra word per element to store the two (strong and weak) refcounts. So for a 64-bit type, a Vec takes 1x space 1xN, a list takes 3xN, and a ref-counted list 4xN. Performance wise, the extra space doesn't change anything, since that word is allocated with the element in the same cache line and would have been read anyways (even if you don't access it, the hardware does access it). If you are using a doubly-linked list, you really don't care that much about any of this, and the only thing that makes a real difference, is the guarantee that your list implementation is correct.

mushishi 5y ago

I wonder if that's still relevant way to learn Rust as seems to written in 2018.

ATsch 5y ago
The changes since 2018 have been very minor
- dbrgn 5y ago
  Yep, the core concepts did not change. It's still relevant.