// Simple-minded code to determine the performance of various node-management
// strategies.
//
// CS 306 - Computer Algorithms II
// Fall '08
#include <iostream> // for printf()
#include <numeric> // for accumulate()
#include <cassert> // for assert()
#include "stopwatch.h"
// The node that's being managed.
template <typename t>
struct node {
t data
node * left, * right
}
// One of the node element types; the other is an int.
struct point {
double x, y, z
}
// A static node manager.
template <typename t, unsigned node_count = 1000>
class static_node_mgr {
public:
typedef node<t> node_type
node_type * alloc() {
if (free_list) {
node_type * const n = free_list
free_list = n→left
return n
}
assert(!"no more nodes")
return 0
}
void free(node_type * n) {
n→left = free_list
free_list = n
}
static_node_mgr() {
for (unsigned i = 1; i < node_count; i++)
nodes[i - 1].left = nodes + i
free_list = nodes
nodes[node_count - 1].left = 0
}
private:
node_type nodes[node_count]
node_type * free_list
}
// A simple node manager that calls new on every allocation and delete on every
// deallocation. This is the least sophisticated and presumably lowest
// performing of the dynamic node managers.
template <typename t>
class simple_node_mgr {
public:
typedef node<t> node_type
node_type * alloc() {
return new node_type
}
void free(node_type * n) {
delete n
}
}
// A free-list node manager. Deallocated nodes are hung up on the free list
// rather than being passed on to delete. Allocations first check the free
// list and, if the free list is empty, then call new.
template <typename t>
class flist_node_mgr {
public:
typedef node<t> node_type
node_type * alloc() {
if (not free_list) {
free_list = new node_type
free_list→left = 0
}
node_type * n = free_list
free_list = n→left
return n
}
void free(node_type * n) {
n→left = free_list
free_list = n
}
flist_node_mgr() : free_list(0) { }
~flist_node_mgr() {
while (free_list) {
node_type * n = free_list
free_list = n→left
delete n
}
}
private:
node_type * free_list
flist_node_mgr(flist_node_mgr &) { }
flist_node_mgr & operator = (const flist_node_mgr &) { return *this; }
}
// A block node manager. Similar to the free-list node manager except it
// allocates a bunch of nodes when the free list is empty rather than just one
// as the free-list manager does. The size of the block in elements is passed
// in as the integral template parameter bs.
template <typename t, unsigned bs>
class block_node_mgr {
public:
typedef node<t> node_type
node_type * alloc() {
if (not free_list) {
if (free_list_next == free_list_end) {
free_list_next = new node_type [bs]
free_list_end = free_list_next + bs
free_list_next→left = block_list
block_list = free_list_next++
}
free_list = free_list_next++
free_list→left = 0
}
node_type * n = free_list
free_list = n→left
return n
}
void free(node_type * n) {
n→left = free_list
free_list = n
}
block_node_mgr()
: free_list(0), free_list_next(0), free_list_end(0), block_list(0)
{ }
~block_node_mgr() {
while (block_list) {
node_type * n = block_list
block_list = n→left
delete [] n
}
}
private:
// Points to the next free node to allocate. If free_list == 0, there
// are no free nodes available.
node_type * free_list;
// Points to the first unallocated node in the most recently allocated
// block. The node pointed to by free_list_next is the one that will be
// moved to the free list when the free list is empty.
node_type * free_list_next
// Points to one past the last unallocated node in the most recently
// allocated block. It's time to allocate a new block when
// free_list_next == free_list_end.
node_type * free_list_end
// Head of the list of blocks allocated. The first node of the block is
// used as the list link and is not available for allocation.
node_type * block_list
block_node_mgr(block_node_mgr &) { }
block_node_mgr & operator = (const block_node_mgr &) { return *this; }
}
// Deja vu c++ style.
template <typename t>
static void run_test(unsigned *, unsigned, t &, const char * const)
template<typename t>
static void
do_test(unsigned a[], unsigned n) {
// Test the node managers on nodes containing elements of type t. The
// n-element array a contains allocation-deallocation pattern to use for the
// test.
simple_node_mgr<t> snm
flist_node_mgr<t> fnm
block_node_mgr<t, 1000u> bnm
static_node_mgr<t, 200000u> stnm
run_test(a, n, snm, "simple")
run_test(a, n, stnm, "static")
run_test(a, n, snm, "simple")
run_test(a, n, fnm, "free-list")
run_test(a, n, bnm, "block")
}
int
main() {
// Write to std-out some performance data for various node managers executing
// a synthetic allocation-deallocation pattern.
const unsigned size = 1000
unsigned cnts[size]
srandom(getpid())
for (unsigned i = 0; i < size; i++)
cnts[i] = random() % 100000
printf("%9u aloc-frees\n", std::accumulate(cnts, cnts + size, 0u))
do_test<int>(cnts, size)
}
template <typename t>
static void
run_test(unsigned a[], unsigned n, t & nm, const char * const name) {
// Run performance tests on the node manager nm with the identifier name.
// The n-element array a contains the synthetic allocate-deallocate load:
// allocate a[i] nodes then deallocate them.
stopwatch sw
sw.start()
for (unsigned i = 0; i < n; i++) {
typename t::node_type
* nd = nm.alloc(),
* n2 = nd
unsigned j
for (j = 0; j < a[i]; j++)
n2 = n2→left = nm.alloc()
n2 = nd
for (j = 0; j < a[i]; j++) {
typename t::node_type * n3 = n2
n2 = n3→left
nm.free(n3)
}
}
sw.stop()
const double ops = 2*std::accumulate(a, a + n, 0u)
printf("%9s %9u usec., %g usec/pair\n",
name, sw.elapsed(), sw.elapsed()/ops)
}
// $Log: node-mgr.cc,v $
// Revision 1.2 2007-09-23 15:19:28 rclayton
// Remove some unneeded includes.
//
// Revision 1.1 2007-09-16 22:20:06 rclayton
// Created.
//
syntax highlighted by Code2HTML, v. 0.9.1