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

151–160 of 179 posts

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

#151

Post by peteretep »

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…

> But nobody actually writes linked lists in Rust

It feels entirely like you didn't even start reading this. He spends a whole long first page bitching about Linked Lists and why nobody uses them in Rust.

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

#152

Post by aw1621107 »

dmitrygr wrote: post #150
dodobirdlord wrote: post #114

Earlier quoted context omitted.

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…

> It is like you have never heard of caches

But isn’t that part of the point of putting nodes into an array? So the nodes are guaranteed to sit next to each other in memory, and so are quite likely to be in cache?

> do not understand that modern CPUs have multiple special prefetchers for pointer chasing and no prefetchers for "rust fanatics"

Doesn’t array indexing reduce down to pointer chasing anyways? Or are you saying that the prefetchers can’t see through “nested” array accesses (e.g. nodes[nodes[i].out[0]].data vs node.out[0].data)?

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

#153

Post by dmitrygr »

aw1621107 wrote: post #152
dmitrygr wrote: post #150

Earlier quoted context omitted.

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

> It is like you have never heard of caches But isn’t that part of the point of putting nodes into an array? So the nodes are guaranteed to sit next to each other in memory, and so are quite likely to be in cache? > do not understand that modern CPUs have multiple special prefetchers for pointer chasing and no prefetchers for "rust fanatics" Doesn’t array indexing reduce down to pointer chasing anyways? Or are you sa…

Yes that is what I am saying. See Intel manuals for patterns they can detect. Mostly it is strided accesses and use of pointers at fixed offsets of a structure which the previous pointer pointed to.

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

#154

Post by aw1621107 »

dmitrygr wrote: post #153
aw1621107 wrote: post #152

Earlier quoted context omitted.

> It is like you have never heard of caches But isn’t that part of the point of putting nodes into an array? So the nodes are guaranteed to sit next to each other in memory, and so are quite likely to be in cache? > do not understand that modern CPUs have multiple special prefetchers for pointer chasing and no prefetchers for "rust fanatics" Doesn’t array indexing reduce down to pointer chasing anyways? Or are you sa…

Yes that is what I am saying. See Intel manuals for patterns they can detect. Mostly it is strided accesses and use of pointers at fixed offsets of a structure which the previous pointer pointed to.

So I guess it comes down to whether the graph would fit into cache and the particulars of the access patterns? If the graph fits into cache as an array the prefetchers would be more or less unnecessary since everything is already there. Beyond that, I probably don’t have enough experience or knowledge to make a good guess.

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

#155

Post by dmitrygr »

aw1621107 wrote: post #154
dmitrygr wrote: post #153

Earlier quoted context omitted.

Yes that is what I am saying. See Intel manuals for patterns they can detect. Mostly it is strided accesses and use of pointers at fixed offsets of a structure which the previous pointer pointed to.

So I guess it comes down to whether the graph would fit into cache and the particulars of the access patterns? If the graph fits into cache as an array the prefetchers would be more or less unnecessary since everything is already there. Beyond that, I probably don’t have enough experience or knowledge to make a good guess.

Yes. If the entire thing fits yes, but then it is small enough that you might as well manage it in Basic or JavaScript. No real programming required

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

#156

Post by Dylan16807 »

viraptor wrote: post #145
mikepurvis wrote: post #113

Earlier quoted context omitted.

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)

A reasonable allocator should already be grouping allocations of similar size together. In a whole lot of cases this means your metadata is no more than a single byte per object, and the padding is no more than you'd have inside an array.

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

#157

Post by johnisgood »

grok22 wrote: post #91
pas wrote: post #80

Earlier quoted context omitted.

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

Yeah, and there is a reason for why there are not many "industry-standard libraries for common data-structures" out there in C. I think the reason (or one of the reasons) is that there are zillions of ways to implement them, and "one size does not fit all". I often have to ditch the standard library's implementation of this and that in other languages, too, because they are not fine-tuned enough for my use case.

That said, there are lots and lots of C libraries installed by default on Linux distributions (via the distribution's own package manager!) that are reused by other projects.

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

#158

Post by dntbnmpls »

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.

I wouldn't say niche. B-trees and B+ trees with doubly linked lists connecting the leaf nodes are used in every major database server for indexes. Hash tables are generally used by optimizers to handle unindexed data in queries. Doesn't make hash tables niche.

> and is already at the point where frequently linearly copying kilobytes of arrays is almost always faster than using a linked list.

That's only half the story. Sure reading arrays in sequential order is fast. What about inserting or deleting items within an array? What are the costs to having to constantly resize arrays? It is very expensive.

At the end of the day, it's about finding the right data structure for the data and your needs.

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

#159

Post by johnisgood »

rascul wrote: post #127
pas wrote: post #80

Earlier quoted context omitted.

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?

With rust and cargo it's often trivial to use a third party lib from a centralized location that has a rich collection of submitted libs to choose from. It's also fairly easy with python/pip and node/npm. There's nothing quite like it on the same scale and as widely used with c/c++, which means it's more difficult to pull in third party libs. It's often easier to just implement the stuff yourself. Or at least that's…

> There's nothing quite like it on the same scale and as widely used with c/c++

I use my Linux distribution's package manager. It works fine for C, and it is fairly easy, too. You only have to learn to use one package manager; your system's package manager. Plus I am totally fine with "reinventing the wheel" if that wheel is just 2 lines of code. :)

Heck, I would even go out on a limb here and claim that it is on the same scale and as widely used with C as it is with Rust or Python, if not more. A typical Linux distribution contains quite a lot of C libraries alone upon which other projects written in C (or other languages, for that matter) depend. If the program you install via your system's package manager depends on a C library, it will get installed (obviously), and it is often reused by many other programs. Most C developers I know have the tendency to make their program depend on as fewer dependencies as possible. "Zero dependencies" is usually a "feature" or a selling point, and a good one at that, IMO. I prefer this over having a package manager for all programming languages separately, depending on over 300 dependencies of which 80% is just 2-10 lines of code and so forth. Additionally, take for example this: if I want to cargo build two projects that depend on the same crate, it fetches and builds it twice, or at least it did a year ago. I found it to be odd. It is a waste of space and time. There are ways to solve this.

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

#160

Post by winrid »

rascul wrote: post #137
winrid wrote: post #133

Earlier quoted context omitted.

I guess it just doesn't solve problems for me yet. The problems Rust solves I don't run into. Even with big Java apps with lots of concurrency and crap I hardly shoot myself in the foot. Oh well.

Seems to me that if rust doesn't solve problems you have any better than the other languages at your disposal, it might not be the best choice to solve those problems for you. That is very reasonable to me.

Right! Also I suppose I'm feeling very disagreeable today. :)
Post reply on HN