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

John Rose john.r.rose at
Thu Nov 19 23:48:18 UTC 2015

On Nov 19, 2015, at 7:19 AM, Rezaei, Mohammad A. <Mohammad.Rezaei at> 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: (shrink long to 63 bits to introduce slack) (add new basictype)

— John

More information about the valhalla-dev mailing list