Category : Files from Magazines
Archive : DDJ9406A.ZIP
Filename : MEMORY.ASC
Output of file : MEMORY.ASC contained in archive : DDJ9406A.ZIP
by Arthur D. Applegate
Listing One
//--------------------------------------------------------------------
// Memory management exerciser. By Arthur Applegate.
// Program 1: Creates, traverses, and destroys linked links, to show
// the effect of memory management on an application's performance.
//--------------------------------------------------------------------
#include
#include
#include
#include
//--------------------------------------------------------------------
// class Timer: Instances of this class, when declared as automatic
// variables, record and print the time block in which they are declared.
//--------------------------------------------------------------------
class Timer
{
private: const char *m;
clock_t startTime;
public: Timer(const char *msg) : m(msg), startTime(clock()) { }
~Timer()
{ printf("\n%s: %.2f seconds.", m,
(double)(clock()-startTime) / (double)CLOCKS_PER_SEC);
}
};
//-------------------------------------------------------------------
class Link // Link objects are list elements
{ friend class List;
public: Link (const char *val, Link *p, Link *n);
~Link ();
private: char *value;
Link *prev;
Link *next;
};
//-------------------------------------------------------------------
class List // List objects are doubly-linked lists
{
public: List ();
~List ();
const Link *Insert (Link *prev, const char *val);
void Delete (Link *remove);
void RandomOp ();
const Link *Find (const char *val) const;
private: Link *head;
Link *tail;
};
//------------------------------------------------------------------
// create a list element
Link::Link (const char *val, Link *p, Link *n)
{
value = new char[strlen(val)+1];
strcpy(value, val);
if ((prev = p) != NULL) prev->next = this;
if ((next = n) != NULL) next->prev = this;
}
//-----------------------------------------------------------------
Link::~Link () // destroy a list element
{
delete value;
if (prev) prev->next = next;
if (next) next->prev = prev;
}
//------------------------------------------------------------------
List::List () // create a new list: clear head, tail
{
head = tail = NULL;
}
//------------------------------------------------------------------
List::~List () // destroy list: delete each Link individually
{
while (head)
Delete(head);
}
//-----------------------------------------------------------------
// add a new link after specified element
const Link *List::Insert (Link *prev, const char *val)
{
Link *next = prev ? prev->next : head;
Link *l = new Link (val, prev, next);
if (!prev) head = l;
if (!next) tail = l;
return l;
}
//-----------------------------------------------------------------
void List::Delete (Link *l) // remove a link; no-op if link NULL
{
if (!l) return;
if (head == l) head = l->next;
if (tail == l) tail = l->prev;
delete l;
}
//-----------------------------------------------------------------
void List::RandomOp () // insert (80%) or delete (20%) an element
{
if (rand() % 5 != 0)
{
const maxStr = 64;
char buf[maxStr+1];
// generate a string of random length between
// 1 and 64 bytes, with random fill value
int len = rand() % maxStr + 1;
memset(buf, rand() % 128, len);
buf[len] = '\0';
Insert(tail, buf);
}
else
Delete(head);
}
//-----------------------------------------------------------------
// find the first element with a given value
const Link *List::Find (const char *val) const
{
for (register Link *l = head; l; l = l->next)
if (strcmp(l->value, val) == 0)
break;
return l;
}
//-----------------------------------------------------------------
void main(int argc, char *argv[])
{
if (argc < 2)
{
printf("\nusage: lists
return;
}
long count = atol(argv[1]);
Timer t("Overall Application");
List *list1 = new List, *list2 = new List, *list3 = new List,
*list4 = new List, *list5 = new List;
// test allocation speed
// note that to properly benchmark allocations, we need
// interspersed de-allocations since all allocators will
// be fast with an empty free-list!
{
Timer t("Insertion");
// generate and insert `count' strings of random lengths
// and contents; occasionally delete to simulate a
// dynamically shrinking and growing linked list
while (count--)
{
// intersperse each operation so that elements are
// chaotically distributed in memory if we do not
// have multiple memory pools
list1->RandomOp();
list2->RandomOp();
list3->RandomOp();
list4->RandomOp();
list5->RandomOp();
}
}
// test locality: each list will touch five times as many
// pages if allocations were from a single heap
{
Timer t("Search");
list1->Find("not present");
list2->Find("not present");
list3->Find("not present");
list4->Find("not present");
list5->Find("not present");
}
// destructors for list1-5: test freeing speed
// note that if properly implemented, freeing the memory pool
// will not even _touch_ the pages that contain the individual
// blocks -- so there is no swapping regardless of heap size
{
Timer t("Deletion");
delete list1;
delete list2;
delete list3;
delete list4;
delete list5;
}
}
Listing Two
//--------------------------------------------------------------------
// Memory management exerciser, version 2. By Arthur Applegate.
// This version has changes for improved performance. Only ten lines
// of code needed to be changed from version shown in Listing 1. These
// changes are indicated with "***" in the comment line.
//--------------------------------------------------------------------
#include
//--------------------------------------------------------------------
class Link
{ friend class List;
public: // *** constructor receives memory pool parameter
Link (MEM_POOL pool, const char *val, Link *p, Link *n);
~Link ();
private: // *** overload new/delete to use fixed-size algorithm,
// *** allocating from the owning List's memory pool
void *operator new(size_t, MEM_POOL pool)
{ return MemAllocFS(pool); }
void operator delete(void *mem) { MemFreeFS(mem); }
char *value;
Link *prev;
Link *next;
};
//--------------------------------------------------------------------
class List
{
public: List();
~List();
const Link *Insert(Link *prev, const char *val);
void Delete(Link *remove);
void RandomOp();
const Link *Find(const char *val) const;
private: Link *head;
Link *tail;
MEM_POOL pool; // *** per-List memory pool data member
};
//--------------------------------------------------------------------
// *** create a list element
Link::Link(MEM_POOL pool, const char *val, Link *p, Link *n)
{
// *** use placement syntax to allocate string
// *** from owning List's memory pool
value = new (pool) char[strlen(val)+1];
strcpy(value, val);
if ((prev = p) != NULL) prev->next = this;
if ((next = n) != NULL) next->prev = this;
}
//--------------------------------------------------------------------
List::List() // create a new list
{
// *** initialize memory pool for Link's and strings
pool = MemPoolInitFS(sizeof(Link), 0, 0);
head = tail = NULL;
}
//--------------------------------------------------------------------
List::~List() // destroy a list
{
// *** no need to free individual links or values,
// *** as freeing the pool frees all Links and string values
MemPoolFree(pool);
}
//--------------------------------------------------------------------
// add a new link after specified element
const Link *List::Insert(Link *prev, const char *val)
{
Link *next = prev ? prev->next : head;
// *** use placement syntax to allocate Link
// *** from current List's memory pool
Link *l = new (pool) Link(pool, val, prev, next);
if (!prev) head = l;
if (!next) tail = l;
return l;
}
Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!
This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.
But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/