[Lev1a]

Seriously, what is this fascination with linked lists?

In comparison to array-based lists they're: - less memory-efficient, - do not allow random-access, - worse for cache locality (so can be up to orders of magnitude slower) and - more complex.

They are nice to learn some principles in the context of an Intro to FP course but apart from that, meh.

[jnordwick]

The linked list is just an lowest common denminator example. I think he and others (and me when I bring it up) mean mutually linking data strauctures.

Almost any kind of data structure in Rust is extremely painful to do efficiently. You either go the unsafe route of you drowned in a sea of boxes and cells.

On Reddit recently somebody gave the ludicrous claim that you shouldn't have to write your own data structures in rust - the rust system library should have everything you need.

[roca]

On the real, large projects I have worked on for years (Firefox, rr, Pernosco) in C++ and Rust I have spent negligible time writing container data structures. Of course I create data structures, but almost always by combining hashtables, arrays and smart pointers and occasionally something more exotic from a library.

It's unfortunate that a lot of teaching programmer has people implement data structures from scratch. It gives the false impression that that's what programming is largely about.

[jnordwick]

Maybe the project should have implemented more from scratch instead of cobbling together some Frankenstein data structure (and Firefox wouldn't be such a massive memory hog with poor performance)?

I guess it really depends on your job, skill level, and mentality. While I do use a lot of off the shelf pieces, their relationships don't always it neatly and shoehorning them can cause performance issues. (I'm not going to pay for a double indirection when I can avoid it entirely).

But then again, I think this cookie-cutter approach to software is poor craftsmanship and often results in bloated, slow code that is way larger than it needs to be. I want to write something better than everybody else, not just make the same paint-by-numbers piece everybody else does.

[roca]

I have a PhD in computer science from CMU, I have published many academic papers, and I was a distinguished engineer at Mozilla. The issue isn't skill level.

Randomly lashing out at Firefox is silly, especially at this time when it's getting so much praise for performance compared to Chrome. Firefox does indeed contain some complex, micro-optimized data structures for its core data (e.g. the CSS fragment tree and the DOM). It's just that it also contains a lot more code besides.

You wouldn't use an off-the-shelf hashtable to implement the mapping from a DOM node to its attributes. You should use an off-the-shelf hashtable to track, say, the set of images a document is currently loading. Like any kind of optimization, you optimize your data structures where it matters and you write simple, maintainable code everywhere else.

[jnordwick]

Slow down there turbo. Nobody said anything about your skill (although PhD doesn't particularly mean a talented developer - some of the worst code ive seen come from cs phds where some only understand the highest polynomial in big-o but forget the other factors). And nobody cares a cent about you getting whatever award from moz.

A said anything about optimizing in inappropriate areas (honestly, what did you get that from). This entire thread started because somebody didn't understand why people often user linked list as an example of something difficult in rust.

> Of course I create data structures, but almost always by combining hashtables, arrays and smart pointers and occasionally something more exotic from a library.

But that does scream "I don't really do a lot of performance oriented work". That you can somehow cobble together an apple out of a banana and a cat by probably using a metric ton of boxes and refcounts (that are just used to get around the borrow checker) doesn't surprise me if you are willing to make the readability and performance sacrifices.

[kspp]

> Maybe the project should have implemented more from scratch instead of cobbling together some Frankenstein data structure (and Firefox wouldn't be such a massive memory hog with poor performance)?

Sorry, but what is that supposed to mean? Have you looked at Chromium's (or any other modern browsers') memory usage? Firefox is timid compared to it, and always has been so. Maybe it's not due to the browser engineers' low skill level, but due to the enormous complexity of modern web? It's a separate operating system on top of your operating system.