Home / Learn / 16 Memory

Release v0.4.0Edition 0.2

16.4 Limits: call depth and memory

Page 5 of 10

16.4.1 What the call depth and the memory budget are

When a function calls another, the first one waits until the second returns. A call that is running, or waiting for one it made, is in progress. Picture a stack of plates: each call puts a plate on top, and each return takes one off. The call depth is the height of the stack: the number of calls in progress at once. Calls of functions, lambdas, predicates and the operations of handlers all count.

Memory is where a running program keeps its values. A run's memory budget is how much memory it may hold beyond what it held when it started, measured in MiB, mebibytes, of 1,048,576 bytes each.

16.4.2 Why a run has limits

A recursion that never reaches its base case, the case it answers without calling itself, never stops calling itself. This function counts the weeks a stock lasts, and stops only when the stock is exactly 0:

steps/13-runaway/src/restock.unauna
module restock

--- How many weeks `stock` units last when `per_week` units sell each week. It stops only when
--- the stock is exactly 0.
weeks_left(stock: Int, per_week: Int) -> Int = if stock == 0 then 0 else 1 + weeks_left(stock - per_week, per_week)

pub main() -> Unit
  uses @console: Console[print]
=
  @console.print("12 units at 3 a week: {weeks_left(12, per_week: 3)} weeks")
  @console.print("10 units at 3 a week: {weeks_left(10, per_week: 3)} weeks")

With 12 units at 3 a week, the stock reaches 0. With 10 units, it goes 10, 7, 4, 1, −2, and never meets 0. una --json run . shows the run as one JSON document:

Terminal
$ una --json run .
{"schema":"una.run/1","tier":1,"status":"aborted","output":["12 units at 3 a week: 4 weeks"],"failure":null,"diagnostics":[{"schema":"una.diagnostic/1","code":"U6003","severity":"error","domain":"runtime","message":"this call exceeds the maximum call depth of 10000","primary":{"file":"src/restock.una","start":{"line":5,"col":78},"end":{"line":5,"col":116}},"related":[],"repairs":[],"explain":"una explain U6003"}],"trace":[{"seq":1,"instance":"host:Console","capability":"Console","op":"print","args":{"line":"\"12 units at 3 a week: 4 weeks\""},"outcome":{"kind":"ok","value":"unit"}}]}

The first line was printed, and then status is aborted, with U6003 at the call that went one level too deep. Without the limit, the program would use memory until the machine ran out. The limit turns that into a clear stop, at the line that caused it. The fix is the base case of chapter 9: if stock < per_week then 0, with the requires per_week >= 1 that keeps every call moving toward it.

16.4.3 How the limits are set

Every run has both limits, and crossing either stops it with U6003:

Limit Default Flag
Call depth 10,000 calls in progress --max-depth <n>
Memory budget 4096 MiB --max-memory <MiB>, at least 1

The flags work on una run, una test and a built executable, for one run. --max-depth can go up to what a stack of 1 GiB (1,024 MiB) holds.

16.4.4 A loop is not a call

A call is one function running another and waiting for its answer, and only calls in progress count toward the call depth. A loop's turns are not calls: the body runs again, in the same function, and nothing waits for it. So a loop does not use up the call depth, however many turns it takes, while a function that calls itself, as weeks_of_stock of section 9.1 does, adds one call in progress per step. For the same reason, a value has no depth limit of its own: a loop can build a list, or a structure inside a structure, much deeper than the call depth.

This step builds 20,000 shelf labels with a for loop, and runs with the default depth:

steps/14-loop/src/labels.unacheckrununa
module labels

--- The shelf labels SKU-1 to SKU-`count`. A loop builds them: its iterations are not calls,
--- so the call depth stays the same however many labels there are.
labels(count: Int) -> List[Text]
=
  let edit made: List[Text] = []
  for n in 1..count
    made = made.append(item: "SKU-{n}")
  made

pub main() -> Unit
  uses @console: Console[print]
=
  let printed = labels(20000)
  let last = printed.at(index: 19999)
    if none use "none"
  @console.print("{printed.len} labels, the last {last}")

una run . prints:

Output
20000 labels, the last SKU-20000

16.4.5 Recursion that goes too deep

The same labels built by recursion need one call in progress per label. The program still checks, since the checker does not count calls, but the run stops:

src/labels.unadiff
--- a/src/labels.una
+++ b/src/labels.una
@@ -1,13 +1,7 @@
 module labels
 
---- The shelf labels SKU-1 to SKU-`count`. A loop builds them: its iterations are not calls,
---- so the call depth stays the same however many labels there are.
-labels(count: Int) -> List[Text]
-=
-  let edit made: List[Text] = []
-  for n in 1..count
-    made = made.append(item: "SKU-{n}")
-  made
+--- The shelf labels SKU-1 to SKU-`count`, built by recursion: one call in progress per label.
+labels(count: Int) -> List[Text] = if count == 0 then [] else labels(count - 1).append(item: "SKU-{count}")
 
 pub main() -> Unit
   uses @console: Console[print]
Terminal
$ una --json run .
{"schema":"una.run/1","tier":1,"status":"aborted","output":[],"failure":null,"diagnostics":[{"schema":"una.diagnostic/1","code":"U6003","severity":"error","domain":"runtime","message":"this call exceeds the maximum call depth of 10000","primary":{"file":"src/labels.una","start":{"line":4,"col":63},"end":{"line":4,"col":80}},"related":[],"repairs":[],"explain":"una explain U6003"}],"trace":[]}

status is aborted, diagnostics holds U6003 at the call that went one level too deep, and nothing was printed. In a terminal, una run . shows the same diagnostic on the terminal's error output (stderr) and exits with code 1. For more, run:

sh
una explain U6003

It explains both limits, and ends with a failing and a fixed example.

16.4.6 How the limits behave

16.4.6.1 The memory budget

The memory budget is checked at each call and at each turn of a loop. A run over it stops with U6003 too, and the message names the limit in MiB: this call exceeds the memory limit of N MiB. Where exactly the memory runs out depends on the machine, so a test should not rely on it. The depth limit is exact.

16.4.6.2 Why the checker cannot see the limits

The checker cannot see either limit: how deep a recursion goes, and how much a run holds, depend on the values the program meets when it runs. So U6003 is never a diagnostic of una check. Under una test, an example whose do line crosses a limit fails, and its report says that the do line aborted.

16.4.6.3 In tasks

Each task of a together block (chapter 15) counts its call depth from the depth of the block that started it, and the memory of all tasks counts against one budget.

Tip

Build long lists with a for loop, as labels does, and keep recursion for structures that are shallow, such as a tree of categories. A run that only needs more depth can raise --max-depth.

16.4.7 A loop or recursion

Which to use:

You want… Use
One step per element of a list, or per number of a range A for loop: no depth at all
A long list built step by step A for loop with let edit
To walk a shallow structure, such as categories inside categories Recursion
To repeat until something happens, with no limit known in advance Recursion, with a base case every path reaches, and fewer steps than the call depth (10,000 by default)

16.4.8 Check yourself: how deep

The recursive labels of Recursion that goes too deep now builds 9,000 labels:

steps/16-depth-9000/src/labels.unauna
pub main() -> Unit
  uses @console: Console[print]
=
  let printed = labels(9000)
  let last = printed.at(index: 8999)
    if none use "none"
  @console.print("{printed.len} labels, the last {last}")

With the default limit, does the run stop with U6003, or print? If it prints, what?

Show the answer
Output
9000 labels, the last SKU-9000

9,000 labels need about 9,000 calls in progress, one per label, plus main: fewer than the 10,000 of the default limit. At 20,000, the same function stops. The limit counts calls in progress, not calls made, and a loop counts none.

Next:16.5 Day-to-day: an end-of-day stock count