Tuesday, August 11, 2015

Stack allocated variables in ELENA

In many programming languages numbers are immutable, so result of any arithmetic operation is a new number. For an object-oriented language it means creating a new object, putting an extra load to GC. Different languages choose different strategies to fight this problem.

In ELENA it is possible to declare embeddable objects which will be stack allocated. All basic numeric classes (IntNumber, LongNumber, RealNumber, ...) are embeddable.

Declaring a stack allocated object is quite straightforward - we have to declare a strong typed variable

   int i := 0.

The "type" attribute tells the compiler that we creates a variable which is bound to system'IntNumber (int is a strong type associated with it). If the class is embeddable then it will allocate a space in the method stack and copies 0 into it.

The following operation

   int m := 2 * i + 1.

will be executed directly without allocating any additional space in the program heap.

But if we will pass it into the message call

   console writeLine(a[n]).

the compiler will box it (create an object copy in the heap). Moreover if the object is changeable after the operation the object will be unboxed (content of the dynamic object will be copied into original variable). In our case IntNumber is immutable, so no need to unbox.

In most cases we have to pass our number to one or another method. So there should be a way to reduce explicit boxing. It is possible to declare a method to be stack safe. As a result this will allow the compiler pass stack allocated variables directly. The only limitation that it should be a direct / virtual message call (it means that the target should be known. i.e. "typecasted" and be sealed or limited). Many classes provide such an interface, for example - an array

   console writeLine
              (a array; getAt int:n).

In this case n is passed directly. Note that by sending get&array message to a, we typecast it.

This approach works quite good, except it cannot be used for returning values.

   int l := a array; length.

In this case a new dynamic object is created despite using a stack allocated variable and known operation - get&length.

So we have to introduce a new concept - the type wrapper. If the class is sealed and has only one typed embeddable field it can be marked as a wrapper. In this case it could be used as by-reference parameter.

   int l := 0.
   a array; readLengthTo vint:l.

vint is a strong type associated with Integer class. Integer is a wrapper around IntNumber value.

Some magic has to happen here. In normal case the compiler should send vint message to boxed l variable. Because IntNumber does not support get&vint message the operation will be broken. But in this case the compiler knowns that vint is a wrapper around int, so it will implicitly box it into an instance of Integer class. Moreover readLength&vint is direct and stack safe so the compiler will be able to pass a reference to our variable directly without extra boxing / unboxing operations.

As a result we are able to read the array length into the variable without allocating the number in the heap.

As you may see using this simple tricks we were able to write quite optimized code.