4 ms·

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

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

by varjag 7y ago

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.