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

[Timo Kinnunen]

Yes, now that you mention, being able to type-specialize over value types and void to do something like this is going to be really nice:

	// In a Map<T, U> kind of API:
	// …
	<R=U, R=void, T=K> // all of these are true, just not simultaneously
	public R get(K key) {
		int at = index(key);
		if(at == -1) return void;
		return table[at+1];
	}

	// In a caller:
	Map<long, long> longMap = //…
	<L> L value = longMap.get(key);
	if(<L=void>) {
		return NOT_FOUND;    // value is not even in scope here
	}                                                      // implicit else block with L is long starting from here
	value += 1;                                    // no need for unboxing
	longMap.put(key, value);          // no trace of void either
	// etc..
	


This is lot cooler than having nullable boxes of values and using them just return a null, and unlike null a void can’t ever be forgotten about and not get checked.



Sent from Mail for Windows 10



From: John Rose
Sent: Friday, November 20, 2015 00:48
To: Rezaei, Mohammad A.
Cc: valhalla-dev at openjdk.java.net
Subject: Re: Sentinels in collections, was RE: Primitive Queueconsiderations


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