Performance issue with switches on reified types

[Renato Athaydes]

I have been profiling my Ceylon code on Java 8's Flight Recorder and was surprised to find out that my switches on generic types seem to take up a lot of the JVM's time!

50% of my code's time was spent on this.

Here's a call tree from Flight recorder (starting from my code's method):

Stack Trace    Sample Count    Percentage(%)
com.athaydes.parcey.combinator.seq_$1anonymous_0_.doParse$canonical$(Iterator, Sequence, String)    291    54.699
  com.redhat.ceylon.compiler.java.Util.isReified(Object, TypeDescriptor)    117    21.992
    com.redhat.ceylon.compiler.java.runtime.metamodel.Metamodel.isReified(Object, TypeDescriptor)    117    21.992
      com.redhat.ceylon.compiler.typechecker.model.ProducedType.isSubtypeOf(ProducedType)    109    20.489
        com.redhat.ceylon.compiler.typechecker.model.ProducedType.isSubtypeOfInternal(ProducedType)    108    20.301
          com.redhat.ceylon.compiler.typechecker.model.ProducedType.getSupertypeInternal(TypeDeclaration)    56    10.526
            com.redhat.ceylon.compiler.typechecker.context.ProducedTypeCache.get(ProducedType, TypeDeclaration)    21    3.947
              java.util.concurrent.ConcurrentHashMap.get(Object)    21    3.947
                com.redhat.ceylon.compiler.typechecker.model.ProducedType.equals(Object)    20    3.759
                  com.redhat.ceylon.compiler.typechecker.model.ProducedType.equals(Object)    8    1.504
                    java.util.HashMap.get(Object)    4    0.752
                      java.util.HashMap.hash(Object)    3    0.564
                        com.redhat.ceylon.compiler.typechecker.model.Declaration.hashCode()    3    0.564
                          com.redhat.ceylon.compiler.typechecker.model.Declaration.hashCode()    3    0.564

This is really strange because my code is a parser library and I expected the most time to be spent parsing, not type checking.

Here's what the guilty code looks like:

    for (parser in parsers) {
            value current = parser.doParse(effectiveInput,
                locationAfterParsing(result.consumed, parsedLocation));
            switch (current) // I BELIEVE HERE'S THE PERFORMANCE ISSUE
            case (is ParseError) {
                value consumed = result.consumed.chain(current.consumed);
                return parseError("Expected ``delegateName else parser.name`` but found '``String(current.consumed)``'",
                    consumed, parsedLocation);
            }
            case (is ParseResult<{Item*}>) {
                if (!current.overConsumed.empty) {
                    effectiveInput = chain(current.overConsumed, effectiveInput);
                }
                result = append(result, current, false);
            }
        }

I cannot confirm it's the switch which is taking up too much time, but it seems so from the call tree, right? Unfortunately I cannot see which line of the method is responsible for calling the isReified method, so I assume it is the switch.

Anyway, this has to run much faster for my library to be great :)

Any hints on how to make this code run faster (assuming the switch is the bottleneck, or otherwise pointing out where I should look instead)?

[Renato Athaydes]

I posted only one of the branches of the function call which takes nearly 55% of the JVM's time.
However, the other branch (slightly less significant than the one posted) also goes down to Util.isReified, where this call alone takes another 12.97% of the total time.

This has become the bottleneck after I optimized out other thing in my own code which were making the code slow. But I hope there's a way to make switches in Ceylon faster... otherwise I will have to find a different way  to do this that does not use types like this. Unfortunately.

[John Vasileff]

Renato,

switch (c = current of ParseError | ParseResult<{Item*}>)

case (is ParseError) {}

case (is ParseResult<Anything>) {}

might fix the problem assuming ParseResult is covariant. This or something like it can often be used to eliminate `isReified` calls in favor of `instanceof` checks.

John

--
You received this message because you are subscribed to the Google Groups "ceylon-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ceylon-users...@googlegroups.com.
To post to this group, send email to ceylon...@googlegroups.com.
Visit this group at http://groups.google.com/group/ceylon-users.
To view this discussion on the web visit https://groups.google.com/d/msgid/ceylon-users/5a057c6d-d7d8-46c5-af81-5adbdabc785d%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Renato Athaydes]

I've tried with the modified code and the performance did not change noticeably....

The method calls seem to still go down to Util.isReified.

Stack Trace    Sample Count    Percentage(%)

com.redhat.ceylon.compiler.java.Util.isReified(Object, TypeDescriptor)    57    20.652

Maybe I need a clean build.... will try again tomorrow.

[Tom Bentley]

Hi Renato,

John basically has it right; it's almost certain that the case (is ParseResult<{Item*}>)is the culprit. When the type you test against in an `is` test has type arguments we usually have to invoke Util.isReified() to use the reified type information to determine whether the instance is a subtype. That's a lot slower than a JVM-level instanceof, and there's not much we can do about that (apart from come up with better algorithms in the typechecker). This is the case for all uses of `is`: if, assert, case, while and the is operator.

The compiler tries a few tricks to avoid having to call Util.isReified() though:

Firstly, as John mentioned, when the type parameter is covariant and the type argument is Anything (or a supertype of the type parameter's upper bound) we can safely just use instanceof. Similarly with contravariant and Nothing.

Secondly, isReified() calls are protected with a shortcircuit instanceof ("instance instanceof BaseType && Util.isReified(BaseType<Foo>, instance)") so in the case where instance is not BaseType we avoid the call to isReified().

Thirdly, in the specific case of switch we will reorder the cases so the ones which are the cheapest to evaluate are done first.

Sadly, a consequence of doing these things is it's just more surprising to the programmer when they hit Util.isReified() and notice how long it takes, when many (usually?) switches are fast.

If people can spot other optimizations we can make for switch we will consider them, just open an issue.

Getting back to your specific case Renato, if current has cases ParseResult<{Item*}>|ParseError you might find changing the slow case to an else has an effect.

Cheers,

Tom

--
You received this message because you are subscribed to the Google Groups "ceylon-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ceylon-users...@googlegroups.com.
To post to this group, send email to ceylon...@googlegroups.com.
Visit this group at http://groups.google.com/group/ceylon-users.

To view this discussion on the web visit https://groups.google.com/d/msgid/ceylon-users/97eb4f21-ddb5-4751-912a-8a684faada3f%40googlegroups.com.

[Gavin King]

Also, it's important to note that there are *often*, but not always,
ways to avoid a reified "is". For example, if I have a Box<Anything>,
and I want to get a String out of it, it's quicker to first get an
Anything from the Box, and then check that it's a String, than it is
to check that the Box is a Box<String> and then get the String out of
it.

> https://groups.google.com/d/msgid/ceylon-users/CAMd5Ysw7FkYs5SzGO7mPjviXgRJGRcQz_6-yJzWXeTjNVo9AfA%40mail.gmail.com.

>
> For more options, visit https://groups.google.com/d/optout.

--
Gavin King
ga...@ceylon-lang.org
http://profiles.google.com/gavin.king
http://ceylon-lang.org
http://hibernate.org
http://seamframework.org

[Renato Athaydes]

Thank you everyone for all the great input!

Thanks to that, I was able to get the parser to run somewhat faster. Parsing 45k values was taking 2.5 seconds, now it is taking 1.3 seconds consistently.

What I did, as per the recommendations, was use "else" in all switches where the type of the variable was a union of 2 types (so, I check for the non-generic type in a (case is), and let the generic case fall into the else).
This replacement, by the way, seems like an easy optimization for the compiler to make??

I also made the two types in the union final... just in case that helps the compiler figure things out.

Now there's no significant cost in the switches and I can work on a different bottleneck (on my own code)... hoping to get that time well under 1 second (using parseInteger and String.split to separate them first, parsing the same input takes just 130ms - of course that's not a generic parser, but still... a parser library needs to be fast!).

[Gavin King]

Great!

And yeah, please submit issues for cases you think can be optimized by
the backend.

> --
> You received this message because you are subscribed to the Google Groups
> "ceylon-users" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to ceylon-users...@googlegroups.com.
> To post to this group, send email to ceylon...@googlegroups.com.
> Visit this group at http://groups.google.com/group/ceylon-users.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/ceylon-users/0d371dba-8af6-42bc-af36-37db57ee9eaf%40googlegroups.com.

[Tom Bentley]

What I did, as per the recommendations, was use "else" in all switches where the type of the variable was a union of 2 types (so, I check for the non-generic type in a (case is), and let the generic case fall into the else).
This replacement, by the way, seems like an easy optimization for the compiler to make??

I thought you might say that. In §5.5.2 of the spec it says:

A switch is exhaustive if there are no literal values in its cases, and the union type formed by the types of the case conditions of the switch covers the switched type, as defined by §3.4.1 Coverage. If no else block is specified, the switch must be exhaustive.

Note: On the other hand, even if the switch is exhaustive, an else block may be specified, in order to allow a switch that accommodates additional cases without resulting in a compilation error.

...

If an else block is specified, then the switch variable or, if there is no inline variable declared by the switch, the value referred by the switch expression, will be treated by the compiler as having the type V~U inside the case block, where V is the switched type, and U is the union type formed by the types of the case conditions of the switch.

So in the worse performing situation of an exhaustive switch without an else the compiler effectively adds an `else` which will throw with a clear explanation. We throw because this switch was supposed to cover every possible case and hasn't (due to someone adding a case to an `of` clause of a switched type after the switch was compiled, for example). This is very safe but means we can end up evaluating every case of the switch, which in your situation is the cause of the slowness. Note because of things like definite initialization we really do need to cover the else situation.

On the other hand, in the better performing situation with some number of (non-exhaustive) cases and an explicit `else` you're basically trading a little of the safety for speed. If someone added an extra case to an `of` clause we could fall into the else block with a runtime type that was not a subtype of complement type the typechecker surmised for the else block. This will in general result in an ugly and much less understandable CCE.

It's not entirely clear to me that this behaviour is ideal, but nor is it obvious what better behaviour there should be. We could transform the else differently to avoid the CCE in the latter situation, but only with the perf cost of the former situation.

[Renato Athaydes]

I created an issue: https://github.com/ceylon/ceylon-spec/issues/1304

The speed improvement in my very simple example was quite dramatic, over 10x!

On the other hand, in the better performing situation with some number of (non-exhaustive) cases and an explicit `else` you're basically trading a little of the safety for speed. If someone added an extra case to an `of` clause we could fall into the else block with a runtime type that was not a subtype of complement type the typechecker surmised for the else block. This will in general result in an ugly and much less understandable CCE.

But in this case the optimisation is safe: the type of the variable is a union of two types... you can't add a case to the union without re-compiling the function itself in which the switch is in, so even though your concern is valid for enumerated types (especially coming from a different module which may be re-compiled separately), it does not seem to be the case here.... hope I didn't misunderstand something...

[Gavin King]

Well you have to consider what happens if a Java class subclasses a
Ceylon enumerated type, of if there is a change that breaks binary
compatibility, etc.

> --
> You received this message because you are subscribed to the Google Groups
> "ceylon-users" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to ceylon-users...@googlegroups.com.
> To post to this group, send email to ceylon...@googlegroups.com.
> Visit this group at http://groups.google.com/group/ceylon-users.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/ceylon-users/a1ba1fdf-191d-479a-842f-1f469b0c5698%40googlegroups.com.