Computer Algorithms II Lecture Notes

13 September 2007 • Dynamic Storage Management

Outline

• Implementation binary trees.

• Node and storage management.

  • Free nodes, fields, and lists.

• Dynamic storage management and costs.

  • Redundancy and amortizing costs.

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.

  • Where's the destructor, copy constructor, and assignment operator?

Some Excuses

• node is a private class, managed privately.

  • Implicit assumption: 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 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

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: 
  
    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 a compile-time programming facility.

  • And 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.

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 efficent 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.