• But not necessarily new and delete.

Dynamic Storage and Classes

• Three class specific problems - destructors, copying, and assignments.

• Worse than dynamic storage and exceptions; leaks apos(o, ) plenty.

Compile-Time Allocation

• Use a big-enough array to hold the data.

  • Grossly over-estimating the worst case size.

  • It wastes space, but so what?

• Good for small amounts of data with small variability.

  • The more data, the more waste.

  • Highly variable data may be too big too often.

Compile-Time Problems

• Space inefficient, but implementation- and run-time efficient.

  • However, run-time costs include virtual storage behavior.

• Not flexible, but safe with proper checking.

  • Make sure you do the checking.

  • This is a dangerous form of program design.

• Also known as pre-allocation.

Example

• Compute statistics for everyone at Monmouth.

  • Assumption: the data set is small and slowly varying.

  • Around 6,000 students.

  • Double for the administrators - 12,000 total.

  • Double it to be safe - 24,000 total.

      const unsigned mu_population = 24000
      static personnel_record[mu_population]

  • Around 5 meg at 200 bytes/record.

Class and Pointers

struct C {
  data * data_ptr;
  C() : data_ptr(new data) { }
  };

static void t(void) { C c; }

• apos(What, s) wrong with this code?

  

Destructors and Pointers

• If a class allocates it, the class should free it.

  struct C {
    data * data_ptr;
    C() : data_ptr(new data) { }
   ~C() { delete data_ptr; }
    };

• The class destructor frees class-allocated storage.

  

Classes and Pointers II

struct C {
  data * data_ptr;
  C() : data_ptr(new data) { }
 ~C() { delete data_ptr; }
  };

static void t(C & c) { C local_c(c); }

• apos(What, s) wrong with this code?

  

Class Instance Copying

• By default, class instances are byte-wise copied.

• This replicates pointers, leading to un-intented sharing and dangling pointers on destruction.

• Class instance copying happens all the time.

  • For example, non-reference class parameters.

    void t(C c) {...}

    The call t(c) makes a copy of c.

The Copy Constructor

• A copy constructor handles dynamic-storage copying.

  • The prototype is C::C(const C &).

  • apos(Don, t) forget the reference &.

• The details depend on the storage being managed.

  • Assume internal data has copy constructors too.

Copying Data

struct C {
  data * data_ptr;
  C() : data_ptr(new data) { }
 ~C() { delete data_ptr; }
  C(const C & c) 
    : data_ptr(new data(*(c.data_ptr))) {...}
  };

• The copy constructor replicates data.

  

Classes and Pointers III

struct C
  data * data_ptr;
  C() : data_ptr(new data) { }
 ~C() { delete data_ptr; }
  C(const C & c) 
    : data_ptr(new data(*(c.data_ptr))) {...}

static void t(C & c) {C local_c; local_c = c;}

• apos(What, s) wrong with this code?

  

Class Instance Assignment

• Instance assignment is similar to instance copying.

• The default assignment copies byte-by-byte.

  • This leads to unintended sharing, dangling pointers, and garbage.

    • The previous contents of local_c.data_ptr is garbage.

    • local_c.data_ptr and c.data_ptr are sharing storage.

Assignments

• Classes should define an assignment operator to manage storage during assignments.

• Dynamic storage management in assignments involves:

  1. Deallocating storage in the instance to the left of the =.

  2. Duplicating storage from the instance to the right of the =.

  3. Doing the pointer assignment.

The Assignment Operator

struct C
  data * data_ptr;
  C() : data_ptr(new data) {...}
  C(const C & c) 
    : data_ptr(new data(*c.data_ptr)) {...}
 ~C() { delete data_ptr; }
  // Bad example.
  C & operator = (const C & c) { 
    delete data_ptr;
    data_ptr = new data(*c.data_ptr);
    return *this;
    }

Assignment Fine Points

• apos(There, re) two fine points to keep in mind about assignments:

  1. Self-assignments.

     • Getting self-assignments right is necessary.

  2. Assignments as expressions.

     • Not as important, but expected behavior.

Self Assignment

• An expression like c = c is a self-assignment.

  • Self-assignment occurs in code, particularly with references and parameters.

  • This is a source of nasty errors.

• What happens with c = c?

  

The Self-Assignment Problem

• What went wrong?

  C & C::operator = (const C & rhs) {
    delete data_ptr;
    data_ptr = copy_data(rhs.data_ptr);
    return *this;
    }

• Deallocating in lhs also deallocates in rhs.

  • For c = c, *this = rhs.

  • Deleting data_ptr deletes rhs.data_ptr.

Handling Self-Assignment

• Make sure *this is different from rhs.

  • If *this and rhs are different, proceed as normal.

  • If *this and rhs are the same, do nothing.

  C & C::operator = (const C & rhs) {
    if (this != &rhs) {
      delete data_ptr;
      data_ptr = new data(*(rhs.data_ptr));
      }
    return *this;
    }

Assignments as Expressions

• A little-known C++ fun fact: an assignment is an expression.

  • x = y = z = 0.0;

  • if ((ch = getch()) != EOF) ...

  • The value of an assignment is the value on the left after assignment.

• Overloaded assignment should support this behavior.

Assignment Prototype

• The assignment prototype

  T & operator = (const T & rhs)
  

  • The prototype can be different, but it usually apos(shouldn, t) be.

• Value reference returns should be a red flag.

  • In this case, a returning a value reference is efficient and safe.

  • The assignment returns *this.

Seeming Assignments

• apos(What, s) the difference between

  C c2 = c1;
  

  and

  c2 = c1;
  

  Or maybe apos(there, s) no difference?

• Assignment redefines a defined instance,

  copying constructing defines an undefined instance.

Assignment vs. Copying

• Despite the syntax, declared variables are initialized; the target state is undefined.

  • The alternative syntax is C c2(c1);

  • Getting it wrong means unintentional replication and dangling pointers.

• In assignment, the target is defined and is redefined.

  • Getting it wrong means unintentional replication, dangling pointers and garbage.

Assigning and Copying

• Assignment and copy constructors usually can share code.

  class blob {
    public:
  
      ~blob() { delete(); }
      blob(const blob & b) { copy(b); }
      blob & operator = (const & blob b)
        { if (&b != this) { delete(); copy(b); } }
  
    private:
  
      void copy(const & blob b) {...}
      void delete() {...}
    };

The Rule of Three

• The Rule of Three:

  If a class implements a destructor, a copy constructor, or an assignment operator, then it needs to implement all three.

• More simply:

  A class with pointer instance variables must have a destructor, a copy constructor, and an assignment operator.

• The rule is non-symmetric, and not hard and fast.

Observations

• A destructor without a body breaks the rule.

  • A virtual destructor tends to have no body.

• Either the other two may or may not imply the other two.

  • Implemented for debugging or performance analysis.

• However, any class with explicit pointers must obey the rule.

Extended Example

• A binary tree abstract data type (ADT).

• Node storage managed within a tree instance.

  • Static management,
    dynamic management,
    hybrid management.

  • Cost amortization.

Binary Trees

template <typename T>
class binary_tree {

  public:

    void add(const T & value);

    binary_tree();

    bool find(const T & value);

    void remove(const T & value);
  };

Implementation

template <typename T>
class binary_tree {

  private:

    struct node {
      T value;
      node * left, * right;
      };

    node * root;
  };

But Wait!

struct node {
  T value;
  node * left, * right;
  };

• What happened to the Rule of Three?

  • This class has pointer fields.

  • apos(Where, s) the destructor, copy constructor, and assignment operator?

Some Excuses

• node is a private class, managed privately.

  • Implicit assumption: apos(I, m) perfect and never make mistakes.

• No node values, only pointers to node values.

  • Never node n, always node * n.

  • Class destructors, copy constructors, and assignments work on instances, not instance pointers.

    • They apos(aren, t) used on node * values.

Validate Assumptions

• Validate the pointer-value-only assumption with the Rule of Three:

  class node {
    public:
  
      T value;
      node * left, * right;
  
    private:
  
     ~node() { }
      node(const node &) { }
      node & operator = (const node &) 
        { return *this; }
    };

Example

• Sometime later, turn the root into a node, not a node pointer.

  node * root;
  node root;
  

• The revised node class causes this compilation error (among others):

  t.cc:27: error: 
    'binary_tree::node::~node() 
     [with T = int]' is private
  t.cc:2: error: within this context
  

Problem Solved?

• Hint:

  template <typename T>
  class binary_tree {
  
    private:
  
      class node { . . . };
  
      node * root;
    };
  

• The Rule of Three is an automatic here.

Node Management

• Hide node management so apos(it, s) easy to change.

  template <typename T>
  class binary_tree {
  
    private:
  
      node * get_node();
      
      void ret_node(node *);
  

• Assume get_node() and ret_node() explode on errors.

Example

template <typename T>
void binary_tree<T>::
add(const T & value) {

  node * const n = get_node();

  n→value = value;
  n→right = 0;
  n→left = root;
  root = n;
  }

Storage Management

• From where do nodes come?

• First thought: use compile-time allocation.

  private: 
  
    static const unsigned node_count = 10000;
    node nodes[node_count];
  

• How do get_node() and ret_node() work?

  • What do they need to know to work?

Free Nodes

• get_node() needs to distinguish between nodes being used and nodes available for allocation.

• Add a field to the node.

  struct node {
    T value;
    node * left, * right;
    bool free;
    };
  

Free Fields

• Initialization (in the constructor):

  for (i = 0; i < node_count; i++)
    nodes[i].free = true;
  

• Allocation (in get_node()):

  for (i = 0; i < node_count; i++)
    if (nodes[i].free) { ... }
  // explode
  

• Deallocation (in ret_node()):

  node→free = true;
  

Free Lists

• Statically allocated nodes are reasonably efficient, except for allocation.

  • Searching for a free node is a loss.

• Thread the free nodes into a linked list.

  const unsigned node_count = 10000;
  node nodes[node_count];
  node * free_nodes;
  

  

Free-List Management

• Initialization (in the constructor):

  for (i = 1; i < node_count; i++)
    nodes[i - 1].left = &nodes[i];
  free_nodes = nodes;
  nodes[node_count - 1].left = 0;
  

• Allocation (in get_node()):

  if (free_nodes) { ... }
  // explode
  

• Deallocation (in ret_node()):

  n->left = free_nodes;
  free_nodes = n;
  

Tree Size

• Having to guess a maximum tree size is a pain.

  • And generally impossible for a binary-tree AST.

• The compile-time constraint seems severe, and it is.

  • But C++ templates are a compile-time programming facility.

  • Other languages are starting to add such facilities.

Template Tree Size

• Hand the problem off to the client with templates.

  template 
    <typename T, unsigned node_count = 512>
  class binary_tree {
    private:
      node nodes[node_count];
    };
  

• Now the client can decide.

  binary_tree<int, 100> ibt;
  binary_tree<std::string> sbt;
  

Dynamic Storage

• Avoid tree size problems by moving to dynamic storage for nodes.

• Also simplifies the class implementation by shifting node handling elsewhere.

  • Albeit perhaps to an elsewhere more expensive.

Dynamic-Storage Management

• No initialization needed because initially there's no nodes.

• Allocation:

  get_node() {
    return new node;
    }
  

• Deallocation:

  ret_node(node * n) {
    delete n;
    }
  

Dynamic Storage Costs

• The main cost for dynamic storage is allocation and deletion costs.

  • These may represent system calls.

• There may be other, second-order costs.

  • Such as cache and paging effects.

• How can the system cost of dynamic-storage management be reduced?

Avoiding Redundant Work

• Allocating and deleting and then re-allocating nodes is redundant work.

• Avoid it by hanging deleted nodes on a free list.

• Allocation first checks the free list.

  • If it's empty, then system allocate a node.

  • This slightly complicates instance destruction.

Amortizing Costs

• Suppose the cost of something is (largely) independent of the amount of work done.

  • For example, the cost of allocation or deallocation is (roughly) independent of the chunk size.

• In such cases, increasing the amount of work done decreases the unit costs.

  • More work/same costs = cheaper work per unit costs.

• This trick is called amortizing costs.

Amortizing Dynamic Storage

• How can dynamic storage costs be amortized?

• The size of each request is not available for adjustment, nor can requests be batched.

  • In this case, the request size is fixed by the node size.

• However, the number of requests can be adjusted and batched.

  • Don't make 100 requests for one node,
    make 1 request for 100 nodes.

Block Allocation

• Splitting the difference is always a good choice:

  • Static allocation is efficient but inflexible.

  • Dynamic allocation is flexible but inefficient.

  • So, dynamically allocate large blocks and manage the blocks statically.

• This form of allocation is known as block allocation.

Does It?

• Around 50,000,000 alloc-free pairs.

  		int		point
  static		0.02		0.05
  simple		0.1		0.1
  free list		0.03		0.07
  block		0.02		0.05

  • Time in usec/alloc-free.

  • Block size is 1000 elements.

  • See the code.

Summary

• Use statically allocated storage.
  • But use it carefully, and well.
• Dynamic storage is not your friend.
• Learn and follow the Rule of Three.
  • The troika: destructors, copy constructors, assignment.

• Amortize storage-management costs.