3 ms·
Linked Lists Are Immoral
- Terr_ 3y agoA new reason to program in Erlang/Elixir... The thrill of transgressing against societal norms! Explaining the joke: The basic list data type is a singly linked-list, for reasons of memory-efficiency when spawning lots of different processes that refer to subsequences of the list. So if you want to append, you need to reverse, prepend, and reverse again.
- Conscat 3y agoI'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`.