Custom allocator for std::map

[Catfish3]

Is the below code correct?
Or does the allocated type mismatch with what an std::map will try to allocate?

typedef std::allocator<std::pair<int, std::string>> MyAlloc;

std::map<int, std::string, std::less<int>, MyAlloc> m;

[LB]

Is there a specific reason you are explicitly specifying the allocator in this case? (And technically it should be const int in the allocator pair)

[Catfish3]

I want to use a memory pool for better std::map performance.

I'm currently trying to decipher the members of std::allocator. Have you any tips?

[LB]

I'm not sure what there is to decipher?
http://www.cplusplus.com/reference/memory/allocator/
http://en.cppreference.com/w/cpp/memory/allocator

Are you just trying to make sense of the implementation?

[Cubbi]

I want to use a memory pool

Use a memory pool allocator then, instead of std::allocator
http://www.boost.org/doc/libs/release/libs/pool/doc/html/boost/pool_allocator.html
http://www.drdobbs.com/cpp/improving-performance-with-custom-pool-a/cpp/sourcecode/improving-performance-with-custom-pool-a/30100465
http://warp.povusers.org/FSBAllocator/
etc.. everyone who needs one, makes one.

[Catfish3]

Thanks for the links, Cubbi.
I tried to implement my own allocator, but its performance is abysmal.

class PoolAllocator: public std::allocator<std::pair<const KeyType, CodeType>> {

    class MemoryPool {
    public:

        std::stack<pointer, std::vector<pointer>> aa; // Available Addresses

        MemoryPool():
            bytes(new char[sizeof (CodeType) * globals::dms])
        {
            pointer begin       = reinterpret_cast<pointer> (bytes.get());
            const pointer end   = begin + globals::dms;

            while (begin != end)
                aa.push(begin++);
        }

    private:

        std::unique_ptr<char[]> bytes; // actual memory
    };

public:

    pointer allocate(size_type n, std::allocator<void>::const_pointer = 0)
    {
        if (n > max_size())
            throw std::invalid_argument("MemoryPool::allocate(), bad `n'");

        // memory pool depleted
        if (mp.aa.empty())
            throw std::bad_alloc();

        pointer p = mp.aa.top();
        mp.aa.pop();
        return p;
    }

    /// @warning Naive implementation, assumes `p` is valid.
    void deallocate(pointer p, size_type n)
    {
        if (n > max_size())
            throw std::invalid_argument("MemoryPool::deallocate(), bad `n'");

        // memory pool full
        if (mp.aa.size() == globals::dms)
            throw std::runtime_error("MemoryPool::deallocate(), `aa' is full");

        mp.aa.push(p);
    }

    size_type max_size() const
    {
        return 1;
    }

private:

    static MemoryPool mp;
};

[Cubbi]

the rebind member template is missing (and since it's derived from std::allocator (why), the c++11 automatic rebind won't help either)

[Catfish3]

Please give more detail, what's wrong with deriving from std::allocator?

Also is the missing rebind the cause of the slowness?

[Cubbi]

Deriving from concrete, non-polymorphic, classes is typically a bad idea. If a class doesn't have a virtual destructor, it wasn't designed with inheritance in mind (compare to inheritable standard library classes like streams, buffers, and facets)

In this case, because you don't provide rebind, parent class rebind is selected, and parent (std::allocator<K,V>) is used for all allocations done by a container that's instantiated with this PoolAllocator<K,V>.

[zb0S216C]

I don't see any checks to ensure "PoolAllocator::bytes's" alignment. Most modern operating systems try to return aligned pointers, but this is not always the case. On some CPUs, attempting to read misaligned data can cause a complete failure of the CPU which requires a restart. Granted, the CPUs we have now are capable of handling misaligned addresses, but it's not without a performance penalty. If you want performance, align your data.

Based on what I've seen in the implementation of "std::malloc_allocator" and "std::new_allocator", neither assure alignment of the allocated memory, which leads me to believe that the implementers of the aforementioned classes assume the OS will align the memory for them.

In your implementation of "PoolAllocator::deallocate( )", why are you throwing exceptions left, right and centre? Throwing exceptions is expensive and you should only throw them when something really has gone wrong. I personally think you're misusing exceptions in your code.

Also, what's the purpose of "PoolAllocator::max_size( )"?

_Wazzak

[Cubbi]

both malloc() and operator new() assure alignment.

malloc() (quoted from C99 7.20.3/1)

The pointer returned if the allocation succeeds is suitably aligned so that it may be assigned to a pointer to any type of object

operator new() (quoted from C++11 §18.6.1.1[new.delete.single]/1)

The allocation function (3.7.4.1) called by a new-expression (5.3.4) to allocate size bytes of storage suitably aligned to represent any object of that size.

and in 3.7.4.1

The pointer returned shall be suitably aligned so that it can be converted
to a pointer of any complete object type with a fundamental alignment requirement

[zb0S216C]

Actually, alignment is not always respected even though the standard says so due to compiler bugs. In addition, even if "new" and "malloc( )" do return aligned memory, it's not guaranteed to be sufficiently aligned for the program's needs; alignment to a CPU cache-line springs to mind.

_Wazzak

[Cubbi]

Such fundamental bugs are rare, but need to be reported in any case.
Over-aligned types do need special care (and special allocators if they are placed in a container), but this isn't the case.

[zb0S216C]

How do we know that Catfish's allocator is not a special case? We don't know what sort of data is going to be stored. In addition, the allocator needs respect special alignment requirements for types that it may be required to store at some point in the future if it [the allocator] has any chance of being flexible and reusable.

_Wazzak