CakeML / CakeML/cakeml

Local named functions can allocate dead closures after inlining

Open
#1,453 1 comment 0 reactions 0 assignees View on GitHub
bug high reward performance
Dominant language
Standard ML
Stars
1.2k
Forks
104
Avg merge
2d 21h
Merged PRs (30d)
16

Description

## Summary

A small nonrecursive local function written with `fun` can allocate a fresh
closure on every execution even though its only call is eventually inlined. The
semantically equivalent `val f = fn ...` spelling is inlined earlier and does
not allocate.

In the example below, the late BVL inliner removes the call to `bump` but leaves
a dead 24-byte closure allocation inside the loop. Over 100 million iterations,
that is 2.4 GB (about 2.24 GiB) of avoidable allocation. The named form was
1.76× slower in paired x64-64 measurements.

## Reproducer

Named local function:

```sml
fun loop n acc =
if n = 0 then acc
else
let fun bump x = x + 1
in loop (n - 1) (acc + bump n) end;

fun main () =
let val n = Option.valOf (Int.fromString (List.hd (CommandLine.arguments ())))
in print_int (loop n 0); print "\n" end;

main ();
```

The control changes only the local binding:

```diff
- let fun bump x = x + 1
+ let val bump = fn x => x + 1
in loop (n - 1) (acc + bump n) end;
```

From an x64-64 build directory containing `cake` and `basis_ffi.c`, save the
variants as `/tmp/named.cml` and `/tmp/anonymous.cml`, then run:

```sh
./cake < /tmp/named.cml > /tmp/named.S
./cake < /tmp/anonymous.cml > /tmp/anonymous.S
cc -O2 /tmp/named.S basis_ffi.c -lm -o /tmp/named
cc -O2 /tmp/anonymous.S basis_ffi.c -lm -o /tmp/anonymous

env CML_HEAP_SIZE=32 CML_STACK_SIZE=16 taskset -c 2 \
/tmp/named 100000000 > /tmp/named.out
env CML_HEAP_SIZE=32 CML_STACK_SIZE=16 taskset -c 2 \
/tmp/anonymous 100000000 > /tmp/anonymous.out
cmp /tmp/named.out /tmp/anonymous.out

/usr/bin/time -f 'named: %e s' \
env CML_HEAP_SIZE=32 CML_STACK_SIZE=16 taskset -c 2 \
/tmp/named 100000000 > /dev/null
/usr/bin/time -f 'anonymous: %e s' \
env CML_HEAP_SIZE=32 CML_STACK_SIZE=16 taskset -c 2 \
/tmp/anonymous 100000000 > /dev/null
```

Both variants print `5000000150000000`.

## Measurements

| Form | Median | Interquartile range | Relative |
|---|---:|---:|---:|
| local `fun bump` | 0.640 s | 0.620–0.670 s | 1.76× |
| local `val bump = fn` | 0.365 s | 0.350–0.385 s | 1.00× |

## Generated-code evidence

After `clos_known`, the named form still contains a `Letrec` and an annotated
application of `bump`. The anonymous form has already substituted the body at
the call site.

After `bvl_inline`, the named loop has this shape:

```text
(let
(c <- (Cons closure_tag 0 (Label loop_bump_clos)))
(call loop
(Add (let (d <- n) (Add 1 d)) acc)
(Sub 1 n)))
```

The `Add 1 d` is the inlined body of `bump`, while `c` is never read. The closure
allocation is therefore dead, but it survives through final code generation.
The x64 loop checks for 24 bytes of heap and stores the closure header, code
pointer, and empty environment on every iteration. The anonymous loop has no
corresponding heap check or allocation.

The named executable also retains separate `loop_bump` worker and closure-wrapper
symbols; the anonymous executable does not retain a `bump` symbol.

## Cause

`clos_known` treats anonymous `Fn` and `Letrec` differently:

- an anonymous `Fn` can receive a body-carrying `Clos` approximation
([`clos_knownScript.sml`](https://github.com/CakeML/cakeml/blob/0fe74ee25d03a7d6d72892927edcaf5ae9677e10/compiler/backend/clos_knownScript.sml#L610-L616));
- every `Letrec`, including this single function with no recursive occurrence,
receives `ClosNoInline`
([`clos_knownScript.sml`](https://github.com/CakeML/cakeml/blob/0fe74ee25d03a7d6d72892927edcaf5ae9677e10/compiler/backend/clos_knownScript.sml#L617-L629)).

`decide_inline` can body-inline only `Clos`; `ClosNoInline` merely enables a
direct-call annotation
([`clos_knownScript.sml`](https://github.com/CakeML/cakeml/blob/0fe74ee25d03a7d6d72892927edcaf5ae9677e10/compiler/backend/clos_knownScript.sml#L511-L529)).
Closure conversion consequently materializes the local closure before the BVL
pass gets an opportunity to inline its call; the single-function `Letrec`
lowering constructs a closure block
([`clos_to_bvlScript.sml`](https://github.com/CakeML/cakeml/blob/0fe74ee25d03a7d6d72892927edcaf5ae9677e10/compiler/backend/clos_to_bvlScript.sml#L453-L466)).
The later inliner substitutes the worker body but does not perform the
higher-level use/escape cleanup needed to remove the already-materialized
closure, wrapper, and worker.

This is a source-spelling performance cliff, not a correctness problem.

## Expected behavior

For a small local function that is provably nonrecursive and nonescaping,
equivalent `fun f x = e` and `val f = fn x => e` forms should produce equivalent
optimized code. If all uses have been inlined or converted to direct worker
calls, no closure should be allocated.

## Possible implementation direction

1. Analyze dependencies within `Letrec` groups and identify singleton or
otherwise nonrecursive SCCs.
2. Give small nonrecursive members body-carrying approximations, subject to the
existing inlining and growth limits, instead of assigning every member
`ClosNoInline`.
3. Split recursive groups into dependency SCCs where possible; retain the
conservative treatment for genuinely recursive members.
4. Add post-inlining closure use/escape cleanup so a closure allocation and its
wrapper/worker can be removed when no value use remains.

The first two steps should fix this minimal case by allowing the inlining to
happen before closure conversion.

## Regression coverage

- Compare equivalent nonrecursive local `fun` and `val ... = fn ...` forms.
- Check optimized IR or emitted code to ensure the hot loop contains no closure
construction or heap-space check.
- Check that an unused wrapper and worker are removed in sealed compilation.
- Cover self recursion and mutually recursive `and` groups to ensure SCC and
growth handling remain bounded.
- Include a nonescaping direct-call case too large to inline, which should use a
worker call without allocating a closure if all uses are known.

## Related issues

- [#338, “Function inlining in closLang”](https://github.com/CakeML/cakeml/issues/338), introduced the relevant early-inlining capability and is closed. This issue is a concrete remaining gap for nonrecursive `Letrec` bindings plus post-inline cleanup.
- [#267, “Add simple form of higher-order inlining”](https://github.com/CakeML/cakeml/issues/267), concerns specialization of higher-order recursive library functions and is distinct from this first-order local case.

_Written by Codex (OpenAI)._

Contributor guide

No contributing guide indexed for this repository

Research direction

Start with the cited clos_knownScript.sml locations for Letrec approximations and decide_inline, then inspect the single-function Letrec lowering in clos_to_bvlScript.sml. Reproduce the named and anonymous examples with cake and compare the generated output. Done means equivalent optimized forms avoid the dead closure allocation while recursive groups retain conservative handling and regression coverage checks the listed cases.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.