3 ms·
I'm sure this presenter understands the nuance, but I think it's worth mentioning that linked lists are important for many highly efficient data structures and
by Conscat 3y ago
I'm sure this presenter understands the nuance, but I think it's worth mentioning that linked lists are important for many highly efficient data structures and algorithms. For instance, see
https://plflib.org/ https://plflib.org/
Pool allocators are also a kind of linked list. I suspect that the benchmarks in his slides are for a very simple kind of linked list, like `std::list` in C++.
- dekhn 3y agoI learned about linked lists in high school (mid-80s) when resources were fairly constrained. I never really liked them compared to arrays, but not for any good reason. However, over the years, I've looked at a lot of codes that use either lists or arrays as a hot datatype and the numbers almost always come out in favor of arrays over lists, for the simple reason that Intel optimized for lazy programmers. The only cases where it wasn't true were extremely highly specific problems with well understood data patterns on extremely resource-poor machines.
- Conscat 3y agoIt sounds like you're talking about unsophisticated sparse data structures, such as `std::list`, not the aforementioned chained memory allocation data structures which optimize for memory latency and vectorizability while retaining pointer stability and fast insertion time, such as `std::hive`.