Collections in a region: where a list's memory comes from
On this page
A list's elements live in a block of memory that grows, and that block has to come from somewhere. By default it comes from the program's heap, but a list made in an arena should take its block from the arena too, and a list in an actor from the actor's own region, so that the whole of it lives and dies by one strategy. This page covers how a collection gets its block, how to make one in an arena or an actor's region, how collections of garbage-collected references are traced, and how to give a collection a region of your own. Afterwards you can place a collection, and everything it holds, under the strategy you chose:
mod placed;
import stdio use *;
import collections use *;
import arena use *;
fn main() i32 {
// The heap's region is what a collection uses unless it is given another
let heap = new List[i32](100, heapRegion());
print <- heap.capacity();
print <- "\n";
// A collection made in an arena: its words and its block both live there
var a = Arena.empty();
let xs = new a[List[i32]](16);
var i = 0;
while i < 40 {
xs.push(i); // the block grows in the arena
i += 1;
}
print <- xs.len();
print <- "\n";
print <- *xs[39usize];
print <- "\n";
0i32; // the arena dies here and takes the list with it
}
It prints 100, 40 and 39.
Every collection draws on a region#
Every growable collection (List, String, Deque, Dict, OrderedDict, Set, and the pool package's Pool) gets, grows and gives back its block through a *MemRegion it holds as its last field, not through the C library. This is regions nesting (What a region is): wherever the collection itself lives, its block is managed by the region it was given, and inside the block the collection manages its elements.
The heap's region and the raw blocks layer#
The heap's region, heapRegion(), is one static object that is never null. Its functions take blocks from the program's heap through core's raw blocks layer, RawBlocks, with alloc, resize and release: the one place the heap's bytes come from, which today forwards to the C library's malloc, realloc and free. A block always comes back to it, never to the C library directly. A collection made without a region points to the heap's, so new List[i32] and List[i32].empty() take their blocks from the heap.
Starting sizes, and what the region word costs#
The region pointer costs 8 bytes a collection: a List and a String are 32 bytes, a Deque 40, a Dict and a Set 56, an OrderedDict 64. Every collection takes a starting size as its first argument: new Deque[i32](100), new String(100) (bytes), new Dict[String, i64](100) and likewise OrderedDict and Set (entries, without growing; the table rounds the room up to its size), new Pool[Npc](100) (slots). A withCapacity(n) function makes one too: Dict[String, i64].withCapacity(100).
A collection in an arena#
A collection made in an arena, new arena[List[i32]](16) (Allocating in an arena), has its own words in the arena and its block there too: an arena is a region, and the construction hands the list the arena's unless the arguments pass another last. The list is built where it stays: its words are placed first, then its block (made with a starting size, the block is allocated after the words, so it is the last thing the arena allocated).
The list grows its block in place while it is the last thing the arena allocated and the room is there, so a list alone in its arena does, as long as the block the arena is bumping through (4096 bytes, or the size of a value that needed more) has the room. Otherwise the arena bumps a new block, copies the values and abandons the old one, which it holds until it dies. A block taken because a resize outgrew the arena's current one is twice the size asked, so a lone list that keeps doubling finds the room for its next doubling where it is, and is copied once for every block it fills, not at every doubling (100,000 values of 8 bytes: five copies, through six blocks). Two lists in one arena that grow in turn still copy at every growth, each finding the other's block last. Giving a block back does nothing. When the arena dies it finalizes the list, which gives its elements' own memory back to wherever it came from (a List[String] whose strings came from the heap frees them then).
A collection in an actor's own region#
An actor's own region is a region too: new self[List[T]](16) takes the list's block from the region's allocate, resize and release, a block of its own that the region's collector never moves, and the list's final gives it back (Its own region):
mod tally;
import stdio use *;
import actors;
import collections use *;
alias NumsRef = ActorGc[mut, List[i64]];
actor Tally {
nums Option[NumsRef];
fn init(self &new) {
*self = new Self(None[NumsRef]);
}
pub async do open(self) {
nums = Some[NumsRef](new self[List[i64]](16usize)); // in the actor's own region
}
pub async do add(self, n i64) {
match nums {
case let l Some[NumsRef] { l.push(n); }
else { }
}
}
pub async do report(self) {
var sum = 0i64;
match nums {
case let l Some[NumsRef] {
each v in l.iter() { sum = sum + *v; }
}
else { }
}
print <- sum;
print <- "\n";
}
}
fn main() {
let t = new Tally();
t.open();
t.add(5i64);
t.add(7i64);
t.report();
}
This prints 12.
Collections of garbage-collected references#
A collection can hold garbage-collected references (Gc, or in an actor its own ActorGc): a List[Gc[mut, Node]] is traced value by value. A collection, a Pool and an Arena each declare the built-in trait GcTraceElements (a provisional name) and a method fn gcTraceElements(self &mut) I giving a cursor over a writable reference to each value they hold (I declares is Iterator[&mut E], as List's mutItems() cursor does), and a type of your own that holds values behind a raw pointer declares it the same way. The collector traces each reference the cursor gives as it traces a value of its type, and rewrites it where it moves what it points at; a list of numbers holds nothing to trace, and costs nothing.
A Dict and an OrderedDict give their values, and refuse a key that holds a traced reference (a collector that moved a key would leave it hashed where it was). An arena holds values of many types, so its cursor gives each value whose type holds a traced reference as an Erased (core's address of a value and the type record of its type), traced by its record's own trace. A type with a raw pointer to a value that holds a traced reference, that does not declare GcTraceElements, cannot be traced, and a variable or a traced allocation of it is refused.
Giving a collection a region of your own#
Rarely needed, but it is how a program counts, limits or places its collections' memory. A MemRegion (core) is three function references, allocFn, resizeFn and releaseFn, held in a struct's first field and handed that field's address: allocate(bytes, align) gives a block, resize(block, old, new, align) makes it longer, in place or by copying to a new one (a null block of 0 bytes is an allocation), and release(block, bytes) gives it back.
Another region is the construction's last argument: new List[i32](100, r), new Dict[String, i64](r), where r is a *MemRegion. Every block of the collection is then the region's, and its death gives each back to it. A collection that cannot hand its block over, because the owner freeze() makes gives it back to the heap, moves its values into a heap block first when its region is not the heap's. This region counts what it is asked for:
mod counting;
import stdio use *;
import collections use *;
import libc;
// A region is three function references held in a struct's first field.
// This one counts what it is asked for and takes its memory from the C library.
struct Counting {
header MemRegion;
blocks usize;
bytes usize;
}
fn countAlloc(r *MemRegion, bytes usize, align usize) *u8 {
let c = r as *Counting;
(*c).blocks = (*c).blocks + 1usize;
(*c).bytes = (*c).bytes + bytes;
libc.malloc(bytes);
}
fn countResize(r *MemRegion, block *u8, oldBytes usize, newBytes usize, align usize) *u8 {
let c = r as *Counting;
(*c).bytes = (*c).bytes + newBytes - oldBytes;
libc.realloc(block, newBytes);
}
fn countRelease(r *MemRegion, block *u8, bytes usize) {
if block as usize == 0usize { return; }
let c = r as *Counting;
(*c).bytes = (*c).bytes - bytes;
libc.free(block);
}
// A type of your own that carries a region hands it on to what it is made of:
// its last init parameter is the region, and a construction that names none gets the heap's.
struct Mesh is CarriesRegion {
pub points List[f32];
pub fn init(self &new, n usize, region *MemRegion) {
*self = new Mesh(new List[f32](n, region));
}
}
fn main() i32 {
var counting = new Counting(new MemRegion(&countAlloc, &countResize, &countRelease), 0usize, 0usize);
let region = (&counting) as *MemRegion;
{
var xs = new List[i64](region); // asks the region for nothing yet
var i = 0i64;
while i < 100i64 {
xs.push(i);
i = i + 1i64;
}
print <- "bytes held: ";
print <- counting.bytes; // 128 slots of 8 bytes
print <- "\n";
} // the list's death gave the block back
print <- "bytes held after: ";
print <- counting.bytes;
print <- "\n";
let mesh = new Mesh(50usize, region); // the mesh's list comes from the same region
print <- "bytes for the mesh: ";
print <- counting.bytes;
print <- "\n";
let onHeap = new Mesh(50usize); // no region named: the heap's
print <- onHeap.points.capacity();
print <- "\n";
0i32;
}
This prints bytes held: 1024, bytes held after: 0, bytes for the mesh: 200 and 50.
A type that carries a region#
A type declares CarriesRegion (a provisional name) to say that it gets its memory this way: it declares an init, and every init it declares ends with the parameter region *MemRegion, which a construction naming none leaves out and the compiler fills in with the heap's. Any type may declare CarriesRegion, not only a collection: a struct that holds lists declares it and passes its own region on to them, so everything it is made of comes from the one region it was handed (the Mesh above).
You can now put a collection, block and all, in an arena or an actor's region, and count or place its memory with a region of your own. The last page goes one step further: writing a region ref of your own, the kind new allocates through.