RFC: Tuples with Value Semantics in Encore

Proposal: tuples should be passed around by copy by default, not by pointer

Rationale: one less allocation, one less indirection

Downsides: incurs some copying overhead, meaning more memory bandwidth stress

Details

The compiler will have to maintain two internal tuple type kinds -- stack tuples and heap tuples. The current implementation only has heap tuples.

An n-tuple should be implemented equivalent to the following C struct:

struct tuple_T1_T2_..._Tn {
  T1 const f1;
  ...
  Tn const fn;
};

and manipulated in the C code as a value type. Tracing of tuples is solved by inserting calls to the correct trace function for each static type of each field of a tuple.

Tuples that will not fit in a single cache line should should be allocated on the heap, meaning we default to the current tuple implementation. Such tuples thus have pointer semantics.

Stack tuple arguments to polymorphic functions or asynchronous calls must be promoted to heap tuples before being passed in, meaning such calls are expensive. The reason for the former is that heap tuples have the necessary meta data for calling trace functions. The reason for the latter is that we have no guarantee that a stack tuple on the calling stack wont be prematurely deallocated.

Compact representation of heap tuples

The following is only relevant once objects know their type.

Proposal: more compact heap tuples

Rationale: small objects should be small

Downsides: imposes a limit on the number of fields of a tuple (proposal: 32)

A n-heap tuple should be implemented thus:

struct tuple_T1_T2_..._Tn {
  uint64_t metadata;
  T1 const f1;
  ...
  Tn const fn;
};

The metadata is an array of 32 2-bit elements. The value of index i is interpreted thus:

00 Field i holds primitive data
01 Field i holds a pointer to an object
10 Field i holds a pointer to an active object
11 There is no field i, meaning the size of the heap tuple is i-1

Tracing a heap tuple thus works like this (pseudocode):

def trace(tuple):
  for md,index in tuple.metadata
    if md == 00:
      pass # or whatever we do on primitives
    if md == 01:
      obj = tuple.fields[index]
      obj.type._trace_function(obj)
    if md == 10: 
      obj = tuple.fields[index]
      trace_actor(obj)
    if md == 11:
      break