📄 9new.html
字号:
<html>
<head>
<title>Operator New</title>
<link rel="stylesheet" href="../rs.css">
</head>
<body background="../images/margin.gif" bgcolor="#ffffe0">
<!-- Main Table -->
<table cellpadding="6">
<tr>
<td width="78"> </td>
<td>
<h2>Overloading operator new</h2>
<p>Both <var>new</var> and <var>delete</var> are considered operators in C++. What it means, in particular, is that they can be overloaded like any other operator. And just like you can define a class-specific <var>operator=</var>, you can also define class-specific operators <var>new</var> and <var>delete</var>. They will be automatically called by the compiler to allocate and deallocate objects of that particular class. Moreover, you can overload and override global versions of <var>new</var> and <var>delete</var>.
<h3>Class-specific new</h3>
<p>Dynamic memory allocation and deallocation are not cheap. A lot of programs spend the bulk of their time inside the heap, searching for free blocks, recycling deleted blocks and merging them to prevent heap fragmentation. If memory management is a performance bottleneck in your program, there are several optimization techniques that you might use.
<p>Overloading <var>new</var> and <var>delete</var> on a per-class basis is usually used to speed up allocation/deallocation of objects of that particular class. There are two main techniques--caching and bulk allocation.
<h4>Caching</h4>
</td></tr>
<tr>
<td class=margin valign=top>
<a href="source/calc12.zip">
<img src="../images/brace.gif" width=16 height=16 border=1 alt="Download!"></a>
</td>
<td>
<p>The idea behind caching is that recycling is cheaper than manufacturing. Suppose that we wanted to speed up additions to a hash table. Every time an addition is performed, a new link is allocated. In our program, these links are only deallocated when the whole hash table is destroyed, which happens at the end of the program. Imagine, however, that we are using our hash table in another program, where it's either possible to selectively remove items from the hash table, or where there are many hash tables created and destroyed during the lifetime of the program. In both cases, we might speed up average link allocation time by keeping around the links that are currently not in use.
<p>A <var>FreeList</var> object will be used as storage for unused links. To get a new link we call its <var>NewLink</var> method. To return a link back to the pool, we call its <var>Recycle</var> method. The pool of links is implemented as a linked list. There is also a <var>Purge</var> method that frees the whole pool.
<!-- Code --><table width=100% cellspacing=10><tr> <td class=codetable>
<pre>class Link;
class FreeList
{
public:
FreeList () : _p (0) {}
~FreeList ();
void Purge ();
void * NewLink ();
void Recycle (void * link);
private:
Link * _p;
};</pre>
</td></tr></table><!-- End Code -->
<p>Class <var>Link</var> has a static member <var>_freeList</var> which is used by the overloaded class-specific operators <var>new</var> and <var>delete</var>. Notice the assertion in operator <var>new</var>. It protects us from somebody calling this particular operator for a different class. How could that happen? Operators <var>new</var> and <var>delete</var> are inherited. If a class derived from <var>Link</var> didn't override these operators, <var>new</var> called for the derived class would return an object of the wrong size (base-class size).
<!-- Code --><table width=100% cellspacing=10><tr> <td class=codetable>
<pre>class Link
{
friend class FreeList;
public:
Link (Link * pNext, int id)
: _pNext (pNext), _id (id) {}
Link * Next () const { return _pNext; }
int Id () const { return _id; }
// allocator
void * <b>operator new</b> (size_t size)
{
assert (size == sizeof (Link));
return _freeList.NewLink ();
}
void <b>operator delete</b> (void * mem)
{
if (mem)
_freeList.Recycle (mem);
}
static void Purge () { _freeList.Purge (); }
private:
static <b>FreeList</b> _freeList;
Link * _pNext;
int _id;
};</pre>
</td></tr></table><!-- End Code -->
<p>Inside <var>List::Add</var> the creation of a new <var>Link</var> will be translated by the compiler into the call to the class-specific operator <var>new</var> followed by the call to its constructor (if any). The beauty of this method is that no changes to the implementation of <var>List</var> are needed.
<!-- Code --><table width=100% cellspacing=10><tr> <td class=codetable>
<pre>class List
{
public:
List ();
~List ()
{
while (_pHead != 0)
{
Link * pLink = _pHead;
_pHead = _pHead->Next();
<b>delete</b> pLink;
}
}
void Add (int id)
{
Link * pLink = <b>new</b> Link (_pHead, id);
_pHead = pLink;
}
Link const * GetHead () const { return _pHead; }
private:
Link * _pHead;
};</pre>
</td></tr></table><!-- End Code -->
<p>A hash table contains an array of <var>List</var>s which will all internally use the special-purpose allocator for its links.
<p>After we are done with the hash table, we might want to purge the memory stored in the private allocator. That would make sense if, for instance, there was only one hash table in our program, but it allowed deletion as well as addition of entries. On the other hand, if we wanted our pool of links to be shared between multiple hash tables, we wouldn't want to purge it every time a hash table is destroyed.
<!-- Code --><table width=100% cellspacing=10><tr> <td class=codetable>
<pre>class HTable
{
public:
explicit HTable (int size): _size(size)
{
_aList = new List [size];
}
~HTable ()
{
delete [] _aList;
// release memory in free list
<b>Link::Purge</b> (); // optional
}
// ...
private:
List * _aList;
int _size;
};</pre>
</td></tr></table><!-- End Code -->
<p>Notice: <var>Purge</var> is a <i>static</i> method of <var>Link</var>, so we don't need an instance of a <var>Link</var> in order to call it.
<p>In the implementation file, we first have to define the static member <var>_freeList</var> of the class <var>Link</var>. Static data is automatically initialized to zero.
<!-- Code --><table width=100% cellspacing=10><tr> <td class=codetable>
<pre>FreeList Link::_freeList;</pre>
</td></tr></table><!-- End Code -->
<p>The implementation of <var>FreeList</var> is pretty straightforward. We try to reuse <var>Links</var>, if possible; otherwise we call the global operator <var>new</var>. Since we are allocating raw memory, we ask for <var>sizeof (Link)</var> bytes (<var>char</var>s). When we delete this storage, we cast <var>Link</var>s back to their raw form. Deleting a <var>Link</var> as a <var>Link</var> would result in a (second!) call to its destructor. We don't want to do it here, since destructors for these <var>Links</var> have already been called when the class-specific <var>delete</var> was called.
<!-- Code --><table width=100% cellspacing=10><tr> <td class=codetable>
<pre>void * FreeList::NewLink ()
{
if (_p != 0)
{
void * mem = _p;
_p = _p->_pNext;
return mem;
}
else
{
// use global operator new
return ::new char [sizeof (Link)];
}
}
void FreeList::Recycle (void * mem)
{
Link * link = static_cast<Link *> (mem);
link->_pNext = _p;
_p = link;
}
FreeList::~FreeList ()
{
Purge ();
}
void FreeList::Purge ()
{
while (_p != 0)
{
// it was allocated as an array of char
char * mem = reinterpret_cast<char *> (_p);
_p = _p->Next();
::delete [] mem;
}
}</pre>
</td></tr></table><!-- End Code -->
<p>Notice all the casting we have to do. When our overloaded <var>new</var> is called, it is expected to return a void pointer. Internally, however, we either recycle a <var>Link</var> from a linked-list pool, or allocate a raw chunk of memory of the appropriate size. We don't want to call <var>::new Link</var>, because that would have an unwanted side effect of calling <var>Link</var>'s constructor (it will be called anyway after we return from operator <var>new</var>).
<p>Our <var>delete</var>, on the other hand, is called with a void pointer, so we have to cast it to a <var>Link</var> in order to store it in the list.
<p>Purge deletes all as if they were arrays of chars--since that is how they were allocated. Again, we don't want to delete them as <var>Links</var>, because <var>Link</var> destructors have already been called.
<p>As usually, calls to global operators <var>new</var> and <var>delete</var> can be disambiguated by prepending double colons. Here, they ar not strictly necessary, but they enhance the readability.
<h4>Bulk Allocation</h4>
</td></tr>
<tr>
<td class=margin valign=top>
<a href="source/calc13.zip">
<img src="../images/brace.gif" width=16 height=16 border=1 alt="Download!"></a>
</td>
<td>
<p>Another approach to speeding up allocation is to allocate in bulk and thus amortize the cost of memory allocation across many calls to operator <var>new</var>. The implementation of <var>Link</var>s, <var>List</var>s and <var>HashTable</var>s is as before, except that a new class, <var>LinkAllocator</var> is used in place of <var>FreeList</var>. It has the same interface as <var>FreeList</var>, but its implementation is more involved. Besides keeping a list of recycled <var>Link</var>s, it also has a separate list of blocks of links. Each block consists of a header of class <var>Block</var> and a block of 16 consecutive raw pieces of memory each the size of a <br>Link.
<!-- Code --><table width=100% cellspacing=10><tr> <td class=codetable>
<pre>class Link;
class LinkAllocator
{
enum { BlockLinks = 16 };
class <b>Block</b>
{
public:
Block * Next () { return _next; }
void SetNext (Block * next) { _next = next; }
private:
Block * _next;
};
public:
LinkAllocator () : _p (0), _blocks (0) {}
~LinkAllocator ();
void Purge ();
void * NewLink ();
void Recycle (void * link);
private:
Link * _p;
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -