If developers learn 2 basic things:
1. How SQL queries work
2. Network latency exists. Moving stuff between your database and your server can get expensive.
You'll solve _most_ of the issues that I've seen in my career to this point. There are a few big ones that came from abusing API's too, but it's really the same root issue:
You're either thinking about how much information is being moved around or you're not.
Also, for parallel stuff: locks tend to be bottlenecks. Writing parallel code is tricky overall. Stick to libraries that provide high level lockless data structures like mpsc queues if possible.
A linked list is basically only better on embedded systems because you have much better knowledge about the used ram/runtime. It’s also useful if you have a very large data structure and you need real time performance (a lag of a few hundred milliseconds are unacceptable for some applications such games or financial applications). But whenever your insert becomes too expensive, a linked list is probably not the best choice either and you should consider why your data structure is so big.
Lastly a linked list is rather simple to implement but that’s also only really useful for embedded stuff.
Which allocator is used for these? I'm not familiar with the Linux kernel, but since there is no malloc() in the kernel, I would guess that they allocate from an arena that's going to be page-aligned and thus exhibit the same locality characteristics as a vector.
That's not a "niche algorithm" to me, but rather a reasonable use case. The add and delete operations should be faster than for the array case.
(Not that I actually use linked list much myself, but I mean I see the use of them.)
Isn't the linked list pretty much the main collection data structure in the Linux kernel?
Like, if you want a running mean of the last 250ms, you put a timestamp and value pair in the back a deque, and every update you check the front of the deque to see if it should be popped (i.e. the timestamp is older than 250ms), and the mean updated.
I suppose you could use a circular buffer with a vector as well, but you have to guess what your max size will ever be, or handle dynamic resizing. Maybe it would be worth it in some circumstances.
Not to put too fine a point on it, but I think you meant how often information is being moved around. That's the scenario where latency has a disproportionate effect on performance.
(Bandwidth is usually not a problem these days unless you're doing something at the very high end.)
4. When [not] to use the network
A lot of the performance wins I have been able to pull off (1000x) were from removing unnecessary distribution and unnecessary databases.
Every tiny bit of data was being loaded as needed, often from EAV tables. Obviously this sucked or performance so we ended up with an elaborate memory cache that is effectively it's own DBMS which uses a real database as a backing store. This didn't really solve the performance issues though because Hash maps might be fast but they are still far from free and doing 10's of thousands at a time is still quite slow.
Fast forward a decade and we have caches in front of caches in front of caches in front of our database instead of just loading courser chunks of data at once.