#include <memory>
namespace std
{
template <class T>
class allocator
{
//...
};
}
Object, dealing memory allocation and deletion.
Allocator represents a special memory model.
It is used as an abstraction to translate the need
to use memory into a raw call for memory.
Originally were introduced as part of STL to handle
the nasty problem of different pointer types on PCs.
(near, far, huge...).
Now they are serve as a base for technical solutions
that use different memory models, such as shared memory,
garbage collection and object-oriented databases.
Usage:
std::vector<int, MyAlloc<int> > v;
std::map<int, float, less<int>,
MyAlloc<std::pair<const int, float> > > m;
typedef std::basic_string<char, std::char_traits<char>,
MyAlloc<char> > xstring;
typedef std::map<xstring, xstring, less<xstring>,
MyAlloc<std::pair<const xstring, xstring> > > xmap;
if ( mymap.get_allocator() == s.get_allocator() )
{
// ok. allocators of s and mymap are interchangeable:
// one can free the others allocated memory
}
else
{
// be care! objects are not interchangeable: don't mix
// elemenets with different allocators.
}
Fundamental allocator operations:
a.allocate(num) Allocates memory for num elements
a.construct(p,val) Initialize the element to which p refers with val1
a.destruct(p) Destroys the element to which p refers
a.deallocate(p,num) Deallocates memory for num elemenst to which p refers
A (naive) vector implementation:
template <class T, class Allocator = allocator<T> >
class vector
{
public:
explicit vector(const Allocator& = Allocator());
explicit vector(size_type num, const T& val = T(),
const Allocator& = Allocator());
template <class InputIterator>
vector(InputIterator beg, InputIterator end,
const Allocator& = Allocator());
vector(const vector<T,Allocator>& v);
// ...
private:
Allocator alloc; // allocator
T* elems; // array of elements
size_type numElems; // number of elements
size_type sizeElems; // size of memory for the elements
};
template <class T, class Allocator>
vector<T,Allocator>::vector(size_type num, const T& val,
const Allocator& a) : alloc(a)
{
sizeElems = numElems = num;
elems = alloc.allocate(num);
for ( size_type i = 0; i < num; ++i )
{
// initialize element
alloc.construct( &elems[i], val);
}
}
Convenience functions for uninitialized memory:
uninitialized_fill( beg, end, val) Initializes [beg,end[ with val
uninitialized_fill_n( beg, num, val) Initialize num elements with val
uninitialized_copy( beg, end, mem) Initialize elements starting at mem
with elements of interval [beg,end[
This way the implementation is much easy:
template <class T, class Allocator>
vector<T,Allocator>::vector(size_type num, const T& val, const Allocator& a)
: alloc(a)
{
sizeElems = numElems = num;
elems = alloc.allocate(num);
uninitialized_fill_n(elems, num, val);
}
A reserve():
template <class T, class Allocator>
void vector<T,Allocator>::reserve(size_type size)
{
// reserve never shrinks memory for vector
if ( size <= sizeElems )
return;
// allocate new memory
T* newmem = alloc.allocate(size);
uninitialized_copy(elems, elems+numElems, newmem);
// destroy old elements
for ( size_type i = 0; i < numElems; ++i )
{
alloc.destroy(&elems[i]);
}
// deallocate old memory
alloc.deallocate(elems,sizeElems);
sizeElems = size;
elems = newmem;
}
Raw storage iterators:
The class raw_storage_iterator is provided to iterate over
uninitialized memory to initialize it.
copy( x.begin(), x.end(), // source
raw_storage_iterator<T*,T>(elems)); // destination
// T* output iterator
// T type of element
Temporary buffer:
// not really exception - safe :-((
void f()
{
// allocate memory for num elements of type T
pair<T*, std::ptrdiff_t> p = get_temporary_buffer<T>(num);
if ( p.second == 0 )
{
// could not allocate any memory
}
else if ( p.second < num )
{
// we have memory only for p.second elements
}
else
{
// we have enough memory
}
// ...
if ( p.first != 0 )
{
// free allocated memory
return_temporary_buffer(p.first);
}
}
The default allocator:
template <class T>
class allocator
{
public:
// type definitions
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef T value_type;
// rebind allocator to type U
template <class U>
struct rebind
{
typedef allocator<U> other;
};
// return address of values
pointer address(reference value) const;
const_pointer address(const_reference value) const;
// constructors and destructors
allocator() throw();
allocator(const allocator&) throw();
template <class U>
allocator(const allocator<U>&) throw();
~allocator() throw();
// return maximum number of elements that can be allocated
size_type max_size() const throw();
// allocate but do not initialize num elements of type T
// may throw std::bad_alloc exception
pointer allocate(size_type num,
allocator<void>::const_pointer hint = 0);
// initialize elements
void construct(pointer p, const T& value);
// delete elements
void destroy(pointer p);
// deallocate storage
void deallocate(pointer p, size_type num);
};
The default allocator uses the global operators new and delete
to allocate and deallocate memory. Thus, allocate() may throw
bad_alloc exception. However the default allocator may be optimized
by reusing deallocated memory or by allocating more memory than
needed to save time for additional allocations. So the exact moments,
when operator new and delete are called is unspecified.
Struct rebind:
template <class U>
struct rebind
{
typedef allocator<U> other;
};
This template structure provides the ability that any allocator
may allocate storage of another type indirectly. If Allocator is
an allocatortype, then
Allocator::rebind<T2>::other
is the type of the same allocator specialized for elements of type T2.
Rebind is useful, if you implement a container and have to allocate memory
for a type that differs from the element's type.
template <class T, class Allocator = allocator<T> >
class deque
{
//...
private:
typedef typename Allocator::rebind<T*>::other PtrAllocator;
Allocator alloc; // allocator for values of T
PtrAllocator block_alloc; // allocator for values of T*
T** elems; // array of blocks of elements
};
Default allocator for void:
template<>
class allocator<void>
{
public:
typedef void* pointer;
typedef const void* const_pointer;
typedef void value_type;
template <class U>
struct rebind
{
typedef allocator<U> other;
};
};
User defined allocator:
#include <limits>
#include <iostream>
namespace MyLib {
template <class T>
class MyAlloc {
public:
// type definitions
typedef T value_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
// rebind allocator to type U
template <class U>
struct rebind {
typedef MyAlloc<U> other;
};
// return address of values
pointer address (reference value) const {
return &value;
}
const_pointer address (const_reference value) const {
return &value;
}
/* constructors and destructor
* - nothing to do because the allocator has no state
*/
MyAlloc() throw() { }
MyAlloc(const MyAlloc&) throw() { }
template <class U>
MyAlloc (const MyAlloc<U>&) throw() { }
~MyAlloc() throw() { }
// return maximum number of elements that can be allocated
size_type max_size () const throw() {
return std::numeric_limits<std::size_t>::max() / sizeof(T);
}
// allocate but don't initialize num elements of type T
pointer allocate (size_type num, const void* = 0) {
// print message and allocate memory with global new
std::cerr << "allocate " << num << " element(s)"
<< " of size " << sizeof(T) << std::endl;
pointer ret = (pointer)(::operator new(num*sizeof(T)));
std::cerr << " allocated at: " << (void*)ret << std::endl;
return ret;
}
// initialize elements of allocated storage p with value value
void construct (pointer p, const T& value) {
// initialize memory with placement new
new((void*)p)T(value);
}
// destroy elements of initialized storage p
void destroy (pointer p) {
// destroy objects by calling their destructor
p->~T();
}
// deallocate storage p of deleted elements
void deallocate (pointer p, size_type num) {
// print message and deallocate memory with global delete
std::cerr << "deallocate " << num << " element(s)"
<< " of size " << sizeof(T)
<< " at: " << (void*)p << std::endl;
::operator delete((void*)p);
}
};
// return that all specializations of this allocator are interchangeable
template <class T1, class T2>
bool operator== (const MyAlloc<T1>&,
const MyAlloc<T2>&) throw() {
return true;
}
template <class T1, class T2>
bool operator!= (const MyAlloc<T1>&,
const MyAlloc<T2>&) throw() {
return false;
}
}
#include <vector>
#include "myalloc.hpp"
int main()
{
// create a vector, using MyAlloc<> as allocator
std::vector<int,MyLib::MyAlloc<int> > v;
// insert elements
// - causes reallocations
v.push_back(42);
v.push_back(56);
v.push_back(11);
v.push_back(22);
v.push_back(33);
v.push_back(44);
}
allocate 1 element(s) of size 4
allocated at: 0x804ad58
allocate 2 element(s) of size 4
allocated at: 0x804ad68
deallocate 1 element(s) of size 4 at: 0x804ad58
allocate 4 element(s) of size 4
allocated at: 0x804ad78
deallocate 2 element(s) of size 4 at: 0x804ad68
allocate 8 element(s) of size 4
allocated at: 0x804ad90
deallocate 4 element(s) of size 4 at: 0x804ad78
deallocate 8 element(s) of size 4 at: 0x804ad90
====================================================
template <class ForwIter, class T>
void uninitialized_fill( ForwIter beg, ForwIter end, const T& value)
{
typedef typename iterator_traits<ForwIter>::value_type VT;
ForwIter save(beg);
try
{
for( ; beg != end; ++beg )
{
new (static_cast<void*>(&*beg)) VT(value);
}
}
catch(...)
{
for( ; save != beg ; ++save )
{
save->~VT();
}
throw;
}
}
template <class ForwIter, class Size, class T>
void uninitialized_fill_n( ForwIter beg, Size num, const T& value)
{
typedef typename iterator_traits<ForwIter>::value_type VT;
ForwIter save(beg);
try
{
for( ; num--; ++beg )
{
new (static_cast<void*>(&*beg)) VT(value);
}
}
catch(...)
{
for( ; save != beg ; ++save )
{
save->~VT();
}
throw;
}
}
template <class ForwIter, class Size, class T>
void uninitialized_copy( InputIter beg, InputIter end, ForwIter dest)
{
typedef typename iterator_traits<ForwIter>::value_type VT;
ForwIter save(beg);
try
{
for( ; beg != end; ++beg, ++dest )
{
new (static_cast<void*>(&*dest)) VT(*beg);
}
return dest;
}
catch(...)
{
for( ; save != dest ; ++save )
{
save->~VT();
}
throw;
}
}
Garbage collection:
Boehm-Demers-Weiser (BDW) conservative garbage collector
http://www.hpl.hp.com/personal/Hans_Boehm/gc/
The Boehm-Demers-Weiser conservative garbage collector can be used
as a garbage collecting replacement for C malloc or C++ new. It allows
you to allocate memory basically as you normally would, without explicitly
deallocating memory that is no longer useful. The collector automatically
recycles memory when it determines that it can no longer be otherwise
accessed.
The collector is also used by a number of programming language implementations
that either use C as intermediate code, want to facilitate easier
interoperation with C libraries, or just prefer the simple collector
interface.
Alternatively, the garbage collector may be used as a leak detector
for C or C++ programs, though that is not its primary goal.
Typically several versions will be available. Usually you should first
try to use gc_source/gc.tar.gz, which is normally an older, more stable
version.
Platforms
The collector is not completely portable, but the distribution includes
ports to most standard PC and UNIX/Linux platforms. The collector should
work on Linux, *BSD, recent Windows versions, MacOS X, HP/UX, Solaris,
Tru64, Irix and a few other operating systems. Some ports are more polished
than others.
Irix pthreads, Linux threads, Win32 threads, Solaris threads (old style and
pthreads), HP/UX 11 pthreads, Tru64 pthreads, and MacOS X threads are
supported in recent versions.
Scalable multiprocessor versions
Kenjiro Taura, Toshio Endo, and Akinori Yonezawa have made available
a parallel collector based on this one. Their collector takes advantage
of multiple processors during a collection. Starting with collector
version 6.0alpha1 we also do this, though with more modest processor
scalability goals.
Some Collector Details
The collector uses a mark-sweep algorithm. It provides incremental
and generational collection under operating systems which provide the
right kind of virtual memory support. (Currently this includes SunOS[45],
IRIX, OSF/1, Linux, and Windows, with varying restrictions.) It allows
finalization code to be invoked when an object is collected. It can take
advantage of type information to locate pointers if such information is
provided, but it is usually used without such information.
Performance of the nonincremental collector is typically competitive with
malloc/free implementations. Both space and time overhead are likely to be
only slightly higher for programs written for malloc/free.
For programs allocating primarily very small objects, the collector may be
faster; for programs allocating primarily large objects it will be slower.
If the collector is used in a multithreaded environment and configured for
thread-local allocation, it may in some cases significantly outperform
malloc/free allocation in time.
We also expect that in many cases any additional overhead will be more than
compensated for by decreased copying etc. if programs are written and tuned
for garbage collection.
The garbage collector uses a modified mark-sweep algorithm. Conceptually
it operates roughly in four phases, which are performed occasionally as
part of a memory allocation:
1. Preparation Each object has an associated mark bit. Clear all mark bits,
indicating that all objects are potentially unreachable.
2. Mark phase Marks all objects that can be reachable via chains of pointers
from variables. Often the collector has no real information about the
location of pointer variables in the heap, so it views all static data
areas, stacks and registers as potentially containing pointers. Any bit
patterns that represent addresses inside heap objects managed by the
collector are viewed as pointers. Unless the client program has made heap
object layout information available to the collector, any heap objects
found to be reachable from variables are again scanned similarly.
3. Sweep phase Scans the heap for inaccessible, and hence unmarked, objects,
and returns them to an appropriate free list for reuse. This is not really
a separate phase; even in non incremental mode this is operation is usually
performed on demand during an allocation that discovers an empty free list.
Thus the sweep phase is very unlikely to touch a page that would not have
been touched shortly thereafter anyway.
4. Finalization phase Unreachable objects which had been registered for
finalization are enqueued for finalization outside the collector.
Time overhead: +20-30 %
Memory overhead: BIIIG