Trouble with custom allocator

This is a discussion on Trouble with custom allocator within the C++ Programming forums, part of the General Programming Boards category; This question is partially related to Boost so I'm hoping someone here will still be able to help. I haven't ...

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    119

    Trouble with custom allocator

    This question is partially related to Boost so I'm hoping someone here will still be able to help. I haven't been able to find a Boost forum anywhere, only a mailing list.

    I'll start by stating the problem I'm trying to solve. I want to be able to look up both negative and positive values and have them map to some other value. So I'm thinking some kind of map is the best way to do this. From reading about map, it sounds like it's slow and has O(n) since it iterates from the start of the map up to the key. If I'm wrong about that, let me know.

    So instead, I plan to use an unordered map. Specifically Boost's unordered map since I don't have the standard unordered map available to me.

    Here's where it gets tricky. The values I want to use as keys are floats. I also want to use a preset pool of memory. After a lot of googling, I found a solution that works with all of this except it only works on std::maps. When I try to use a custom allocator with boost::unordered_map, I get a segfault on my 4th insert into my map, and the 3rd insert ends up storing a wrong value (again, when used with std::map, everything works fine).

    Is there anyone here familiar enough with Boost to see what is causing this? It could also be a general C++ error, I'm not sure. You'll probably also notice I've commented out code dealing with freeing any memory. That's because I don't care about freeing the maps memory. The map is populated once on start up and then only read from until the program exits. I didn't want to deal with that extra complication since I really didn't need to.

    Custom Allocator header
    Code:
    #ifndef __CUSTOM_ALLOCATOR_H__
    #define __CUSTOM_ALLOCATOR_H__
    
    #include <assert.h>
    #include <limits.h>
    
    template<class T>
    class Custom_Allocator
    {
    
    public:
    
      typedef T value_type;
      typedef size_t size_type;
      typedef ptrdiff_t difference_type;
      typedef T* pointer;
      typedef const T* const_pointer;
      typedef T& reference;
      typedef const T& const_reference;
    
      Custom_Allocator( signed char *pool, int nPoolSize )
      {
        Init();
        m_pool = pool;
        m_nPoolSize = nPoolSize;
      }
    
      Custom_Allocator( int n )
      {
        Init();
      }
    
      Custom_Allocator()
      {
        Init();
      }
    
      void Init()
      {
        m_pool = 0;
        m_nPoolSize = 0;
        g_nCnt = 0;
        g_nTot = 0;
      }
    
      Custom_Allocator( const Custom_Allocator &obj ) // copy constructor
      {
        Init();
        m_pool = obj.m_pool;
        m_nPoolSize = obj.m_nPoolSize;
    
      }
    
    private:
    
      long g_nCnt; // total # blocks allocated
      long g_nTot; // total allocated
    
      void operator =( const Custom_Allocator & );
    
    public:
    
      signed char *m_pool;
      unsigned m_nPoolSize;
    
      template<class _Other>
      Custom_Allocator( const Custom_Allocator< _Other > &other )
      {
        Init();
        m_pool = other.m_pool;
        m_nPoolSize = other.m_nPoolSize;
      }
    
      ~Custom_Allocator()
      {
    
      }
    
      template<class U>
      struct rebind
      {
        typedef Custom_Allocator< U > other;
      };
    
      pointer  address( reference r ) const
      {
        return &r;
      }
    
      const_pointer address( const_reference r ) const
      {
        return &r;
      }
    
      pointer allocate( size_type n, const void* /*hint*/= 0 )
      {
        pointer p = 0;
        unsigned nSize = n * sizeof(T);
    
        if( m_pool ) // if we have a mem pool from which to allocated
        {
          p = (pointer) m_pool;// just return the next available mem in the pool
    
          if( g_nTot + nSize > m_nPoolSize )
          {
            assert( 0 );//,"out of mem pool");
            return 0;
          }
    
          m_pool += nSize; // and bump the pointer
        }
        else
        {
    //      p = (pointer) malloc( nSize );// no pool: just use malloc
        }
    
        g_nCnt += 1;
        g_nTot += nSize;
        assert( p );
    
        return p;
      }
    
      void deallocate( pointer p, size_type /*n*/)
      {
    //    if( !m_pool )// if there's a pool, nothing to do
    //    {
    //      free( p );
    //    }
      }
    
      void construct( pointer p, const T& val )
      {
        new (p) T( val );
      }
    
      void destroy( pointer p )
      {
        p->~T();
      }
    
      size_type max_size() const
      {
        return ULONG_MAX / sizeof(T);
      }
    };
    
    template<class T>
    bool operator==( const Custom_Allocator< T >& left, const Custom_Allocator< T >& right )
    {
      if( left.m_pool == right.m_pool )
      {
        return true;
      }
      return false;
    }
    
    template<class T>
    bool operator!=( const Custom_Allocator< T >& left, const Custom_Allocator< T >& right )
    {
      if( left.m_pool != right.m_pool )
      {
        return true;
      }
    
      return false;
    }
    #endif
    Container header
    Code:
    #ifndef __CONTAINER_H__
    #define __CONTAINER_H__
    #include <boost/unordered_map.hpp>
    #include <Custom_Allocator.h>
    
    using namespace std;
    using namespace __gnu_cxx;
    
    template<float const &threshold> class compare_float {
      public:
        compare_float() : m_d(threshold){}
        inline bool operator()(const float &x, const float &y) const { return ((x + m_d) < y); }// return abs(abs(x)-abs(y))<m_d; }
        float m_d;
    };
    
    class Container
    {
    public:
      static const float map_threshold;
    
      Container();
    
    private:
      typedef Custom_Allocator<std::pair<float, float> > MyAllocator;
      boost::unordered_map<float, float, boost::hash<float>, compare_float<map_threshold>, MyAllocator >map_test;
      static const float c_max_key = 10.0f;
      static const float c_min_key = -10.0f;
    };
    #endif
    Container Source
    Code:
    #include <Container.h>
    #include <stdio.h>
    
    const float Container::map_threshold = .001f;
    signed char map_pool[sizeof(float)*3000];
    
    Container::Container() : map_test(MyAllocator(map_pool, sizeof(map_pool)))
    {
      for(float i = c_min_key; i < c_max_key + .1f; i += .1f)
      {
    	printf("Storing: %f => %f.\n", i, (i*1000.0f));
        map_test[i] = i*1000.0f;
        printf("Stored:  %f => %f.\n", i, map_test[i]);
        printf("++++++++++++++++++++++++++++++\n");
      }
    
      printf("=====================================\n");
    
      printf("%f.\n", map_test[1.2f]);
      printf("%f.\n", map_test[-1.2f]);
      printf("%f.\n", map_test[6.2f]);
      printf("%f.\n", map_test[-13.2f]);
      printf("%f.\n", map_test[.2f]);
    }
    Main
    Code:
    #include <Container.h>
    
    int main()
    {
    	Container c;
    
    	return 0;
    }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,593
    Quote Originally Posted by homer_3
    From reading about map, it sounds like it's slow and has O(n) since it iterates from the start of the map up to the key. If I'm wrong about that, let me know.
    Whether it is "slow" depends on your requirements and the data, but when it comes to finding an element in a std::map given a key, the time complexity is required to be logarithmic. If the implementation has linear time complexity, then it has a bug.

    By the way, names that begin with an underscore followed by an uppercase letter, or that contain consecutive underscores, are reserved to the implementation for any use. Therefore, you should not use __CUSTOM_ALLOCATOR_H__. Something like HOMER_3_CUSTOM_ALLOCATOR_H, maybe including the current date, would probably suffice.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Nov 2008
    Posts
    119
    Quote Originally Posted by laserlight View Post
    Whether it is "slow" depends on your requirements and the data, but when it comes to finding an element in a std::map given a key, the time complexity is required to be logarithmic. If the implementation has linear time complexity, then it has a bug.

    Thanks. I should have kept reading the description on cplusplus.com. It did say they are typically implemented as binary search trees after saying they were slower than unordered maps. /facepalm

    I'm thinking that should be fast enough. My map won't be that big (~3000 items). Maybe I'll just stick with maps and work on creating something to profile the access performance.

  4. #4
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,214
    O_o

    I admit I didn't look at the code for that long as I have a bit of a headache today, but I think you have a very serious issue.

    I think your allocator is "stateful". The allocator looks to me like you are using member variables to reference a pool that the individual allocator instances own.

    If that is not the case, you can stop reading now and chock this up to me being dumb today.

    If that is the case, you need to understand that such "stateful" allocators are allowed but not required by the standard.

    This means that some standard library implementations will support allocators carrying state properly while other implementations will fail.

    Let me give you an example:

    Code:
    {
    std::list<int, myalloc<int> > s1; // This is a default constructed object.
    std::list<int, myalloc<int> > s2; // This is a default constructed object.
    // We add elements to `s1' and `s2'.
    s1.splice(s1.begin(), s2);
    // The `s2' list has no elements so is not relevant.
    // The `s1' list is now destroying the elements owned
    // using the allocator as obtained from using `rebind'
    // and copy-constructing the altered custom allocator
    // from the default-constructed parameter of the
    // default constructed `std::list' object.
    }
    Now again, several implementations will get this right, but several implementations will also simply crash due to trying to free and destroy an object the relevant allocator knows nothing about.

    Note: C++11 clarified and refined some of the rules which makes allocators with "state" far more reliable.

    If you want to do the job and be strongly portable, bind the strategy (*) to a type using an extra parameter for the allocator, forward this type with `rebind', and use static members to store references to the pool.

    *shrug*

    If you don't understand this, feel free to just continue as you are and hope you have a strong standard library implementation.

    Soma

    (*) The strategy would be things like the relevant pool, pool size, and target element size.

  5. #5
    Registered User
    Join Date
    Nov 2008
    Posts
    119
    Quote Originally Posted by homer_3 View Post
    I'm thinking that should be fast enough. My map won't be that big (~3000 items). Maybe I'll just stick with maps and work on creating something to profile the access performance.
    Well crap. After profiling, the map lookup is too slow So I guess it's back to trying to figure out why what I have crashes.

  6. #6
    Registered User
    Join Date
    Nov 2008
    Posts
    119
    Quote Originally Posted by homer_3 View Post
    Well crap. After profiling, the map lookup is too slow So I guess it's back to trying to figure out why what I have crashes.
    Actually, I found I was off by a power of 10 in my measurement, so it's not as big an issue as I thought.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. std::allocator <memory>
    By Imanuel in forum C++ Programming
    Replies: 0
    Last Post: 02-13-2013, 07:49 AM
  2. std::allocator <memory>
    By Imanuel in forum C++ Programming
    Replies: 2
    Last Post: 02-08-2013, 07:05 PM
  3. Allocator
    By darren78 in forum C++ Programming
    Replies: 2
    Last Post: 09-07-2010, 07:57 AM
  4. allocator::destroy
    By dra in forum C++ Programming
    Replies: 8
    Last Post: 03-03-2008, 10:33 AM
  5. Allocator
    By Scarvenger in forum C++ Programming
    Replies: 2
    Last Post: 01-08-2008, 09:30 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21