input = [1, 2, 3]
squares = map(input, x → x*x)
total = sum(squares)
emit(total)
Here map squares each number in input, and sum adds the squares, an operation called a reduction.
The squares are [1, 4, 9]. That makes a total of 14.
Three values, no mystery readers. input feeds the map, squares feeds the sum, and total feeds the output.
I'm calling my array-language experiment Floatyboat. It's separate from the Go interpreter, where I have somebody else's language rules to implement. Here I can choose rules that make readers and dependencies easier to follow. The question about leaving features out gives me a reason to try this graph. The memory-management choices frustrate me. I don't want a garbage collector doing extra work while the calculation runs or the development overhead of arranging code around Rust's borrowing rules, and C's memory-management footguns aren't appealing either. I'd like to write the calculation and let the compiler sort out where its values live.
That's why I'm starting with this little graph. Once I've followed the readers, I can mark where each value stops being needed and then ask what to do with the space it leaves behind.
For this example, values stay in the graph and every read is shown. There are no callbacks or external storage retaining them.
Follow the readers
After the map has finished reading input, no later operation needs that input value. After the sum has finished reading squares, no later operation needs the squares. The graph gives the release points directly:
| Value | Last reader | Storage becomes eligible for release |
|---|---|---|
input | map | After its input reads finish |
squares | sum | After the reduction reads finish |
total | emit | After output has consumed the value |
Can I overwrite it? I could reclaim the input's storage now, well, once the map has finished reading it. Overwriting it any earlier is another matter. The map is still using those input elements to calculate its output, so I have to follow its reads before giving that space another job.
The input's old space is sitting there (an attractive home for the output).
Why allocate another array if this one will do?
For this elementwise map I could read an element and write its square back into the same position, provided the storage is compatible and no other reader needs the original contents. An operation that reads neighbouring elements would need a different argument.
I like the idea of making the compiler work quite hard, I can be lazy when writing the calculation, following all those readers is fiddly, and I'd rather spend my attention on what I want to calculate.
So I have two questions. When can I let the storage go? And can this operation safely read and overwrite it as it goes?
Finding the last reader answers the first. I still have to check the order of reads and writes for the second.
Plan the reuse
Here I don't really care how long compilation takes. Floatyboat is meant to be an embedded language for computational kernels, pieces of work called from a general-purpose language which still runs the rest of the application. I can spend more time figuring out a memory plan for that kernel before it runs.
In-place evaluation isn't the only way to reuse storage. Once sum has finished with squares, a later array could use the same buffer. Their lifetimes don't overlap. The new array would need to fit its capacity and alignment.
I'd like the compiler to plan the whole lifecycle. The kernel could acquire storage, hand its slots between values as their readers finish and release it when the kernel finishes, reserving the workspace once where the buffer sizes are known.
That could also reduce page faults. The OS backs memory in chunks called pages. On Linux the first write to fresh heap pages can trigger a page fault while the OS supplies physical memory without reading from disk. Reusing a buffer I've already written, while its pages remain in physical memory, can avoid those first-touch faults. The OS still decides which pages stay in memory.
Now give the input another name and use that name after the sum. Both names refer to the same array, so they are aliases:
input = [1, 2, 3]
later = input
squares = map(input, x → x*x)
total = sum(squares)
emit(total)
emit(later)
The map is no longer the final reader of the underlying input. If I overwrite that array with its squares, emit(total) still prints 14. But emit(later) now prints [1, 4, 9] instead of [1, 2, 3]. Saving an allocation has changed the program's answer.
I'm not worried about the extra name by itself because I can see this alias and follow its reader, but another alias I can't account for could hide a reader of the original contents. Language restrictions interest me because they could give the compiler a complete set of readers. I could end up following readers and checking capacities and drawing up another storage plan. If I'm still tracing every lifetime by hand, I've kept the job I was trying to get rid of.
Both names lead to one array. If I only look for the last mention of input, I miss the read through later. That later read keeps the original contents alive. An unused name isn't another reader.
Position and size are different facts
What about a filter? Put one between the map and the sum, keeping only even values:
filtered = filter(squares, even)
total = sum(filtered)
emit(total)
For [1, 4, 9], the filter keeps [4] and the sum is 4. These literals make the answer easy to calculate ahead of time. With input arriving at runtime, the number of matches depends on its contents.
How much space? The sum is the filtered array's final reader, so I know when its storage can be released. Its size before the filter runs is the part I'm still missing.
I'd need an upper bound, a counting pass or another allocation policy. Reserving enough for every input element is simple but could leave most of that space unused, while counting first gives me an exact size at the cost of another trip through the data. The count can still happen at runtime. I want the compiler to choose the policy, so writing this filter doesn't mean managing another buffer by hand.