Valid uses for a linked list are extremely niche. Yes, you can name some, and I can name several valid uses for bloom filters.
If there are any other allocations taking place at the same time -- say, allocations from other threads, or for other data you had to create while building the list, that locality is shot. Same goes if you insert more elements to the list later, or if you perform an operation which changes its order (like sorting it).
You can reorder and modify the contents of the list without losing locality.
Changing any of the pointers, however, will make memory prefetch much less efficient. CPUs like linear memory access patterns; they're easy to predict. Chasing pointers is much less predictable, even if the pointers are all to the same region of memory.
For example, if your list item is page aligned like the task_struct in the Linux kernel, rescheduling the next process could traverse the process list. The process list links will be at the same page offset and associate with a restricted set of the L1/L2/L3 caches lines and thrash from memory. Worse, the TLB will thrash as well. This was actually the case for Linux until about 2000.
https://www.usenix.org/legacy/publications/library/proceedin...
It is not too large (a few thousand of entries usually), but it needs to be accessed and modified extremely fast. There can be insertions and deletions anywhere, but it is strongly biased towards front. It is ordered by price, either ascending or descending.
Various “ordered queue” implementations are usually a poor fit, as there are many insertions and deletions in the middle, and they need to avoid any additional latency. The same goes to vectors. Red-black trees etc. are too complex (and slow) for such a small size.
So we start with a humble linked list, and optimize it (unrolled, skip search etc). But we respect linked lists, they work.
I think your parent's point is that if you're a C++ programmer, recognizing that vectors outperform other data structures for most use cases is what separates a good engineer from a great one. Often even for things that require lookup (i.e. vector outperforming a set).
During code reviews, a senior C++ programmer in my company (formerly sat in the C++ standards committee) would always demand benchmarks from the developer if they used anything else. In most cases, using representative real world data, they discovered that vectors outperformed even when the theoretical complexity of the other data structure was better.
A great engineer knows the limitation of theory.
Of course, my comment is only regarding C++. No guarantees that vectors are great in other languages.
This is something I've heard before (not often benchmarked) and it makes intuitive sense, and sometimes I've also told it to myself in order to not feel bad for writing O(n) where n is always small.
But somehow, reading this snippet, I'm reminded that the vector does not maintain the semantic reminder that it's used in a key/value use case. So it has me thinking there should be a map/hashtable/dictionary interface that's really just a vector with linear lookup.
Then I think, hmm, maybe the standard containers should just do that. Maybe the authors of those should have some heuristic of "when to get fancy".
So if you have a small data structure and/or large cache, and the key is not complicated.
Linear search generally does outperform for small collections though (it’s better for caches and the branch predictor).
I am always uncomfortable using higher algorithmic complexity. Sure, for small data sets, the vector will outperform the set, but it may not stay small forever. I may waste a millisecond now, but at least, I won't waste an hour if the user decides to use 100x the amount of data I initially considered. And using much more data than expected is a very common thing. It is a robustness thing more than optimization.
If you want both, there are staged algorithms, a typical example is a sort algorithm that goes insertion -> quicksort -> mergesort. Insertion sort is O(N^2), but it is great for small arrays, quicksort is O(N log N) on average but may become O(N^2) in some cases, and mergesort is guaranteed O(N log N) and parallelizable, but it is also the slowest for small arrays. For lists, that would be a list of vectors.
Obviously, there is an overhead cost of the staging itself, which hits the use case for small data, and there is the question "From what data size onwards to use what algorithm?".
For example, I just had a look at sort in Clang's STL implementation, which seems to set a boundary at N=1000. Since the number is a multiple of 10, it looks like it might be arbitrarily picked, in any case there is no paper references in the comments to back it up.
Are people aware of formal studies that explore whether it is worth the trouble to inspect data structure and then to dispatch to different algorithms based on the findings?
Other than that, I'd suggest that big O complexity is already telling you that the inspection is worth it. Assuming inspection of an array is constant.
In over 90% of SW applications written in C++, there is little to no uncertainty on the size of the data set. Most applications are written for a very specific purpose, with fairly well known needs.
If my data set is size N, and I can benchmark and show the vector outperforms the theoretical option up to, say, 20N, it's a safe choice to go with vector. Doing these analyses is engineering.
In any case, it's almost trivial to swap out the vector with other options when needed, if you plan for it.
The standard library gives you plenty of tools to maintain and search in a sorted vector. Often enough still faster than maps.
> Oh and of course that senior engineer will also hopefully be the one monitoring the lengths of all those vectors in production.
Doesn't a std::map have more space overhead than a vector?
But to your point - I once needed to do a key/value lookup for a large data set, and so of course I used a map. Then I ran out of RAM (had 80GB of it too!). So I switched to a vector and pre-sorted it and used binary_search for lookups (data set was static - populate once and the rest of the codebase didn't modify it). And of course, the RAM consumption was less than half that of the map.