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 description
The task is to 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>
Erlang
Given automatic memory handling the only way to ask for memory in Erlang is when creating a process. Likewise the only way to manually return memory is by killing a process. So the pool could be built like this. The unit for memory is word, b.t.w.
<lang Erlang> -module( arena_storage_pool ).
-export( [task/0] ).
task() ->
Pid = erlang:spawn_opt( fun() -> loop([]) end, [{min_heap_size, 10000}] ),
set( Pid, 1, ett ),
set( Pid, "kalle", "hobbe" ),
V1 = get( Pid, 1 ),
V2 = get( Pid, "kalle" ),
true = (V1 =:= ett) and (V2 =:= "hobbe"),
erlang:exit( Pid, normal ).
get( Pid, Key ) ->
Pid ! {get, Key, erlang:self()},
receive
{value, Value, Pid} -> Value
end.
loop( List ) ->
receive
{set, Key, Value} -> loop( [{Key, Value} | proplists:delete(Key, List)] ); {get, Key, Pid} -> Pid ! {value, proplists:get_value(Key, List), erlang:self()}, loop( List ) end.
set( Pid, Key, Value ) -> Pid ! {set, Key, Value}. </lang>
Go
<lang go>package main
import (
"fmt" "runtime" "sync"
)
// New to Go 1.3 are sync.Pools, basically goroutine-safe free lists. // There is overhead in the goroutine-safety and if you do not need this // you might do better by implementing your own free list.
func main() {
// Task 1: Define a pool (of ints). Just as the task says, a sync.Pool
// allocates individually and can free as a group.
p := sync.Pool{New: func() interface{} {
fmt.Println("pool empty")
return new(int)
}}
// Task 2: Allocate some ints.
i := new(int)
j := new(int)
// Show that they're usable.
*i = 1
*j = 2
fmt.Println(*i + *j) // prints 3
// Task 2 continued: Put allocated ints in pool p.
// Task explanation: Variable p has a pool as its value. Another pool
// could be be created and assigned to a different variable. You choose
// a pool simply by using the appropriate variable, p here.
p.Put(i)
p.Put(j)
// Drop references to i and j. This allows them to be garbage collected;
// that is, freed as a group.
i = nil
j = nil
// Get ints for i and j again, this time from the pool. P.Get may reuse
// an object allocated above as long as objects haven't been garbage
// collected yet; otherwise p.Get will allocate a new object.
i = p.Get().(*int)
j = p.Get().(*int)
*i = 4
*j = 5
fmt.Println(*i + *j) // prints 9
// One more test, this time forcing a garbage collection.
p.Put(i)
p.Put(j)
i = nil
j = nil
runtime.GC()
i = p.Get().(*int)
j = p.Get().(*int)
*i = 7
*j = 8
fmt.Println(*i + *j) // prints 15
}</lang>
- Output:
3 9 pool empty pool empty 15
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>
ooRexx
In ooRexx:
- 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, method, and routine definitions, and ::requires directives can create objects and assign references to them to variables. Objects can also be referred to from other objects e.g. in collections such as lists. When objects are no longer referenced, the objects become candidates for garbage collection. It is not possible to explicitly destroy an object.
OxygenBasic
<lang oxygenbasic> '============== Class ArenaPool '==============
string buf sys pb,ii
method Setup(sys n) as sys {buf=nuls n : pb=strptr buf : ii=0 : return pb} method Alloc(sys n) as sys {method=pb+ii : ii+=n} method Empty() {buf="" : pb=0 : ii=0}
end class
macro Create(type,name,qty,pool)
type name[qty] at (pool##.alloc qty * sizeof type)
end macro
'==== 'DEMO '====
ArenaPool pool : pool.setup 1000 * sizeof int
Create int,i,100,pool Create int,j,100,pool
j[51] <= 1,2,3,4,5
print j[51] j[52] j[53] j[54] j[55] 'result 15
pool.empty </lang>
PARI/GP
GP has no particular control over the layout of objects in memory.
PARI allocates objects on the PARI stack by default, but objects can be allocated on the heap if desired. <lang C>pari_init(1<<20, 0); // Initialize PARI with a stack size of 1 MB. GEN four = addii(gen_2, gen_2); // On the stack GEN persist = gclone(four); // On the heap</lang>
Pascal
The procedure New allocates memory on the heap: <lang pascal>procedure New (var P: Pointer);</lang>
The Pointer P is typed and the amount of memory allocated on the heap matches the type. Deallocation is done with the procedure Dispose. In ObjectPascal constructors and destructors can be passed to New and Dispose correspondingly. The following example is from the rtl docs of Free_Pascal
<lang pascal>Program Example16; { Program to demonstrate the Dispose and New functions. } Type
SS = String[20]; AnObj = Object I : integer; Constructor Init; Destructor Done; end;
Var
P : ^SS; T : ^AnObj;
Constructor Anobj.Init; begin
Writeln ( ' Initializing an instance of AnObj! ' );
end;
Destructor AnObj.Done; begin
Writeln ( ' Destroying an instance of AnObj! ' ) ;
end;
begin
New ( P ); P^ := 'Hello, World!'; Dispose ( P );
{ P is undefined from here on! }
New ( T, Init ); T^.i := 0; Dispose ( T, Done );
end .</lang>
Instead of implicit specification of the amount of memory using a type, the explicit amount can directly specified with the procedure getmem (out p: pointer; Size: PtrUInt);
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.
Racket
As is common with high-level languages, Racket usually deals with memory automatically. By default, this means using a precise generational GC. However, when there's need for better control over allocation, we can use the malloc() function via the FFI, and the many variants that are provided by the GC: <lang racket> (malloc 1000 'raw) ; raw allocation, bypass the GC, requires free()-ing (malloc 1000 'uncollectable) ; no GC, for use with other GCs that Racket can be configured with (malloc 1000 'atomic) ; a block of memory without internal pointers (malloc 1000 'nonatomic) ; a block of pointers (malloc 1000 'eternal) ; uncollectable & atomic, similar to raw malloc but no freeing (malloc 1000 'stubborn) ; can be declared immutable when mutation is done (malloc 1000 'interior) ; allocate an immovable block with possible pointers into it (malloc 1000 'atomic-interior) ; same for atomic chunks (malloc-immobile-cell v) ; allocates a single cell that the GC will not move </lang>
REXX
In the REXX language, each (internal and external) procedure has its
own storage (memory) to hold local variables and other information
pertaining to a procedure.
Each call to a procedure (to facilitate recursion) has its own
storage.
Garbage collection can be performed after a procedure finishes
executing (either via an EXIT, RETURN,
or some other external action),
but this isn't specified in the language.
A DROP will mark a variable
as not defined, but doesn't necessarily deallocate its storage, but the freed
storage can be used by another variable within the program (or procedure).
Essentially, the method used by a particular REXX interpreter isn't
of concern to a programmer as there is but one type of variable
(character), and even (stemmed) arrays aren't preallocated or even
allocated sequentially in virtual (local) storage (as its elements are
defined).
Some REXX interpreters have built-in functions to query how much free
memory is available (these were written when real storage was a premium
during the early DOS days).
<lang rexx>/*REXX doesn't have declarations/allocations of variables, */
/* but this is the closest to an allocation: */
stemmed_array.= 0 /*any undefined element will have this value. */
stemmed_array.1 = '1st entry' stemmed_array.2 = '2nd entry' stemmed_array.6000 = 12 ** 2 stemmed_array.dog = stemmed_array.6000 / 2
drop stemmed_array.</lang>
Scala
The purpose of Scala is the realizing of solutions, not to make problems with memories, transistors and cooling fans. The use of memory is completely transparent for the Scala programmer. The notifiable effects are the garbage collection latency which gives random execution times. There is only one API call which addresses this scala.compat.Platform.collectGarbage() but the implementation is not guaranteed. If you still want to use this "Don't Try This At Home" stuff and your VM is a JVM the Java run-time library can be used. Good luck.
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
zkl
Memory allocation "just happens", unreachable memory is recovered via garbage collection. The closest thing to explicit memory allocation is Data object, which is a bit bucket you can [optionally] set the size of upon creation. However, it grows as needed. The closest thing to "new" is the create method, which tells an object to create a new instance of itself. For this task: <lang zkl>var pool=List(); // pool could be any mutable container pool.append(Data(0,1234)); // allocate mem blob and add to pool pool=Void; // free the pool and everything in it.</lang>