Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Learn Rust with entirely too many linked lists (2019)

rust-unofficial.github.io

Post reply on HN
Print view View original

111–120 of 179 posts

Re: Learn Rust with entirely too many linked lists (2019)

#111

Post by mikepurvis »

chapium wrote: post #105
Animats wrote: post #73

Earlier quoted context omitted.

Yes. Lists were fine when memory was random-access. Today, if you're linking all over memory, cache misses dominate performance. So contiguous data structures are preferred.

This isn't a linked list issue at all, but a problem with constructing the nodes. If you construct list nodes in a contiguous location cache misses are a non issue.

But that's fundamentally a function of the usage pattern. If the usage is "construct a bunch of nodes" and then nothing, then you should be using a vector-type structure anyway.

The promise of a linked list is being able to iterate and make constant-time insertions/deletions wherever you want. But the more such mutations occur, the more fragmented your memory will end up, and the more you'll get hit by the cache issues—especially if your list is large, exactly where the purported benefits of a linked list are strongest.

Re: Learn Rust with entirely too many linked lists (2019)

#113

Post by mikepurvis »

estebank wrote: post #110
chapium wrote: post #105

Earlier quoted context omitted.

This isn't a linked list issue at all, but a problem with constructing the nodes. If you construct list nodes in a contiguous location cache misses are a non issue.

That's no longer a linked list, it's a vector.

I think the argument is that if the nodes are fixed size then you can preallocate a big block of them slab-style, and for the pointers you just use indexes into that array rather than "real" pointers.

Potentially there's a small memory savings as well if you can use 2 or 4 bytes for the index instead of a full 8 byte pointer. But you're taking on a lot of complexity and tuning by going this route so you'd really have to test and make sure the gains were worth it.

Re: Learn Rust with entirely too many linked lists (2019)

#114

Post by dodobirdlord »

magicalhippo wrote: post #90
Animats wrote: post #88

Doubly-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 b…

As 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.

Rust's ownership rules aren't for the purpose of making the user's life hard, they are the least restrictive system that could be devised that allow the compiler to uphold Rust's safety guarantees. It was not too long ago that it was common knowledge that a programming language either has a garbage collector or has manual memory management, or possible both. Safe Rust has neither, but not without the effect of making awkward certain kinds of programming that are fundamentally difficult to make safe.

The Rust question to ask here is: Do you really need pointers, specifically? Or would some other reference mechanism work? You could put all of your graph nodes into a linear data structure like an array, and have them point to each other by holding a list of indices instead of a list of pointers. Or you could give all of your nodes unique keys and keep them in a table, and have them hold references to each other by key. The compiler will not try to prove the correctness of your graph algorithm, and in the event of programmer error that leads to dangling references your program will have to handle the scenario of following an index or a key and not finding a value, so bugs will not introduce memory unsafety.

There's also ongoing work on memory arenas in the nightly compiler, and I believe some libraries. Putting a graph into an arena is a good way to appease the compiler, because the entire arena will be freed at the same time, ensuring that hanging pointers will never exist between graph nodes.

Re: Learn Rust with entirely too many linked lists (2019)

#115

Post by wcrichton »

Another 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-in...

Re: Learn Rust with entirely too many linked lists (2019)

#116

Post by lrem »

magicalhippo wrote: post #90
Animats wrote: post #88

Doubly-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 b…

As 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.

In your graph, the nodes are not owning each other, are they?

Re: Learn Rust with entirely too many linked lists (2019)

#117

Post by dodobirdlord »

grok22 wrote: post #63
jasondclinton wrote: post #12

I 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`.

I am learning Rust due to it's memory safety features and comments like this rub me the wrong way for some reason -- they give me an uneasy feeling that I will run into unexpected limitations in the language because these corners are not exercised enough. Because people who know the language are saying that the kind of data-structures that I deal with day in and out in my day-to-day work are not the "preferred" thing…

Linking my comment from elsewhere.

https://news.ycombinator.com/item?id=22393723

Re: Learn Rust with entirely too many linked lists (2019)

#118

Post by Animats »

magicalhippo wrote: post #90
Animats wrote: post #88

Doubly-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 b…

As 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.

This is an enforced invariant. This results in proposals that it should be done by adding a system for general invariants and design by contract features. Those are then rejected as too complicated and something for the far future.

So, the usual answer is "use unsafe code." What could possibly go wrong?

Re: Learn Rust with entirely too many linked lists (2019)

#119

Post by moth-fuzz »

magicalhippo wrote: post #90
Animats wrote: post #88

Doubly-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 b…

As 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.

Historically, the classic graph structures are adjacency lists and adjacency matrices. Those are quite easy to represent in Rust if you use indices instead of pointers. Node/Pointer type graph structures aren't particularly efficient anyway, even in C or C++.

Re: Learn Rust with entirely too many linked lists (2019)

#120

Post by magicalhippo »

lrem wrote: post #116
magicalhippo wrote: post #90

Earlier quoted context omitted.

As 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.

In your graph, the nodes are not owning each other, are they?

No, but they do point to each other. For example, each node can have an array of all the edges, and each edge has two pointers to each node it connects. Via this you can walk around cycles for example. And typically these can change when nodes are inserted or removed.
Post reply on HN