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

141–150 of 179 posts

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

#141

Post by int_19h »

saagarjha wrote: post #134
int_19h wrote: post #96

Earlier quoted context omitted.

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.

But that would still happen at the point of dereference, no? Or does it allow to tag even operations like moves and adds?

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

#142

Post by int_19h »

deckard1 wrote: post #97
int_19h wrote: post #93

Earlier quoted context omitted.

A hash table is vulnerable to collision attacks, if keys are derived from any kind of untrusted external input. Trees might be slow, but they're consistently slow.

non sequitur. No one mentioned security, nor do any elementary data structures concern themselves with such higher level things. If you're allowing unlimited untrusted data to control internal data structures, you're going to have a bad time regardless of which data structure you're using.

Security is a thing that is implicitly pervasive. If it doesn't apply, that should be explicit.

And yes, elementary data structures concern themselves with such things all the time - because, regardless of how they "must" be used, in practice they do get used on untrusted inputs on the time, simply because it's the easiest thing. Have you noticed how many languages and standard libraries have switched to random seeds for their hash tables lately?

And no, it's not true that you're going to "have a bad time regardless of the data structure". You're not going to have a bad time with an RB tree, regardless of where your inputs for keys come from - because it is a data structure that doesn't have a quirk of extremely bad perf on pathological inputs.

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

#143

Post by Igelau »

SAI_Peregrinus wrote: post #101

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

A lot of them seem to have not clicked the link and just took the opportunity to demonstrate how much Rust jargon they know.

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

#144

Post by School-Cotton »

slaymaker1907 wrote: post #135
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.

For 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 next; }`

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

#145

Post by viraptor »

mikepurvis wrote: post #113
estebank wrote: post #110

Earlier quoted context omitted.

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…

A bigger saving is in the allocation metadata. Every time you allocate something on the heap, you also need to save information about the size, maybe some flags and padding to align on a page. And if the entries are small, you also get better cache locality.

Putting things in an array works around all of that (unless you need to handle tombstones)

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

#146

Post by naasking »

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

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

#147

Post by jfkebwjsbx »

Jasper_ wrote: post #124
estebank wrote: post #95

Earlier quoted context omitted.

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

An array of pointers you call a virtual method on is indistinguishable in "pointer-chase" time (with current caches, at least), to an embedded linked list. Embedded linked lists have better insertion/deletion costs, and are easier to manage, so they're used quite frequently in games.

That model (bag of polymorphic objects) is avoided nowadays in everything from games to simulation software.

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

#148

Post by jfkebwjsbx »

chongli wrote: post #98
estebank wrote: post #95

Earlier quoted context omitted.

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

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

No, they don't. You are talking about the state of affairs 20 years ago.

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

#149

Post by jfkebwjsbx »

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…

You are wrong in several fronts:

+ Linked lists are a thing of the past.

+ Game engines use complex data structures and algorithms. Some are cutting-edge research implemented from papers, specially in graphics.

+ A generational index is not complex.

Yes, game development (as opposed to game engine development or video/audio rendering) is a mess. That does not mean the actual technical fields involved are simple.

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

#150

Post by dmitrygr »

dodobirdlord wrote: post #114
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.

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…

> 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

Rust practitioners keep proposing this solution. It is like you have never heard of caches or do not understand that modern CPUs have multiple special prefetchers for pointer chasing and no prefetchers for "rust fanatics"

This solution will be SIGNIFICANTLY slower on any modern CPU. By a wide margin! Since you'll keep having to wait for main memory as the cache prefetchers have no idea about this insane scheme and will not prefetch the data for you. They will for actual pointers.

Post reply on HN