How to match a 13-bit value with a 4-bit code?

Question

I have std :: map for some package processing programs.

I did not notice before profiling, but, unfortunately, this map view by itself consumes about 10% of the processor time (the so-called too much time).

Typically, the input contains no more than 10 keys. Therefore, I am trying to implement a cache key in front of a card.

The key value is a 13-bit integer. I know that there are only 8192 possible keys, and an array of 8192 elements can give a constant search for time, but I already feel ashamed and do not want to use such a naive approach :(

Now I'm just guessing some kind of hashing method that very quickly outputs a 4-bit code value for a 13-bit integer.

Any cool idea?

Thanks in advance.

UPDATE

Besides my shame, I do not have full control over the source code, and for this purpose it is almost forbidden to create a new array.

The project manager said (who launched the profiler), the linked list showed a slight increase in performance and recommended using std :: list instead of std :: map.

UPDATE

The meaning of the keys is random (without relation) and does not have a good distribution.

Example:
1) 0x100, 0x101, 0x10, 0x0, 0xffe
2) 0x400, 0x401, 0x402, 0x403, 0x404, 0x405, 0xff

Answer 1

You can go with the middle solution and the open addressing method : one array of size 256. The index for the array is a simple hash function like XOR of two bytes. The array element is struct {key, value}. Collisions are handled by storing the counter element at the next available index. If you need to remove an element from the array, and if removal is rare, simply recreate the array (create a temporary list of the remaining elements, and then create an array from this list).

If you quickly type in your hash function, there will be almost no collisions. For example, from your two examples, one such hash would be XOR with a low jib of a high byte with a high verb of a low byte (and do what you like with the remaining 13th bit).

Answer 2

Assuming your hash table contains some basic type - it has almost no memory. Even on 64-bit systems, it is only 64 KB of memory. There is no shame in using a similar lookup table; it has the best performance you can get.

Answer 3

If you are not writing some kind of embedded system where 8K is really significant, just use an array and move on. If you really insist on doing something else, you might consider a perfect hash generator (like gperf ).

Answer 4

If your table really has something like 10 active records, you can seriously consider using an unsorted vector to store this mapping. Something like that:

typedef int key_type; typedef int value_type; std::vector<std::pair<key_type, value_type> > mapping; inline void put(key_type key, value_type value) { for (size_t i=0; i<mapping.size(); ++i) { if (mapping[i].first==key) { mapping[i].second=value; return; } } mapping.push_back(std::make_pair(key, value)); } inline value_type get(key_type key) { for (size_t i=0; i<mapping.size(); ++i) { if (mapping[i].first==key) { return mapping[i].second; } } // do something reasonable if not found? return value_type(); } 

Now the asymptotic speed of these algorithms (each O(n) ) is much worse than yours with a red-black tree (for example, std::map at O(log n) ) or a hash table ( O(1) ), but you don't talk about dealing with a lot of objects, so asymptotic estimates don't really buy you much.

In addition, std::vector buys you both low overhead and the terrain of links that neither std::map nor std::list can offer. Therefore, it is more likely that a small std::vector will remain completely in the L1 cache. Since it's almost certainly a memory bottleneck causing performance issues, using std::vector even with my low choice of algorithm is likely to be faster than a tree or linked list. Of course, only a few solid profiles will tell you for sure.

There are, of course, algorithms that might be preferable: a sorted vector could potentially give even better performance; A well-tuned small hash table may also work. I suspect you will come across Amdahl's law pretty quickly, trying to improve a simple unsorted vector. Pretty soon, you may run into overhead function calls or some other such problem as a big contributor to your profile.

Answer 5

I agree with GWW, you don’t use so much memory at the end ... But if you want, you can use an array of 11 or 13 linked lists and hash keys with the% function. If the key number is less than the size of the array, O (1) tents are still complex.

Answer 6

If you always have only ten keys, use a list (or array). Do some benchmarking to see if using a sorted list (or array) and binary search improves.

Answer 7

First you can see if there are extra calls to search for keys. You only want to do this once in a package ideally - every time you call a function, some overhead is imposed on it, so getting rid of additional calls is good.

The map is usually pretty fast, but if there is any pattern to use in how the keys map to elements that you could use, and potentially better. Could you provide a little more information about keys and associated 4-bit values? For instance. are they consistent, is there some kind of pattern?

Finally, as others have noted, the lookup table is very fast, 8192 values ​​* 4 bits - only 4 KB, in fact it is a small amount of memory.

Answer 8

I would use a lookup table. It is tiny if you are not using a microcontroller or something like that.

Otherwise, I would do it -

Create a table of approximately 30 elements. For each search, calculate the hash value (key% 30) and compare it with the stored key in this place in the table. If the key is there, you have found your meaning. if the slot is empty, add it. If the key is incorrect, go to the next free cell and repeat.

With 30 cells and 10 key collisions should be rare, but if you quickly get one of them to go to the next cell, and regular searches are just a module and a comparison operation, so pretty fast