2 ms·
Nobody ever used a linked list for performance. And it's not reasonable to abandon trees and graphs and everything just for the sake of cache locality. Algorit
by TillE 11y ago
Nobody ever used a linked list for performance.
And it's not reasonable to abandon trees and graphs and everything just for the sake of cache locality. Algorithm first, CPU optimization second. Especially because you can control allocation very easily with something like an object pool, which will minimize cache misses.
- adrianN 11y agoYou basically shouldn't use vanilla _binary_ trees ever. b-trees with appropriate node sizes provide much better cache locality without sacrificing any of the nice properties trees have. They are easier to implement too. You don't have to go full van Emde Boas layout trickery to get most of the benefits.