13 ms·
Learn Rust with entirely too many linked lists (2019)
- ajross 7y ago> Mumble mumble kernel embedded something something intrusive. And this is why kernel/embedded/something/something developers don't take Rust as seriously as you want them to. You can't simultaneously declare your language the best choice for system software development and treat the long-evolved patterns of those paradigms as a joke. There are very good reasons for intrusive data structures, not least of which being their ability to operate in contexts where no heap is available. If you don't understand them or don't want to talk about them or want to limit your discussion to situations with different requirements, then say so.
- deleted 7y ago[deleted]
- jszymborski 7y agoI think it must be stressed that this is an unofficial guide and not "the voice of the project", etc...
- robbyt 7y agoTo explain what I think this comment means. When working on embedded systems, you can interact with hardware devices by writing directly to specially mapped memory areas. E.g., if you want to write text to a small screen, the kernel driver gives you a memory region that you write bytes to, and they're shown on the screen immediately, without requiring the CPU.
- redrobein 7y ago> To explain what I think this comment means. When working on embedded systems, you can interact with hardware devices by writing directly to specially mapped memory areas. And why can't you do this in rust?
- jasondclinton 7y agoYou can. Rust allows full memory addressing.
- lawn 7y agoThere's nothing to prevent you from doing this, although you may have to wrap it in an unsafe block.
- monocasa 7y agoThey're saying more that intrusive data structures are really nice in situations that restrict heap allocation. The memory overhead outside of the structures linked together is O(1), because all of the per object metadata is stored in the objects themselves. That means consumers generally don't have to be hardcoded for certain number of objects like you would for an array/vector that doesn't have access to a heap.
- fortran77 7y agoMy feelings, too. I do both embedded programming (in C/C++ and CUDA) and Erlang programming for a living. Erlang, too, doesn't let you (easily) write your own linked list structures, etc. But for embedded programming with tight memory or performance constraints these data structures are essential so we use C++ or even C. They're well understood and the implementations have simple, elegant solutions. For "safety" when we don't need absolute control, we'll choose a GC language like C# or F#. No need for the complication of Rust.
- saagarjha 7y agoRust gives you just as much control as C when you need it.
- throwaway17_17 7y agoI may be mistaken, but if using unsafe does not allow for the ‘borrow-checker’ to be turned off and allow for code which doesn’t abide by the checker’s requirements, then it clearly does not give “as much control as C”. Again, I might have missed some of the subtleties of circumventing Rust’s static checking, but I don’t think I can purposely create some non-deterministic racy-appearing abstractions, which would be trivial to do using global variables in C.
- saagarjha 7y ago> if using unsafe does not allow for the ‘borrow-checker’ to be turned off and allow for code which doesn’t abide by the checker’s requirements It does, that’s why it’s there.
- steveklabnik 7y agoUnsafe doesn’t turn off the borrow checker, but it does give you access to pointers that aren’t checked.
- zozbot234 7y ago> if using unsafe does not allow for the ‘borrow-checker’ to be turned off and allow for code which doesn’t abide by the checker’s requirements It allows the latter. 'Code that doesn't abide by the checker's requirements' uses separate facilities that are only allowed in unsafe code. This means that `unsafe` doesn't have to turn off anything, and further pinpoints the parts of the code where caution is needed in order to maintain the invariants that Safe Rust is based on.
- steveklabnik 7y agoIt explicitly says that there are good use cases, just that they’re very rare.
- ajross 7y agoIt does not. Maybe somewhere else it does. That section, verbatim, says: It's niche. You're talking about a situation where you're not even using your language's runtime. Is that not a red flag that you're doing something strange? It's also wildly unsafe. But sure. Build your awesome zero-allocation lists on the stack. And this is (1) wildly mistating the requirements and (2) deeply offensive to those of us who work in those regimes. Obviously, yes, there's room for a reasoned argument about this stuff and whether alternative paradigms can be deployed in heapless contexts. This isn't it.
- steveklabnik 7y ago> It's a fine data structure with several great use cases, but those use cases are exceptional, not common.
- MaulingMonkey 7y ago> And this is (1) wildly mistating the requirements and (2) deeply offensive to those of us who work in those regimes. Care to expand how? While not a kernel dev, I've had my share of use cases where I've done exactly this kind of thing in gamedev, and I simply cannot bring myself to disagree with what's been said, or see what's offensive. It's strange, debugging when the pointers get corrupted by other code exhibiting UB is painful, it's a potential multithreading hazard, and flat contiguous arrays are frequently more appropriate - but it's sometimes useful. It's not arguing that an alternative paradigm can - or even should - be deployed in a heapless context. It's explicitly admitting that intrusive linked lists are an appropriate paradigm.
- catatattat 7y ago> (2) deeply offensive to those of us who work in those regimes You know how sometimes someone who is A Little Too Online gets offended because they think you said a Bad Thing, but it was actually just a typo or a straight misreading, and you try to explain that they’re reacting to something you didn’t even say let alone believe, but because they have already decided you are the Bad Person they interpret that as you “doubling down“ on the bad opinion that they attributed to you, so they get even angrier and even more convinced that you sincerely believe the Bad Thing? I mean no judgment. We all have such sensitivities. But maybe now you see how easily you can wind up on the wrong side of a public debate by searching for offense where there is in fact none.
- roblabla 7y agoThe actual context of your quote: > Just so we're totally 100% clear: I hate linked lists. With a passion. Linked lists are terrible data structures. Now of course there's several great use cases for a linked list: > > - You're writing a kernel/embedded thing and want to use an intrusive list. So I’ve got no clue what you’re railing about. The project specifically acknowledges that there is a need in kerneldev for those data structures. I’m a kernel dev using Rust for my kernel. I use both intrusive linked list and growable vectors in it. The thing is, the sentiment expressed in the article really resonates in me: in most cases, growable vectors are a better choice, performance-wise.
- ajross 7y ago(Had to edit in a quote to what I was replying to because you fixed the original): > The actual context of your fake quote: Good grief, that was a verbatim quote! Here's a link to the exact text I quoted: https://rust-unofficial.github.io/too-many-lists/#mumble-mumble-kernel-embedded-something-something-intrusive https://rust-unofficial.github.io/too-many-lists/#mumble-mum...
- throwaway17_17 7y agoThe quote that the GP is talking about is included below, which copy/pasted from the project page, and the Mumble mumble line is the heading for a paragraph: ‘’’Mumble mumble kernel embedded something something intrusive. It's niche. You're talking about a situation where you're not even using your language's runtime. Is that not a red flag that you're doing something strange? It's also wildly unsafe.’’’ Also, prior to this author claims the following, where the first line also a section heading: ‘’’ I can't afford amortization You've already entered a pretty niche space’’’ These fiat rulings based on one an authors generalization of what is ‘niche’ are what I assume GP was commenting on. These are the kinds of dismissals that some developers take issue with, as GP states.
- saagarjha 7y agoKernel development is niche. Most of the time you don’t need linked lists.
- jasondclinton 7y agohttps://github.com/Amanieu/intrusive-rs https://github.com/Amanieu/intrusive-rs implements what you're looking for with no heap. There's no need to flame or misrepresent what the book says (no one said embedded was a joke). The Rust embedded community is strong.
- ajross 7y agoYou're like the sixth person to argue I'm somehow "misrepresenting" what is being said in this book? I'm quoting it directly. The "flame" is in the original, and I'm responding to it. Take it out. It's bad.
- jasondclinton 7y agoAssuming that you're not trolling, I'll explain how you misinterpreted what you read: the section that you quoted is a sub-heading under: > An Obligatory Public Service Announcement which is an argument that: > Linked lists are as niche and vague of a data structure as a trie. The author then goes on to state that many people have contacted him to argue that linked lists are not niche and he puts each of those arguments under a heading: > Mumble mumble kernel embedded something something intrusive. is one such heading. Inside of it, he continues the argument that linked lists for embedded no-heap scenarios are niche and—to continue his argument—we therefore shouldn't be teaching undergrads linked lists just like we don't teach them tries.
- fhars 7y agoI think what ajross is arguing is that it is the author of the tutorial who is trolling here. It is all true what you and everyone else say against ajross‘ argument on the purely factual layer, it is just that the tone of the PSA is needlessly aggressive and condescending.
- deleted 7y ago[deleted]
- jasondclinton 7y agoI went through this a few years ago for fun. It's a great guided tour of the compiler errors when working with complex memory safety needs. The most important thing to know about these is that you would almost certainly never do these in a real project: lists are in `std` but even then the vast majority of cases should use `Vec`.
- Dylan16807 7y agoLinked lists are inherently niche on modern hardware.
- varjag 7y agoSeriously? Are trees also niche?
- Dylan16807 7y agoWhat kind of tree? A binary tree isn't great for many uses, and doesn't excel at much. But a nice fat B+ tree removes the vast majority of pointer-chasing latency.
- kybernetikos 7y agoI've got quite keen on B+ trees. It seems like the world where we had fast main memory and slow drive storage is not very different to the world where we have fast cache memory and slow main memory.
- Tuna-Fish 7y agoYes. For the vast majority of uses, you should probably use a hash table instead. There are still niche uses for both linked lists and trees, but the sad fact is that the relative time it takes to chase a random pointer compared to doing literally anything else keeps getting worse, and is already at the point where frequently linearly copying kilobytes of arrays is almost always faster than using a linked list.
- _bxg1 7y agoWhen I was first getting started with Rust this tutorial was eye-opening. It gave me a clear view into the somewhat impenetrable world of working with Boxes (pointers to the heap) directly, in the context of the borrow-checker. It also convinced me that you usually just want to use the standard library data structures if you can :P
- ubercow13 7y agoThis is great as an intro to Rust, I preferred this as a Rust starter tutorial to the main rust book or any other tutorial I tried
- Waterluvian 7y agoI'm loving both. The book is comprehensive and teaches you even the most basic concepts, so it's great for a broader skill range. But I love this one too because it digs into some CS archaeology and that helps me dig into the theory and history. I doubt I'll ever have to implement a linked list but knowing how they work and are implemented and their advantages and drawbacks is great. Tangentially, there's a wonderful game called Human Resource Machine which teaches linked lists and other assembly-like programming without you even realising it.
- ubercow13 7y agoThe book is very comprehensive but it didn't click for me as a beginner, I found much of the exposition left me with unanswered questions while it went on to cover more ground. I'm not sure if those questions were answered later but I got lost very quickly. Maybe it's aimed at people with more C++ background? This linked list tutorial answered every question I thought of almost exactly as I thought of them, which made it a joy to read. I also liked Rust By Example [1] over the book. Based on my experience I'd recommend this tutorial and then implementing something using Rust By Example as reference. But everyone learns differently! [1] https://doc.rust-lang.org/rust-by-example/ https://doc.rust-lang.org/rust-by-example/
- xlap 7y agoBasically anything published about Rust is turning me away from the language. It could be unfair though: Technical writing (and that includes humorous opinionated pieces) has declined dramatically in the last 10 years. Or perhaps writing as a whole has declined.
- Dylan16807 7y agoIt wouldn't hurt to be specific.
- caconym_ 7y agoA while ago now, this was the tutorial that got me to the point where I could implement linked structures in Rust. Highly recommended.
- kybernetikos 7y agoI really value this guide. Writing data structures in a language is one of the standard ways that I convince myself that I understand it. Rust really messes hard with that mindset. This guide talked me through all the things I'm not used to worrying about in garbage collected languages, showed me the error messages that I'd been banging my head against, explained what they meant, and did so with humor.
- Igelau 7y agoThis Gonzo approach of running headlong into a bad idea is refreshing.
- zackify 7y agoCan’t wait to follow this. I’ve been going through the official book these past couple weeks. As someone who’s never used systems languages (mainly a js / node person) I was able to write a redis-like database quickly on top of TCP. I’ve also picked up async / await and how it works in rust. There’s so much to learn but the compiler is surprisingly helpful. I loved Typescript and it is like TS on steroids. When I get stuff compiling I have so much confidence.
- matthewaveryusa 7y ago>You're doing some awesome lock-free concurrent thing. I can confirm lists are pretty rarely used. The four times I've used a linked list in 10 years of professional programming were: -quick&dirty hashmap in C -threadsafe queue -keeping track of a set of objects that can't be copied ( threads) -LRU cache In C++ at least, the nice thing about a list is you can push/pop in the front/back without a reallocattion or invalidating iterators.
- chongli 7y agoLinked lists are used a lot in game programming where the worst-case behaviour of std::vector and similar structures is undesirable. Linked lists may be slow for a variety of reasons but they're simple and predictable which is very nice when you're trying not to miss the 16.67ms per-frame window.
- estebank 7y agoI thought it was the other way around: games using arrays, non arbitrarily growable vectors to precisely be able to iterate over everything quickly in a deterministic fashion. Specially because a lot of what games have to deal with is "visit every node".
- chongli 7y agoThey use arrays for static vertex, texture, etc. data to send to the GPU. They don't use arrays for things that are being created and destroyed all the time, such as units in a strategy game, they use lists for those things.
- estebank 7y agoBut do they use linked lists for them? I would have assumed you would use an arena for something like that, precisely because you already need to iterate over all of them and can represent any graph as keys into a generational index, so that reading stale keys is trivially handled. Again, I'm not a game dev and this is just my understanding after reading up on these topics after watching https://youtu.be/aKLntZcp27M https://youtu.be/aKLntZcp27M.
- geraldbauer 7y agoA little more light-hearted but the same style to learn Ruby with Entirely Too Many Fizz Buzzes. See https://yukimotopress.github.io/fizzbuzz https://yukimotopress.github.io/fizzbuzz
- winrid 7y agoI'll try this at some point. My first couple forays into Rust made me miss Java and C.
- winrid 7y agoDownvotes by the Rust fanatics again! :) Edit - it's just funny because it always happens. Say anything against Rust - get downvoted. It kind of reminds me of the really hardcore Linux community.
- rascul 7y agoIf you're anything like me, rust was a bit difficult at first due to ownership, lifetimes, traits, and the borrow checker. At some point though, things finally just clicked in my head and now I have the understanding I needed and my difficulties went away. After that point, I began writing safer code in every language because I was using the same ideas that rustc brute forced into my brain. It took probably a few weeks or so before I got it. Now I rarely have (those) issues, and when I do it's probably because I'm trying to do something weird or I was drinking and missed a place where I obviously should have used .clone() or maybe a reference. I'm just a hobby coder though, perhaps at a beginner-intermediate level with a background of writing unsafe python and c. Your mileage may vary.
- winrid 7y agoI guess it just doesn't solve problems for me yet. The problems Rust solves I don't run into. Even with big Java apps with lots of concurrency and crap I hardly shoot myself in the foot. Oh well.
- rascul 7y agoSeems to me that if rust doesn't solve problems you have any better than the other languages at your disposal, it might not be the best choice to solve those problems for you. That is very reasonable to me.
- 7y ago
- Animats 7y agoDoubly-linked lists are hard with Rust's ownership system. I've argued for Rust having backpointers as a built-in type the borrow checker understands. You have to maintain the invariant that if A points to B, B points back to A. A is an owning pointer, and B is a non-owning pointer locked in a relationship with A. Easy to check if the language lets you say that's what you're doing. Rust lacks that. If you have safe backpointers, most tree-type data structures with backpointers can be constructed. A nice feature to have.
- magicalhippo 7y agoAs a non-Ruster, any particular reason they didn't include this? A lot of the code I've done over the years involve graphs, which have a lot of circular pointer and/or backpointers. I find it kinda weird they'd make such a common thing a PITA in a new language.
- habitue 7y agoIt might actually be possible now with Pin. Could anyone actually knowledgeable about this comment?
- renox 7y agoI don't know much about Rust (and nearly nothing about Pin) but if this was true, don't you think someone would already have written a library providing doubly linked list without using unsafe?
- eximius 7y agoRust has a concept of ownership and borrowing. (I think) everything is fine when you just have immutable references everywhere. But as soon as you start taking mutable references (of which only one can exist at a time) or ownership (stronger than mutable references), then cycles break things. You can get around it with Interior Mutability, it's just slightly more verbose. Also, it isn't really that they made an easy thing hard. Properly maintaining the invariants with cyclical references is hard and unsafe. Rust exposes that difficulty in a very literal way
- SAI_Peregrinus 7y agoLots of these comments seem confused about the purpose of this. It's not about using linked lists (that's easy, they're in std::collections), it's about implementing them. So the common non-kernel/embedded use cases are well supported, just use std::collections::LinkedList! But if you're in a no-std context then you might need this.
- Igelau 7y agoA lot of them seem to have not clicked the link and just took the opportunity to demonstrate how much Rust jargon they know.
- wcrichton 7y agoAnother great space of exercises in this vein are in-place operations on binary trees. Specifically, rebalancing [1] proved particularly tricky for my students. I think it's a good litmus test for whether you understand ownership, borrowing, and algebraic data types. [1] http://cs242.stanford.edu/f19/assignments/assign6/#22-bst-interface-40 http://cs242.stanford.edu/f19/assignments/assign6/#22-bst-in...
- pornel 7y agoLearning Rust by writing a linked list is like learning Python by writing a CPython extension. Sure, you'll learn a lot, and it may even be useful, but it's not the typical experience of using the language. I've seen people completely confused that such simple "CS 101" thing is such a mess in Rust. But nobody actually writes linked lists in Rust: • The borrow checker wants to have clear single ownership, and doesn't support reference cycles. Lists happen to have mixed ownership. I'm not sure if it's even possible to prove at compile time that a list will never have a cycle, but it seems at least in the Sufficiently Smart Compiler territory. • Safe linked lists are in the std lib if you really need them, but std has also plenty of other containers that are more efficient on modern hardware. Compile-time safety checks can't prove all valid programs are valid (halting problem). Instead of going after the enormously complex problem, the borrow checker rules are actually pretty simple. It's a feature, not a defect. Simplifying the problem to single ownership with shared-immutable vs exclusive-mutable makes it much easier to reason about borrow checking. If something doesn't fit these rules, you either use a different approach, or use `unsafe`, and then wrap it in a higher-level safe abstraction that fits the model.
- slaymaker1907 7y agoAlso, the way destructors work make it such that most custom linked lists are prone to stack overflows unless they use unsafe.
- umanwizard 7y agoFor what it's worth, this is also true of C++, where the most "natural" way to write a linked list is `struct Node { unique_ptr<Node> next; }`
- Igelau 7y agoI think you missed the point. The guide is fairly upfront about it being a bad idea and a very atypical approach to learning Rust.
- peteretep 7y ago> But nobody actually writes linked lists in Rust It feels entirely like you didn't even start reading this. He spends a whole long first page bitching about Linked Lists and why nobody uses them in Rust.
- naasking 7y agoI think the doubly linked list is to Rust's ownership semantics as the double slit experiment is to Quantum Mechanics: each exposes a seemingly counterintuitive behaviour, and truly understanding why requires a depth of understanding indicative of true mastery.
- 0xdead 7y agoI stopped reading when the author started trashing linked lists. If you don’t like linked lists, just say so instead of stating a lie as a fact.