4 ms·

Writing a doubly linked list is trivial if you use a backing vector and view into it. Which is how you should do it. Linked lists are awful data structures and

by duped 5y ago

Writing a doubly linked list is trivial if you use a backing vector and view into it. Which is how you should do it. Linked lists are awful data structures and just as difficult to implement soundly in a thread safe context everywhere else. Rust just yells at you for doing it wrong. I reiterate, unless you have a damn good reason, a linked list is an awful data structure. They're slow and cumbersome and have no advantages at small or large scales. The cases where you want them are few and far between and not in any undergraduate DSA course or application.

platinumrad 5y ago
Yes, linked lists are overused in userspace, especially by beginners, but the "linked list bad" meme has gone too far. In particular, intrusive linked lists are commonly used in game engines and, oh yeah, operating system kernels for reasons ranging from memory efficiency to the ability to cheaply rearrange nodes. > Linked lists are awful data structures and just as difficult to implement soundly in a thread safe context everywhere else. Rust just yells at you for doing it wrong. This is a non-sequitur. Vectors and vector-based data structures are just as thread unsafe as basic linked lists. Furthermore, Rust isn't yelling at you for "doing it wrong". Safe Rust is yelling at you because the type system (by design) does not like cyclic ownership.
thesz 5y ago
I beg to disagree. An old presentation by Simon Peyton-Jones (of GHC fame) has a line like that: "Linked list implementation is first year programming course task; linked list implementation on multiprocessor is a PhD-level task; linked list implementation on multiprocessor using software transactional memory is again first year course task." SPJ actually teaches students and oversees PhD students so these are not vain words. STM greatly simplifies everything that is done in parallel, including, but not limited to, double linked lists. Rust "yells at you doing it wrong" because Rust does not know any better way. Effects would help expressing safe STM computations, and they are just coming into Rust, hesitantly. Let's see what will happen.
saagarjha 5y ago
This is exactly the mindset that people hate about Rust, although I think it's unfair to associate it with the language because it's perpetuated by people who hold opinions like yours. Linked lists are often not very performant on modern hardware. There's a lot of usecases where a vector (just as a generic collection or as the backing view) would be a better choice. Rust happens to make creating linked lists non-trivial. These are all facts. The incorrect way to interpret this is how you've done: that linked lists are just wrong, and Rust happens to not let you use them because it wants you to not write wrong code so it makes this hard. Rust is a good language, but this is just a limitation of Rust, full stop. It's not some secret "the language authors are super smart and want you to stop writing linked lists". It's just that the language doesn't really let you do this, and it so happens that you can often get by with not creating them so Rust remains a productive language most of the time. Linked lists remain incredibly useful in certain situations, of which an operating system kernel happens to be to feature a lot of. The ability to reliably allocate contiguous memory is not a given, and various thread safety and reference identity requirements make lists the only choice for a lot of parts of the kernel. This would be true regardless of the language you used to write it. Suggestions that linked lists are awful and have no advantages are quite frankly more of a sign of your limited experience with the environments where they would be useful than them being "wrong". (Do note that I am not saying that the kernel only uses linked lists where appropriate: there's a lot of places where they're just a crutch to get around C being unable to deal with generic types without indirecting them behind a pointer, and Rust or even C++ would definitely be able to remove some of these "unfortunate" uses. But there's still plenty of linked lists that can not and will not be replaced regardless of the language the kernel is written in.)
- imtringued 5y ago
  Actually Rust lets you write linked lists of any kind very easily with reference counting. It's just that reference counting is no fun in C land. People like running around with loaded guns with disabled safety in their pocket. Linked lists have a lot of pointers, that means a lot of things can go wrong. It's just that the mental strain of lots of things going wrong is too much for most humans so they just straight up ignore the safety aspects. When you think about it, the ownership hierarchy of a linked list is quite complex. A lot of rust developers simply solve the problem by having a linked list container that owns all nodes. But in C land, it is pretty normal that the first node owns the second, the second owns the third, the third owns the fourth and so on. The ownership hierarchy is much more complicated, for not much benefit. Once you have a doubly linked list, ownership is no longer trivial because it cannot be expressed as a hierarchy. Most languages have solved this with a garbage collector so it's really Rust that is the first language that is attempting a solution without a GC. In C land, the danger is part of the job, not something that anyone particularly cares about.

by duped 5y ago

platinumrad 5y ago

Yes, linked lists are overused in userspace, especially by beginners, but the "linked list bad" meme has gone too far. In particular, intrusive linked lists are commonly used in game engines and, oh yeah, operating system kernels for reasons ranging from memory efficiency to the ability to cheaply rearrange nodes. > Linked lists are awful data structures and just as difficult to implement soundly in a thread safe context everywhere else. Rust just yells at you for doing it wrong. This is a non-sequitur. Vectors and vector-based data structures are just as thread unsafe as basic linked lists. Furthermore, Rust isn't yelling at you for "doing it wrong". Safe Rust is yelling at you because the type system (by design) does not like cyclic ownership.

thesz 5y ago

I beg to disagree. An old presentation by Simon Peyton-Jones (of GHC fame) has a line like that: "Linked list implementation is first year programming course task; linked list implementation on multiprocessor is a PhD-level task; linked list implementation on multiprocessor using software transactional memory is again first year course task." SPJ actually teaches students and oversees PhD students so these are not vain words. STM greatly simplifies everything that is done in parallel, including, but not limited to, double linked lists. Rust "yells at you doing it wrong" because Rust does not know any better way. Effects would help expressing safe STM computations, and they are just coming into Rust, hesitantly. Let's see what will happen.

saagarjha 5y ago

This is exactly the mindset that people hate about Rust, although I think it's unfair to associate it with the language because it's perpetuated by people who hold opinions like yours. Linked lists are often not very performant on modern hardware. There's a lot of usecases where a vector (just as a generic collection or as the backing view) would be a better choice. Rust happens to make creating linked lists non-trivial. These are all facts. The incorrect way to interpret this is how you've done: that linked lists are just wrong, and Rust happens to not let you use them because it wants you to not write wrong code so it makes this hard. Rust is a good language, but this is just a limitation of Rust, full stop. It's not some secret "the language authors are super smart and want you to stop writing linked lists". It's just that the language doesn't really let you do this, and it so happens that you can often get by with not creating them so Rust remains a productive language most of the time. Linked lists remain incredibly useful in certain situations, of which an operating system kernel happens to be to feature a lot of. The ability to reliably allocate contiguous memory is not a given, and various thread safety and reference identity requirements make lists the only choice for a lot of parts of the kernel. This would be true regardless of the language you used to write it. Suggestions that linked lists are awful and have no advantages are quite frankly more of a sign of your limited experience with the environments where they would be useful than them being "wrong". (Do note that I am not saying that the kernel only uses linked lists where appropriate: there's a lot of places where they're just a crutch to get around C being unable to deal with generic types without indirecting them behind a pointer, and Rust or even C++ would definitely be able to remove some of these "unfortunate" uses. But there's still plenty of linked lists that can not and will not be replaced regardless of the language the kernel is written in.)

imtringued 5y ago
Actually Rust lets you write linked lists of any kind very easily with reference counting. It's just that reference counting is no fun in C land. People like running around with loaded guns with disabled safety in their pocket. Linked lists have a lot of pointers, that means a lot of things can go wrong. It's just that the mental strain of lots of things going wrong is too much for most humans so they just straight up ignore the safety aspects. When you think about it, the ownership hierarchy of a linked list is quite complex. A lot of rust developers simply solve the problem by having a linked list container that owns all nodes. But in C land, it is pretty normal that the first node owns the second, the second owns the third, the third owns the fourth and so on. The ownership hierarchy is much more complicated, for not much benefit. Once you have a doubly linked list, ownership is no longer trivial because it cannot be expressed as a hierarchy. Most languages have solved this with a garbage collector so it's really Rust that is the first language that is attempting a solution without a GC. In C land, the danger is part of the job, not something that anyone particularly cares about.