RFR: 8291966: SwitchBootstrap.typeSwitch could be faster [v2]
Chen Liang
liach at openjdk.org
Sun Apr 30 21:16:27 UTC 2023
On Tue, 17 Jan 2023 15:55:40 GMT, Jan Lahoda <jlahoda at 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
More information about the core-libs-dev
mailing list