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

71–80 of 179 posts

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

#71

Post by jdsully »

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…

The comment applies word for word to C++ as well. Linked lists are just bad datastructures for modern CPUs.

I don’t use rust so I can’t speak to the quality of the std lib, but I don’t think its fair to use the parent comment as evidence either way.

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

#72

Post by varjag »

staticassertion wrote: post #52
varjag wrote: post #45

Earlier quoted context omitted.

If your data/algorithm calls for a certain dynamic structure, let's say a red-black tree, replacing it with array is pointless. Last time I looked, kobjects in Linux kernel were still dynamically linked in a bunch of ways, and tree-like data structures are widely used.

I think it's probably fair to call kernel development niche? And the fact that Linux uses linked lists a lot is not necessarily a strong case for linked lists, but just a matter of very specific constraints - like perhaps not wanting to optimize too much for underlying hardware?

I used Linux kernel as an example of easily accessible, extremely well known, performance tuned open source project. Of course dynamic data structures are used in countless other applications, like DBMS, web servers and web browsers. Really in nearly any non-trivial codebase.

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

#73

Post by Animats »

Dylan16807 wrote: post #38
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`.

Linked lists are inherently niche on modern hardware.

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.

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

#74

Post by varjag »

adrianN wrote: post #53
varjag wrote: post #45

Earlier quoted context omitted.

If your data/algorithm calls for a certain dynamic structure, let's say a red-black tree, replacing it with array is pointless. Last time I looked, kobjects in Linux kernel were still dynamically linked in a bunch of ways, and tree-like data structures are widely used.

Sure, but algorithms that explicitly need a linked structure for performance are very few compared to algorithms that have the same or better asymptotic with a hash and a vector or for which the input sizes are such that the large constants pointer chasing causes don't make up for worse asymptotics.

If the algorithm calls for a balancing tree, you'd end up re-implementing it across of bunch of (linked) hash tables or over an array treated like a heap. Explicitly, or if one does not know what they are doing, implicitly. In either case you would have no performance advantage.

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

#75

Post by dpbriggs »

varjag wrote: post #48
saagarjha wrote: post #46

Earlier quoted context omitted.

What’s an adjustable array? A vector?

A vector is a one-dimensional array. Adjustable arrays can have arbitrary number of dimensions, although am not sure if it's a thing in Rust.

I've spent years programming rust and I'm not sure what you mean. Do you mean arrays of tuples, or nested arrays?

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

#76

Post by dpbriggs »

varjag wrote: post #47
yazaddaruvala wrote: post #43

Earlier quoted context omitted.

Trees and Lists are types of data structures. Both are very useful in all contexts. Linked List is a special kind of List. It typically implies a non-sequential data layout. With all of the modern layers of abstraction, non-sequential memory access typically means poor cache friendliness, i.e. poor performance. Hopefully that helps explain why Linked Lists are considered niche, I.e. specific to embedded programming o…

Tree is a special case of a linked list. Linked list is definitely sequential (it's a list!), and it can even be sequentially allocated in memory, depending on allocator implementation.

That's not necessary true. You can implemented binary trees as an array, so are trees a special case of arrays?

There can be sequential and non-sequential implementations of ADTs.

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

#77

Post by varjag »

dpbriggs wrote: post #75
varjag wrote: post #48

Earlier quoted context omitted.

A vector is a one-dimensional array. Adjustable arrays can have arbitrary number of dimensions, although am not sure if it's a thing in Rust.

I've spent years programming rust and I'm not sure what you mean. Do you mean arrays of tuples, or nested arrays?

I mean a multi-dimensional array.

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

#78

Post by matthewaveryusa »

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

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

#79

Post by zozbot234 »

Hello71 wrote: post #60
aw1621107 wrote: post #51

Earlier quoted context omitted.

> AIUI, there are some hardware architectures where even creating a wild pointer might be undefined behavior, regardless of whether that pointer is subsequently dereferenced Would you be able to point me to some references for such hardware? Im not sure how that would work (at least based on my admittedly limited amount of experience). Wouldn’t a pointer look like any other integer right up until it’s used as a memor…

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.

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

#80

Post by pas »

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…

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?

Post reply on HN