Was passt an meinem Allocator nicht?

Ethon

Hallo,
ich weiß dass es nicht gerne gesehen wird wenn ein ganzer Quellcode hingeklatscht wird - ich erachte es aber in diesem Fall als das Sinnvollste.

Also, ich habe einen kleinen Allocator geschrieben, der möglichst auf Allokationen vom Heap verzichtet, wenn sehr wenig angefordert wird.
Das klappt bei STL-Containern, die primitive Typen halten, auch toll:

typedef SmallOptimizedAllocator<std::pair<const int, int>, 10> Alloc10;
    typedef std::map<int, int, std::less<int>, Alloc10> IntIntMap10;

    IntIntMap10 map;
    for(int i = 0; i < 10; ++i)
        map[i] = i * 2;

Kein Byte wird vom Heap geholt, toll.

Ganz anders aber bei nested Containern:

typedef SmallOptimizedAllocator<int, 5> IntAlloc5;
    typedef vector<int, IntAlloc5> IntVec;

    typedef SmallOptimizedAllocator<IntVec, 5> IntVecAlloc5;
    typedef vector<IntVec, IntVecAlloc5> IntVecVec;

    IntVecVec vec;
    vec.reserve(5);
    for(int i = 0; i < 5; ++i)
    {
        vec[i].reserve(5);
        for(int j = 0; j < 5; ++j)
        {
            std::cerr << "Adding " << j << " to vector " << i << ".\n";
            vec[i].push_back(j);
        }
    }

Der äußere Vektor holt sich brav den Speicher aus seinem Storage, bei den inneren ist der der put-Zeiger immer 0 (Wie zur Hölle kann das sein?) und Speicher wird per malloc geholt.

Es wird auch nur ein einziges Mal der Konstruktor aufgerufen? Wie kann das sein, jeder Vektor im Vektor hat doch seine eigene Allocator Instanz?

Output: http://pastebin.com/1eb33ExT

Und hier der Code des Allocators:

template<typename T, std::size_t N>
class SmallOptimizedAllocator
{
public:
    typedef std::size_t     size_type;
    typedef std::ptrdiff_t  difference_type;
    typedef T*              pointer;
    typedef T const*        const_pointer;
    typedef T&              reference;
    typedef T const&        const_reference;
    typedef T               value_type;

    template<class U>
    struct rebind
    {
        typedef SmallOptimizedAllocator<U, N> other;
    };

private:
    // Aligned, uninitialized storage.
    typename std::aligned_storage
    <
        sizeof(value_type),
        std::alignment_of<value_type>::value
    >::type m_data[N];

    // Where to put data into the local array.
    pointer m_put;

    // Begin of storage.
    pointer storageBegin()
    {
        return reinterpret_cast<pointer>(std::begin(m_data));
    }

    const_pointer storageBegin() const
    {
        return reinterpret_cast<const_pointer>(std::begin(m_data));
    }

    // End of storage.
    pointer storageEnd()
    {
        return reinterpret_cast<pointer>(std::end(m_data));
    }

    const_pointer storageEnd() const
    {
        return reinterpret_cast<const_pointer>(std::end(m_data));
    }

    // Utility.
    bool isInLocalStorage(pointer p) const
    {
        return p >= storageBegin() && p < storageEnd();
    }

    // Allocation functions.
    pointer localAllocateImpl(size_type n)
    {
        pointer p = m_put;
        m_put += n;
        return p;
    }

    pointer localAllocate(size_type n)
    {
        LOG_TRACE(n);
        size_type freeSlots = size_type(storageEnd() - storageBegin());
        if(freeSlots < n)
            return nullptr;
        return localAllocateImpl(n);
    }

    static pointer heapAllocate(size_type n)
    {
        LOG_TRACE(n);
        pointer p = static_cast<pointer>(std::malloc(sizeof(T) * n));
        if(p == nullptr)
            throw std::bad_alloc();
        return p;
    }

    void localFree(pointer p, size_type n)
    {
        LOG_TRACE((void*)p, n);

        //If it was the most recent allocation ...
        if(m_put - n == p)
            m_put -= n;

        // Else it's gone.
    }

    static void heapFree(pointer p)
    {
        LOG_TRACE((void*)p);
        std::free(p);
    }

public:
    SmallOptimizedAllocator()
        : m_data(), m_put(storageBegin())
    {
        LOG_TRACE("");
        LOG_VVDEBUG("storageBegin(): ", (void*)storageBegin(), " storageEnd(): ", (void*)storageEnd(),
            " m_put: ", (void*)m_put);
    }

    pointer address(reference ref) const
    {
        return std::addressof(ref);
    }

    const_pointer address(const_reference ref) const
    {
        return std::addressof(ref);
    }

    pointer allocate(size_type n, void const* hint = 0)
    {
        LOG_TRACE(n, hint);
        LOG_VVDEBUG("Total local storage slots: ", storageEnd() - storageBegin(),
            ", free slots: ", storageEnd() - m_put);
        LOG_VVDEBUG("storageBegin(): ", (void*)storageBegin(), " storageEnd(): ", (void*)storageEnd(),
            " m_put: ", (void*)m_put);

        // Valid behaviour.
        if(n == 0)
            return nullptr;

        // Integer overflow check.
        if(n > max_size())
            throw std::length_error("allocate n > max_size()");

        // Use the local array if possible.
        pointer p = localAllocate(n);
        if(p != nullptr)
            return p;

        // Serve other requests with malloc.
        return heapAllocate(n);
    }

    void deallocate(pointer p, size_type n)
    {
        LOG_TRACE((void*)p, n);

        // If the data was malloced, just call free on it.
        if(!isInLocalStorage(p))
        {
            heapFree(p);
            return;
        }

        return localFree(p, n);
    }

    size_type max_size() const
    {
        return std::numeric_limits<size_type>::max() / sizeof(T);
    }

    template<typename Type, typename... Args>
    void construct(Type* p, Args&&... args) const
	{
        void* vp = static_cast<void*>(p);
        new(vp) Type(std::forward<Args>(args)...);
    }

    template<typename Type>
    void destroy(Type* p) const
    {
         p->~Type();
    }

    bool operator==(SmallOptimizedAllocator const& o) const
    {
        return this == &o; // Never allow deallocation by another allocator.
    }

    bool operator!=(SmallOptimizedAllocator const& o) const
    {
        return this != &o; // Never allow deallocation by another allocator.
    }
};

Danke schon mal und Grüße,
Ethon

camper

vec.reserve(5);
    for(int i = 0; i < 5; ++i)
    {
        vec[i].reserve(5);

Das soll sicher

vec.resize(5);

heißen.

return p >= storageBegin() && p < storageEnd();

Das erzeugt UB, falls p nicht im Array liegt, auf std::less&co. ausweichen.

void* vp = static_cast<void*>(p);

Das soll sicher eher ein const_cast sein. Die Umwandlung nach void ist sowieso implizit möglich.

Ich befürchte es gibt da ein paar Probleme mit dem Design des Allocators. Nehmen wir zuerst an, dass du einen C++11 kompatiblem Compiler nutzt, sonst wäre ein stateful allocator ja undefiniertes Verhalten. Da dein Allocator keine propagate_on_container_xxx ( http://en.cppreference.com/w/cpp/concept/Allocator ) traits definiert, wird die std::allocator_traits Klasse defaults annehmen, und zwar für einen stateless allocator. Dein Allocator wird also nicht kopiert, wenn der dazugehörige Container kopiert oder geswappt wird, das gilt also auch für den m_data member. Aber selbst wenn du deinen Allocator korrekt für C++11 aufrüstest, was eigentlich nötig währe, gibt es noch das Problem, dass die "allozierten" Objekte jetzt an einer anderen Stelle verweilen. Mann kann nicht einfach zulassen, dass Speicheradressen plötzlich ungültig werden, nur wenn zwei Container geswappt werden, mal abgesehen davon, dass der default-copy deines Allocators die Objekte bitweise kopiert.

Ich fürchte man kann dieses Design nicht mit dem Puffer im Allocator selbst durchsetzen. Jedenfalls nicht ohne erheblichen Mehraufwand.

Ich bin mir nicht so ganz sicher mit deinem Beispiel:

IntVecVec vec;
    vec.reserve(5);
    for(int i = 0; i < 5; ++i)
    {
        vec[i].reserve(5);
        for(int j = 0; j < 5; ++j)
        {
            std::cerr << "Adding " << j << " to vector " << i << ".\n";
            vec[i].push_back(j);
        }
    }

Es sieht hier ein wenig so aus als ob du zwar in vec 5 Objekte reservierst aber nie erstellst bevor du mit vec[i] darauf zugreifst. Wolltest du stattdessen vec.resize(5) benutzen? Nun ich weiß jetzt nicht ob es das Problem behebt, aber es soltle trotzdem bedacht werden. Und jemand ist mir mit dem zweiten Teil zuvorgekommen.

Ethon

Danke für eure Antworten.

Jo, ich habe mir ernsthaft wegen dem reserve anstatt resize nen halben Tag lang die Augen blutig gesucht. Jetzt funktioniert es.

Dass das mit dem Allocator so nicht korrekt ist habe ich bereits gelesen. Eigentlich müsste der Buffer außerhalb des Allocators leben. Schade dass man das nicht korrekt so elegant implementieren kann.

camper schrieb:

return p >= storageBegin() && p < storageEnd();
Das erzeugt UB, falls p nicht im Array liegt, auf std::less&co. ausweichen.

Verstehe ich nicht ganz. Der Vergleich von Pointern ist doch wohldefiniert? Inwiefern kann da UB entstehen?

Ethon schrieb:

camper schrieb:
return p >= storageBegin() && p < storageEnd();
Das erzeugt UB, falls p nicht im Array liegt, auf std::less&co. ausweichen.
Verstehe ich nicht ganz. Der Vergleich von Pointern ist doch wohldefiniert? Inwiefern kann da UB entstehen?

Der Vergleich von Pointern, welche nicht auf das selbe Array/Objekt zeigen ist unspezifiziert, std::less garantiert eine totale Ordnung. Ich sehe allerdings auch nicht ganz, wo hier das UB erzeugt wird.

Ethon

Habe es mir selbst zusammengereimt. Zb. bei den 16bit Intels gab es ja die Segment:Offset Unterteilung. Da ist es möglich dass 2 Zeiger den gleichen Wert haben aber ganz woanders hinzeigen.
Hoffe das wird nicht peinlich für mich.

camper

ubu schrieb:

Ethon schrieb:
camper schrieb:
return p >= storageBegin() && p < storageEnd();
Das erzeugt UB, falls p nicht im Array liegt, auf std::less&co. ausweichen.
Verstehe ich nicht ganz. Der Vergleich von Pointern ist doch wohldefiniert? Inwiefern kann da UB entstehen?
Der Vergleich von Pointern, welche nicht auf das selbe Array/Objekt zeigen ist unspezifiziert,

Das. Unaufmerksamkeit meinerseits.