CODEWITHSUNDEEP
stldictionary
roscoe_casita
roscoe_casita

Reputation: 175

Pre-Allocation of std::map<unsigned long long,void *> , How to pre-allocate properly?

Problem:

I'm working with very large data-sets, up to a maximum of 8 * 1024 * 1024 identities;

  1. I've pre-allocated an array of structures, pointed to by the void * portion.

  2. The 'free' pointers are pushed on a stack, popped as they are used, and pushed as they are removed from the hash_map. (this is close to 256mb of memory)

  3. I've identified the majority of the system time / performance as being consumed in the add operations of the std::hash_map.

struct Order; std::hash_map OrderDatabase;

What I would really like to do, is just pass the MAX_ORDERS into the constructor:

std::hash_map OrderDatabase(MAX_ORDERS);

// and have it pre-allocate the containers so that insertion / removal don't involved malloc/free.

Suggestions are appreciated! I'm trying to stick to strictly STL/C++ as a side note.

Edit/Update:

I've also tried the following:

hash_map MapTest; hash_map::allocator_type MapAlloc = MapTest.get_allocator();

pair *ary = MapAlloc.allocate(MAX_ORDERS); // the problem here is that ulonglong is const!

The idea was to push each one unto a stack, and pop for alloc, and use insert instead of maptest[id] = ptr;

//Update 2:

  1. Create stack< pair * > pointer_stack, and push pre-allocated pointers,
  2. Pop a pointer. Assign values;
  3. Insert into hash_map:
  4. Find the item, get a pointer to the address: it appears the hash_map allocated a new pair even though I called insert.

This makes removal & pushing unto the stack not feasible.

Upvotes: 1

Views: 1678

Answers (1)

hamstergene
hamstergene

Reputation: 24429

Do you have to use map? Even if you defeat malloc slowliness with custom allocator, the map's implementation will still have to perform tree rebalancing a lot of times, and I don't think you can change that.

If the map is intented to be read-only (i.e. the only use of insert is to populate it before using), simply have a sorted array of key/index pairs, and use binary search. Searches will then be as fast as map, and much less memory will be consumed. You can always wrap it with operator[] and iteration for convenience.

C++11 unordered_map allows preallocation via reserve() method. Search/insertion/removal will take constant time. However, it will consume more memory than std::map.

Upvotes: 1

Related Questions