<p>I want to remove explicit addressing from my type system.</p>
<p>In low level languages like C or Rust, you always have a choice whether to store some data by value or by reference. There are some advantages to each:</p>
<div class="s-table-container">
<table class="s-table">
<thead>
<tr>
<th>By value</th>
<th>By reference</th>
</tr>
</thead>
<tbody>
<tr>
<td>Space can be reserved at compile time, no memory allocations needed</td>
<td>Fast to pass regardless of size</td>
</tr>
<tr>
<td>Better cache consistency</td>
<td>Allows recursive, potentially infinitely sized, data structures</td>
</tr>
<tr>
<td>Always needs to be at least as large as the largest potential size</td>
<td>Allows dynamic size</td>
</tr>
<tr>
<td>...many more subtle differences</td>
<td></td>
</tr>
</tbody>
</table>
</div>
<p>There is an issue with this: Determining which is more efficient depends on a dozen factors and is hard for a programmer to determine. Even if one option is better for the moment it could change, but it's hard to make changes to the type of things.</p>
<p>There is also a matter of philosophy. I view the type system as describing the relationships between data and the set of valid states. How an object is stored should not be part of that; it's just noise.</p>
<p>Many object oriented languages solve this by only ever storing pointers. This works, but is not always the most efficient. It leads to many very small memory allocations, which is slow and hurts cache consistency. I don't need inheritance-based polymorphism. One exception is C# which allows declaring at the type, instead of at the declaration level whether the type should be stored by value or by reference, which is still not ideal.</p>
<p>So here is my question: <strong>If I have a type declaration without any explicit indicators for how memory should be managed, how do I determine if it is more efficient to store a specific attribute by value or by reference?</strong> Ideally it would work for any kind of place data is stored or transferred, like a local variable, function argument, field of a different type etc.</p>
<p>If no exact answers exist, at least some heuristics would be nice.</p>

<types><memory-management>
To box or not to box? (how to determine if a value can be more efficiently passed by value or by reference)
CC BY-SA 4.0
2024-01-03T09:30:37.667Z
If there were a simple answer to this question, I suppose you would see it implemented in a number of existing programming languages. The fact that this is apparently not the case is a strong hint hat this problem is hard and potentially unsolvable. As with any code optimization problem, you would need to have an optimization goal - do you want faster or more compact code or data memory layout, is code actually part of the hot path, etc.?
Hans-Martin Mosner
CC BY-SA 4.0
2024-01-03T10:09:55.667Z
Adding on to this, [performance is workload dependent](https://performanceisworkloaddependent.com/).
Moonchild
CC BY-SA 4.0
2024-01-03T10:20:31.900Z
@Moonchild I wish that site would actually explain what that meant
mousetail 'he-him'
CC BY-SA 4.0
2024-01-03T10:39:36.153Z
I suppose it means that, sometimes it is more efficient to box, and sometimes not. And it does not just depend on the program you're compiling, it also depends on the program's input. So, even for a fixed program, there is no definite perfect answer to your question. (I still think it's an interesting question to look at how existing compilers do it)
Eldritch Conundrum
CC BY-SA 4.0
2024-01-03T10:45:02.390Z
That is exactly what it means.  I don't expect you'll see anything other than simple, ad-hoc heuristics, like boxing everything above a certain size (3 or 4 words, say).  A further confounder is the performance and locality characteristics of your allocator; a copying garbage collector will likely do better with small objects than many other allocation strategies because it can keep them closer together and free them more easily.
Moonchild
CC BY-SA 4.0
2024-01-03T15:25:56.177Z
The title of the question is about *passing* by value or by reference (a matter of semantics), but the question seems to really be about type layouts and memory allocation (a matter of implementation). It's worth mentioning that storing copies of objects inline, instead of as pointers, is only allowed as an optimisation when the copy cannot be mutated (or, will not be), otherwise mutations will not be correctly reflected in the original; so that is the main constraint you need to consider.
kaya3
CC BY-SA 4.0
2024-01-04T16:09:01.550Z
There is a wide variety of data structures that rely on indirect access to objects, and these will be difficult to express in your language if it does not have built-in support for indirection.  That and other questions of your language's semantics should be your first consideration, well before you turn to efficiency.  If you don't want pointers / references as data types of their own, then you probably want either Python-style everything is (a reference to) an object, or a Java-style distinction between specific primitive types, and everything else a reference type.
John Bollinger
CC BY-SA 4.0
2024-01-10T17:07:29.717Z
Just a small correction: you probably just mean 'caching performance' rather than 'consistency' which more has to do with how threads/cores communicate changes to data.
golvok
CC BY-SA 4.0
2024-01-11T09:33:15.507Z
Your language should have both - values and references - or only values (e.g. in a copy-on-write fashion). If it has both, you can have complex data structures, where the references appear only for some member variables/attributes or at a certain level. It is not (only) about performance, but about functionality and identity of objects. How do your algorithms work and handle data?
Sebastian
CC BY-SA 4.0
2024-01-11T09:34:22.843Z
A language with only references would be not very useful and confusing: `1=2; print(1);`
Sebastian
CC BY-SA 4.0
2024-01-11T09:39:30.427Z
@Sebastian High level garbage collected languages usually have only references. Even python has only references. And yes you can change the value of 1 to 2 but it requires ctypes abuse
mousetail 'he-him'
CC BY-SA 4.0
2024-01-11T10:09:10.720Z
@mousetail You can do value semantics in those languages with shallow and deep copy operations.
Sebastian
<p><strong>I am not aware of any such compile-time algorithm, and I doubt an optimal one may exist.</strong></p>
<h4>Calling convention</h4>
<p>One consideration that is missing from your table is calling convention. When compiling to native code, an important optimization is to pass via registers, rather than passing via the stack.</p>
<p>Passing via registers avoids writing to and then reading from the stack, whenever possible. It is actually so critical that GCC and LLVM will pass small <code>struct</code> in multiple registers when possible.</p>
<p>If a function only accepts arguments by reference, and is not inlined, then an argument sitting in a register must be written to the stack so its address can be taken, and then will be read from the stack within the function. And that's how one bleeds performance.</p>
<h4>Coalesced Boxing</h4>
<p>As you mentioned, in your table, boxing or not affects quite a few parameters. Worse, though, your table is incomplete!</p>
<p>When boxing is performed for recursion reasons, it's also possible to use unrolling techniques (ie, box N items at once) or just build a single stack of items, rather than boxing them all individually. There are, therefore, many, many, choices.</p>
<h4>Optimization</h4>
<p>It may be useful to reformulate the problem, instead, as: given that all objects are boxed by default -- a safe transformation -- which can we <em>coalesce</em> or <em>fully unbox</em>?</p>
<p>It is fairly well-known amongst optimizer developers that there's no perfect ordering of optimizations. The current optimization pipelines have been achieved by careful tuning, driven by heuristics and benchmarks, and there are Super-Optimizers whose only added-value is to juggle optimization pipelines and compare the performance of the resulting binaries.</p>
<p>As an illustration, it will likely be more optimal to box a large array before passing it down (as a single pointer, or a pointer/size pair) several functions, rather than copying the array at each call. However, should the functions be inlined, the copies can be trivially eliminated, and boxing is now a pessimization!</p>
<p>Hence, whether to unbox the array or not depends on whether the function(s) it is passed to is(are) inlined or not...</p>
<p>The fact that JS engines and the JVM leave so many smallish types boxed, however, leads me to think that the problem is highly non-trivial.</p>
<h3>Case by case</h3>
<p>Attempting to decide on a <em>type</em> basis seems untractable. As mentioned, even a somewhat large-ish array may be better off unboxed -- if it's never copied <em>and</em> fits on the stack.</p>
<p>The special case is values that are smaller than a pointer, such as booleans, most integrals &amp; floating points, etc... Unless reference semantics are necessary, those are better off unboxed at all times.</p>
<h3>Polymorphism to the rescue?</h3>
<p>Instead of, or in complement to, attempting to decide for each value whether to box it or not, polymorphism may be an interesting approach.</p>
<p>Instead of generating a single function which takes either a boxed or unboxed argument, you could instead generate a function which accepts <em>both</em>, so that the caller may pass whichever it has in hands.</p>
<p>Similarly, it may be possible for a <em>field</em> of a type to accept either boxed or unboxed value. This may be more complicated -- though JS engines typically do so through the concept of &quot;shape&quot; -- but would once again allow NOT to pick one at a compile-time.</p>
<p>Whether this would lead to relatively optimal code, however, is quite unclear to me.</p>

CC BY-SA 4.0
2024-01-03T15:25:45.380Z
2024-01-03T15:25:45.380Z
Matthieu M.
CC BY-SA 4.0
2024-01-03T17:50:42.423Z
Passing by pointer in default then gradually add specific conditions when passing by value is safe and beneficial is a good idea
mousetail 'he-him'
<h2>Register size</h2>
<p>Very small, <code>zeroinit</code> types, that typically fits the machine register size, are &quot;passed&quot; and &quot;returned&quot; via registers, that act as effectively reserved space for arguments and return on specific <a href="https://faultlore.com/blah/c-isnt-a-language/" rel="nofollow noreferrer">target triplets</a>.</p>
<p>These basic types have value semantics <em>because</em> copying them into/from these reserved registers have a very crucial performance impact.</p>
<h2>Immutable types</h2>
<p>If your language defines <code>const</code> or immutable semantics, passing stack references of immutable instances increases the performance substantially, because you don't need to either copy the object to simulate value semantics, and also can further cache read-only data obtained from these immutable instances.</p>
<p><code>const</code>/<code>constexp</code>/<code>comptime</code> semantics also enable some more optimizations that are only possible with <a href="https://en.wikipedia.org/wiki/Restrict" rel="nofollow noreferrer"><code>restrict</code>ed</a> arguments.</p>
<h2>Escape analysis</h2>
<blockquote>
<p>I want to remove explicit addressing from my type system.</p>
</blockquote>
<p>If your compiler can determine that one leaf function creates and returns, or otherwise use an object that never &quot;escapes&quot; -- that is, the only references of the object created or passed only exists in local thread stack references, and never are stored in any heap allocated object -- your compiler can automatically mark this argument/return a <code>noescape</code> or <a href="https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/ref" rel="nofollow noreferrer"><code>ref</code></a> variation of argument/return.</p>
<p>This, in turn, enables further optimizations in callers of these functions, &quot;bubbling up&quot; the escape analysis results.</p>
<p>This enables that the <em>calling</em> code decides if an <code>ref.in</code> argument is allocated on heap or stack, and further enables disabling garbage collection on <code>ref.out</code> heap allocated objects temporally.</p>
<p><code>ref.out</code> instances reduce garbage collection pressure as they only exist and are managed in stack references, and would need be &quot;converted&quot; in normal, heap allocated objects, if they &quot;escape&quot; this restriction.</p>

CC BY-SA 4.0
2024-01-03T18:07:26.380Z
2024-01-03T18:07:26.380Z
André L F S Bacci
CC BY-SA 4.0
2024-01-04T12:02:38.660Z
Are you talking about a JIT?  Calling conventions can't normally be optimization-dependent in ahead-of-time compiled code.
Peter Cordes
CC BY-SA 4.0
2024-01-04T22:06:18.377Z
@PeterCordes If a function is limited in scope to one module or file, the compiler can do whatever it needs with in that scope; there is no need for a function with the normal ABI to exist. Even if it escapes, a compiler could create multiple functions, some only for us in that module. GNAT emits .ali files alongside .o files, storing data not provided by the object file; a compiler that did that could mutate calling conventions at will, as long as it was noted in the data file used by to compile and link any users.
prosfilaes
CC BY-SA 4.0
2024-01-04T22:21:10.860Z
@prosfilaes: True.  GCC will do that to some degree, making `foo.constprop.0` clones of functions for callers within the compilation unit (or with LTO), such as https://godbolt.org/z/co4nq7TT8 .  And Clang/LLVM will rewrite a function for its only caller if you make it `static`.  GCC and LLVM aren't as aggressive about optimizing calling conventions as they could be, probably since it's a hard problem.  But they will also do stuff like taking advantage of the fact that a function doesn't clobber a certain call-clobbered register, even if they don't inline it.
Peter Cordes
# To box or not to box? (how to determine if a value can be more efficiently passed by value or by reference)
Posted by: username_0 on 2024-01-03
I want to remove explicit addressing from my type system.

In low level languages like C or Rust, you always have a choice whether to store some data by value or by reference. There are some advantages to each:

| By value | By reference |
| --- | --- |
| Space can be reserved at compile time, no memory allocations needed | Fast to pass regardless of size |
| Better cache consistency | Allows recursive, potentially infinitely sized, data structures |
| Always needs to be at least as large as the largest potential size | Allows dynamic size |
| ...many more subtle differences |  |

There is an issue with this: Determining which is more efficient depends on a dozen factors and is hard for a programmer to determine. Even if one option is better for the moment it could change, but it's hard to make changes to the type of things.

There is also a matter of philosophy. I view the type system as describing the relationships between data and the set of valid states. How an object is stored should not be part of that; it's just noise.

Many object oriented languages solve this by only ever storing pointers. This works, but is not always the most efficient. It leads to many very small memory allocations, which is slow and hurts cache consistency. I don't need inheritance-based polymorphism. One exception is C# which allows declaring at the type, instead of at the declaration level whether the type should be stored by value or by reference, which is still not ideal.

So here is my question: **If I have a type declaration without any explicit indicators for how memory should be managed, how do I determine if it is more efficient to store a specific attribute by value or by reference?** Ideally it would work for any kind of place data is stored or transferred, like a local variable, function argument, field of a different type etc.

If no exact answers exist, at least some heuristics would be nice.
**Tags:** types memory-management
> **Comments:**
> **username_1**: If there were a simple answer to this question, I suppose you would see it implemented in a number of existing programming languages. The fact that this is apparently not the case is a strong hint hat this problem is hard and potentially unsolvable. As with any code optimization problem, you would need to have an optimization goal - do you want faster or more compact code or data memory layout, is code actually part of the hot path, etc.?  
> **username_2**: Adding on to this, [performance is workload dependent](https://performanceisworkloaddependent.com/).  
> **username_0**: @Moonchild I wish that site would actually explain what that meant  
> **username_3**: I suppose it means that, sometimes it is more efficient to box, and sometimes not. And it does not just depend on the program you're compiling, it also depends on the program's input. So, even for a fixed program, there is no definite perfect answer to your question. (I still think it's an interesting question to look at how existing compilers do it)  
> **username_2**: That is exactly what it means.  I don't expect you'll see anything other than simple, ad-hoc heuristics, like boxing everything above a certain size (3 or 4 words, say).  A further confounder is the performance and locality characteristics of your allocator; a copying garbage collector will likely do better with small objects than many other allocation strategies because it can keep them closer together and free them more easily.  
> **username_4**: The title of the question is about *passing* by value or by reference (a matter of semantics), but the question seems to really be about type layouts and memory allocation (a matter of implementation). It's worth mentioning that storing copies of objects inline, instead of as pointers, is only allowed as an optimisation when the copy cannot be mutated (or, will not be), otherwise mutations will not be correctly reflected in the original; so that is the main constraint you need to consider.  
> **username_5**: There is a wide variety of data structures that rely on indirect access to objects, and these will be difficult to express in your language if it does not have built-in support for indirection.  That and other questions of your language's semantics should be your first consideration, well before you turn to efficiency.  If you don't want pointers / references as data types of their own, then you probably want either Python-style everything is (a reference to) an object, or a Java-style distinction between specific primitive types, and everything else a reference type.  
> **username_6**: Just a small correction: you probably just mean 'caching performance' rather than 'consistency' which more has to do with how threads/cores communicate changes to data.  
> **username_7**: Your language should have both - values and references - or only values (e.g. in a copy-on-write fashion). If it has both, you can have complex data structures, where the references appear only for some member variables/attributes or at a certain level. It is not (only) about performance, but about functionality and identity of objects. How do your algorithms work and handle data?  
> **username_7**: A language with only references would be not very useful and confusing: `1=2; print(1);`  
> **username_0**: @Sebastian High level garbage collected languages usually have only references. Even python has only references. And yes you can change the value of 1 to 2 but it requires ctypes abuse  
> **username_7**: @mousetail You can do value semantics in those languages with shallow and deep copy operations.  
---
## 2 answers
### Answer by username_8 on 2024-01-03. Score: 12
**I am not aware of any such compile-time algorithm, and I doubt an optimal one may exist.**

#### Calling convention

One consideration that is missing from your table is calling convention. When compiling to native code, an important optimization is to pass via registers, rather than passing via the stack.

Passing via registers avoids writing to and then reading from the stack, whenever possible. It is actually so critical that GCC and LLVM will pass small `struct` in multiple registers when possible.

If a function only accepts arguments by reference, and is not inlined, then an argument sitting in a register must be written to the stack so its address can be taken, and then will be read from the stack within the function. And that's how one bleeds performance.

#### Coalesced Boxing

As you mentioned, in your table, boxing or not affects quite a few parameters. Worse, though, your table is incomplete!

When boxing is performed for recursion reasons, it's also possible to use unrolling techniques (ie, box N items at once) or just build a single stack of items, rather than boxing them all individually. There are, therefore, many, many, choices.

#### Optimization

It may be useful to reformulate the problem, instead, as: given that all objects are boxed by default -- a safe transformation -- which can we *coalesce* or *fully unbox*?

It is fairly well-known amongst optimizer developers that there's no perfect ordering of optimizations. The current optimization pipelines have been achieved by careful tuning, driven by heuristics and benchmarks, and there are Super-Optimizers whose only added-value is to juggle optimization pipelines and compare the performance of the resulting binaries.

As an illustration, it will likely be more optimal to box a large array before passing it down (as a single pointer, or a pointer/size pair) several functions, rather than copying the array at each call. However, should the functions be inlined, the copies can be trivially eliminated, and boxing is now a pessimization!

Hence, whether to unbox the array or not depends on whether the function(s) it is passed to is(are) inlined or not...

The fact that JS engines and the JVM leave so many smallish types boxed, however, leads me to think that the problem is highly non-trivial.

### Case by case

Attempting to decide on a *type* basis seems untractable. As mentioned, even a somewhat large-ish array may be better off unboxed -- if it's never copied *and* fits on the stack.

The special case is values that are smaller than a pointer, such as booleans, most integrals & floating points, etc... Unless reference semantics are necessary, those are better off unboxed at all times.

### Polymorphism to the rescue?

Instead of, or in complement to, attempting to decide for each value whether to box it or not, polymorphism may be an interesting approach.

Instead of generating a single function which takes either a boxed or unboxed argument, you could instead generate a function which accepts *both*, so that the caller may pass whichever it has in hands.

Similarly, it may be possible for a *field* of a type to accept either boxed or unboxed value. This may be more complicated -- though JS engines typically do so through the concept of "shape" -- but would once again allow NOT to pick one at a compile-time.

Whether this would lead to relatively optimal code, however, is quite unclear to me.
> **Comments:**
> **username_0** (2024-01-03): Passing by pointer in default then gradually add specific conditions when passing by value is safe and beneficial is a good idea  
---
### Answer by username_9 on 2024-01-03. Score: 3
## Register size

Very small, `zeroinit` types, that typically fits the machine register size, are "passed" and "returned" via registers, that act as effectively reserved space for arguments and return on specific [target triplets](https://faultlore.com/blah/c-isnt-a-language/).

These basic types have value semantics *because* copying them into/from these reserved registers have a very crucial performance impact.

## Immutable types

If your language defines `const` or immutable semantics, passing stack references of immutable instances increases the performance substantially, because you don't need to either copy the object to simulate value semantics, and also can further cache read-only data obtained from these immutable instances.

`const`/`constexp`/`comptime` semantics also enable some more optimizations that are only possible with [`restrict`ed](https://en.wikipedia.org/wiki/Restrict) arguments.

## Escape analysis

> I want to remove explicit addressing from my type system.

If your compiler can determine that one leaf function creates and returns, or otherwise use an object that never "escapes" -- that is, the only references of the object created or passed only exists in local thread stack references, and never are stored in any heap allocated object -- your compiler can automatically mark this argument/return a `noescape` or [`ref`](https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/ref) variation of argument/return.

This, in turn, enables further optimizations in callers of these functions, "bubbling up" the escape analysis results.

This enables that the *calling* code decides if an `ref.in` argument is allocated on heap or stack, and further enables disabling garbage collection on `ref.out` heap allocated objects temporally.

`ref.out` instances reduce garbage collection pressure as they only exist and are managed in stack references, and would need be "converted" in normal, heap allocated objects, if they "escape" this restriction.
> **Comments:**
> **username_10** (2024-01-04): Are you talking about a JIT?  Calling conventions can't normally be optimization-dependent in ahead-of-time compiled code.  
> **username_11** (2024-01-04): @PeterCordes If a function is limited in scope to one module or file, the compiler can do whatever it needs with in that scope; there is no need for a function with the normal ABI to exist. Even if it escapes, a compiler could create multiple functions, some only for us in that module. GNAT emits .ali files alongside .o files, storing data not provided by the object file; a compiler that did that could mutate calling conventions at will, as long as it was noted in the data file used by to compile and link any users.  
> **username_10** (2024-01-04): @prosfilaes: True.  GCC will do that to some degree, making `foo.constprop.0` clones of functions for callers within the compilation unit (or with LTO), such as https://godbolt.org/z/co4nq7TT8 .  And Clang/LLVM will rewrite a function for its only caller if you make it `static`.  GCC and LLVM aren't as aggressive about optimizing calling conventions as they could be, probably since it's a hard problem.  But they will also do stuff like taking advantage of the fact that a function doesn't clobber a certain call-clobbered register, even if they don't inline it.  
---
