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

41–50 of 179 posts

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

#41

Post by varjag »

saagarjha wrote: post #21
throwaway17_17 wrote: post #19

Earlier quoted context omitted.

The quote that the GP is talking about is included below, which copy/pasted from the project page, and the Mumble mumble line is the heading for a paragraph: ‘’’Mumble mumble kernel embedded something something intrusive. It's niche. You're talking about a situation where you're not even using your language's runtime. Is that not a red flag that you're doing something strange? It's also wildly unsafe.’’’ Also, prior…

Kernel development is niche. Most of the time you don’t need linked lists.

When all you have is Rust everything starts to look like adjustable array.

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

#42

Post by Tuna-Fish »

varjag wrote: post #40
Dylan16807 wrote: post #38

Earlier quoted context omitted.

Linked lists are inherently niche on modern hardware.

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.

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

#43

Post by yazaddaruvala »

varjag wrote: post #40
Dylan16807 wrote: post #38

Earlier quoted context omitted.

Linked lists are inherently niche on modern hardware.

Seriously? Are trees also niche?

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 or in very special cases when benchmarks provide hard data to use a Linked List.

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

#45

Post by varjag »

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.

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.

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

#46

Post by saagarjha »

varjag wrote: post #41
saagarjha wrote: post #21

Earlier quoted context omitted.

Kernel development is niche. Most of the time you don’t need linked lists.

When all you have is Rust everything starts to look like adjustable array.

What’s an adjustable array? A vector?

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

#47

Post by varjag »

yazaddaruvala wrote: post #43
varjag wrote: post #40

Earlier quoted context omitted.

Seriously? Are trees also niche?

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.

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

#48

Post by varjag »

saagarjha wrote: post #46
varjag wrote: post #41

Earlier quoted context omitted.

When all you have is Rust everything starts to look like adjustable array.

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.

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

#49

Post by Dylan16807 »

varjag wrote: post #40
Dylan16807 wrote: post #38

Earlier quoted context omitted.

Linked lists are inherently niche on modern hardware.

Seriously? Are trees also niche?

What kind of tree? A binary tree isn't great for many uses, and doesn't excel at much. But a nice fat B+ tree removes the vast majority of pointer-chasing latency.
Post reply on HN