2 ms·
Those are just search results for linked lists. It isn't as if sqlite using a linked list somewhere slows the entire thing down. I can promise you that if the
by CyberDildonics 11y ago
Those are just search results for linked lists. It isn't as if sqlite using a linked list somewhere slows the entire thing down.
I can promise you that if there is a linked list in a performance crucial place that it could be sped up a non trivial amount.
Linked lists can be convenient and they can be consistent, but they aren't fast. The pointer chasing hurts performance. The extra heap allocations may or may not be able to be avoided. The alternative is something like a vector of pointers (although I would in practicality not being using a raw pointer, it would be some sort of larger data structure). That will be faster with the exception of resizes, which should be fast in general, since what they hold should be small, but they won't be consistent.
Beyond that there is the idea that concurrency could mean that needing to lock a data structure makes a linked list less of an outlier because the time that it would need to remain locked would be smaller. In that case I think a vector would likely still be much better in general, since you could keep the current index to write to in an atomic, which wouldn't require a lock.
- woodman 11y agoThe point of the search results is that I'm not seeing the use of linked lists, in code bases that I could consider fairly performant, at a level that I would describe as "exotic". I'm not trying to be argumentative, I'd really love for you to point me to a code base that has replaced linked lists with arrays. I've spent the last week writing a library to do just that, but I'd happily abandon it in a heartbeat if I could (the novelty of binary packing parallel arrays wore off after day two). You're preaching to the choir on deference overhead, that I why I prefer c over c++ :)
- altarius 11y agoLinked lists aren't fast in general but there are workloads on which they outperform vectors -- which is why it is important to understand the advantages and disadvantages of each data structure. Most lower-level memory allocators e.g. tend to use linked-lists afaik because you end up removing and inserting slabs a lot, the Linux kernel also makes wide use of linked lists as well. If there were substantial performance gains to be made without other large tradeoffs it would have been done. EDIT: Some additional info: http://www.jikos.cz/jikos/Kmalloc_Internals.html http://www.jikos.cz/jikos/Kmalloc_Internals.html