8 ms·

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 t

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

Dylan16807 7y ago
Linked lists are inherently niche on modern hardware.
- varjag 7y ago
  Seriously? Are trees also niche?
  - Dylan16807 7y ago
    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.
    - kybernetikos 7y ago
      I've got quite keen on B+ trees. It seems like the world where we had fast main memory and slow drive storage is not very different to the world where we have fast cache memory and slow main memory.
  - Tuna-Fish 7y ago
    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.
    - varjag 7y ago
      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.
      - staticassertion 7y ago
        I think it's probably fair to call kernel development niche? And the fact that Linux uses linked lists a lot is not necessarily a strong case for linked lists, but just a matter of very specific constraints - like perhaps not wanting to optimize too much for underlying hardware?
        varjag 7y ago
        I used Linux kernel as an example of easily accessible, extremely well known, performance tuned open source project. Of course dynamic data structures are used in countless other applications, like DBMS, web servers and web browsers. Really in nearly any non-trivial codebase.
      - adrianN 7y ago
        Sure, but algorithms that explicitly need a linked structure for performance are very few compared to algorithms that have the same or better asymptotic with a hash and a vector or for which the input sizes are such that the large constants pointer chasing causes don't make up for worse asymptotics.
        varjag 7y ago
        If the algorithm calls for a balancing tree, you'd end up re-implementing it across of bunch of (linked) hash tables or over an array treated like a heap. Explicitly, or if one does not know what they are doing, implicitly. In either case you would have no performance advantage.
        7y ago
  - yazaddaruvala 7y ago
    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.
    - varjag 7y ago
      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.
      - dpbriggs 7y ago
        That's not necessary true. You can implemented binary trees as an array, so are trees a special case of arrays? There can be sequential and non-sequential implementations of ADTs.
  - saagarjha 7y ago
    B-trees aren’t too bad.
- senderista 7y ago
  Yes, along with binary trees, but there are cache-friendly alternatives like unrolled linked lists and B-trees.
- Animats 7y ago
  Yes. Lists were fine when memory was random-access. Today, if you're linking all over memory, cache misses dominate performance. So contiguous data structures are preferred.
  - chapium 7y ago
    This isn't a linked list issue at all, but a problem with constructing the nodes. If you construct list nodes in a contiguous location cache misses are a non issue.
    - estebank 7y ago
      That's no longer a linked list, it's a vector.
      - deleted 7y ago
        [deleted]
      - mikepurvis 7y ago
        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 to test and make sure the gains were worth it.
        viraptor 7y ago
        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)
        7y ago
monadic2 7y ago
> 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?
- steveklabnik 7y ago
  That is true of Rust. The linked list is bad though, even irrespective of this argument about the utility of lists.
grok22 7y ago
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.
- mkesper 7y ago
  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.
- jdsully 7y ago
  The comment applies word for word to C++ as well. Linked lists are just bad datastructures for modern CPUs. 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.
  - blub 7y ago
    No, it doesn't apply to C++ because the corners of the language required to write lists and trees are exercised enough and don't suffer from unexpected limitations.
    - jdsully 7y ago
      The comment originating this discussion provides no evidence in any direction on the quality of the rust standard library. Merely that you wouldn't use these in practice, nor would you in C++.
- pas 7y ago
  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?

Dylan16807 7y ago

Linked lists are inherently niche on modern hardware.

varjag 7y ago
Seriously? Are trees also niche?
- Dylan16807 7y ago
  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.
  - kybernetikos 7y ago
    I've got quite keen on B+ trees. It seems like the world where we had fast main memory and slow drive storage is not very different to the world where we have fast cache memory and slow main memory.
- Tuna-Fish 7y ago
  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.
  - varjag 7y ago
    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.
    - staticassertion 7y ago
      I think it's probably fair to call kernel development niche? And the fact that Linux uses linked lists a lot is not necessarily a strong case for linked lists, but just a matter of very specific constraints - like perhaps not wanting to optimize too much for underlying hardware?
      - varjag 7y ago
        I used Linux kernel as an example of easily accessible, extremely well known, performance tuned open source project. Of course dynamic data structures are used in countless other applications, like DBMS, web servers and web browsers. Really in nearly any non-trivial codebase.
    - adrianN 7y ago
      Sure, but algorithms that explicitly need a linked structure for performance are very few compared to algorithms that have the same or better asymptotic with a hash and a vector or for which the input sizes are such that the large constants pointer chasing causes don't make up for worse asymptotics.
      - varjag 7y ago
        If the algorithm calls for a balancing tree, you'd end up re-implementing it across of bunch of (linked) hash tables or over an array treated like a heap. Explicitly, or if one does not know what they are doing, implicitly. In either case you would have no performance advantage.
        7y ago
- yazaddaruvala 7y ago
  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.
  - varjag 7y ago
    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.
    - dpbriggs 7y ago
      That's not necessary true. You can implemented binary trees as an array, so are trees a special case of arrays? There can be sequential and non-sequential implementations of ADTs.
- saagarjha 7y ago
  B-trees aren’t too bad.
senderista 7y ago
Yes, along with binary trees, but there are cache-friendly alternatives like unrolled linked lists and B-trees.
Animats 7y ago
Yes. Lists were fine when memory was random-access. Today, if you're linking all over memory, cache misses dominate performance. So contiguous data structures are preferred.
- chapium 7y ago
  This isn't a linked list issue at all, but a problem with constructing the nodes. If you construct list nodes in a contiguous location cache misses are a non issue.
  - estebank 7y ago
    That's no longer a linked list, it's a vector.
    - deleted 7y ago
      [deleted]
    - mikepurvis 7y ago
      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 to test and make sure the gains were worth it.
      - viraptor 7y ago
        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)
        7y ago

monadic2 7y ago

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

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

grok22 7y ago

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.

mkesper 7y ago
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.
jdsully 7y ago
The comment applies word for word to C++ as well. Linked lists are just bad datastructures for modern CPUs. 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.
- blub 7y ago
  No, it doesn't apply to C++ because the corners of the language required to write lists and trees are exercised enough and don't suffer from unexpected limitations.
  - jdsully 7y ago
    The comment originating this discussion provides no evidence in any direction on the quality of the rust standard library. Merely that you wouldn't use these in practice, nor would you in C++.
pas 7y ago
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?