News for hackers. Stuff that matters.

A comment on The Universal Data Structure. Parent comment

Re:The Universal Data Structure by pmelendez on Tuesday June 30, 2015 @01:55PM (#9807161)
> Linked lists don't suffer from this problem, but at the cost of 1-2 pointers per item.

Another cost is the cache misses. If you are doing operations in a sequential fashion using an array would have a significant advantage if the number of elements is high. That's another tradeoff to take in consideration.

[ Parent | on HN ]
Re:The Universal Data Structure by adrusi on Tuesday June 30, 2015 @07:32PM (#9809065)
It can be avoided by choosing a good allocation strategy for the linked list, allocating nodes in an arena can eliminate cache misses.
[ Parent | on HN ]
Re:The Universal Data Structure by yoklov on Tuesday June 30, 2015 @07:59PM (#9809157)
You'll still have more than if you had used an array, due to the low information density (2 extra pointers / node).
[ Parent | on HN ]