CODEWITHSUNDEEP
c++performancestl
Arrrow
Arrrow

Reputation: 542

C++ which container to use for storing cache memory

I'm currently writing a cache simulator, and I'm considering which container to use for this particular application.

I have to read memory from a file, which contains data in the following format:

[instruction] [32 bit address] [amount of instructions since previous data memory access]

example:

s 0x1fffff78 1

the instruction is always 's' or 'l', and the files range from 1 kB to 10 MB.

I'm considering using a Map, so I can pair the instruction with the address. But a Map is not very fast as far as I know with retrieval and insertion, which defeats the purpose of a cache.

A vector is my second choice, but this would make separating the three fields more difficult. I would use a vector of pairs if the files remained small, but this is not the case. Also since I would need to search by memory address this doesn't seem like the right choice.

Should I use a map, a vector, or are there faster/better alternatives?

Upvotes: 0

Views: 801

Answers (2)

darune
darune

Reputation: 11146

The easiest to program and use is probably just a std::unordered_map out of the box. If you really really need to tweak every bit of performance, a std::vector that you keep sorted and use for example std::lower_bound for lookup is probably faster, even for insertions in the middle. This is because of the linear contigous memory is just super fast. This could change in the future if for example the map classes is improved.

See for example this post for some benchmarks: https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html

Upvotes: 0

YSC
YSC

Reputation: 40160

I'm considering using a Map, so I can pair the instruction with the address. But a Map is not very fast as far as I know with retrieval and insertion, which defeats the purpose of a cache.

std::map is generally way faster than the code you will write to handle it. This is especially true if you populate it with data from disk. Do use std::map. If it happens that performance is an issue, profile your code and come back with a question containing the result of your profiling.

Upvotes: 4

Related Questions