Merge: Enable tagging of primitive types
authorJean Privat <jean@pryen.org>
Wed, 18 Mar 2015 05:41:34 +0000 (12:41 +0700)
committerJean Privat <jean@pryen.org>
Wed, 18 Mar 2015 05:41:34 +0000 (12:41 +0700)
Another old optimization since it was present in PRM, the Australopithecus compiler.

This PR bring back tagging of the primitives types Int, Bool and Char.

Previously, all primitive types where boxed.
It means that when a Bool, or any primitive object, must be manipulated in a polymorphic way (i.e. as an Object in a `val*`), a small box is allocated that contain the value and the reference (the `val*`) points to the box.
The boxes use the layout of real objects (with a pointer to the class table and everything) so that boxes are compatible with the various implementation of OO mechanism, eg `obj->class->vtf[METHODID]` to implement a method invocation.

Basically boxes work like Java auxiliary classes (eg. `Integer`) except that they are fully transparent for the user and, more important, a implementation detail unrelated to the specification of the language.
Therefore, one can provide a different implementation, like tagging, without worrying about breaking the specification and existing programs.

The principle of tagging is that `val*` values are overloaded to store primitive value in addition to genuine pointers to allocated object.
The two low bits of the `val*` (so 4 combinations) is used to distinguish if the value is a real pointer (in this case, bits are 00) or one of the masqueraded common type (Int, Bool and Char).
If it is a pointer there is nothing to do and the value can be used as is.
If it is a primitive value, then the real value is stored in the remaining bits (but shifted).
The trick works because allocated objects are aligned so that pointer of genuine allocated object have always their last two bits at 00.

The advantage of tagging is that this reduces the cost of manipulating primitive values in a polymorphic way, especially this reduce the numerous allocations of short lived boxes that is slow to do and increase the workload of the GC.
By comparison, with tagging, masquerading a Bool as a `val*` is easily done with few bit-to-bit operations.

Unfortunately, tagging is not a panacea since `val*` is not always a real pointer and require specific and additional protection to avoid doing `obj->class` in the case of `obj` is in fact a tagged value.
Therefore tagging add a minimal but systematic overhead to OO mechanisms like calls, type tests and equality tests.

After quick tests, the numbers are encouraging.

For nitc/nitc/nitc:
before: 0m6.796s
after: 0m6.452s (-5%, not that bad)

Benches where run and tagging was either comparable or better than systematic boxing:

![](https://cloud.githubusercontent.com/assets/135828/6656784/b5a38698-cb67-11e4-96a4-c46f7df2331f.png)

Especially `lib/ai/examples/queens.nit` get the best of it with a -20% improvement.
That make sense because it use arrays of integers to model the states of the n-queen problem. And unfortunately arrays are implemented in a homogeneous way where elements are always polymorphic `val*` values.
Once generics and collections are implemented in an heterogeneous way for primitive types, the benefit of tagging should be reevaluated.

Note: funnily, the main commit of the series, the one that implements tagging, is only made of insertions of lines (no deletion or changes) and it only modifies a single file.

Pull-Request: #1206
Reviewed-by: Alexis Laferrière <alexis.laf@xymus.net>
Reviewed-by: Alexandre Terrasa <alexandre@moz-code.org>


Trivial merge