1

So my code is using a tr1::unordered_map<int, ContainerA> where ContainerA is something like this :

class ContainerA
{
    int* _M_type; 
    unsigned int _M_check;
    int _M_test;
    unsigned int _M_any;
    index _M_index;
    index _M_newindex;
    objectB _M_cells[10];
    vector<int> _M_mapping[10];
}

The number of entries in my unordered_map is of the order of millions and at every timestep, tens of thousands (if not hundreds of thousands) of entries get deleted and added. It seems like much of my computing time is used up allocating individually each instance of the ContainerA class.

A solution I propose for speeding things up is to dynamically allocate an estimated number of ContainerA objects needed at the start, and replacing the unordered_map to ContainerA objects by an unordered_map to pointers tr1::unordered_map<int, ContainerA*>.

This seems like a good idea to me, however after doing some research, it does not seem to me like this approach is common which is why I am wondering if I am missing something.

Are there any drawbacks to this approach apart from the additional memory overhead of the pointers?

Edit : As pointed out in the comments below, the problem might lie in my memory allocation. I allocate my memory as follows : I construct a ContainerA object using its constructor ContainerA obja(int* type, int test). In this phase, the ContainerA constructor lets the objectB array and the vector<int> array get default constructed.

After constructing my ContainerA, all my vector<int> and objectB need to allocate some memory on the heap. This is probably the time-consuming phase.

It would probably be possible to avoid deallocating and reallocating memory without using an unordered_map to pointers, but by simply swapping memory contents as suggested. However, I would need to have some sort of way of keeping track of which objects are not used anymore and that sounds somehow more tedious than switching to a pointer array?

Vil
  • 126
  • 8
  • I think you haven't quite identified the bottleneck precisely. Are you allocating `ContainerA` on the heap (using `new`)? Is `_M_mapping` usually empty or does that also need to do its own allocation on the heap? Is `_M_type` also pointing to something that needs to get allocated on the heap? If the trouble is *heap* allocation, those can be avoided easily -- just recycle objects and `swap` them in as needed. If the problem is something else, though, well, we'll have to see what it is. – user541686 Nov 14 '13 at 09:49
  • [This maybe interesting.](http://stackoverflow.com/questions/4573566/a-map-and-set-which-uses-contiguous-memory-and-has-a-reserve-function) – Kerrek SB Nov 14 '13 at 09:53
  • I will add more details about how allocation is done in the post above. – Vil Nov 14 '13 at 10:31
  • You shouldn't use [reserved names](http://stackoverflow.com/questions/228783), like the ones with your `_M_` prefix. – Mike Seymour Nov 14 '13 at 12:41
  • Thanks, I did not know that. As for the original question, I have done some thinking. Am I correct in saying the following thing (?) : When inserting an element, I stack allocate `ContainerA`, and insert it into the `unordered_map`. This insertion creates a copy of that stack-allocated `ContainerA` on the heap. Each `_M_cells` and `_M_mapping` need to allocate on the heap and for now I allocate memory individually for each object. By preallocating a large chunk of memory at the very start and reusing the memory, I could then get about a 20x speedup (since there are 10 objects of each)? – Vil Nov 14 '13 at 13:08

0 Answers0