Arena storage pool
You are encouraged to solve this task according to the task description, using any language you may know.
Dynamically allocated objects take their memory from a heap. The memory for an object is provided by an allocator which maintains the storage pool used for the heap. Often a call to allocator is denoted as <lang ada> P := new T </lang> where T is the type of an allocated object and P is a reference to the object.
The storage pool chosen by the allocator can be determined by either:
- the object type T;
- the type of pointer P.
In the former case objects can be allocated only in one storage pool. In the latter case objects of the type can be allocated in any storage pool or on the stack.
Task
Show how allocators and user-defined storage pools are supported by the language. In particular:
- define an arena storage pool. An arena is a pool in which objects are allocated individually, but freed by groups.
- allocate some objects (e.g., integers) in the pool.
Explain what controls the storage pool choice in the language.
Ada
In Ada the choice of storage pool is controlled by the type of the pointer. Objects pointed by anonymous access types are allocated in the default storage pool. Pool-specific pointer types may get a pool assigned to them: <lang ada>type My_Pointer is access My_Object; for My_Pointer'Storage_Pool use My_Pool;</lang> The following example illustrates implementation of an arena pool. Specification: <lang ada>with System.Storage_Elements; use System.Storage_Elements; with System.Storage_Pools; use System.Storage_Pools;
package Arena_Pools is
type Arena (Size : Storage_Count) is new Root_Storage_Pool with private;
overriding
procedure Allocate
( Pool : in out Arena;
Address : out System.Address;
Size : Storage_Count;
Alignment : Storage_Count
);
overriding
procedure Deallocate
( Pool : in out Arena;
Address : System.Address;
Size : Storage_Count;
Alignment : Storage_Count
) is null;
overriding
function Storage_Size (Pool : Arena) return Storage_Count;
private
type Arena (Size : Storage_Count) is new Root_Storage_Pool with record
Free : Storage_Offset := 1;
Core : Storage_Array (1..Size);
end record;
end Arena_Pools;</lang> Here is an implementation of the package: <lang ada>package body Arena_Pools is
procedure Allocate
( Pool : in out Arena;
Address : out System.Address;
Size : Storage_Count;
Alignment : Storage_Count
) is
Free : constant Storage_Offset :=
Pool.Free + Alignment - Pool.Core (Pool.Free)'Address mod Alignment + Size;
begin
if Free - 1 > Pool.Size then
raise Storage_Error;
end if;
Pool.Free := Free;
Address := Pool.Core (Pool.Free - Size)'Address;
end Allocate;
function Storage_Size (Pool : Arena) return Storage_Count is
begin
return Pool.Size;
end Storage_Size;
end Arena_Pools;</lang> The following is a test program that uses the pool: <lang ada>with Arena_Pools; use Arena_Pools;
procedure Test_Allocator is
Pool : Arena_Pools.Arena (1024); type Integer_Ptr is access Integer; for Integer_Ptr'Storage_Pool use Pool; X : Integer_Ptr := new Integer'(1); Y : Integer_Ptr := new Integer'(2); Z : Integer_Ptr;
begin
Z := new Integer; Z.all := X.all + Y.all;
end Test_Allocator;</lang>
C
For C, dynamic memory is often used for structures and for arrays when the size of the array is unknown in advance. 'Objects' in C are pretty much structures, with the structure sometimes including a pointer to a virtual dispatch table.
To use dynamic memory, the header for the standard library must be included in the module. <lang c>#include <stdlib.h></lang> Uninitialized memory is allocated using the malloc function. To obtain the amount of memory that needs to be allocated, sizeof is used. Sizeof is not a normal C function, it is evaluated by the compiler to obtain the amount of memory needed. <lang c>int *var = malloc(n*sizeof(int)); Typename *var = malloc(sizeof Typename); Typename *var = malloc(sizeof(var[0]));</lang> Since pointers to structures are needed so frequently, often a typedef will define a type as being a pointer to the associated structure. Once one gets used to the notation, programs are actually easier to read, as the variable declarations don't include all the '*'s. <lang c>typedef struct mytypeStruct { .... } sMyType, *MyType;
MyType var = malloc(sizeof(sMyType));</lang> The calloc() function initializes all allocated memory to zero. It is also often used for allocating memory for arrays of some type. <lang c>/* allocate an array of n MyTypes */ MyType var = calloc(n, sizeof(sMyType));
MyType third = var+3; /* a reference to the 3rd item allocated */
MyType fourth = &var[4]; /* another way, getting the fourth item */</lang> Freeing memory dynamically allocated from the heap is done by calling free(). <lang c>free(var);</lang> One can allocate space on the stack using the alloca() function. You do not free memory that's been allocated with alloca <lang c>Typename *var = alloca(sizeof Typename);</lang> An object oriented approach will define a function for creating a new object of a class. In these systems, the size of the memory that needs to be allocated for an instance of the class will often be included in the 'class' record. See http://rosettacode.org/wiki/Polymorphic%20copy#C
C++
In C++, the situation with allocators is quite complex:
- You can define class-specific allocation/deallocation by adding class members
operator newandoperator delete. Those are then used whenever you use new for that type (or a type derived from it, if it doesn't itself replace operator new), and when you delete an object of that type. Note that arrays and single objects have both separate allocation functions and deallocation functions. - You can replace the global allocation/deallocation routines, which are used by new/delete whenever there are no class specific functions available.
- You can write operator new/operator delete with additional arguments, both in a class and globally. To use those, you add those parameters after the keyword
new, like
<lang cpp>T* foo = new(arena) T;</lang>
- In addition, for objects in containers, there's a completely separate allocator interface, where the containers use an allocator object for allocating/deallocating memory.
The following code uses class-specific allocation and deallocation functions:
<lang cpp>#include <csttdlib>
- include <cassert>
- include <new>
// This class basically provides a global stack of pools; it is not thread-safe, and pools must be destructed in reverse order of construction // (you definitely want something better in production use :-)) class Pool { public:
Pool(std::size_type sz);
~Pool();
static Pool& current() { return *cur; }
void* allocate(std::size_type sz, std::size_t alignment);
private:
char* memory; // char* instead of void* enables pointer arithmetic char* free; char* end; Pool* prev; static Pool* cur;
// prohibit copying Pool(Pool const&); // not implemented Pool& operator=(Pool const&); // not implemented
};
Pool* pool::cur = 0;
Pool::Pool(std::size_type size):
memory(static_cast<char*>(::operator new(size))), free(memory), end(memory))
{
prev = cur; cur = this;
}
Pool::~Pool() {
::operator delete(memory); cur = prev;
}
void* Pool::allocate(std::size_t size, std::size_t alignment) {
char* start = free;
// align the pointer
std::size_t extra = (start - memory) % aligment;
if (extra != 0)
{
extra = alignment - extra;
}
// test if we can still allocate that much memory if (end - free < size + extra) throw std::bad_alloc();
// the free memory now starts after the newly allocated object free = start + size + extra; return start;
}
// this is just a simple C-like struct, except that it uses a specific allocation/deallocation function. struct X {
int member;
void* operator new(std::size_t);
void operator delete(void*) {} // don't deallocate memory for single objects
};
void* X::operator new(std::size_t size) {
// unfortunately C++ doesn't offer a portable way to find out alignment // however, using the size as alignment is always safe (although usually wasteful) return Pool::current().allocate(size, size);
}
// Example program int main() {
Pool my_pool(3*sizeof(X)); X* p1 = new X; // uses the allocator function defined above X* p2 = new X; X* p3 = new X; delete p3; // doesn't really deallocate the memory because operator delete has an empty body
try
{
X* p4 = new X; // should fail
assert(false);
}
catch(...)
{
}
X* p5 = new X[10]; // uses global array allocation routine because we didn't provide operator new[] and operator delete[] delete[] p5; // global array deallocation
Pool* my_second_pool(1000); // a large pool X* p6 = new X; // allocate a new object from that pool X* p7 = new X; delete my_second_pool // also deallocates the memory for p6 and p7
} // Here my_pool goes out of scope, deallocating the memory for p1, p2 and p3</lang>
J
The concepts of pools and allocation is foreign to J, and excessively verbose for most purposes. However, this task can be accomplished by relying on J's facilities for dealing with code written in foreign languages.
For example, you can define a class which allocates a pool of integers:
<lang j>coclass 'integerPool' require 'jmf' create=: monad define
Lim=: y*SZI_jmf_ Next=: -SZI_jmf_ Pool=: mema Lim
)
destroy=: monad define
memf Pool codestroy
)
alloc=: monad define
assert.Lim >: Next=: Next+SZI_jmf_ r=.Pool,Next,1,JINT r set y r
)
get=: adverb define
memr m
)
set=: adverb define
y memw m
)</lang>
With this script you can then create instances of this class, and use them. In this case, we will create a pool of three integers:
<lang j> pool0=: 3 conew 'integerPool'
x0=: alloc__pool0 0 x1=: alloc__pool0 0 x2=: alloc__pool0 0 x0 set__pool0 7 x1 set__pool0 8 x2 set__pool0 9 x0 get__pool0 + x1 get__pool0 + x2 get__pool0
24</lang>
Finally, the pool can be destroyed:
<lang j> destroy__pool0 _</lang>
That said, using J's built-in support for integers (and for using them) usually results in better code.
Mathematica
Mathematica does not allow stack/heap control, so all variables are defined on the heap. However, tags must be given a value for a meaningful assignment to take place. <lang Mathematica>f[x_] := x^2</lang>
PicoLisp
PicoLisp allocates any kind of data from a single pool, because everything is built out of a "cell" primitive. Most of this allocation happens automatically, but can also be done explicitly with 'new' or 'box'. For memory-allocated objects, there is no explicit way of freeing them. Database objects can be freed with 'zap'.
Python
In Python:
- Everything is an object.
- Objects are dynamically allocated.
- Unused objects are garbage collected.
Where objects appear from, or disappear to, is treated as an implementation detail.
Statements, such as assignments, class and function definitions, and import statements can create objects and assign names to them which can be seen as assigning a reference to objects. Objects can also be referred to from other objects e.g. in collections such as lists.
When names go out of scope, or objects are explicitly destroyed, references to objects are diminished. Python's implementation keeps track of references to objects and marks objects that have no remaining references so that they become candidates for 'garbage collection' at a later time.
Tcl
Tcl does not really expose the heap itself, and while it is possible to use SWIG or Critcl to map the implementation-level allocator into the language, this is highly unusual.
However, it is entirely possible to use a pooled memory manager for Tcl's objects.
The pool engine class itself (a metaclass): <lang tcl>package require Tcl 8.6 oo::class create Pool {
superclass oo::class
variable capacity pool busy
unexport create
constructor args {
next {*}$args set capacity 100 set pool [set busy {}]
}
method new {args} {
if {[llength $pool]} { set pool [lassign $pool obj] } else { if {[llength $busy] >= $capacity} { throw {POOL CAPACITY} "exceeded capacity: $capacity" } set obj [next] set newobj [namespace current]::[namespace tail $obj] rename $obj $newobj set obj $newobj } try { [info object namespace $obj]::my Init {*}$args } on error {msg opt} { lappend pool $obj return -options $opt $msg } lappend busy $obj return $obj
}
method ReturnToPool obj {
try { if {"Finalize" in [info object methods $obj -all -private]} { [info object namespace $obj]::my Finalize } } on error {msg opt} { after 0 [list return -options $opt $msg] return false } set idx [lsearch -exact $busy $obj] set busy [lreplace $busy $idx $idx] if {[llength $pool] + [llength $busy] + 1 <= $capacity} { lappend pool $obj return true } else { return false }
}
method capacity {{value {}}} {
if {[llength [info level 0]] == 3} { if {$value < $capacity} { while {[llength $pool] > 0 && [llength $pool] + [llength $busy] > $value} { set pool [lassign $pool obj] rename $obj {} } } set capacity [expr {$value >> 0}] } else { return $capacity }
}
method clearPool {} {
foreach obj $busy { $obj destroy }
}
method destroy {} {
my clearPool next
}
self method create {class {definition {}}} {
set cls [next $class $definition] oo::define $cls method destroy {} { if {![[info object namespace [self class]]::my ReturnToPool [self]]} { next } } return $cls
}
}</lang> Example of how to use: <lang tcl>Pool create PoolExample {
variable int
method Init value {
puts stderr "Initializing [self] with $value" set int $value incr int 0
}
method Finalize {} {
puts stderr "Finalizing [self] which held $int"
}
method value {{newValue {}}} {
if {[llength [info level 0]] == 3} { set int [incr newValue 0] } else { return $int }
}
}
PoolExample capacity 10 set objs {} try {
for {set i 0} {$i < 20} {incr i} {
lappend objs [PoolExample new $i]
}
} trap {POOL CAPACITY} msg {
puts "trapped: $msg"
} puts -nonewline "number of objects: [llength $objs]\n\t" foreach o $objs {
puts -nonewline "[$o value] "
} puts "" set objs [lassign $objs a b c] $a destroy $b destroy $c destroy PoolExample capacity 9 try {
for {} {$i < 20} {incr i} {
lappend objs [PoolExample new $i]
}
} trap {POOL CAPACITY} msg {
puts "trapped: $msg"
} puts -nonewline "number of objects: [llength $objs]\n\t" foreach o $objs {
puts -nonewline "[$o value] "
} puts "" PoolExample clearPool</lang> Produces this output (red text to stderr, black text to stdout):
Initializing ::oo::Obj4::Obj5 with 0 Initializing ::oo::Obj4::Obj6 with 1 Initializing ::oo::Obj4::Obj7 with 2 Initializing ::oo::Obj4::Obj8 with 3 Initializing ::oo::Obj4::Obj9 with 4 Initializing ::oo::Obj4::Obj10 with 5 Initializing ::oo::Obj4::Obj11 with 6 Initializing ::oo::Obj4::Obj12 with 7 Initializing ::oo::Obj4::Obj13 with 8 Initializing ::oo::Obj4::Obj14 with 9 trapped: exceeded capacity: 10 number of objects: 10 0 1 2 3 4 5 6 7 8 9 Finalizing ::oo::Obj4::Obj5 which held 0 Finalizing ::oo::Obj4::Obj6 which held 1 Finalizing ::oo::Obj4::Obj7 which held 2 Initializing ::oo::Obj4::Obj6 with 10 Initializing ::oo::Obj4::Obj7 with 11 trapped: exceeded capacity: 9 number of objects: 9 3 4 5 6 7 8 9 10 11 Finalizing ::oo::Obj4::Obj8 which held 3 Finalizing ::oo::Obj4::Obj9 which held 4 Finalizing ::oo::Obj4::Obj10 which held 5 Finalizing ::oo::Obj4::Obj11 which held 6 Finalizing ::oo::Obj4::Obj12 which held 7 Finalizing ::oo::Obj4::Obj13 which held 8 Finalizing ::oo::Obj4::Obj14 which held 9 Finalizing ::oo::Obj4::Obj6 which held 10 Finalizing ::oo::Obj4::Obj7 which held 11