This document is an attempt to formalize the memory management design that was proposed in design meeting. If we all agree on this design, it should be used consistently across the codebase, any time a producer passes a value to a consumer, where the consumer needs to be sure the value will remain valid as long as needed.
Note that this only describes the simplest possible version. I can imagine refinements, such as Cotton’s proposal for implementing regions with strictly nested lifetimes using “checkpoints”, which allow a region to free only the memory allocated since a checkpoint. But I don’t see any need to incorporate such refinements in the first pass.
We consider a situation where one entity—the producer—creates a value and gives it to another entity—the consumer. Here, an entity might be a piece of code being generated, a function, an object, whatever level of abstraction is most useful.
The fundamental invariant we must maintain is this: the passed value must be useable for as long as the consumer requires it. For example, the value must not have some memory on which it depends be freed before the consumer is done making use of the value. Likewise, if the value depends on some resource like a file handle, we must ensure that that resource lives as long as the consumer needs the value; however, this proposal doesn’t address non-memory resources.
First, a summary of relevant pieces of the existing region system.
Regionis a reference counted shared pointer to a
RegionMemoryis an arena allocator: it can allocate memory, and it can free all the memory it has allocated. It cannot free some of its memory while preserving the rest. All interaction with a
RegionMemoryis done through a
Regionhandle, and a
RegionMemoryis freed if and only if the last
Regionhandle to it has been released.
RegionMemorycan have any number of “parent” regions. It holds a
Regionhandle to each of its parents. It releases those handles only when it is freed, thus ensuring that the parent regions live at least as long as itself. Region
r1is registered as a parent of region
The following simple protocol suffices to enforce the main invariant:
- The consumer must always pass a destination
Regionto the producer when requesting a value.
- The producer must ensure that the value it produces remains valid until the destination region is freed. It can do this by making sure each component of the value is either:
- constructed in the destination region, or
- in a new region created by the producer, which the producer has registered as a parent of the destination region.
Note that this leaves some choices to the producer. If the producer needs to create some intermediate values, it could
- Create those values in the destination region, which would become junk never to be used.
- Create them in a new region which it frees before returning to the consumer.
In 1, we waste memory, while in 2, we perform more allocations. In general, we will want to make use of contextual knowledge to choose between these options. For example, when filtering rows of a table, we probably want to free each filtered row before building the next row, but when filtering an array, we might be okay with putting all the values, filtered or not, in one region.
In the current model (as I understand it), we make this decision by saying “each row of a table is built in a single region, along with all intermediate values”. We can keep this same behavior by introducing a new IR node
SingleRegion (better names welcome), and by modifying the earlier protocol to require the consumer to pass a flag
singleRegion to the producer. Then all IR nodes except
SingleRegion propagate the flag from their parent to their children, we set
singleRegion = false at the root of the IR, and
SingleRegion always passes
singleRegion = true to its children.
Alternatively, instead of a flag, if we enforce that the only way for a producer to create a new region is through the destination region, then
SingleRegion can enforce that its children use a single region by passing a
Region for which requesting a new region always returns itself.
This would allow us to easily experiment with different points along the spectrum between “more time allocating” and “higher memory usage” by making localized changes in the table lowerer.