Memory Management

Authors

Michael Seel (seel@.nosp@m.mpi-.nosp@m.sb.mp.nosp@m.g.de)

Efi Fogel (efif@.nosp@m.post.nosp@m..tau..nosp@m.ac.i.nosp@m.l)

One of the design goals of CGAL (Section Primary design goals ) is efficiency, and this means not only implementing efficient algorithms but also implementing them efficiently. One way to improve the efficiency of an implementation is through efficient memory management. This can be done by making the library data structures independent of the underlying memory model. However, to avoid unacceptable efficiency degradations complete abstraction of the memory model should be avoided. Here we describe one way to address this using allocators. An allocator encapsulates the information about an allocation model.

We adopted the definition of the Standard C++ allocator [3]. The std::allocator is the only predefined and required allocator imposed by [C++] on all C++ compiler implementations. The exact specification can also be found at https://en.wikipedia.org/wiki/Allocator_(C++).

Objects of type std::allocator<T> can be used to obtain small, typed chunks of memory to be used, for example, as static members of a class. This is especially interesting with classes of a constant size that are frequently allocated and deallocated (e.g., points, lines, circles), since a memory allocator can maintain the corresponding memory chunks in local blocks and thus can answer allocation and deallocation calls much faster than the corresponding system calls.

The allocator macro

The macro CGAL_ALLOCATOR(T) is defined as std::allocator<T> in the file <CGAL/memory.h>. CGAL_ALLOCATOR is used as the default allocator for all CGAL components. You can redefine it, for example, if LEDA is present, you can define it (before including any CGAL header file) as follows:

#include <LEDA/allocator.h>
#define CGAL_ALLOCATOR(t) leda_allocator<t>

Using the allocator

How should a data structure use the allocator mechanism? Just make the allocator one of the template arguments of the data structure. Then use a static member object to allocate items on the heap that you want to keep optimized regarding allocation and deallocation. We show an example using a trivial list structure:

#include <CGAL/memory.h>

template <typename T> 
class dlink 
{ T some_member; };

template < typename T, typename Alloc = CGAL_ALLOCATOR(dlink<T>) >
class list 
{
public:
  typedef dlink<T>* dlink_ptr;
  typedef Alloc list_allocator;

  static list_allocator M;

list() {
  p = M.allocate(1);          // allocation of space for one dlink
  M.construct(p,dlink<T>());  // inplace construction of object
}

~list() {
  M.destroy(p);      // destroy object
  M.deallocate(p,1); // deallocate memory
}

private:
  dlink_ptr p;
};

// init static member allocator object:
template <typename T, typename Alloc>
typename list<T,Alloc>::list_allocator list<T,Alloc>::M =
             typename list<T,Alloc>::list_allocator();

int main()
{
  list<int> L;
  return 0;
}

Requirements and recommendations

Recommendations:

• Use an allocator template parameter (which defaults to CGAL_ALLOCATOR) for data structures for which an optimization with regard to allocation and deallocation is beneficial.