Custom allocator problems
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 20

Thread: Custom allocator problems

  1. #1
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,725

    Custom allocator problems

    Does anyone know if the requirements have changed for writing custom allocators with C++ 0x11?

    A custom allocator (that uses a fixed array as its memory pool) that I have been using successfully for some time, now throws an exception!

    It runs fine under VS2008 but bombs out with VS2010.
    "It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
    Richard P. Feynman

  2. #2
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,297

    Re: Custom allocator problems

    While I don't think the requirements have been changed, there is now an allocator_traits which you are supposed to use, rather than calling the allocator directly. How this affects existing code though... I'm not sure.

    Theory says that changes to C++11 shouldn't break existing C++ code...
    Is your question related to IO?
    Read this C++ FAQ LITE article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

  3. #3
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,725

    Re: Custom allocator problems

    It appears to get upset whilst traversing a linked list, where it comes across an unititialised pointer.

    Code:
            // MEMBER FUNCTIONS FOR _Container_base12
    inline void _Container_base12::_Orphan_all()
        {    // orphan all iterators
     #if _ITERATOR_DEBUG_LEVEL == 2
        if (_Myproxy != 0)
            {    // proxy allocated, drain it
            _Lockit _Lock(_LOCK_DEBUG);
    
            for (_Iterator_base12 **_Pnext = &_Myproxy->_Myfirstiter;
                *_Pnext != 0; *_Pnext = (*_Pnext)->_Mynextiter)
                (*_Pnext)->_Myproxy = 0;
            _Myproxy->_Myfirstiter = 0; <<<< Here
            }
     #endif /* _ITERATOR_DEBUG_LEVEL == 2 */
        }
    In this case, the allocator has been applied to a std::vector. The exception occurs when calling 'reserve'.

    Code:
    vector<int, ArrayAllocator<int, 10>> test;
    
    int main()
    {
        test.reserve(2);
    }
    I'll give allocator_traits a look.
    "It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
    Richard P. Feynman

  4. #4
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,725

    Re: Custom allocator problems

    I don't seem to be able to get to the bottom of this yet.

    Here's a demo that compiles correctly with both VS2008 & VS2010, but exceptions under VS2010.

    The allocator shown is a simplified version which only works with items that have a trivial destructor.

    All of the tests should print 'true'.

    Code:
    #include <vector>
    #include <iostream>
    
    using namespace std;
    
    template <typename T, const size_t MAX_SIZE>
    class ArrayAllocator
    {
    public:
        typedef T                 value_type;
        typedef value_type*       pointer;
        typedef const value_type* const_pointer;
        typedef value_type&       reference;
        typedef const value_type& const_reference;
        typedef size_t            size_type;
        typedef std::ptrdiff_t    difference_type;
    
        //*********************************************************************
        template <typename U>
        struct rebind
        {
            typedef ArrayAllocator<U, MAX_SIZE> other;
        };
    
        //*********************************************************************
        ArrayAllocator()
        {
        }
    
        //*********************************************************************
        ArrayAllocator(const ArrayAllocator &rhs)
        {
            std::copy(rhs.buffer, rhs.buffer + MAX_SIZE, buffer);
        }
    
        //*********************************************************************
        template <typename U>
        ArrayAllocator(const ArrayAllocator<U, MAX_SIZE> &rhs)
        {
        }
    
        //*********************************************************************
        pointer address(reference x) const
        {
            return (&x);
        }
    
        //*********************************************************************
        const_pointer address(const_reference x) const
        {
            return (x);
        }
    
        //*********************************************************************
        pointer allocate(size_type     n,
                         const_pointer cp = 0)
        {
            // Too big?
            if (n > MAX_SIZE)
            {
                throw std::bad_alloc();
            }
    
            // Return the beginning of the buffer.
            return buffer;
        }
    
        //*********************************************************************
        void deallocate(pointer   p,
                        size_type n)
        {
        }
    
        //*********************************************************************
        size_type max_size() const
        {
            return (MAX_SIZE);
        }
    
        //*********************************************************************
        void construct(pointer          p,
                       const value_type &x)
        {
            *p = x;
        }
    
        //*********************************************************************
        void destroy(pointer p)
        {
            p->~value_type();
        }
    
    private:
    
        // Disabled operator.
        void operator =(const ArrayAllocator &);
    
        // The allocation pool.
        T buffer[MAX_SIZE];
    };
    
    //*********************************************************************
    template <typename T, const size_t MAX_SIZE>
    inline bool operator ==(const ArrayAllocator<T, MAX_SIZE> &,
                            const ArrayAllocator<T, MAX_SIZE> &)
    {
        return (false);
    }
    
    //*********************************************************************
    template <typename T, const size_t MAX_SIZE>
    inline bool operator !=(const ArrayAllocator<T, MAX_SIZE> &,
                            const ArrayAllocator<T, MAX_SIZE> &)
    {
        return (true);
    }
    
    //*********************************************************************
    int main()
    {
        const size_t MAX_SIZE = 10;
    
        std::vector<int, ArrayAllocator<int, MAX_SIZE>> test;
    
        cout << std::boolalpha << (test.size()     == 0)        << "\n";
        cout << std::boolalpha << (test.max_size() == MAX_SIZE) << "\n";
        cout << std::boolalpha << (test.capacity() == 0)        << "\n";
    
        test.push_back(1); // Exception here for VS2010.
        test.push_back(2);
    
        cout << std::boolalpha << (test[0] == 1) << "\n";
        cout << std::boolalpha << (test[1] == 2) << "\n";
    
        cout << std::boolalpha << (test.size()     == 2)        << "\n";
        cout << std::boolalpha << (test.max_size() == MAX_SIZE) << "\n";
        cout << std::boolalpha << (test.capacity() == 2)        << "\n";
    
        test.reserve(5);
    
        cout << std::boolalpha << (test.size()     == 2)        << "\n";
        cout << std::boolalpha << (test.max_size() == MAX_SIZE) << "\n";
        cout << std::boolalpha << (test.capacity() == 5)        << "\n";
    }
    "It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
    Richard P. Feynman

  5. #5
    Join Date
    Oct 2008
    Posts
    1,137

    Re: Custom allocator problems

    the allocator requirements ( both in c++11 and c++2003 ) basically imply that the allocator instance cannot "contain" the memory used for allocation, because given two instances a,b of the same (or rebinded) allocator type, a==b implies that b can deallocate what a has previously allocated and vice versa. Hence, your allocator will break whenever the container uses (legally) more then one "rebind" of your passed allocator type.

    Indeed, in the vs2010 vector ctor code there is

    Code:
    {	// construct allocator from _Al
    		typename _Alloc::template rebind<_Container_proxy>::other
    			_Alproxy(_Alval);
    		this->_Myproxy = _Alproxy.allocate(1);
    		_Cons_val(_Alproxy, this->_Myproxy, _Container_proxy());
    		this->_Myproxy->_Mycont = this;
    
    		_Myfirst = 0;
    		_Mylast = 0;
    		_Myend = 0;
    	}
    as you can see, your allocator is returning a pointer to a memory region to be destroyed at scope exit, hence the error. This doesn't happen in vs2008 just by chance, because only one allocator instance is used throughout the container lifetime ( allocator<T> for std::vector, allocator<T>::rebind<Node<T>>:ther for std::list etc... )
    Stack based allocators should use an external stack space instead, a so called "memory arena" ...
    Last edited by superbonzo; March 5th, 2012 at 04:51 AM.

  6. #6
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,725

    Re: Custom allocator problems

    Quote Originally Posted by superbonzo View Post
    , a==b implies that b can deallocate what a has previously allocated and vice versa.
    I understand what you're saying, but I understood that the purpose of the == and != operators was to inform the container code whether allocators were equivalent or not, and so take appropriate action. a==b in the case of this allocator would be false.

    I'm programming in a real-time embedded environment and the purpose of the array allocators was to allow use of STL containers in a more deterministic manner.

    Oh well, time to roll up the sleeves and refactor.
    "It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
    Richard P. Feynman

  7. #7
    Join Date
    Oct 2008
    Posts
    1,137

    Re: Custom allocator problems

    Quote Originally Posted by JohnW@Wessex View Post
    I understand what you're saying, but I understood that the purpose of the == and != operators was to inform the container code whether allocators were equivalent or not, and so take appropriate action. a==b in the case of this allocator would be false.
    this would work if allocators were not required to be copy-constructible. Copy constructibility semantically implies that copies compare equal, hence the STL code above is legitimate ( although an _ASSERT( _Alproxy == _Alval ) would have been appropriate in this case ).

  8. #8
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,725

    Re: Custom allocator problems

    Quote Originally Posted by superbonzo View Post
    this would work if allocators were not required to be copy-constructible. Copy constructibility semantically implies that copies compare equal
    PITA! What with these allocator restrictions, the requirement that predicates do not have state and non-guaranteed iteration order for some algorithms, I'm increasingly finding myself reverse engineering parts of the STL to work around around STL's 'flexibility' of implementation.

    I've read all of the reasons it was designed this way, but in practice these restrictions have tended to make the code I want to write more complex (and sometimes less efficient).
    "It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
    Richard P. Feynman

  9. #9
    Join Date
    Oct 2008
    Posts
    1,137

    Re: Custom allocator problems

    Quote Originally Posted by JohnW@Wessex View Post
    PITA! What with these allocator restrictions...
    well, I think you're asking too much here, as you're trying to enforce a memory layout ( = all allocations must fit into an array of objects of the same type ) and not just a memory allocation scheme. This is impossible unless severe restrictions are applyed to containers implementations ...

    alternatively, did you take a look at boost memory pool ?

    BTW, one scenario I found myself in is of having a container that most of the times has a small bounded memory requirement and predictable memory access; like, say, a vector v for which v.size()<=10 99/100 of times. Now, I would have liked an allocator working on the stack in such "normal" circumstances and reverting to the heap otherwise ( or throwing, or logging etc... ) in such a way to exploit that statistical advantage while retaining the std::vector interface and flexibility. Oversimplifying, something like:

    Code:
    #include <memory>
    #include <list>
    
    template < std::size_t N = 0, class FallbackAlloc = std::allocator<void> >
    class lazy_buffer;
    
    template <>
    class lazy_buffer<0,std::allocator<void>>
    {
    public:
    	lazy_buffer() {}
    
    	virtual void* allocate( std::size_t n ) = 0;
    	virtual void  deallocate( void* p, std::size_t n ) = 0;
    
    private:
    	lazy_buffer( const lazy_buffer& ); // deleted
    	lazy_buffer& operator=( const lazy_buffer& ); // deleted
    };
    
    template < std::size_t N, class FallbackAlloc >
    class lazy_buffer:
    	public lazy_buffer<>
    {
    public:
    	lazy_buffer(): current_( buffer_ ) {}
    	lazy_buffer( const FallbackAlloc& fallback ): current_( buffer_ ), fallback_( fallback ) {}
    
    	void* allocate( std::size_t n )
    	{
    		void* result;
    
    		if( current_ + n <= buffer_ + N )
    		{
    			result = current_;
    			current_ += n;
    		}
    		else
    			result = fallback_.allocate( n );
    		
    		return result;
    	}
    
    	void  deallocate( void* p, std::size_t n )
    	{
    		if( p < buffer_ || p >= buffer_ + N )
    		{
    			fallback_.deallocate( reinterpret_cast<char*>( p ), n );
    		}
    	}
    
    private:
    	char  buffer_[N];
    	char* current_;
    	typename FallbackAlloc::template rebind<char>::other	fallback_;
    };
    
    
    template < class T >
    class lazy_allocator
    {
    public:
    	typedef T                 value_type;
        typedef value_type*       pointer;
        typedef const value_type* const_pointer;
        typedef value_type&       reference;
        typedef const value_type& const_reference;
        typedef size_t            size_type;
        typedef std::ptrdiff_t    difference_type;
    
        template <typename U>
        struct rebind { typedef lazy_allocator<U> other; };
    
        lazy_allocator( lazy_buffer<>& rhs ): buffer_( &rhs ) {}
    
    	template <class V>
    	lazy_allocator( const lazy_allocator<V>& rhs ): buffer_( rhs.get_buffer() ) {}
    
        pointer			address(reference x) const { return &x; }
    	const_pointer	address(const_reference x) const { return &x; }
    
    	size_type max_size() const { return std::numeric_limits<std::size_t>::max() / sizeof( T ); }
    
        pointer allocate( size_type n, const_pointer hint = 0 ) { return reinterpret_cast<pointer>( buffer_->allocate( n * sizeof( T ) ) ); }
        void	deallocate( pointer p, size_type n ) { return buffer_->deallocate( p, n * sizeof( T ) ); }
    
        void construct( pointer p, const value_type &v ) { new( reinterpret_cast<void*>( p ) ) value_type( v ); }
        void destroy( pointer p ) { p->~value_type(); }
    
    	lazy_buffer<>* get_buffer() const { return buffer_; }
    
    private:
    	lazy_buffer<>* buffer_;
    };
    
    int main()
    {
    	static const std::size_t expected_size = 2; // "mean" number of elements
    	static const std::size_t reserved_size = 3 * expected_size / 2; // optimal number of reserved elements to minimize probability of buffer exhaustion
    	static const std::size_t reserved_memory_size = 3 * reserved_size * sizeof(int); // estimate of the actual memory per element consumption
    
    	lazy_buffer<reserved_memory_size>  abuffer;
    	std::list<int,lazy_allocator<int>> alist( abuffer );
    
    	alist.push_back(0);
    	alist.push_back(1);
    
    	// ... ^ no heap allocations in vc2010
    }
    PS1: not tested, just a copy&past exercise
    PS2: clearly, the code above ignores memory alignment and pointer representation issues, thus is wrong, in general. Moreover, it could be interesting to add further customization, like abstracting allocations relative to the "expected" memory access pattern ...
    PS3: implementing this would be much more easier in c++11 thanks to allocator_traits ( no need to define allocator members with obvious definition ) and std::align(); unfortunately, vc2010 supports none of them

  10. #10
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,725

    Re: Custom allocator problems

    Thanks, I'll give that a look.
    What I want is something like that, but with no fallback.

    I've spent all morning trying to come up with a bounded size allocator that doesn't blow up with VS2010 or leak memory, with no luck yet. I was about ready to throw in the towel.
    Last edited by JohnW@Wessex; March 6th, 2012 at 05:46 AM.
    "It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
    Richard P. Feynman

  11. #11
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,725

    Re: Custom allocator problems

    Thanks for the help, but I've run out of time to try and get something working

    I'm beginning to think that the allocator implementation that I am after may be impossible with STL containers. Or at least, far more difficult than I'm prepared to spend time on.

    I could probably have written and debugged an array based linked list class in the time I've wasted on this!
    "It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
    Richard P. Feynman

  12. #12
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,013

    Re: Custom allocator problems

    Quote Originally Posted by JohnW@Wessex View Post
    Here's a demo that compiles correctly with both VS2008 & VS2010, but exceptions under VS2010.
    I didn't test it, but wouldn't the solution be to take the buffer out of the allocator? Something like
    Code:
    int main()
    {
        const size_t MAX_SIZE = 1024; // bytes
        char buffer[MAX_SIZE];
    
        std::vector<int, ArrayAllocator<int, MAX_SIZE>> test(
            ArrayAllocator<int, MAX_SIZE>(buffer));
    //...
    }
    where the buffer is passed to the allocator's constructor.
    Cheers, D Drmmr

    Please put [code][/code] tags around your code to preserve indentation and make it more readable.

    As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky

  13. #13
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,725

    Re: Custom allocator problems

    I think I've tried some variations of that, given superbonzo's comments , but I'll give it a second look.

    Whenever I've put together an allocator that returns the same address as previously (which in theory should be perfectly valid for a vector of objects with trivial destructors, as I don't actually have to allocate more memory and move any data, just let it use more of the original array), VS2010 exceptions.

    An experimental bodge that returned the last address+1 at every call kept it happy. (though of course it wasn't a solution)

    I even tried alternating between two arrays to no avail.

    It seems to expect that all allocations will be at new and unique addresses.
    "It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
    Richard P. Feynman

  14. #14
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,013

    Re: Custom allocator problems

    Quote Originally Posted by JohnW@Wessex View Post
    Whenever I've put together an allocator that returns the same address as previously (which in theory should be perfectly valid for a vector of objects with trivial destructors, as I don't actually have to allocate more memory and move any data, just let it use more of the original array), VS2010 exceptions.
    It's not valid in general. Take the situation where you create two vectors using the same allocator (i.e. the same instance of your allocator class, thus using the same buffer). They would be writing to each other's memory.

    With what you describe here, it seems that you are trying to change the behavior (or at least the implementation) of vector through the allocator. I think you'd be better of writing your own container class(es).
    Cheers, D Drmmr

    Please put [code][/code] tags around your code to preserve indentation and make it more readable.

    As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky

  15. #15
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,725

    Re: Custom allocator problems

    Quote Originally Posted by D_Drmmr View Post
    It's not valid in general. Take the situation where you create two vectors using the same allocator (i.e. the same instance of your allocator class, thus using the same buffer). They would be writing to each other's memory.
    The idea was that different vectors wouldn't use the same allocator instance. The allocators would also be marked as 'non-equivalent' via the overloaded == and != allocator operators.

    Quote Originally Posted by D_Drmmr View Post
    I think you'd be better of writing your own container class(es).
    I'm beginning to think the same. I'm just not looking forward to the implementations of set & map!
    "It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
    Richard P. Feynman

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center