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

91–100 of 179 posts

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

#91

Post by grok22 »

pas wrote: post #80
grok22 wrote: post #63

Earlier quoted context omitted.

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…

Do you currently use C? C++ perhaps? I mean basically no other language that currently comes to mind fiddles so much with the basics. In Rust, just as in Java, people write highly optimized safe and fast data structures and others build upon that. In C/C++ it seems every project reinvents the wheel to a large degree. Or am I mistaken?

I use C. And you are right, in my field there is a tendency to a large degree to re-invent the wheel of data-structures :-). Sometimes justified, but most times not. But mostly because C doesn't usually have well-known, industry-standard libraries for common data-structures. Or even if they do, it's kind of trivial to implement basic data-structures (not saying they will be bug-free!) instead of relying on some random distribution of a library from the Internet.

BTW, most times, the problem is not performance, but tight control of memory usage.

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

#92

Post by varjag »

dpbriggs wrote: post #89
varjag wrote: post #77

Earlier quoted context omitted.

I mean a multi-dimensional array.

Thanks! Why does everything look like a multi-dimensional array for you in rust?

An array (an ADT) can be arbitrary dimensional, with one-dimensional case often called vector (and two-dimensional called matrix). An array can also be adjustable, both in one and multi-dimension variants.

So a vector can be both adjustable and non adjustable, and some language do have both versions. Some language have adjustable one-dimensional array/vector as the only dynamic aggregate/ordered datatype.

And to answer the post I replied to originally, a vector in rust is a one-dimensional adjustable array. To answer your question above, no that's not what I meant, sorry for not being clear enough from the beginning.

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

#93

Post by int_19h »

Tuna-Fish wrote: post #42
varjag wrote: post #40

Earlier quoted context omitted.

Seriously? Are trees also niche?

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

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.

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

#94

Post by int_19h »

pas wrote: post #80
grok22 wrote: post #63

Earlier quoted context omitted.

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…

Do you currently use C? C++ perhaps? I mean basically no other language that currently comes to mind fiddles so much with the basics. In Rust, just as in Java, people write highly optimized safe and fast data structures and others build upon that. In C/C++ it seems every project reinvents the wheel to a large degree. Or am I mistaken?

It is definitely not the case for C++. It has a decent standard library - when it comes to collections, richer than many other languages, in fact - and then there's Boost for more exotic needs.

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

#95

Post by estebank »

chongli wrote: post #84
matthewaveryusa wrote: post #78

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

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

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

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

#96

Post by int_19h »

zozbot234 wrote: post #79
Hello71 wrote: post #60

Earlier quoted context omitted.

Allegedly, some platforms have pointer trap representations, where a certain pointer can be created, but may not be used in any operations of that type. No modern systems have such trap representations for pointer types, but the C standard inherits their legacy, and, more importantly, C compilers use it as justification for certain types of optimizations. Since it's not a hardware limitation, Rust can perfectly well…

> 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?

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

#97

Post by deckard1 »

int_19h wrote: post #93
Tuna-Fish wrote: post #42

Earlier quoted context omitted.

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

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.

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

#98

Post by chongli »

estebank wrote: post #95
chongli wrote: post #84

Earlier quoted context omitted.

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

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.

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

#99

Post by habitue »

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.

It might actually be possible now with Pin. Could anyone actually knowledgeable about this comment?

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

#100

Post by estebank »

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.

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.

Post reply on HN