Sentinels in collections, was RE: Primitive Queue<any T> considerations

[John Rose]

On Nov 19, 2015, at 7:19 AM, Rezaei, Mohammad A. <Mohammad.Rezaei at gs.com> wrote:
> 
> If we’re willing to pay for a tag, and occasionally get lucky and pay nothing, all sorts of possibilities open up. From a complexity/optimization budget perspective, I’d rather see that spent on a more general purpose concept: union types. The above code would look like this with union types (excuse the syntax):

Good point!  Tagged unions have a number of interesting tricks they can play for data structure layout and packing.

Adding a sentinel to a type with slack bits can be generalized slightly by adding another small type.
For example, the type double has about 50 slack bits, which are enough to code all other basic types, except long.
A sentinel can be viewed as a unit type (like void or null, of zero bits and one value).
A coproduct (union) of two types requires enough bits to represent all points of either type.
So if the larger type has enough unused code points to represent the smaller type, we win.
Otherwise we need an extra bit to manufacture more code points.

There are various proposals to do tagged unions in the JVM; see for example:
 http://mail.openjdk.java.net/pipermail/mlvm-dev/2012-July/004665.html (shrink long to 63 bits to introduce slack)
 http://hg.openjdk.java.net/mlvm/mlvm/hotspot/rev/0afdd88556bc (add new basictype)


— John