Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster [v3]
On Wed, 3 Apr 2024 16:17:57 GMT, ExE Boss wrote: >> Jan Lahoda has updated the pull request with a new target base due to a >> merge or a rebase. The pull request now contains six commits: >> >> - Reflecting review feedback. >> - Merge branch 'master' into JDK-8291966 >> - 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 389: > >> 387: } >> 388: } >> 389: return enumMap.map[value.ordinal()]; > > `enumMap.map` never gets set before this line. There's a bug filed for this already: https://bugs.openjdk.org/browse/JDK-8332522 @lahodaj explained that this broken code is part of an optimization which is never attempted (IIRC due to the bug you noted on line 327). JDK-833522 seem like a good place to continue this conversation..? - PR Review Comment: https://git.openjdk.org/jdk/pull/9779#discussion_r1649761928
Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster [v3]
On Mon, 29 May 2023 07:25:26 GMT, Jan Lahoda 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 -> ;
>> }
>>
>>
>> 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 pull request now contains six commits:
>
> - Reflecting review feedback.
> - Merge branch 'master' into JDK-8291966
> - Adding comments
> - Improving performance
> - Merge branch 'master' into JDK-8291966
> - 8291966: SwitchBootstrap.typeSwitch could be faster
Changes requested by exe-b...@github.com (no known OpenJDK username).
src/java.base/share/classes/java/lang/runtime/SwitchBootstraps.java line 327:
> 325:
> 326: MethodHandle target;
> 327: boolean constantsOnly = Stream.of(labels).allMatch(l ->
> enumClass.isAssignableFrom(EnumDesc.class));
This expression is always false, it should be:
Suggestion:
boolean constantsOnly = Stream.of(labels).allMatch(l ->
l.isAssignableFrom(EnumDesc.class));
-
PR Review: https://git.openjdk.org/jdk/pull/9779#pullrequestreview-2133851725
PR Review Comment: https://git.openjdk.org/jdk/pull/9779#discussion_r1649740572
Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster [v3]
On Mon, 29 May 2023 07:25:26 GMT, Jan Lahoda 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 -> ;
>> }
>>
>>
>> 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 pull request now contains six commits:
>
> - Reflecting review feedback.
> - Merge branch 'master' into JDK-8291966
> - 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 340:
> 338:
>createRepeatIndexSwitch(lookup, labels),
> 339:
>MethodHandles.insertArguments(MAPPED_ENUM_LOOKUP, 1, lookup, enumClass,
> labels, new EnumMap(;
> 340: target = MethodHandles.permuteArguments(body,
> MethodType.methodType(int.class, Object.class, int.class), 1, 0);
This `guardWithTest` does the opposite to what’s described in the above comment.
src/java.base/share/classes/java/lang/runtime/SwitchBootstraps.java line 389:
> 387: }
> 388: }
> 389: return enumMap.map[value.ordinal()];
`enumMap.map` never gets set before this line.
-
PR Review Comment: https://git.openjdk.org/jdk/pull/9779#discussion_r1550058760
PR Review Comment: https://git.openjdk.org/jdk/pull/9779#discussion_r1550057327
Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster [v3]
On Wed, 31 May 2023 14:05:56 GMT, Jan Lahoda wrote:
>> Jan Lahoda has updated the pull request with a new target base due to a
>> merge or a rebase. The pull request now contains six commits:
>>
>> - Reflecting review feedback.
>> - Merge branch 'master' into JDK-8291966
>> - Adding comments
>> - Improving performance
>> - Merge branch 'master' into JDK-8291966
>> - 8291966: SwitchBootstrap.typeSwitch could be faster
>
> This patch is intended to eliminate some consecutive unnecessary tests like
> in case like:
>
> switch (o) {
> case Runnable r when ... -> {}
> case Runnable r when ... -> {}
> case Runnable r when ... -> {}
> case Object o -> {}
> }
>
>
> If `o` is not a `Runnable`, the `instanceof` will only happen for the first
> case, and the rest will be skipped, as these tests could not pass. But (as a
> current limitation), if it is not a consecutive run, the duplicate
> `instanceof` checks will still happen.
>
> I am quite sure there are ways to improve the bootstrap further, but might be
> better to have some (more) real-world examples to know what to optimize for.
@lahodaj
> This patch is intended to eliminate some consecutive unnecessary tests like
> in case like:
>
> ```java
> switch (o) {
> case Runnable r when ... -> {}
> case Runnable r when ... -> {}
> case Runnable r when ... -> {}
> case Object o -> {}
> }
> ```
I would expect that the above code would produce bytecode equivalent to:
loop: for (int _i = 0;;) {
switch (invokedynamic typeSwitch(o, _i) { Runnable.class, Object.class
}) {
case 0 /* Runnable */ -> {
_i++;
Runnable r = (Runnable) o;
if (...) {
break loop;
} else if (...) {
break loop;
} else if (...) {
break loop;
}
continue loop;
}
case 1 /* Object */ -> {
_i++;
break loop;
}
case -1 -> throw new NullPointerException();
default -> throw new MatchException();
}
}
-
PR Comment: https://git.openjdk.org/jdk/pull/9779#issuecomment-1577468813
Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster [v3]
On Mon, 29 May 2023 07:25:26 GMT, Jan Lahoda 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 -> ;
>> }
>>
>>
>> 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 pull request now contains six commits:
>
> - Reflecting review feedback.
> - Merge branch 'master' into JDK-8291966
> - Adding comments
> - Improving performance
> - Merge branch 'master' into JDK-8291966
> - 8291966: SwitchBootstrap.typeSwitch could be faster
This patch is intended to eliminate some consecutive unnecessary tests like in
case like:
switch (o) {
case Runnable r when ... -> {}
case Runnable r when ... -> {}
case Runnable r when ... -> {}
case Object o -> {}
}
If `o` is not a `Runnable`, the `instanceof` will only happen for the first
case, and the rest will be skipped, as these tests could not pass. But (as a
current limitation), if it is not a consecutive run, the duplicate `instanceof`
checks will still happen.
I am quite sure there are ways to improve the bootstrap further, but might be
better to have some (more) real-world examples to know what to optimize for.
-
PR Comment: https://git.openjdk.org/jdk/pull/9779#issuecomment-1570306708
Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster [v2]
On Tue, 30 May 2023 09:32:02 GMT, Jan Lahoda wrote: >> @forax >> >> Hi! Sorry for this sudden message, but this one captured my attention >> >>> and subtype checks are usually fast. >> >> And I hope this PR to be the right place to raise this. >> >> I was looking this PR to better understand how it applies to secondary >> supers and https://bugs.openjdk.org/browse/JDK-8180450 (that's still WIP) >> doesn't look like subtype checks are yet fast nor scalable (with multiple >> interfaces and > 1 receiver types observed) - see >> https://ionutbalosin.com/2023/03/jvm-performance-comparison-for-jdk-17/#typecheckscalabilitybenchmark >> that can be modified to use type switch too. >> >> In addition, at least for secondary types, a missed `IsInstance` (ie which >> type isn't implemented) can cost O(n) over the secondary supers types (see >> https://ionutbalosin.com/2023/03/jvm-performance-comparison-for-jdk-17/#typecheckslowpathbenchmark) >> that's still not ideal, due to the high bootstrapping cost of `prnz scas`. >> >> Hence, the implementation of type switch is likely to account for the >> existing (performance) deficiencies of the secondary supers type check or is >> relying on the fix https://bugs.openjdk.org/browse/JDK-8180450 that will >> appear at some point? >> >> Hope to have interacted in the right way with this with the JDK dev >> community, and thanks again for your hard work on this wonderful piece of >> engineering! > > @franz1981, thanks for your comment. I am afraid I don't know much about > JDK-8180450, but I suspect that it will affect the (type) switch lookup. > Please correct me if I am wrong, but it seems this patch is still an > improvement over the current state, and when JDK-8180450 is resolved, it > should automatically improve the type switch lookup as well. So, this patch > still seems useful to me, with a potential for future improvements, both > inside and outside type switch bootstrap itself. @lahodaj > So, this patch still seems useful to me, with a potential for future > improvements, both inside and outside type switch bootstrap itself. Yep, it is indeed still valuable: sorry if I didn't make it clear. My point is more related the need of the amount of type checks in some cases (reducing the impact of JDK-8180450); if a typecheck-like op is still required to route to some case (and which cost depends by many factors really), any target `checkcast` could be maybe saved. I'm currently unaware if the current state of this PR bring any improvement on this front too (or if is even possible), but this would be welcome regardless JDK-8180450 and much more if considering the mentioned issue too. This can be left for a follow-up PR too, obviously. I'm bringing the attention to this exactly because regardless JDK-8180450, secondary supers negative type check still have costs that would be awesome if could be addressed while exposing this feature to final users. - PR Comment: https://git.openjdk.org/jdk/pull/9779#issuecomment-1570214110
Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster [v2]
On Mon, 29 May 2023 07:33:36 GMT, Francesco Nigro wrote: >> Also there is a lot of use cases where the type switch is called only with >> instances of the same class, for those scenarii, the VM should be able to >> fully remove the type switch and inline the body of the corresponding case >> like this is done with a virtual call. >> >> I don't think there is a way currently to explain to the VM that the a hash >> map really acts as a cache so if the key is a constant then the value is a >> constant too (this optimization is also missing when JITing >> ClassValue.get()). > > @forax > > Hi! Sorry for this sudden message, but this one captured my attention > >> and subtype checks are usually fast. > > And I hope this PR to be the right place to raise this. > > I was looking this PR to better understand how it applies to secondary supers > and https://bugs.openjdk.org/browse/JDK-8180450 (that's still WIP) doesn't > look like subtype checks are yet fast nor scalable (with multiple interfaces > and > 1 receiver types observed) - see > https://ionutbalosin.com/2023/03/jvm-performance-comparison-for-jdk-17/#typecheckscalabilitybenchmark > that can be modified to use type switch too. > > In addition, at least for secondary types, a missed `IsInstance` (ie which > type isn't implemented) can cost O(n) over the secondary supers types (see > https://ionutbalosin.com/2023/03/jvm-performance-comparison-for-jdk-17/#typecheckslowpathbenchmark) > that's still not ideal, due to the high bootstrapping cost of `prnz scas`. > > Hence, the implementation of type switch is likely to account for the > existing (performance) deficiencies of the secondary supers type check or is > relying on the fix https://bugs.openjdk.org/browse/JDK-8180450 that will > appear at some point? > > Hope to have interacted in the right way with this with the JDK dev > community, and thanks again for your hard work on this wonderful piece of > engineering! @franz1981, thanks for your comment. I am afraid I don't know much about JDK-8180450, but I suspect that it will affect the (type) switch lookup. Please correct me if I am wrong, but it seems this patch is still an improvement over the current state, and when JDK-8180450 is resolved, it should automatically improve the type switch lookup as well. So, this patch still seems useful to me, with a potential for future improvements, both inside and outside type switch bootstrap itself. - PR Comment: https://git.openjdk.org/jdk/pull/9779#issuecomment-1568108121
Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster [v2]
On Tue, 2 May 2023 13:57:37 GMT, Rémi Forax wrote: >> 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 > > Also there is a lot of use cases where the type switch is called only with > instances of the same class, for those scenarii, the VM should be able to > fully remove the type switch and inline the body of the corresponding case > like this is done with a virtual call. > > I don't think there is a way currently to explain to the VM that the a hash > map really acts as a cache so if the key is a constant then the value is a > constant too (this optimization is also missing when JITing ClassValue.get()). @forax Hi! Sorry for this sudden message, but this one captured my attention > and subtype checks are usually fast. And I hope this PR to be the right place to raise this. I was looking this PR to better understand how it applies to secondary supers and https://bugs.openjdk.org/browse/JDK-8180450 (that's still WIP) doesn't look like subtype checks are yet fast nor scalable (with multiple interfaces and > 1 receiver types observed) - see https://ionutbalosin.com/2023/03/jvm-performance-comparison-for-jdk-17/#typecheckscalabilitybenchmark that can be modified to use type switch too. In addition, at least for secondary types, a missed `IsInstance` (ie which type isn't implemented) can cost O(n) over the secondary supers types (see https://ionutbalosin.com/2023/03/jvm-performance-comparison-for-jdk-17/#typecheckslowpathbenchmark) that's still not ideal, due to the high bootstrapping cost of `prnz scas`. Hence, the implementation of type switch is likely to account for the existing (performance) deficiencies of the secondary supers type check or is relying on the fix https://bugs.openjdk.org/browse/JDK-8180450 that will appear at some point? Hope to have interacted in the right way with this with the JDK dev community, and thanks again for your hard work on this wonderful piece of engineering! - PR Comment: https://git.openjdk.org/jdk/pull/9779#issuecomment-1566691245
Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster [v2]
On Tue, 17 Jan 2023 15:55:40 GMT, Jan Lahoda 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 -> ;
>> }
>>
>>
>> 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
I've merged with the current master, and tried to reflect the review feedback.
I tried to run a performance test:
[PatternsOptimizationTest.java.txt](https://github.com/openjdk/jdk/files/11589470/PatternsOptimizationTest.java.txt)
with these changes (the test uses a patch javac, and an current (old) version
of `SwitchBootstraps` - javac use the old bootstrap for classes that contain
`Legacy` in their name, new bootstrap in all other cases). The results when I
ran this were:
PatternsOptimizationTest.testHandleIndyLongSwitch thrpt 25 236.273 ±
49471.586 ops/s
PatternsOptimizationTest.testLegacyIndyLongSwitch thrpt 25 1341944.936 ±
163396.221 ops/s
PatternsOptimizationTest.testHandleIndyShortSwitch thrpt 25 9746865.005 ±
115379.432 ops/s
PatternsOptimizationTest.testLegacyIndyShortSwitch thrpt 25 5535534.370 ±
1275754.361 ops/s
So, this patch still seems to improve the state.
-
PR Comment: https://git.openjdk.org/jdk/pull/9779#issuecomment-1566682417
Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster [v3]
> 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 -> ;
> }
>
>
> 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 pull request now contains six commits:
- Reflecting review feedback.
- Merge branch 'master' into JDK-8291966
- Adding comments
- Improving performance
- Merge branch 'master' into JDK-8291966
- 8291966: SwitchBootstrap.typeSwitch could be faster
-
Changes: https://git.openjdk.org/jdk/pull/9779/files
Webrev: https://webrevs.openjdk.org/?repo=jdk=9779=02
Stats: 197 lines in 2 files changed: 110 ins; 15 del; 72 mod
Patch: https://git.openjdk.org/jdk/pull/9779.diff
Fetch: git fetch https://git.openjdk.org/jdk.git pull/9779/head:pull/9779
PR: https://git.openjdk.org/jdk/pull/9779
Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster [v2]
On Tue, 17 Jan 2023 15:55:40 GMT, Jan Lahoda 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 -> ;
>> }
>>
>>
>> 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
FWIW, @liach, thanks for the comments. I've decided to wait for PR #13074 to be
done. After that, I'll update this patch to it, and reflect your comments.
Thanks!
-
PR Comment: https://git.openjdk.org/jdk/pull/9779#issuecomment-1554878491
Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster [v2]
On Tue, 17 Jan 2023 15:55:40 GMT, Jan Lahoda 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 -> ;
>> }
>>
>>
>> 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
I did several experiments with generated lookupswitch over class hashes (for
final and sealed class labels only).
My experiments and benchmark results are actually showing following facts:
- traversal expanded to tableswitch (as proposed here) is significantly faster
than circulating over an array
- expanded lookupswitch over class hashes is unfortunately slower than this
proposal, even when benchmarked on large switches containing final or sealed
class labels only
-
Marked as reviewed by asotona (Reviewer).
PR Review: https://git.openjdk.org/jdk/pull/9779#pullrequestreview-1424836407
Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster [v2]
On Tue, 17 Jan 2023 15:55:40 GMT, Jan Lahoda 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 -> ;
>> }
>>
>>
>> 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
Also there is a lot of use cases where the type switch is called only with
instances of the same class, for those scenarii, the VM should be able to fully
remove the type switch and inline the body of the corresponding case like this
is done with a virtual call.
I don't think there is a way currently to explain to the VM that the a hash map
really acts as a cache so if the key is a constant then the value is a constant
too (this optimization is also missing when JITing ClassValue.get()).
-
PR Comment: https://git.openjdk.org/jdk/pull/9779#issuecomment-1531526385
Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster [v2]
On Fri, 28 Apr 2023 19:30:43 GMT, Neal Gafter wrote: > Building a map or hash table will be faster than sequential search. I agree it there will be usecases (and maybe even a majority of usecases) where using some kind of hash-based structure would work better than this patch. However, as Remi points out: - we cannot generally create a hash map just from the labels, as the inputs may be arbitrary subtypes of the label types. This means the hash-based structure would be (in a sense) a cache - the queries may be (massively) concurrent - the hash-based structure should not prevent class unloading (as the input classes may generally originate in arbitrary ClassLoaders) And while a lot of this may not be an issue for a majority of usecases, there must be some support for the minority usecases. There may be also be a subset of the usecases where VM's ability to see through the code an optimize it would have more impact than having clever code that's more difficult to understand. This may need much more testing to see if it is possible to distinguish these various cases. The current proposal improves the performance, but does not preclude improvements in the future - this is a runtime part, which we can adjust over time, as needed. - PR Comment: https://git.openjdk.org/jdk/pull/9779#issuecomment-1531339312
Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster [v2]
On Tue, 17 Jan 2023 15:55:40 GMT, Jan Lahoda 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 -> ;
>> }
>>
>>
>> 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 labelsList = new ArrayList<>(Arrays.asList(labels));
Suggestion:
List 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 labelsList = new ArrayList<>(Arrays.asList(labels));
> 176:
> 177:
Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster [v2]
On Tue, 17 Jan 2023 15:55:40 GMT, Jan Lahoda 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 -> ;
>> }
>>
>>
>> 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
Sequential search can be faster, the array length is known by the JIT so the
loop can be unrolled and subtype checks are usually fast.
A hash table is more complex to build because it needs to store the actual
classes of the objects switched upon (those classes may not have been loaded
yet), so it's a data structure that need to be dynamically updated by several
threads. While it's possible to write this kind of data structures, it will
require quite a lot of engineering to get it right.
So yes, it's planned.
-
PR Comment: https://git.openjdk.org/jdk/pull/9779#issuecomment-1529136366
Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster [v2]
On Tue, 17 Jan 2023 15:55:40 GMT, Jan Lahoda 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 -> ;
>> }
>>
>>
>> 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
Building a map or hash table will be faster than sequential search.
-
PR Comment: https://git.openjdk.org/jdk/pull/9779#issuecomment-1528000461
Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster [v2]
> 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 -> ;
> }
>
>
> 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
-
Changes:
- all: https://git.openjdk.org/jdk/pull/9779/files
- new: https://git.openjdk.org/jdk/pull/9779/files/a7052742..004e63d6
Webrevs:
- full: https://webrevs.openjdk.org/?repo=jdk=9779=01
- incr: https://webrevs.openjdk.org/?repo=jdk=9779=00-01
Stats: 592268 lines in 7950 files changed: 296207 ins; 212001 del; 84060 mod
Patch: https://git.openjdk.org/jdk/pull/9779.diff
Fetch: git fetch https://git.openjdk.org/jdk pull/9779/head:pull/9779
PR: https://git.openjdk.org/jdk/pull/9779
Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster
On Fri, 5 Aug 2022 16:12:08 GMT, Jan Lahoda 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 -> ;
> }
>
>
> 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.
src/java.base/share/classes/java/lang/runtime/SwitchBootstraps.java line 140:
> 138: Stream.of(labels).forEach(SwitchBootstraps::verifyLabel);
> 139:
> 140: MethodHandle target = createMethodHandleSwitch(labels);
let's remove redundant space before `=`
-
PR: https://git.openjdk.org/jdk/pull/9779
Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster
On Tue, 9 Aug 2022 10:28:02 GMT, Jan Lahoda wrote:
> > Would it be possible to add a special case where the labels are all the
> > same type? Like all labels are Class.class or Object.class? While testing
> > out the pattern matching, I've found myself doing the following
> > ```java
> > switch (o) {
> > case Class c when c == Object.class -> {}
> > case Class c when c == Integer.class -> {}
> > case Class c when c == String.class -> {}
> > case Class c when c == Double.class -> {}
> > // ...
> > }
> > ```
>
> I think that there may eventually be some improvements, although the current
> round of patches is not intended to improve this pattern, sorry. Also, I
> would not expect better behavior that a sequence of ifs.
If it eventually gets the same speed as a sequence of ifs, it would be great
for me. Right now it is much slower. However, do you think it would be good to
track this pattern or should the javac simplify the code generation to not use
`SwitchBootstrap.typeSwitch` in this case?
-
PR: https://git.openjdk.org/jdk/pull/9779
Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster
On Fri, 5 Aug 2022 16:12:08 GMT, Jan Lahoda 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 -> ;
> }
>
>
> 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.
> Would it be possible to add a special case where the labels are all the same
> type? Like all labels are Class.class or Object.class? While testing out the
> pattern matching, I've found myself doing the following
>
> ```java
> switch (o) {
> case Class c when c == Object.class -> {}
> case Class c when c == Integer.class -> {}
> case Class c when c == String.class -> {}
> case Class c when c == Double.class -> {}
> // ...
> }
> ```
I think that there may eventually be some improvements, although the current
round of patches is not intended to improve this pattern, sorry. Also, I would
not expect better behavior that a sequence of ifs.
-
PR: https://git.openjdk.org/jdk/pull/9779
Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster
- Original Message - > From: "Jan Lahoda" > To: "core-libs-dev" > Sent: Friday, August 5, 2022 11:03:06 PM > Subject: Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster > On Fri, 5 Aug 2022 20:20:56 GMT, Remi Forax wrote: > >> You only need restart index at the beginning and after a when, so in your >> example, only 0 and 1 are required, you can skip the generation of 2 because >> you will never restart at 2. >> > > The bootstrap protocol does not specify which cases have guards, so I don't > think the bootstrap cannot do such a decision. ahh, double negation :) the bootstrap protocol can be updated as it please you no ? Rémi
Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster
On Fri, 5 Aug 2022 16:12:08 GMT, Jan Lahoda 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 -> ;
> }
>
>
> 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.
Would it be possible to add a special case where the labels are all the same
type? Like all labels are Class.class or Object.class?
While testing out the pattern matching, I've found myself doing the following
switch (o) {
case Class c when c == Object.class -> {}
case Class c when c == Integer.class -> {}
case Class c when c == String.class -> {}
case Class c when c == Double.class -> {}
// ...
}
-
PR: https://git.openjdk.org/jdk/pull/9779
Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster
On Fri, 5 Aug 2022 20:20:56 GMT, Remi Forax wrote: > You only need restart index at the beginning and after a when, so in your > example, only 0 and 1 are required, you can skip the generation of 2 because > you will never restart at 2. > The bootstrap protocol does not specify which cases have guards, so I don't think the bootstrap cannot do such a decision. > If you start to see the typeswitch as a bunch of method handles, i wonder if > it's not better to lift any when expressions as a static methods (exactly > like a lambda body) and then send them as constant method handles to the type > switch so you do not need a restart index. > The issue with guards is that they can not only capture, but also produce new bindings. Like: case Box b when b.o() instanceof String component -> System.err.println(component); This really makes modeling this at runtime notably more difficult than lambdas. There were multiple experiments with this, and the runtime API and the handles are not really easy to understand. Jan > Anyway, i agree that it's a better translation than the existing one. > > I think that in the end game, we will go to the same route as with the lambda > proxy, the whole pattern matching with the when expressions as constant > method handles will be send to one bootstrap method that will create an > intermediary decision tree, generate the corresponding bytecode (using the > classfile API) and load it as a hidden class. This provides a clean API > separation between the compiler and the runtime that knows how to optimize > pattern matching query. > > R?mi - PR: https://git.openjdk.org/jdk/pull/9779
Re: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster
- Original Message -
> From: "Jan Lahoda"
> To: "core-libs-dev"
> Sent: Friday, August 5, 2022 6:22:48 PM
> Subject: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster
> 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 -> ;
>}
You only need restart index at the beginning and after a when, so in your
example, only 0 and 1 are required, you can skip the generation of 2 because
you will never restart at 2.
If you start to see the typeswitch as a bunch of method handles, i wonder if
it's not better to lift any when expressions as a static methods (exactly like
a lambda body) and then send them as constant method handles to the type switch
so you do not need a restart index.
Anyway, i agree that it's a better translation than the existing one.
I think that in the end game, we will go to the same route as with the lambda
proxy, the whole pattern matching with the when expressions as constant method
handles will be send to one bootstrap method that will create an intermediary
decision tree, generate the corresponding bytecode (using the classfile API)
and load it as a hidden class. This provides a clean API separation between the
compiler and the runtime that knows how to optimize pattern matching query.
Rémi
