Using custom allocator to make std::list cache friendly?

Question

During my daily work, I am always advised by senior member of the team that list is not cache friendly so I should vector. I understand that list is not continuous so that the memory allocation is scattered around the whole memory.

However, very often I do need the functionality of a list (or a map). So I am wondering if I can write my own allocator, which is a vector underneath. Every time when I push_back, my own allocator will allocate a new item from a per-allocated vector.

When I travel the list/map, the cache locality is preserved.

Does this make sense to any of you?

Obvious question: why not just use a vector? What does this construction give you that a vector doesn't? If you try to use any of the functionality that's ordinarily more efficient on a list than a vector, you'll leak memory. — user2357112
– user2357112, Commented Mar 29, 2017 at 21:27
I have a roughly fixed size list, i constantly need to insert/erase in the middle of it, i don't think this can be easily replaced by a vector — user152503
– user152503, Commented Mar 29, 2017 at 21:28
Do some benchmarks. For 500,000 elements vector out performed list (and map) doing random insert deletes. — Richard Critten
– Richard Critten, Commented Mar 29, 2017 at 21:34

BayK · Accepted Answer · 2017-04-17 03:29:39Z

1

std::list and std::set (I believe you need set as alternative to list, not a map) both will use allocator for there internals. You can preallocating a block of memory and use it to create your objects and containers. If you google, you will find several. In this case your objects instead if "scattered around the whole memory" will be scattered around your block of memory. If block fit on the cache, you will get some improvement. But it will not completely solve you problem.

From description of the problem, you really need deque. Deque is implemented as a list of arrays. It is compromise between vector and a list. It is cache friendly for iteration and faster then array when you insert.

So you can choose either custom allocator or deque, depends on your collection size.

edited Apr 17, 2017 at 3:29

answered Apr 5, 2017 at 21:04

BayK

1187 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Using custom allocator to make std::list cache friendly?

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related