# Add support for stack allocation

**URL:** <https://discuss.ocaml.org/t/add-support-for-stack-allocation/7039>\
**Category:** Learning\
**Tags:** language-design\
**Created:** [January 2, 2021, 12:20am UTC](https://discuss.ocaml.org/t/add-support-for-stack-allocation/7039 "2021-01-02T00:20:05Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![olleharstedt](https://avatars.discourse-cdn.com/v4/letter/o/f1d935/32.png) [@olleharstedt](https://discuss.ocaml.org/u/olleharstedt)\
**Post date:** [January 2, 2021, 12:20am UTC](https://discuss.ocaml.org/t/add-support-for-stack-allocation/7039/1 "2021-01-02T00:20:05Z")

</div>

How hard would it be to add support for stack allocated variables that are not traced by the GC? The constraint would be that those variables are not allowed to “escape” (for a proper definition of escaping). This could be useful for tight loops. Many JITs do escape analysis to automatically achieve stack allocation (or reduce allocations), but I think it’s more attractive to have the ability to control when this happens, as a way to “opt out” of the GC.

Example using `local` for stack allocation:

```auto
let test () =
  let local a : point = {x = 10; y = 20} in
  let local b : string = point_to_string a in
  print_endline b;
  b; (* Error: b is not allowed to escape scope *)

```

---

<div class="post-metadata">

**Author:** ![silene](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/silene/32/2707_2.png) [@silene](https://discuss.ocaml.org/u/silene)\
**Post date:** [January 2, 2021, 7:14am UTC](https://discuss.ocaml.org/t/add-support-for-stack-allocation/7039/2 "2021-01-02T07:14:11Z")

</div>

> [@olleharstedt](#):
>
> How hard would it be to add support for stack allocated variables that are not traced by the GC?

Be careful what you wish for. If a block is not scanned by the GC, then it cannot refer to GC-allocated values, otherwise the GC might consider them dead while they can still be acceded through the stack-allocated block. So, it means that it would only contain integer values. Moreover, its address cannot even be passed to other functions, as it would then become markable by the GC, which would confuse it to no end (due to the no-naked-pointer feature). So, the use of stack-allocated blocks would be severely limited.

So, if you consider your example, variable `a` contains only integer values, so it could be allocated on stack, except that it is passed to function `point_to_string`. As for value `b`, it could never have been stack-allocated in the first place. First, it is returned by `point_to_string`, so it needs to be allocated on the heap anyway (unless the call to the function is inlined). Second, its size is dynamically determined, so it again needs to be allocated on the heap. Third, as with `a`, it is passed to another function.

That said, your motivation (“tight loops”) is actually a meaningful one. Thus, the OCaml compiler does perform an optimization pass to allocate such values on the stack. For example, the following example does not allocate anything on the heap (and using the `ref` syntactic sugar does not change that):

```ocaml
let foo n =
  let a = { contents = 1 } in
  for i = 1 to n do a.contents <- a.contents * i; done;
  a.contents

```

---

<div class="post-metadata">

**Author:** ![xavierleroy](https://avatars.discourse-cdn.com/v4/letter/x/a9adbd/32.png) [@xavierleroy](https://discuss.ocaml.org/u/xavierleroy)\
**Post date:** [January 2, 2021, 10:56am UTC](https://discuss.ocaml.org/t/add-support-for-stack-allocation/7039/3 "2021-01-02T10:56:40Z")

</div>

Bruno Blanchet’s PhD thesis was on escape analysis and its use for automatic stack allocation of data structures in Java and in OCaml: [DEA training and PhD thesis: Escape Analysis](https://prosecco.gforge.inria.fr/personal/bblanche/escape-eng.html) .

He observed significant speedups in Java but much more modest speedups in OCaml. This is probably because the Java implementation he modified had a slow memory allocator and GC.

Heap allocation of small, short-lived data structures is very efficient in OCaml, so the benefits of stack allocation are low. Getting rid of memory allocation altogether, as in the example given by @silene, is still a clear win, however.

---

<div class="post-metadata">

**Author:** ![olleharstedt](https://avatars.discourse-cdn.com/v4/letter/o/f1d935/32.png) [@olleharstedt](https://discuss.ocaml.org/u/olleharstedt)\
**Post date:** [January 2, 2021, 11:39am UTC](https://discuss.ocaml.org/t/add-support-for-stack-allocation/7039/4 "2021-01-02T11:39:28Z")

</div>

> So, it means that it would only contain integer values.

Not sure I understand. Why wouldn’t it be possible to allocate, say, a known string on the stack? Like

```auto
let local s = "this is a string on the stack" in
...

```

> its address cannot even be passed to other functions, as it would then become markable by the GC

OK, this would make the feature useless. 🙂 Is there a way to tell the GC to not mark some values? Boxed vs unboxed values, or such.

---

<div class="post-metadata">

**Author:** ![olleharstedt](https://avatars.discourse-cdn.com/v4/letter/o/f1d935/32.png) [@olleharstedt](https://discuss.ocaml.org/u/olleharstedt)\
**Post date:** [January 2, 2021, 11:41am UTC](https://discuss.ocaml.org/t/add-support-for-stack-allocation/7039/5 "2021-01-02T11:41:25Z")

</div>

> [@xavierleroy](#):
>
> Heap allocation of small, short-lived data structures is very efficient in OCaml, so the benefits of stack allocation are low. Getting rid of memory allocation altogether, as in the example given by @silene, is still a clear win, however.

Hm, well, stack allocation could be used for long-lived values as well, if their size is “known” and they don’t escape (but only if they can be passed to other functions, obviously). Still not sure about the benefit, though. 🙂 One would have to test with a benchmark which is open for this kind of optimization, however that would be designed.

---

<div class="post-metadata">

**Author:** ![silene](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/silene/32/2707_2.png) [@silene](https://discuss.ocaml.org/u/silene)\
**Post date:** [January 2, 2021, 2:49pm UTC](https://discuss.ocaml.org/t/add-support-for-stack-allocation/7039/6 "2021-01-02T14:49:41Z")

</div>

> [@olleharstedt](#):
>
> > So, it means that it would only contain integer values.
> 
> Not sure I understand. Why wouldn’t it be possible to allocate, say, a known string on the stack? Like
> 
> ```auto
> let local s = "this is a string on the stack" in
> 
> ```

By integer values, I meant anything that is out of the scope of the GC, so it could also be floating-point numbers, pointers to statically allocated data, and so on. As for strings, they are represented as a pointer to a block containing a sequence of characters (and its length). If this is a literal value (i.e., a known string), the block is hardcoded in the code segment of the program. So, copying it on the stack would just waste some space without any benefit.

> [@olleharstedt](#):
>
> Is there a way to tell the GC to not mark some values?

You could make your stack-allocated block look like a regular block (i.e., prepend it with a header), and preemptively color it black, so that the GC skips it if it ever follows a pointer to it.

Obviously, you would still need to perform an interprocedural analysis to make sure that none of the called functions cause the pointer to outlive the stack frame. Once you have implemented such an analysis, there is not much point in having a `let local` keyword anymore.

If you wanted to avoid such an interprocedural analysis, you would instead need to annotate all the function signatures using a `[@@local]` attribute. Then, a simpler intraprocedural analysis would be able to check that local pointers are never passed as nonlocal arguments. That said, this would still make the `let local` keyword useless, since the escape analysis would be trivial.

---

<div class="post-metadata">

**Author:** ![olleharstedt](https://avatars.discourse-cdn.com/v4/letter/o/f1d935/32.png) [@olleharstedt](https://discuss.ocaml.org/u/olleharstedt)\
**Post date:** [January 2, 2021, 3:49pm UTC](https://discuss.ocaml.org/t/add-support-for-stack-allocation/7039/7 "2021-01-02T15:49:53Z")

</div>

> [@silene](#):
>
> You could make your stack-allocated block look like a regular block (i.e., prepend it with a header), and preemptively color it black, so that the GC skips it if it ever follows a pointer to it.

True. Since stack allocation is known on compile time, it could even be one huge block allocated at program start.

> [@silene](#):
>
> That said, this would still make the `let local` keyword useless, since the escape analysis would be trivial.

No, the point with being explicit is two-fold:

1. Predictable performance, not have to guess which optimization is being done.

2. Make compilation fail if you violate the constraint on `local`, so you can adapt your code to stack allocation.

---

<div class="post-metadata">

**Author:** ![silene](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/silene/32/2707_2.png) [@silene](https://discuss.ocaml.org/u/silene)\
**Post date:** [January 2, 2021, 4:11pm UTC](https://discuss.ocaml.org/t/add-support-for-stack-allocation/7039/8 "2021-01-02T16:11:12Z")

</div>

> [@olleharstedt](#):
>
> Since stack allocation is known on compile time, it could even be one huge block allocated at program start.

What I said at the beginning of the discussion still holds: This block cannot container any non-integer values, since it will not be scanned by the garbage collector. So, your code needs to be quite peculiar to exhibit such huge blocks.

---

<div class="post-metadata">

**Author:** ![olleharstedt](https://avatars.discourse-cdn.com/v4/letter/o/f1d935/32.png) [@olleharstedt](https://discuss.ocaml.org/u/olleharstedt)\
**Post date:** [January 2, 2021, 4:39pm UTC](https://discuss.ocaml.org/t/add-support-for-stack-allocation/7039/9 "2021-01-02T16:39:43Z")

</div>

Related topic: Value types in Java: [The new ValueType in Java: Why value types are important](https://jaxenter.com/java-value-type-163446.html)

Also compare with value typed structs in Swift.

---

<div class="post-metadata">

**Author:** ![raphael-proust](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/raphael-proust/32/415_2.png) [@raphael-proust](https://discuss.ocaml.org/u/raphael-proust)\
**Post date:** [January 2, 2021, 7:18pm UTC](https://discuss.ocaml.org/t/add-support-for-stack-allocation/7039/10 "2021-01-02T19:18:59Z")

</div>

> [@silene](#):
>
> This block cannot contain any non-integer values, since it will not be scanned by the garbage collector. So, your code needs to be quite peculiar to exhibit such huge blocks.

Is this necessarily true?  
Consider the following type:

```auto
type t = {
  a : int;
  b : string;
}

```

The block contains an integer (not scanned by the GC) and a string (a pointer, followed by a GC, to a block marked by the GC).  
What would prevent to allocate a `t` directly on the stack?  
When the GC follows roots from the stack, what would be a fundamental obstacle to having these blocks on the stack?

Specifically, consider a function that has two local variables: `a` an integer and `b` a string. The stack frame has two words for these two values: one word to represent the integer and one word to point to a block on the heap that represents the string.  
What is the fundamental difference between these two situations (a stack-allocated block that contains pointers to heap-allocated objects vs. stack pointers to heap-allocated objects) that prevents one from occurring?

---

<div class="post-metadata">

**Author:** ![silene](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/silene/32/2707_2.png) [@silene](https://discuss.ocaml.org/u/silene)\
**Post date:** [January 2, 2021, 8:00pm UTC](https://discuss.ocaml.org/t/add-support-for-stack-allocation/7039/11 "2021-01-02T20:00:00Z")

</div>

You are right. If you color the stack-allocated block in black, and then register all the fields of the block as roots, then you can store GC-handled values in it. But you are going to lose a lot of the advantages of a stack-allocated block. In particular, your stack-allocated block will be scanned by the GC a lot more often than an oldified block, and thus be slower.

---

<div class="post-metadata">

**Author:** ![olleharstedt](https://avatars.discourse-cdn.com/v4/letter/o/f1d935/32.png) [@olleharstedt](https://discuss.ocaml.org/u/olleharstedt)\
**Post date:** [January 2, 2021, 9:35pm UTC](https://discuss.ocaml.org/t/add-support-for-stack-allocation/7039/12 "2021-01-02T21:35:36Z")

</div>

What if `b` points to another stack allocated value, like a string buffer with fixed size (not just another int or float)?

---

<div class="post-metadata">

**Author:** ![olleharstedt](https://avatars.discourse-cdn.com/v4/letter/o/f1d935/32.png) [@olleharstedt](https://discuss.ocaml.org/u/olleharstedt)\
**Post date:** [January 3, 2021, 12:31pm UTC](https://discuss.ocaml.org/t/add-support-for-stack-allocation/7039/13 "2021-01-03T12:31:56Z")

</div>

A related white paper perhaps:

> **[CiteSeerX — Combining Garbage Collection and Region Inference in The ML Kit](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.1455)**

---

<div class="post-metadata">

**Author:** ![Armael](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/armael/32/1223_2.png) [@Armael](https://discuss.ocaml.org/u/Armael)\
**Post date:** [January 3, 2021, 12:45pm UTC](https://discuss.ocaml.org/t/add-support-for-stack-allocation/7039/14 "2021-01-03T12:45:49Z")

</div>

On this line of work, you might want to read the retrospective by some of the people involved:  
“A Retrospective on Region-Based Memory Management” (Tofte, Birkedal, Elsman, Hallenberg).

> **[B:LISP.0000029446.78563.a4.pdf](https://link.springer.com/content/pdf/10.1023/B:LISP.0000029446.78563.a4.pdf)**
>
> 176.92 KB

---

<div class="post-metadata">

**Author:** ![gadmm](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/gadmm/32/877_2.png) [@gadmm](https://discuss.ocaml.org/u/gadmm)\
**Post date:** [January 3, 2021, 1:52pm UTC](https://discuss.ocaml.org/t/add-support-for-stack-allocation/7039/15 "2021-01-03T13:52:26Z")

</div>

> [@silene](#):
>
> If you wanted to avoid such an interprocedural analysis, you would instead need to annotate all the function signatures using a `[@@local]` attribute. Then, a simpler intraprocedural analysis would be able to check that local pointers are never passed as nonlocal arguments. That said, this would still make the `let local` keyword useless, since the escape analysis would be trivial.

A relevant paper: _“Gentrification gone too far? affordable 2nd-class values for fun and (co-)effect”_ by Osvald et al.

> **[Gentrification gone too far? affordable 2nd-class values for fun and...](https://dl.acm.org/doi/10.1145/2983990.2984009)**

Perhaps a lower-hanging fruit than (or a stepping stone to) more invasive proposals involving regions/lifetimes (the paper presents some more use-cases than avoiding allocations in higher-order code).

---

<div class="post-metadata">

**Author:** ![olleharstedt](https://avatars.discourse-cdn.com/v4/letter/o/f1d935/32.png) [@olleharstedt](https://discuss.ocaml.org/u/olleharstedt)\
**Post date:** [January 3, 2021, 2:24pm UTC](https://discuss.ocaml.org/t/add-support-for-stack-allocation/7039/16 "2021-01-03T14:24:03Z")

</div>

> [@gadmm](#):
>
> Perhaps a lower-hanging fruit than (or a stepping stone to) more invasive proposals involving regions/lifetimes (the paper presents some more use-cases than avoiding allocations in higher-order code).

That paper has very ambitious targets, IMO. 🙂 Not so “low hanging”.

---

<div class="post-metadata">

**Author:** ![olleharstedt](https://avatars.discourse-cdn.com/v4/letter/o/f1d935/32.png) [@olleharstedt](https://discuss.ocaml.org/u/olleharstedt)\
**Post date:** [January 3, 2021, 8:17pm UTC](https://discuss.ocaml.org/t/add-support-for-stack-allocation/7039/17 "2021-01-03T20:17:36Z")

</div>

OK, so C# actually supports this, but maybe not as safe as it should/could be.

> **[Structure types - C# reference](https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/builtin-types/struct#ref-struct)**
>
> Learn about the struct type in C#

> **[stackalloc expression - C# reference](https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/operators/stackalloc)**
>
> stackalloc expression - C# reference

---

<div class="post-metadata">

**Author:** ![silene](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/silene/32/2707_2.png) [@silene](https://discuss.ocaml.org/u/silene)\
**Post date:** [January 4, 2021, 7:38am UTC](https://discuss.ocaml.org/t/add-support-for-stack-allocation/7039/18 "2021-01-04T07:38:07Z")

</div>

> [@olleharstedt](#):
>
> That paper has very ambitious targets, IMO.

It is exactly the scheme I described, i.e., annotate all the relevant function arguments with a `[@local]` attribute (except that their attribute is named `@local`, because this is Scala and not OCaml). So, it is not that ambitious. In fact, this is the strict minimum to support stack allocations in a viable way, as far as I know. Any less and you will fail to be sound.

---

<div class="post-metadata">

**Author:** ![olleharstedt](https://avatars.discourse-cdn.com/v4/letter/o/f1d935/32.png) [@olleharstedt](https://discuss.ocaml.org/u/olleharstedt)\
**Post date:** [January 4, 2021, 4:03pm UTC](https://discuss.ocaml.org/t/add-support-for-stack-allocation/7039/19 "2021-01-04T16:03:40Z")

</div>

Oh ok. Thanks for the feedback! I should read the paper again (and again…).

---

<div class="post-metadata">

**Author:** ![sadiq](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/sadiq/32/2175_2.png) [@sadiq](https://discuss.ocaml.org/u/sadiq)\
**Post date:** [January 4, 2021, 6:12pm UTC](https://discuss.ocaml.org/t/add-support-for-stack-allocation/7039/20 "2021-01-04T18:12:20Z")

</div>

I suspect you will find this talk by Stephen Dolan interesting: [Unboxed Types for OCaml :: Jane Street](https://www.janestreet.com/tech-talks/unboxed-types-for-ocaml/)

Also the accompanying RFC: [RFCs/unboxed-types.md at unboxed-types · ocaml/RFCs · GitHub](https://github.com/ocaml/RFCs/blob/unboxed-types/rfcs/unboxed-types.md)

[Next page](https://discuss.ocaml.org/t/add-support-for-stack-allocation/7039.md?page=2)