Lecture Notes for Advanced Programming II

16 December 2003 - Allocators

A Simple Vector Class

template < typename T >
class vtr

  public:

    vtr() : elements(0), size(0), max(0) { }

    void push_back(const T & v)
      if size >= max, grow()
      assert(size <= max)
      elements[size++] = v

  private:

    T * elements
    size_t size, max

    void grow()
      max = (max == 0 ? 1 : max*2)
      T * const ne = new T [max]
      for size_t i = 0; i < size; i++
	ne[i] = elements[i]
      delete [] elements
      elements = ne

An Expensive Vector Class

grow() is expensive.

void grow()
  max = (max == 0 ? 1 : max*2)
  T * const ne = new T [max]

  for size_t i = 0; i < size; i++
    ne[i] = elements[i]

  delete [] elements
  elements = ne

The new allocates and initializes new elements.
The assignment clobbers them with old elements.

The `memcpy()` Optimization

Can't we replace

  for size_t i = 0; i < size; i++
    ne[i] = elements[i]

with

memcpy(ne, elements, sizeof(T)*size)

Absolutely not!
- There's still the new overhead.
- memcpy() violates the Rule of Three in so many ways.
  - Dangling pointers, in particular.

C vs. C++ Storage Management

Well, how about

void grow()
  max = (max == 0 ? 1 : max*2)
  T * const ne = 
    static_cast<T *>(malloc(sizeof(T)*max))
  memcpy(ne, elements, sizeof(T)*size)
  free(elements)
  elements = ne

This doesn't work either, for much sublter reasons.
- push_back() is now broken.
  - Assignment doesn't work on the uninitialized elements.
- ~vtr is broken for the same reason.
  - Destructing uninitialized elements.
- memcpy() still subverts the Rule of Three.
  - Consider a class with pointers to member variables.
We need C-style storage management that understands C++ class-instance construction and destruction.

Allocators

The part of the STL of which we did not speak.
Allocators implement storage-management models.

Allocators are an optional, default-specified parameter on containers and other library components.

template < 
  typename ElementT, 
  class Allocator = allocator<ElementT> >
class vector;
  
template <
  typename CharT,
  class Traits = char_traits<CharT>,
  class Allocator = allocator<CharT> >
class basic_string;

typename basic_string<char> string;

Allocators are general purpose, and may be used anywhere storage-management is required.
- This talk is STL-oriented, but allocators are not.

Storage Management

C++ storage management is concerned with two things:
1. Allocating and deallocating storage chunks.
2. Initializing allocated chunks and cleaning-up deallocated chunks.
C storage management is concerned only with allocation and deallocation.
- Which is why you shouldn't use delete on malloc()ed storage.
- And shouldn't use free() on newed storage.
- There are other reasons too.
This lecture is about with C++ storage management.
- C can have similar capabilities with extra work.

Storage Allocation and Deallocation

Storage allocation carves a chunk of storage off available free storage.
- Usually but not necessarily the heap.
Storage Deallocation returns a chunk of storage to the free stoage.
Allocation and deallocation do nothing to the allocated storage itself.
- This is sometimes known as raw storage.

Storage Initialization and Clean-Up

Storage initialization initializes raw storage.
There are three forms of storage initialization.
- Default initialization for plain-old-type (POT) data is no initialization at all (or initialization to an undefined value).
- Class-instance initialization is controlled by the appropriate constructor.
- Value initialization sets POT data to some value.
  - Globals are initialized to (the equivalent of) zero.
- See Koenig and Moo, Section 9.5.
Storage clean-up takes working storage and cleans it up.
- Class instances are cleaned-up as directed by the destructor.
- POT data are not cleaned-up, unless they're part of a class and the destructor does something to them.

`new` and `delete`

The operator new is responsible for allocation and initialization.
- new is complicated and confusing.
- There is what Stroustrup calls "operator new" and "operator new()"
  - operator new() isn't required to initialize storage.
The operator delete is responsible for clean-up and deallocation.

The Allocator Storage-Management Abstraction

The std::allocator<T> class is an abstraction for storage-management policies.
- Each allocator-class instance is a particular form of storage management.
  - A persistent-storage allocator, a shared-storage allocator, a debugging allocator and so on.
Using a particular allocator in a container instantiation gives the container the properties of the allocator.
- A persistent vector, a shared-storage map, a debugging list.
Allocators are defined in the <memory> header of the standard library.

The Allocator Class

template < typename T >
class allocator {

  public:

    T * allocator(size_t);
    void deallocate(T *, size_t);
    void construct(T *, const T &);
    void destroy(T *);

  // Lots o' other stuff.
  }

allocator(i) allocates enough uninitialized storage for i elements of type T.
- The allocated storage size is sizeof(T)*i.
deallocate(p, i) frees the storage pointed to by pfor i elements of type T.
construct(p, v) uses the T value v to initialized the storage pointed to by p.
destroy(p) calls T's destructor on the storage pointed to by p.

An Improved Vector Class

template <typename T> class avtr

  public:

   ~avtr() { uncreate() }

  private:

    std::allocator<T> alloc

    void grow()
      max_size = max(max_size*2, ptrdiff_t(1))
      T * ne = alloc.allocator(max_size)
      uninitialized_copy(data, data + size, ne)
      uncreate()
      data = ne

    void uncreate()
      for i = data + size - 1; i != data; i--
	alloc.destroy(i)
      alloc.deallocate(data, size)

uninitialized_copy(b, e, n) copies the values in (b, e) to the uninitialized storage pointed to by n.
- It calls T's copy constructor with *b as a parameter.
- It's a helper function in <memory>.

Does It Work?

Intel, Linux, g++.
Unweighted average of 100 iterations per array size.
See the complete code.

This page last modified on 19 December 2003.