To box or not to box? (how to determine if a value can be more efficiently passed by value or by reference)

Question

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.

Answer 1

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.

Answer 2

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.

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 restricted 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 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.