Brtdku

I am developing program for very processing power limited machine where I want to map uint16_t keys to uint16_t values.

I am currently using std::map use non-safe reading:

std::map<uint16_t, uint16_t> m;

//fill m only once



while(true){

    auto x = m[y];

}

The performance is still non-acceptable for the requirements. Is there a better solution in term of execution speed?

Edit:
Some information:

• Total number of items is less than 500


• Insertion is done only once


• Querying values is done more than 250 times / sec


• Keys and values are unique


• Ram is very limited, overall ram is 512KB, free ram for this part of code is less than 50KB


• 100 MHz single core processor

Without some more context about your map,

if you intend to use a lot of keys, a big array like suggested before would be easy enough to handle since there wouldn't be collisions, but if you're not going to use all the memory, it might be wasteful.

if you intend to use a fair amount of data, but not enough that there'd be too many hash collisions, std::unordered_map has amortized O(1) lookups, and if you don't care about the order they're stored in, that could be a good guess.

if you're using not a lot of data and require it to be flexible, std::vector is a good choice

Seeing as all we know is that it's a uin16_t to uint16_t map, there's no one best answer.

• Total number of items is less than 500


• Insertion is done only once

Keep a fixed-size (500) array of key-value pairs plus a "valid items count", if the actual size is known only at runtime; populate it with the data and sort it; then you can simply do a binary search.

Given that the elements are few, depending on the specific processor it may even be more convenient to just do a linear search (perhaps keeping the most used elements first if you happen to have clues about the most frequently looked-up values).

Usually a binary tree (std::map which you currently use) provides adequate performance. Your CPU budget must be really small.

A binary search approach probably won't be much faster. A hashtable (std::unordered_map) might be a solution.

Just make sure to size it properly so as to avoid rehashing and stay just below 1.0 load factor.

std::unordered_map<uint16_t, uint16_t> m(503); // 503 is a prime

m.emplace(123, 234);

m.emplace(2345, 345);



std::cout << m.find(123)->second; // don't use operator to avoid creating entries

std::cout << m.find(2345)->second;

To check the quality of the hashing function, iterate over all the buckets by calling bucket_size() and add up anything above 1 (i.e. a collision).