Compile-time type hierarchy information in pattern switch

[forax at univ-mlv.fr]

----- Mail original -----
> De: "Brian Goetz" <brian.goetz at oracle.com>
> À: "Peter Levart" <peter.levart at gmail.com>, "Remi Forax" <forax at univ-mlv.fr>
> Cc: "amber-spec-experts" <amber-spec-experts at openjdk.java.net>
> Envoyé: Vendredi 6 Avril 2018 14:48:50
> Objet: Re: Compile-time type hierarchy information in pattern switch

> This may be O(n), but its not really something I want to do when linking
> a call site...

I agree :)

Anyway, i've implemented the algorithm of Peter, fix a typo (i++ instead of i--) and add the fact that conceptually the supertype of an interface is java.lang.Object
  https://github.com/forax/exotic/blob/master/src/main/java/com.github.forax.exotic/com/github/forax/exotic/TypeSwitch.java#L96

I've also implemented a strategy that use if instanceof but it doesn't perform well, i suppose it's because with a real instanceof the VM gather a profile while with Class.isInstance(), it does not. It can be fixed by adding a special method handle combiner to java.lang.invoke.MethodHandles. That's said i may be wrong, it's perhaps something else.

TypeSwitchBenchMark.big_big_instanceof_cascade      avgt   15  367.409 ± 1.844  ns/op
TypeSwitchBenchMark.big_big_type_switch             avgt   15   52.238 ± 0.455  ns/op
TypeSwitchBenchMark.small_big_instanceof_cascade    avgt   15   34.940 ± 0.287  ns/op
TypeSwitchBenchMark.small_big_type_switch           avgt   15   52.204 ± 0.319  ns/op
TypeSwitchBenchMark.small_small_instanceof_cascade  avgt   15    7.320 ± 0.100  ns/op
TypeSwitchBenchMark.small_small_type_switch         avgt   15    6.122 ± 0.027  ns/op

The first big/small is for the number of cases, the second is for the number of classes seen at runtime, so small_big_type_switch means a small number of cases with a lot of runtime classes.

To summarize, if the number of classes seen at runtime is small, the type_switch wins (it uses if getClass), if there are a lot of cases, the type_switch wins (it uses ClassValue.get()) but if there are few cases and a lot of classes, the type_switch is behind :(

Rémi

> 
> On 4/6/2018 5:01 AM, Peter Levart wrote:
>>
>>
>> On 04/05/2018 11:20 PM, Peter Levart wrote:
>>>
>>>
>>> On 04/05/18 22:28, Remi Forax wrote:
>>>> the way to detect it is to use the DAG of the supertypes (lazily
>>>> constructed*), from the last to the first case, the idea is to
>>>> propagate the index of down to the super types, if during the
>>>> propagation, you find a supertype which is also a case and with an
>>>> index lower that the currently propagated, then it's a failure.
>>>>
>>>> Rémi
>>>>
>>>> * you do not have to actually create the DAG, just be able to
>>>> traverse it from the subtype to the supertypes.
>>>
>>> Yes, this idea is similar to mine. We just have to find a conflict
>>> between subtype relationships and compile time order of cases which
>>> could be viewed as forming implicit pair-by-pair relationships of
>>> consecutive cases. If there's a cycle, we have a conflict.
>>>
>>
>> And Remi's algorithm is of course the best implementation of this
>> search. Here's a variant that does not need an index, just a set of
>> types:
>>
>> start with an empty set S
>> for each case type T from the last case up to the first:
>>     if S contains T:
>>         bail out with error
>>     add T and all its supertypes to S
>>
>> The time complexity of this algorithm is O(n). It takes at most n * k
>> lookups into a (hash)set where k is an average number of supertypes of
>> a case type. Usually, when case types share common supertypes not
>> far-away, the algorithm can prune branches in type hierarchy already
>> visited. Implementation-wise, if the algorithm uses a HashMap, mapping
>> visited type to case type it was visited from (back to Remi's index of
>> case), it can also produce a meaningful diagnostic message, mentioning
>> precisely which two cases are in wrong order according to type hierarchy:
>>
>>     Class<?>[] caseTypes = ...;
>>     TypeVisitor visitor = new TypeVisitor();
>>     for (int i = caseTypes.length - 1; i >= 0; i++) {
>>         visitor.visitType(caseTypes[i]);
>>     }
>>
>>     class TypeVisitor extends HashMap<Class<?>, Class<?>> {
>>
>>         void visitType(Class<?> caseType) {
>>             Class<?> conflictingCaseType = putIfAbsent(caseType,
>> caseType);
>>             if (conflictingCaseType != null) {
>>                 throw new IllegalStateException(
>>                     "Case " + conflictingCaseType.getName() +
>>                     " matches a subtype of what case " +
>> caseType.getName() +
>>                     " matches but is located after it");
>>             }
>>             visitSupertypes(caseType, caseType);
>>         }
>>
>>         private void visitSupertypes(Class<?> type, Class<?> caseType) {
>>             Class<?> superclass = type.getSuperclass();
>>             if (superclass != null && putIfAbsent(superclass,
>> caseType) == null) {
>>                 visitSupertypes(superclass, caseType);
>>             }
>>             for (Class<?> superinterface : type.getInterfaces()) {
>>                 if (putIfAbsent(superinterface, caseType) == null) {
>>                     visitSupertypes(superinterface, caseType);
>>                 }
>>             }
>>         }
>>     }
>>
>>
>> Regards, Peter