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.
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.
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'm currently taking a class on API design with Josh Bloch (Java Collections, Effective Java, etc.), who pointed out that this wasn't the case until the late 90s or so - he pulled out an example of a KWIC system [1] described in a paper [2] from 1971:
Parnas 1971: This is a small system [that] could be produced by a good programmer within a week or two.
And then Josh proceeded to show his implementation of the same system, which he had written in <2 hours just by making use of the built-in collections, regular expressions, sorting, string formatting, etc.
It's really cool that these standard data structure implementations exist and are so accessible, making people orders of magnitude faster than before.
[1] https://en.wikipedia.org/wiki/Key_Word_in_Context [2] https://prl.ccs.neu.edu/img/p-tr-1971.pdf
BTW, most times, the problem is not performance, but tight control of memory usage.
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.
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.
'cargo build' vs './configure; apt install something-missing; ./configure; apt install something-missing2; ./configure; make'
As for the specific data structures, I recommend setting aside your knowledge of their utility and consider carefully why they are being criticized. Then run some experiments to convince yourself of what is true. If you come to the conclusion that the criticisms make sense, then you can proceed with the knowledge that the people in question have thought about the issue and came to good decisions. This should inspire hope that they have thought about other issues as well and may have valuable insights.
For the record, I concluded many years ago that some variant on arrays/vectors/whatever outperforms linked lists in most situations by a lot. (There are times when arrays/vectors/whatever can't work. But they are less common than most imagine.) And changes in hardware have made that more true over time. Trees, on the other hand, have a flexibility that lends itself to many problems that it is hard to find other structures for many use cases. But even so if performance is critical, it is worth jumping through a lot of hoops to make sure that all of the pointers that make up a tree are physically close together in memory to improve the efficiency of your caches.
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.
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.
For example LevelDB (which is conceptually based on Google BigTable's design) looks a lot like a balancing tree in its access patterns, but is a lot faster than a variety of alternatives. And it is faster in part because sequential data is stored sequentially in order instead of using a data structure that results in random access patterns.
And no. It doesn't use linked lists.
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.
Not explicitly, but they concern themselves with worst-case performance, and tolerable worst-case performance implies security against a certain class of attacks (like HashDoS).
And yes, elementary data structures concern themselves with such things all the time - because, regardless of how they "must" be used, in practice they do get used on untrusted inputs on the time, simply because it's the easiest thing. Have you noticed how many languages and standard libraries have switched to random seeds for their hash tables lately?
And no, it's not true that you're going to "have a bad time regardless of the data structure". You're not going to have a bad time with an RB tree, regardless of where your inputs for keys come from - because it is a data structure that doesn't have a quirk of extremely bad perf on pathological inputs.
> 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.
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.
Linked list is definitely sequential (it's a list!), and it can even be sequentially allocated in memory, depending on allocator implementation.
There can be sequential and non-sequential implementations of ADTs.
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 to test and make sure the gains were worth it.
Putting things in an array works around all of that (unless you need to handle tombstones)
The promise of a linked list is being able to iterate and make constant-time insertions/deletions wherever you want. But the more such mutations occur, the more fragmented your memory will end up, and the more you'll get hit by the cache issues—especially if your list is large, exactly where the purported benefits of a linked list are strongest.
Not if the nodes are variable-sized.
Which is really just the cache doing its job. The linked-list anti-pattern is when you're constantly paging in big speculative chunks of memory only to access a single pointer and then move on.
Not relevant to rust, no?