----- Mail original ----- > De: "Brian Goetz" <brian.go...@oracle.com> > À: "Peter Levart" <peter.lev...@gmail.com>, "Remi Forax" <fo...@univ-mlv.fr> > Cc: "amber-spec-experts" <amber-spec-experts@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
