Performance: Flatten pass does a lot of redundant work on unions.

[jemc]

I'm working on a pure Pony type-safe implementation of the Pony AST trees, for eventual use in a Pony-compiler-in-Pony. I ended up with a lot of large type unions, and unacceptably high compile times (it was taking so long to compile that my first assumption was that it was stuck in an infinite type recursion).

Implementing the patch in #1560 reduced my compile times by about 23x, but it's still taking a significant amount of time, and most of this time is still spent in the flatten pass, flattening my type unions. I added some ast_print calls to flatten_union in flatten.c to print the before and after AST every time a union was flattened, so I could see what calls were going on.

Doing so, I found 181,811 flatten_union operations took place in the compile operation I was testing. Doing some post-processing on the data showed that there were only 277 unique calls. This means that roughly 1 out of 655 calls to flatten_union are performing the flattening operation on a union that we've already seen and flattened before. This translates to a ton of unnecessary work that could be avoided.

Strategies to pursue:

• Find ways to "centralize" union flattening, so that we flatten each union in exactly one place, and refer to the already flattened union.
• Find a way to cache the flatten_union operation based on the structure of the input (less ideal).

Note that other parts of flattening may be able to benefit from a similar optimization, but it's specifically union flattening that is severely affecting my compile time for this use case.

[jemc]

If anyone is curious about the code I'm compiling, here it is:

https://github.com/jemc/pony-ast/blob/85f3ad7ec1a9fd2154ff2b759098b1f19238cddc/static/ast.pony

Note that the code is generated, not hand-written. The definitions that it is generated from are here:

https://github.com/jemc/pony-ast/blob/85f3ad7ec1a9fd2154ff2b759098b1f19238cddc/static/gen/ast_defs.pony

This is based on the macro system used here in the ponyc repo in treecheckdef.h, to define the types of AST nodes, and the allowed types of those nodes' children. It translates rather readily into Pony types.

https://github.com/ponylang/ponyc/blob/a7babdf2/src/libponyc/ast/treecheckdef.h

[jemc]

The extra flattening seems to be due in large part to the way type aliases are eliminated in the names pass, just before the flatten pass.

That is, in the names pass, everywhere a type alias is seen, the alias reference is replaced with the definition being aliased. So, in the flatten pass, every single mention of a type alias is seen as a copy of the alias definition, so every single mention of a type alias referring to a union results in a flattening operation on that union. This leads to a lot of totally unnecessary work - every mention of the type significantly increases the work done in the flatten pass, even though the same work has already been done many times.

So, if I have a type alias named Foo defined as a union of 12 types:

type Foo is (X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 | X11 | X12)

then every single place I mention Foo in my program, it needs to flatten the same union again, in the flatten pass (and for a union of 12, each flatten for the overall union requires 11 total flatten operations).

If possible, I'd like to try to refactor so that union flattening occurs just before type aliases are replaced with the copy of their definitions, instead of just after. Perhaps the type alias substitution could occur as part of the flattening pass, just after structurally flattening the definition of the type alias.

I wanted to bring it up for discussion in case anyone (@sylvanc?) had thoughts or warnings about the ramifications of such a change.

[sylvanc]

I think the right change may be to eliminate both flattening and type alias substitution, and modify the typechecker to understand type aliases directly.

This would give:

1. Better error messages (the end user gets the type alias, rather than a substituted type)
2. The right framework for allowing recursive type aliases

The classic example of the latter is:

type JSON is (
  | None
  | Bool
  | F64
  | String
  | Array[JSON]
  | Map[String, JSON]

[SeanTAllen]

+1 to getting recursive type aliases in.

So +1 to anything that helps us get there.

[jemc]

@sylvanc - Just to be clear, which parts of flattening do we want to eliminate? Get rid of just union flattening? Get rid of union and intersection flattening? Get rid of the entire flatten pass?

Apart from that I'm not sure why getting rid of flattening entirely is desirable. It seems like just getting rid of type alias substitution is enough to accomplish both goals. That is, it would reduce unnecessary union flattening, and also allow for recursive type aliases. Of course getting rid of union flattening entirely would also reduce unnecessary union flattening, but it seems like it would make many places of code more complex, where every union type we have to deal with is nested N-1 levels deep (2 children each) instead of being a flat node with N children.

[jemc]

As discussed on the sync call, @sylvanc was referring to getting rid of union flattening, not the entire flatten pass.

Another alternative would be to keep the structural flattening of unions (going from a node with N-1 nested levels of children to a node with N children), but remove the is_subtype checks used to fold overlapping types into eachother. @sylvanc says this wouldn't affect correctness of the type system for unions, though would be erroneous if we also did it for intersections. This may or may not result in a net performance gain for some cases, because later stages will have to work on a greater number of union type members if there was folding for overlapping types that could have been done, though I suspect that having overlapping types in a union is rare enough in real world code that it wouldn't be a significant performance detriment.

However, we all agreed the best place to start would be to remove type alias substitution entirely, and reform downstream type system logic to understand and correctly handle type aliases as they come. As mentioned earlier, this would pave the way to allowing recursive type aliases, since they would no longer be eagerly dereferenced in the names pass.

[jemc]

I've opened PR #1723 to implement one of the improvements mentioned above:

keep the structural flattening of unions (going from a node with N-1 nested levels of children to a node with N children), but remove the is_subtype checks used to fold overlapping types into eachother.

However, instead of doing structural flattening in the flatten pass, this PR moves it to be done in the parser, so that union type nodes are flattened from the start.