4 ms·

…on the other hand it doesn't take a PhD to write a linked list in C++.

by varjag 4y ago

nezirus 4y ago
... on the third hand it's better not to roll your own list in any language ;-) Joking aside, some stuff are currently really hard in Rust, but the rate of change slowed down, and all I can see now is everyday ergonomic improvements, so there is hope for (slightly) simpler syntax in the future.
- pclmulqdq 4y ago
  Doubly linked lists break one of the fundamental promises you make to the borrow checker: single ownership. I doubt they're going to get much easier.
  - cmrdporcupine 4y ago
    It's also just generally not a wise structure to be making or using in applications level development at this point. Vectors will outperform them most of the time, are more cache friendly, and easier to write these days. And Rust has already done the work of building collections you can already use, including some that can be used no-std in embedded/baremetal environments. And if you really need a linked-list type structure, and are competent to make it and use it properly/safely, unsafe {} is waiting for you.
    - pclmulqdq 4y ago
      You tend to see linked lists in places like operating systems, storage systems, and stackless asynchronous server systems. These kinds of linked lists actually do perform better than vectors in most cases. Specifically, linked lists do well when objects are: 1. Large, specifically 100s of bytes 2. Moved frequently between collections 3. Intrusively linked (meaning that the pointers are part of the struct, not a separate library) and 4. Never randomly accessed One size does not fit all when it comes to performance of list structures, unfortunately. In particular, large items tend to break standard library structures, since they are not the usual case.
      - cmrdporcupine 4y ago
        Yes, hence why I said "applications level" development specifically. 99% of developers will never need to go this path. Those that do, they're already working down in unsafe land usually in embedded systems and OS development, and they need to think carefully about what they're doing. I'm personally not entirely sold on Rust's memory safety model, though I did learn to work with it when I was getting paid to work in it.
karmakurtisaani 4y ago
Linked lists are complicated. You can get something that compiles easily with C++, but to be sure it doesn't leak memory might require you to get that PhD after all.
- pclmulqdq 4y ago
  Linked lists are a very simple data structure, and pretty much everyone can get them right. There haven't been any big memory safety CVEs to my knowledge around linked list manipulation. The same for binary trees. These pointer-based data structures are used a lot when you are manipulating large structs in C and C++, as they let you "move" then between data structures without copying a ton of memory.
  - planede 4y ago
    It's not exactly rocket science or even PhD worthy, but getting basic exception safety right around manual memory management can get tricky.
    - lenkite 4y ago
      Well..implementing them in "safe" Rust is not just tricky - it requires a super-brain.
  - eru 4y ago
    You can use unsafe in Rust to get basically the same guarantees for your simple linked list as in C++?
- jcdentonunatco 4y ago
  If you need a PhD to avoid memory leaks, stop coding immediately, you don’t know what you are doing
  - pebal 4y ago
    Show an example of a lock-free concurrent stack freeing nodes memory.
RcouF1uZ4gsC 4y ago
I don’t think it takes a PhD to write an unsafe linked list in Rust. And an unsafe linked list in Rust would still be safer than the equivalent linked list in C++
- goalieca 4y ago
  How would the equivalent linked list in c++ be unsafe? The problem with c++ was never writing simple data structures, but was writing complete programs without a single mistake in the informal contracts between functions. Static analysis tools and other crutches help but having a stricter ruleset to enforce is what makes rust a winner.
  - RcouF1uZ4gsC 4y ago
    The list itself would not be unsafe, but the usages of it could be. For example, iterator invalidation, access from another thread, etc that Rust would prevent you from doing even if you used unsafe to implement the linked list.

…on the other hand it doesn't take a PhD to write a linked list in C++.

by varjag 4y ago

…on the other hand it doesn't take a PhD to write a linked list in C++.

... on the third hand it's better not to roll your own list in any language ;-) Joking aside, some stuff are currently really hard in Rust, but the rate of change slowed down, and all I can see now is everyday ergonomic improvements, so there is hope for (slightly) simpler syntax in the future.

pclmulqdq 4y ago
Doubly linked lists break one of the fundamental promises you make to the borrow checker: single ownership. I doubt they're going to get much easier.
- cmrdporcupine 4y ago
  It's also just generally not a wise structure to be making or using in applications level development at this point. Vectors will outperform them most of the time, are more cache friendly, and easier to write these days. And Rust has already done the work of building collections you can already use, including some that can be used no-std in embedded/baremetal environments. And if you really need a linked-list type structure, and are competent to make it and use it properly/safely, unsafe {} is waiting for you.
  - pclmulqdq 4y ago
    You tend to see linked lists in places like operating systems, storage systems, and stackless asynchronous server systems. These kinds of linked lists actually do perform better than vectors in most cases. Specifically, linked lists do well when objects are: 1. Large, specifically 100s of bytes 2. Moved frequently between collections 3. Intrusively linked (meaning that the pointers are part of the struct, not a separate library) and 4. Never randomly accessed One size does not fit all when it comes to performance of list structures, unfortunately. In particular, large items tend to break standard library structures, since they are not the usual case.
    - cmrdporcupine 4y ago
      Yes, hence why I said "applications level" development specifically. 99% of developers will never need to go this path. Those that do, they're already working down in unsafe land usually in embedded systems and OS development, and they need to think carefully about what they're doing. I'm personally not entirely sold on Rust's memory safety model, though I did learn to work with it when I was getting paid to work in it.

karmakurtisaani 4y ago

Linked lists are complicated. You can get something that compiles easily with C++, but to be sure it doesn't leak memory might require you to get that PhD after all.

pclmulqdq 4y ago
Linked lists are a very simple data structure, and pretty much everyone can get them right. There haven't been any big memory safety CVEs to my knowledge around linked list manipulation. The same for binary trees. These pointer-based data structures are used a lot when you are manipulating large structs in C and C++, as they let you "move" then between data structures without copying a ton of memory.
- planede 4y ago
  It's not exactly rocket science or even PhD worthy, but getting basic exception safety right around manual memory management can get tricky.
  - lenkite 4y ago
    Well..implementing them in "safe" Rust is not just tricky - it requires a super-brain.
- eru 4y ago
  You can use unsafe in Rust to get basically the same guarantees for your simple linked list as in C++?
jcdentonunatco 4y ago
If you need a PhD to avoid memory leaks, stop coding immediately, you don’t know what you are doing
- pebal 4y ago
  Show an example of a lock-free concurrent stack freeing nodes memory.

RcouF1uZ4gsC 4y ago

I don’t think it takes a PhD to write an unsafe linked list in Rust. And an unsafe linked list in Rust would still be safer than the equivalent linked list in C++

goalieca 4y ago
How would the equivalent linked list in c++ be unsafe? The problem with c++ was never writing simple data structures, but was writing complete programs without a single mistake in the informal contracts between functions. Static analysis tools and other crutches help but having a stricter ruleset to enforce is what makes rust a winner.
- RcouF1uZ4gsC 4y ago
  The list itself would not be unsafe, but the usages of it could be. For example, iterator invalidation, access from another thread, etc that Rust would prevent you from doing even if you used unsafe to implement the linked list.