Using allocators with Gecode
[Memory management]

Classes
struct	Gecode::space_allocator< T >
	Allocator that allocates memory from a space heap. More...
struct	Gecode::region_allocator< T >
	Allocator that allocates memory from a region. More...

---

Detailed Description

Gecode provides two allocator classes that can be used with generic data structures such as those of the STL (e.g. std::set). Memory can be allocated from the space heap (see Space) or from a region (see Region).

Using allocators with dynamic data structures

There are two possible scenarios for allocator usage. One is to let the dynamic data structure allocate memory from the space or region:

struct MySpace : public Space {
  typedef std::set<int, std::less<int>, Gecode::space_allocator<int> > S;
  S safe_set;

  MySpace(void)
    : safe_set(S::key_compare(), S::allocator_type(*this))
  {}

  MySpace(bool share, MySpace& other)
    : Space(share, other),
      safe_set(other.safe_set.begin(), other.safe_set.end(),
               S::key_compare(), S::allocator_type(*this))
  {}

  ...
};

In this example, S is a set that allocates its nodes from the space heap. Note that we pass an instance of space_allocator bound to this space to the constructor of the set. A similar thing must be done in the copying constructor, where we must be sure to pass an allocator that allocates memory from the destination ("this") space, not "other". Note that the set itself is a member of MySpace, so it is destroyed within MySpace::~MySpace as usual. The set destructor destroys all contained items and deallocates all nodes in its destructors.

Preventing unnecessary destruction overhead

In the above example, we know that the value type in S is a builtin type and does not have a destructor. So what happens during safe_set destruction is that it just deallocates all nodes. However, we know that all nodes were allocated from the space heap, which is going to disappear with the space anyway. If we prevent calling safe_set destructor, we may save a significant amount of time during space destruction. A safe way of doing this is to allocate the set object itself on the space heap, and keep only a reference to it as a member of the space. We can use the convenience helpers Space::construct for the construction.

struct MySpace : public Space {
  typedef std::set<int, std::less<int>, Gecode::space_allocator<int> > S;
  S& fast_set;

  MySpace(void)
    : fast_set(construct<S>(S::key_compare(), S::allocator_type(*this)))
  {}

  MySpace(MySpace& other)
    : Space(other),
        fast_set(construct<S>(other.safe_set.begin(), other.safe_set.end(),
        S::key_compare(), S::allocator_type(*this)))
  {}

  ...
};

Region example

The above examples were using a space_allocator. A region_allocator works similarly, one just should keep in mind that regions never really release any memory. Similar to Space, Region provides helper functions Region::construct to make non-stack allocation easy.

Space& home = ...;
typedef std::set<int, std::less<int>, Gecode::region_allocator<int> > SR;
// Create a set with the region allocator. Note that the set destructor is still quite costly...
{
  Region r;
  SR r_safe_set(SR::key_compare(), (SR::allocator_type(r)));
  for(int i=0; i<10000; ++i)
    r_safe_set.insert(i*75321%10000);
}
// Create a set directly in the region (not on the stack). No destructors will be called.
{
  Region r;
  SR& r_fast_set=r.construct<SR>(SR::key_compare(), SR::allocator_type(r));
  for(int i=0; i<10000; ++i)
    r_fast_set.insert(i*75321%10000);
}