Thread: 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;
}

Originally Posted by laserlight

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.

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.

Originally Posted by homer_3

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.

Originally Posted by homer_3

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.