4 ms·

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

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.
    - btilly 7y ago
      If you know what you are doing, you may well realize a performance advantage. 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.
btilly 7y ago
...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.
int_19h 7y ago
A hash table is vulnerable to collision attacks, if keys are derived from any kind of untrusted external input. Trees might be slow, but they're consistently slow.
- deckard1 7y ago
  non sequitur. No one mentioned security, nor do any elementary data structures concern themselves with such higher level things. If you're allowing unlimited untrusted data to control internal data structures, you're going to have a bad time regardless of which data structure you're using.
  - eximius 7y ago
    And rusts default hashing implementation is hardened against these attacks
  - dlubarov 7y ago
    > nor do any elementary data structures concern themselves with such higher level things 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).
  - int_19h 7y ago
    Security is a thing that is implicitly pervasive. If it doesn't apply, that should be explicit. 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.
- viraptor 7y ago
  This has been mitigated in almost every language already by starting the hash calculation with a random per-process seed. It's a theoretical issue of hash tables, but we've got known practical solutions.
dntbnmpls 7y ago
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.

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.
  - btilly 7y ago
    If you know what you are doing, you may well realize a performance advantage. 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.

btilly 7y ago

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

int_19h 7y ago

A hash table is vulnerable to collision attacks, if keys are derived from any kind of untrusted external input. Trees might be slow, but they're consistently slow.

deckard1 7y ago
non sequitur. No one mentioned security, nor do any elementary data structures concern themselves with such higher level things. If you're allowing unlimited untrusted data to control internal data structures, you're going to have a bad time regardless of which data structure you're using.
- eximius 7y ago
  And rusts default hashing implementation is hardened against these attacks
- dlubarov 7y ago
  > nor do any elementary data structures concern themselves with such higher level things 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).
- int_19h 7y ago
  Security is a thing that is implicitly pervasive. If it doesn't apply, that should be explicit. 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.
viraptor 7y ago
This has been mitigated in almost every language already by starting the hash calculation with a random per-process seed. It's a theoretical issue of hash tables, but we've got known practical solutions.

dntbnmpls 7y ago

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.