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

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

#61

Post by btilly » Sat, Feb 22, 2020, 6:31 PM UTC

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.

...time it takes to chase a random pointer compared to doing literally anything else...

When I have had to do serious stuff with linked lists, trees, and so on, I found that it was much, much faster to assign an array of nodes, and allocate the linked list out of that close together. There was a lot of complexity in doing so but colocating data to match my access pattern was a big win.

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

#62

Post by monadic2 » Sat, Feb 22, 2020, 6:38 PM UTC

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

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

Not relevant to rust, no?

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

#63

Post by grok22 » Sat, Feb 22, 2020, 6:43 PM UTC

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

I do system software/networking software and I deal with a lot of linked lists and trees and these comments make me feel that Rust may not be a good language for my use-case in-spite of me wanting the memory safety features.

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

#64

Post by monocasa » Sat, Feb 22, 2020, 6:52 PM UTC

robbyt wrote: post #5

ajross wrote: post #2

> Mumble mumble kernel embedded something something intrusive. And this is why kernel/embedded/something/something developers don't take Rust as seriously as you want them to. You can't simultaneously declare your language the best choice for system software development and treat the long-evolved patterns of those paradigms as a joke. There are very good reasons for intrusive data structures, not least of which being…

To explain what I think this comment means. When working on embedded systems, you can interact with hardware devices by writing directly to specially mapped memory areas. E.g., if you want to write text to a small screen, the kernel driver gives you a memory region that you write bytes to, and they're shown on the screen immediately, without requiring the CPU.

They're saying more that intrusive data structures are really nice in situations that restrict heap allocation. The memory overhead outside of the structures linked together is O(1), because all of the per object metadata is stored in the objects themselves. That means consumers generally don't have to be hardcoded for certain number of objects like you would for an array/vector that doesn't have access to a heap.

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

#65

Post by steveklabnik » Sat, Feb 22, 2020, 6:54 PM UTC

monadic2 wrote: post #62

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

> 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`. Not relevant to rust, no?

That is true of Rust. The linked list is bad though, even irrespective of this argument about the utility of lists.

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

#66

Post by mkesper » Sat, Feb 22, 2020, 6:55 PM UTC

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…

It's just not needed to implement trivial data structures by yourself if it's already implemented before. Also linked lists might be sub-optimal, see other comments.

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

#67

Post by senderista » Sat, Feb 22, 2020, 6:57 PM UTC

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, along with binary trees, but there are cache-friendly alternatives like unrolled linked lists and B-trees.

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

#68

Post by zackify » Sat, Feb 22, 2020, 7:03 PM UTC

Can’t wait to follow this. I’ve been going through the official book these past couple weeks. As someone who’s never used systems languages (mainly a js / node person) I was able to write a redis-like database quickly on top of TCP. I’ve also picked up async / await and how it works in rust.

There’s so much to learn but the compiler is surprisingly helpful. I loved Typescript and it is like TS on steroids. When I get stuff compiling I have so much confidence.

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

#69

Post by varjag » Sat, Feb 22, 2020, 7:05 PM UTC

staticassertion wrote: post #57

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.

That just sounds like a graph.

How in the heaven an array can sound like a graph?

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

#70

Post by fluffy87 » Sat, Feb 22, 2020, 7:06 PM UTC

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.

Rust has singly linked, double linked ( in its minimal std library) and intrusive linked lists - all with APIs that guarantee a lack of memory errors and data races at compiler. I don’t know any good kernel developer that wouldn’t like those guarantees and I work in the Linux kernel professionally full time.