Arena storage pool: Difference between revisions

=={{header|Nim}}==

Nim proposes two ways to manage memory. In the first one, objects are allocated on the heap using "new" and their deallocation is managed by the compiler and the runtime. In this case, objects are accessed via references ("ref").

The second method to allocate objects on the heap consists to do this the C way, using procedures "alloc" or "alloc0" to get blocks of memory. The deallocation is managed by the user who must call "dealloc" to free the memory. Using this method, objects are accessed via pointers ("ptr").

The preferred way is of course to use references which are safe. To allow a better fit to user needs, Nim proposes several options for automatic memory management. By specifying "--gc:refc" in the command line to launch the compilation, a garbage collector using reference counting is used. This is currently the default. Others options are "markAndSweep", "boehm" and "go" to use a different GC, each one having its pros and cons. "--gc:none" allows to deactivate totally automatic memory management which limits considerably the available functionnalities.

Since version 1.2, two more options are proposed. The first one, "--gc:arc" allows to choose the "arc" memory management which, in fact, is not a garbage collector. This is the most efficient option but it cannot free data structures containing cycles. The second option, "--gc:orc", allows to choose the "orc" memory management which is in fact "arc" with a cycle detection mechanism. It will probably become the default option in a future version.

In some cases, especially when a lot of similar objects must be allocated, it is a good idea to use a pool. It allows to allocate by blocks and to free globally.

Nim doesn’t propose any mechanism to manage such pools. There is an option "regions" which may be useful for this purpose but it is experimental and not documented. So, we will ignore it for now.

One way to manage pools consists to allocate blocks of memory and use some pointer arithmetic to return pointers to objects. The blocks may be allocated using "new" (and in this case will be freed automatically) or using "alloc" or "alloc0" and the deallocation must be required explicitely.

We provide here an example using blocks allocated by "new".

<lang Nim>

####################################################################################################

# Pool management.

# Pool of objects.

type

Block[Size: static Positive, T] = ref array[Size, T]

Pool[BlockSize: static Positive, T] = ref object

blocks: seq[Block[BlockSize, T]] # List of blocks.

lastindex: int # Last object index in the last block.

#---------------------------------------------------------------------------------------------------

proc newPool(S: static Positive; T: typedesc): Pool[S, T] =

## Create a pool with blocks of "S" type "T" objects.

new(result)

result.blocks = @[new(Block[S, T])]

result.lastindex = -1

#---------------------------------------------------------------------------------------------------

proc getItem(pool: Pool): ptr pool.T =

## Return a pointer on a node from the pool.

inc pool.lastindex

if pool.lastindex == pool.BlockSize:

# Allocate a new block. It is initialized with zeroes.

pool.blocks.add(new(Block[pool.BlockSize, pool.T]))

pool.lastindex = 0

result = cast[ptr pool.T](addr(pool.blocks[^1][pool.lastindex]))

####################################################################################################

# Example: use the pool to allocate nodes.

type

# Node description.

NodePtr = ptr Node

Node = object

value: int

prev: NodePtr

next: NodePtr

type NodePool = Pool[5000, Node]

proc newNode(pool: NodePool; value: int): NodePtr =

## Create a new node.

result = pool.getItem()

result.value = value

result.prev = nil # Not needed, allocated memory being initialized to 0.

result.next = nil

proc test() =

## Build a circular list of nodes managed in a pool.

let pool = newPool(NodePool.BlockSize, Node)

var head = pool.newNode(0)

var prev = head

for i in 1..11999:

let node = pool.newNode(i)

node.prev = prev

prev.next = node

# Display information about the pool state.

echo "Number of allocated blocks: ", pool.blocks.len

echo "Number of nodes in the last block: ", pool.lastindex + 1

test()

# No need to free the pool. This is done automatically as it has been allocated by "new".</lang>

{{out}}

<pre>

Number of allocated blocks: 3

Number of nodes in the last block: 2000

</pre>