Learn Rust with entirely too many linked lists (2019) • Hacker News Board

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

#131

Post by ssalazar » Sun, Feb 23, 2020, 12:06 AM UTC

chongli wrote: post #123

estebank wrote: post #100

Earlier quoted context omitted.

But 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…

They certainly used linked lists all over the place in StarCraft, WarCraft, and Diablo [1]. I don't know that many game developers would use complicated data structures like the one you've described here. Linked lists are fantastic for insertion/removal in arbitrary places. Game development is not really about showing off with cutting-edge CS research, it's about getting things done. Maybe your arenas with generation…

Arenas aren't "cutting edge CS research," theyre used widely in latency-sensitive applications like gaming. This article [1] describes how to implement one for a game engine. Basic versions are easy to understand and provide good results.

Starcraft/etc. are 20+ year old games and software development patterns as well as gaming hardware have changed in fundamental ways since then. Conventional wisdom nowadays is that cache misses on every list iteration are a lot worse than shuffling a few contiguous bytes around or marking things inactive when removing items.

[1] https://www.gamasutra.com/blogs/MichaelKissner/20151104/2582...

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

#132

Post by rascul » Sun, Feb 23, 2020, 12:13 AM UTC

winrid wrote: post #87

I'll try this at some point. My first couple forays into Rust made me miss Java and C.

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

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

#133

Post by winrid » Sun, Feb 23, 2020, 1:02 AM UTC

rascul wrote: post #132

winrid wrote: post #87

I'll try this at some point. My first couple forays into Rust made me miss Java and C.

If 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 wee…

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

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

#134

Post by saagarjha » Sun, Feb 23, 2020, 1:13 AM UTC

int_19h wrote: post #96

zozbot234 wrote: post #79

Earlier quoted context omitted.

> No modern systems have such trap representations for pointer types This may be incidentally true, but "address sanitizer"-like features are becoming more common on modern hardware, and while these do not currently trap on creation / manipulation of a 'wild' pointer (since, strictly speaking, a trap only happens on dereferencing), there's no solid reason to expect this to remain the case in the future.

I don't see how you could trap creation or manipulation, since those pointers are stored in registers and/or memory, and both are fundamentally untyped. How would the hardware even know that something is a pointer, on any architecture that is popular today?

Because you use typed instructions to access them. For example, on ARM with pointer authentication you’ll sign pointers and unsign them right before using them. If you forge a pointer it’ll cause a crash when it’s used because its signature will be incorrect.

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

#135

Post by slaymaker1907 » Sun, Feb 23, 2020, 1:14 AM UTC

pornel wrote: post #126

Learning 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…

Also, the way destructors work make it such that most custom linked lists are prone to stack overflows unless they use unsafe.

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

#136

Post by mikepurvis » Sun, Feb 23, 2020, 1:18 AM UTC

Jasper_ wrote: post #125

mikepurvis wrote: post #111

Earlier quoted context omitted.

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 issu…

> If the usage is "construct a bunch of nodes" and then nothing, then you should be using a vector-type structure anyway. Not if the nodes are variable-sized.

Again it depends a lot on the usage pattern. If you're going to be dereferencing a pointer off to some allocated-elsewhere object on every little operation or comparison then sure. But if there are sorts or searches or other operations that can take place against a fixed-size "index" object, then it may still make sense to have a vector-like or pre-allocated pool of those objects and only pay the cache hit cost when you do major operations on a particular instance.

Which is really just the cache doing its job. The linked-list anti-pattern is when you're constantly paging in big speculative chunks of memory only to access a single pointer and then move on.

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

#137

Post by rascul » Sun, Feb 23, 2020, 1:51 AM UTC

winrid wrote: post #133

rascul wrote: post #132

Earlier quoted context omitted.

If 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 wee…

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

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

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

#138

Post by Narishma » Sun, Feb 23, 2020, 1:51 AM UTC

chongli wrote: post #123

estebank wrote: post #100

Earlier quoted context omitted.

But 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…

They certainly used linked lists all over the place in StarCraft, WarCraft, and Diablo [1]. I don't know that many game developers would use complicated data structures like the one you've described here. Linked lists are fantastic for insertion/removal in arbitrary places. Game development is not really about showing off with cutting-edge CS research, it's about getting things done. Maybe your arenas with generation…

Those are pretty old games written when caches were small and the CPU-memory speed gap wasn't as large as it is today.

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

#139

Post by Igelau » Sun, Feb 23, 2020, 2:03 AM UTC

pornel wrote: post #126

Learning 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…

I think you missed the point. The guide is fairly upfront about it being a bad idea and a very atypical approach to learning Rust.

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

#140

Post by Igelau » Sun, Feb 23, 2020, 2:11 AM UTC

kybernetikos wrote: post #58

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

This Gonzo approach of running headlong into a bad idea is refreshing.