On Tue, 17 Jan 2023 15:55:40 GMT, Jan Lahoda <jlah...@openjdk.org> wrote:
>> The pattern matching switches are using a bootstrap method >> `SwitchBootstrap.typeSwitch` to implement the jumps in the switch. >> Basically, for a switch like: >> >> switch (obj) { >> case String s when s.isEmpty() -> {} >> case String s -> {} >> case CharSequence cs -> {} >> ... >> } >> >> >> this method will produce a MethodHandle that will be analyze the provided >> selector value (`obj` in the example), and will return the case index to >> which the switch should jump. This method also accepts a (re)start index for >> the search, which is used to handle guards. For example, if the >> `s.isEmpty()` guard in the above sample returns false, the matching is >> restarted on the next case. >> >> The current implementation is fairly slow, it basically goes through the >> labels in a loop. The proposal here is to replace that with a MethodHandle >> structure like this: >> >> obj == null ? -1 >> : switch (restartIndex) { >> case 0 -> obj instanceof String ? 0 : obj instanceof >> CharSequence ? 2 : ... ; >> case 1 -> obj instanceof String ? 1 : obj instanceof >> CharSequence ? 2 : ... ; >> case 2 -> obj instanceof CharSequence ? 2 : ... ; >> ... >> default -> <labels-count>; >> } >> >> >> This appear to run faster than the current implementation, using testcase >> similar to the one used for https://github.com/openjdk/jdk/pull/9746 , these >> are the results >> >> PatternsOptimizationTest.testLegacyIndyLongSwitch thrpt 25 1515989.562 >> ± 32047.918 ops/s >> PatternsOptimizationTest.testHandleIndyLongSwitch thrpt 25 2630707.585 >> ± 37202.210 ops/s >> >> PatternsOptimizationTest.testLegacyIndyShortSwitch thrpt 25 6789310.900 >> ± 61921.636 ops/s >> PatternsOptimizationTest.testHandleIndyShortSwitch thrpt 25 10771729.464 >> ± 69607.467 ops/s >> >> >> The "LegacyIndy" is the current implementation, "HandleIndy" is the one >> proposed here. The translation in javac used is the one from #9746 in all >> cases. > > Jan Lahoda has updated the pull request with a new target base due to a merge > or a rebase. The incremental webrev excludes the unrelated changes brought in > by the merge/rebase. The pull request contains four additional commits since > the last revision: > > - Adding comments > - Improving performance > - Merge branch 'master' into JDK-8291966 > - 8291966: SwitchBootstrap.typeSwitch could be faster src/java.base/share/classes/java/lang/runtime/SwitchBootstraps.java line 70: > 68: try { > 69: INSTANCEOF_CHECK = LOOKUP.findStatic(SwitchBootstraps.class, > "instanceofCheck", > 70: > MethodType.methodType(boolean.class, Object.class, Class.class)); I am tempted to have Suggestion: INSTANCEOF_CHECK = MethodHandles.permuteArguments(LOOKUP.findVirtual(Class.class, "isInstance", MethodType.methodType(boolean.class, Object.class)), MethodType.methodType(boolean.class, Object.class, Class.class), 1, 0); to reduce the implementation methods in SwitchBootstraps src/java.base/share/classes/java/lang/runtime/SwitchBootstraps.java line 75: > 73: OBJECT_EQ_CHECK = LOOKUP.findStatic(Objects.class, "equals", > 74: > MethodType.methodType(boolean.class, Object.class, Object.class)); > 75: NULL_CHECK = LOOKUP.findStatic(SwitchBootstraps.class, > "nullCheck", Suggestion: NULL_CHECK = LOOKUP.findStatic(Objects.class, "isNull", Can remove the `nullCheck` method. src/java.base/share/classes/java/lang/runtime/SwitchBootstraps.java line 79: > 77: IS_ZERO = LOOKUP.findStatic(SwitchBootstraps.class, "isZero", > 78: > MethodType.methodType(boolean.class, int.class)); > 79: ENUM_LOOKUP = LOOKUP.findStatic(SwitchBootstraps.class, > "enumLookup", Appears unused and should be removed. src/java.base/share/classes/java/lang/runtime/SwitchBootstraps.java line 175: > 173: MethodHandle def = > MethodHandles.dropArguments(MethodHandles.constant(int.class, labels.length), > 0, Object.class); > 174: MethodHandle[] testChains = new MethodHandle[labels.length]; > 175: List<Object> labelsList = new ArrayList<>(Arrays.asList(labels)); Suggestion: List<Object> labelsList = Arrays.asList(labels).reversed(); Requires you to update to latest JDK with the SequencedCollection patch; labels is already sanitized upon bootstrap method call, no need to copy again since you don't modify it src/java.base/share/classes/java/lang/runtime/SwitchBootstraps.java line 177: > 175: List<Object> labelsList = new ArrayList<>(Arrays.asList(labels)); > 176: > 177: Collections.reverse(labelsList); Suggestion: src/java.base/share/classes/java/lang/runtime/SwitchBootstraps.java line 321: > 319: if (constantsOnly) { > 320: long nonNullValues = Stream.of(labels).filter(l -> l != > null).count(); > 321: long distinctNonNullValues = Stream.of(labels).filter(l -> l > != null).distinct().count(); Suggestion: long nonNullValues = Stream.of(labels).filter(Objects::nonNull).count(); long distinctNonNullValues = Stream.of(labels).filter(Objects::nonNull).distinct().count(); src/java.base/share/classes/java/lang/runtime/SwitchBootstraps.java line 337: > 335: // }; > 336: //else return "createRepeatIndexSwitch(labels)" > 337: MethodHandle[] map = new > MethodHandle[enumClass.getEnumConstants().length]; Can use JavaLangAccess.getEnumConstantsShared() to get the shared array to avoid copying; same below in the for loop. ------------- PR Review Comment: https://git.openjdk.org/jdk/pull/9779#discussion_r1181294780 PR Review Comment: https://git.openjdk.org/jdk/pull/9779#discussion_r1181294053 PR Review Comment: https://git.openjdk.org/jdk/pull/9779#discussion_r1181294384 PR Review Comment: https://git.openjdk.org/jdk/pull/9779#discussion_r1181293988 PR Review Comment: https://git.openjdk.org/jdk/pull/9779#discussion_r1181293296 PR Review Comment: https://git.openjdk.org/jdk/pull/9779#discussion_r1181293602 PR Review Comment: https://git.openjdk.org/jdk/pull/9779#discussion_r1181278511