Memory Allocation for a Map with a fixed number of insertions

Question

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 going 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_alloc

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

Response 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.