Memory Allocation for a Map with a fixed number of insertions
I want to insert n elements into a map where n is known ahead of time. I do not want memory allocation at each insertion. I want all memory allocation at the beginning. Is there a way to do this? If so, how? Will writing some sort of memory allocator help?
I ran GMan's code and got the following output. GetMem is printed from a call to "new" and FreeMem is printed from a call to delete. size is the number of bytes requested and ptr is the pointer returned. Clearly, allocation/deallocation is g开发者_开发技巧oing on during insertion. How do you explain this?
GetMem size 40, ptr 0x8420008
GetMem size 40, ptr 0x8420038 GetMem size 120, ptr 0x8420068 GetMem size 120, ptr 0x84200e8 FreeMem ptr 0x8420068 FreeMem ptr 0x8420038 FreeMem ptr 0x8420008 Inserting: [0,0] GetMem size 40, ptr 0x8420008 FreeMem ptr 0x8420008 Inserting: [1,2] GetMem size 40, ptr 0x8420008 FreeMem ptr 0x8420008 Inserting: [2,4] GetMem size 40, ptr 0x8420008 FreeMem ptr 0x8420008 Inserting: [3,6] GetMem size 40, ptr 0x8420008 FreeMem ptr 0x8420008 Inserting: [4,8] GetMem size 40, ptr 0x8420008 FreeMem ptr 0x8420008 Inserting: [5,10] GetMem size 40, ptr 0x8420008 FreeMem ptr 0x8420008 GetMem size 40, ptr 0x8420008 FreeMem ptr 0x8420008 GetMem size 40, ptr 0x8420008 FreeMem ptr 0x8420008 GetMem size 40, ptr 0x8420008 FreeMem ptr 0x8420008 GetMem size 40, ptr 0x8420008 FreeMem ptr 0x8420008 FreeMem ptr 0x84200e8 St9bad_allocResponse to allocation test
Add this to either of the samples I give below:
#include <cstdlib>
void* allocate(size_t pAmount)
{
std::cout << "Allocating " << pAmount << " bytes." << std::endl;
return std::malloc(pAmount);
}
void deallocate(void* pPtr)
{
std::cout << "Deallocating." << std::endl;
std::free(pPtr);
}
void* operator new(size_t pAmount) // throw(std::bad_alloc)
{
return allocate(pAmount);
}
void *operator new[](size_t pAmount) // throw(std::bad_alloc)
{
return allocate(pAmount);
}
void *operator new(size_t pAmount, const std::nothrow_t&) throw()
{
return allocate(pAmount);
}
void *operator new[](size_t pAmount, const std::nothrow_t&) throw()
{
return allocate(pAmount);
}
void operator delete(void* pMemory) throw()
{
deallocate(pMemory);
}
void operator delete[](void* pMemory) throw()
{
deallocate(pMemory);
}
void operator delete(void* pMemory, const std::nothrow_t&) throw()
{
deallocate(pMemory);
}
void operator delete[](void* pMemory, const std::nothrow_t&) throw()
{
deallocate(pMemory);
}
(Note, these are not fully correct replacements of the allocation operators, and are for demonstration.)
Running the runtime-sized sample program gives me the following output:
Allocating 40 bytes.
Allocating 40 bytes.
Allocating 40 bytes.
Allocating 40 bytes.
Allocating 40 bytes.
Allocating 40 bytes.
Allocating 40 bytes.
Deallocating.
Deallocating.
Allocating 120 bytes.
Deallocating.
Allocating 20 bytes.
Deallocating.
Allocating 40 bytes.
Deallocating.
Deallocating.
Deallocating.
Inserting: [0,0]
Inserting: [1,2]
Inserting: [2,4]
Inserting: [3,6]
Inserting: [4,8]
Deallocating.
Deallocating.
Deallocating.
bad allocation
Note there are no allocations once insertion has begun. You should be getting no memory allocations. How are you generating your output?
The allocators
What you need is a new allocator. Here's something I made now, so it's relatively untested, but it looks good to me.
It creates a freelist and uses that to give out memory. Construction of the allocator takes O(N), but both allocations and deallocations are O(1). (Very fast!) Also, once it's constructed, no more memory allocations take place. Though freelists have average locality, it probably beats what you'd normally get out of a map with the default allocator.
Here it is:
#include <cassert>
#include <exception>
#include <limits>
#include <vector>
// gets rid of "unused parameter" warnings
#define USE(x) (void)(x)
template <typename T, size_t N>
class freelist_allocator
{
public:
// types
typedef T value_type;
typedef const T const_value_type;
typedef value_type& reference;
typedef const_value_type& const_reference;
typedef value_type* pointer;
typedef const_value_type* const_pointer;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
// ensure it can hold both a pointer and T
struct block_type
{
char data[sizeof(T) > sizeof(void*) ?
sizeof(T) : sizeof(void*)];
};
typedef std::vector<block_type> buffer_type;
// constants
static const size_t Elements = N;
// rebind
template<typename U, size_t M = Elements>
struct rebind
{
typedef freelist_allocator<U, M> other;
};
// constructor
freelist_allocator(void) :
mBuffer(Elements),
mNext(0)
{
build_list();
}
freelist_allocator(const freelist_allocator&) :
mBuffer(Elements),
mNext(0)
{
build_list();
}
template<typename U, size_t M>
freelist_allocator(const freelist_allocator<U, M>&) :
mBuffer(Elements),
mNext(0)
{
build_list();
}
// address
pointer address(reference r)
{
return &r;
}
const_pointer address(const_reference r)
{
return &r;
}
// memory
pointer allocate(size_type pCount, const void* = 0)
{
USE(pCount); // pCount unused when assert is disabled in release
assert(pCount == 1 && "freelist_allocator is noncontiguous");
// end of list
if (!mNext)
throw std::bad_alloc();
// remove from list
void* memory = mNext;
mNext = data_as_ptr(*mNext);
return static_cast<pointer>(memory);
}
void deallocate(pointer pPtr, size_type)
{
// get back our block
block_type* b = reinterpret_cast<block_type*>(pPtr);
// reinsert to list
data_as_ptr(*b) = mNext;
mNext = b;
}
// size
size_type max_size(void) const
{
static const size_t MaxSize =
std::numeric_limits<size_type>::max();
return MaxSize / sizeof(value_type);
}
// construction / destruction
void construct(pointer pPtr, const T& pT)
{
new (pPtr) T(pT);
}
void destroy(pointer pPtr)
{
USE(pPtr); // trivial destructor skips next line
pPtr->~value_type();
}
private:
// utility
block_type*& data_as_ptr(block_type& pBlock)
{
return reinterpret_cast<block_type*&>(pBlock.data);
}
void build_list(void)
{
// build list
for (size_t i = 1; i < mBuffer.size(); ++i)
{
data_as_ptr(mBuffer[i - 1]) = &mBuffer[i];
}
mNext = &mBuffer[0];
}
// members
buffer_type mBuffer;
block_type* mNext;
};
// equality
template<typename T, size_t N>
bool operator==(freelist_allocator<T, N> const&,
freelist_allocator<T, N> const&)
{
return false;
}
template<typename T, size_t N>
bool operator!=(freelist_allocator<T, N> const& pX,
freelist_allocator<T, N> const& pY)
{
return !(pX == pY);
}
#undef USE
And use:
#include <iostream>
#include <map>
#include <string>
static const size_t MaxElements = 5;
typedef std::pair<int, int> pair_type;
typedef freelist_allocator<pair_type, MaxElements> allocator_type;
typedef std::map<int, int,
std::less<int>, allocator_type> map_type;
void do_insert(int pX, int pY, map_type& pMap)
{
std::cout << "Inserting: [" << pX << ","
<< pY << "]" << std::endl;
pMap.insert(std::make_pair(pX, pY));
}
int main(void)
{
try
{
map_type m;
// just keep inserting
for (int i = 0; i <= std::numeric_limits<int>::max() / 2; ++i)
{
// will throw at MaxElements insertions
do_insert(i, i * 2, m);
}
}
catch (const std::exception& e)
{
std::cerr << e.what() << std::endl;
}
}
For now I've made the size a compile-time constant, but you want a run-time version just let me know and I'll write that up. Here's a version that takes a size at run-time:
#include <cassert>
#include <exception>
#include <limits>
#include <vector>
// gets rid of "unused parameter" warnings
#define USE(x) (void)(x)
template <typename T>
class freelist_allocator
{
public:
// types
typedef T value_type;
typedef const T const_value_type;
typedef value_type& reference;
typedef const_value_type& const_reference;
typedef value_type* pointer;
typedef const_value_type* const_pointer;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
// ensure it can hold both a pointer and T
struct block_type
{
char data[sizeof(T) > sizeof(void*) ?
sizeof(T) : sizeof(void*)];
};
typedef std::vector<block_type> buffer_type;
// rebind
template<typename U>
struct rebind
{
typedef freelist_allocator<U> other;
};
// constructor
freelist_allocator(size_t pElements) :
mBuffer(pElements),
mNext(0)
{
build_list();
}
freelist_allocator(const freelist_allocator& pRhs) :
mBuffer(pRhs.size()),
mNext(0)
{
build_list();
}
template<typename U>
freelist_allocator(const freelist_allocator<U>& pRhs) :
mBuffer(pRhs.size()),
mNext(0)
{
build_list();
}
// address
pointer address(reference r)
{
return &r;
}
const_pointer address(const_reference r)
{
return &r;
}
// memory
pointer allocate(size_type pCount, const void* = 0)
{
USE(pCount); // pCount unused when assert is disabled in release
assert(pCount == 1 && "freelist_allocator is noncontiguous");
// end of list
if (!mNext)
throw std::bad_alloc();
// remove from list
void* memory = mNext;
mNext = data_as_ptr(*mNext);
return static_cast<pointer>(memory);
}
void deallocate(pointer pPtr, size_type)
{
// get back our block
block_type* b = reinterpret_cast<block_type*>(pPtr);
// reinsert to list
data_as_ptr(*b) = mNext;
mNext = b;
}
// size
size_type max_size(void) const
{
static const size_t MaxSize =
std::numeric_limits<size_type>::max();
return MaxSize / sizeof(value_type);
}
size_t size(void) const
{
return mBuffer.size();
}
// construction / destruction
void construct(pointer pPtr, const T& pT)
{
new (pPtr) T(pT);
}
void destroy(pointer pPtr)
{
USE(pPtr); // trivial destructor skips next line
pPtr->~value_type();
}
private:
// utility
block_type*& data_as_ptr(block_type& pBlock)
{
return reinterpret_cast<block_type*&>(pBlock.data);
}
void build_list(void)
{
// build list
for (size_t i = 1; i < mBuffer.size(); ++i)
{
data_as_ptr(mBuffer[i - 1]) = &mBuffer[i];
}
mNext = &mBuffer[0];
}
// members
buffer_type mBuffer;
block_type* mNext;
};
// equality
template<typename T>
bool operator==(freelist_allocator<T> const&,
freelist_allocator<T> const&)
{
return false;
}
template<typename T, size_t N>
bool operator!=(freelist_allocator<T> const& pX,
freelist_allocator<T> const& pY)
{
return !(pX == pY);
}
#undef USE
Use:
#include <iostream>
#include <map>
#include <string>
static const size_t MaxElements = 5;
template <typename Key, typename Value>
struct map_types // helpful
{
typedef std::pair<Key, Value> pair_type;
typedef freelist_allocator<pair_type> allocator_type;
typedef std::less<Key> predicate_type;
typedef std::map<Key, Value,
predicate_type, allocator_type> map_type;
};
template <typename Key, typename Value, typename Map>
void do_insert(const Key& pX, const Value& pY, Map& pMap)
{
std::cout << "Inserting: [" << pX << ","
<< pY << "]" << std::endl;
pMap.insert(std::make_pair(pX, pY));
}
int main(void)
{
try
{
typedef map_types<int, int> map_types;
// double parenthesis to avoid vexing parse
map_types::map_type m((map_types::predicate_type()),
map_types::allocator_type(MaxElements));
// just keep inserting
for (int i = 0; i <= std::numeric_limits<int>::max() / 2; ++i)
{
do_insert(i, i * 2, m);
}
}
catch (const std::exception& e)
{
std::cerr << e.what() << std::endl;
}
}
The run-time version could possibly allocate more space if there are no more remaining slots, which can be useful. But I leave that to you. (Don't resize the vector! You'll possibly lose your entire buffer. You'll need a list of vectors, likely.)
Note if you can use Boost, they have such an allocator in their Pool library. That said, their allocator keeps track of the order you request memory, to ensure reverse construction destruction order. This turns allocations and deallocations into O(N). (A terrible choice in my opinion.) I actually wrote my own allocator around boost::pool<> to get around this.
Use a hashtable. unordered_map might be inappropriate as it allows each object to be allocated separately, and uses "closed addressing" with buckets instead of one flat block of memory.
See http://en.wikipedia.org/wiki/Hash_table#Open_addressing for a description of the kind of structure you should consider. It's not too difficult to implement an associative container with constant access time and constant insertion time.
Support for deletion can be a little messy, though, and you will need to allocate considerable empty space in the hash table, perhaps double what you actually use, to keep the address space uncluttered.
This isn't required for a map the way it's required for a vector. Since map is implemented as a tree internally, insertions are cheap (you don't move around whole chunks). On the other hand, for a vector insertions that take it over the currently reserved bound require to move all the previously allocated elements.
That said, if allocation performance is super crucial to you, you can write a custom allocator that, say, allocates from a pre-allocated buffer. If you implement this correctly, it will be faster than the default new used by map. However, I doubt you must go this far.
std::map doesn't provide any built in support for doing this. But, if the number of elements is small enough, then you can create std::vector of pairs and use vector::reserve method to reserve the needed space.
加载中,请稍侯......
精彩评论