Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Revert: Don't automatically virtualize two types in the same hierarchy, unless one is deeper than the other #6351

Merged
merged 1 commit into from Jul 9, 2018

Conversation

asterite
Copy link
Member

@asterite asterite commented Jul 7, 2018

Fixes #6349

Reverts 26635f1

To make it clear:

  • PR Don't automatically virtualize two types in the same hierarchy, unless one is deeper than the other #6024 was just an experiment. I expected compile time for the compiler to go to the roof with that change but that didn't happen.
  • However, it did happen for other projects, namely the one mentioned in Compiler crashes due to an invalid memory access #6349
  • The main problem is that with a big type hierarchy, say N types, all different union types inside that hierarchy is basically a combinatorial explosion (take any M from N where M <= N). The compiler potentially has to create all these different union types, and consider them for method overloads, dispatch, etc. In the given program this happened (a lot it seems), to the point where the compiler crashed
  • Reverting this change makes the above project compile again: "Semantic (main)" takes about 3.3 seconds with a non-release compiler. Total compilation time takes about 31 seconds, again with a non-release compiler (that is, I didn't pass --release when I compiled the compiler). EDIT: "Semantic (main)" takes about 1 second with a release compiler. And it's about 15K lines of code :-O

Not unifying types in the same hierarchy was something that I, and probably others, wanted, but it's simply not possible. That's the whole reason why we unified types in the first place: to avoid this combinatorial explosion of union types.

And remember, this is not that terrible: we've been doing just fine before 0.25.0 without this "feature", and without me trying to play with this it would never have happened, so... :-)

@asterite asterite force-pushed the feature/revert-dont-virtualize branch from fb4f380 to f343019 Compare July 7, 2018 18:08
Copy link
Contributor

@RX14 RX14 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Sad but, I guess necessary.

@ysbaddaden
Copy link
Contributor

I guess it's acceptable.

Given A, and B < A and C < A types, is a specific B | C union inferred as A with this revert? I believe this was the actual issue we had, right? Inferring Array(A) from [B.new, C.new] is fine, and usually what we want, but a specific [] of B | C could be nice, sometimes.

@RX14
Copy link
Contributor

RX14 commented Jul 9, 2018

@ysbaddaden B | C always becomes A. Tracking whether a union was "explicit" (.as) or "implicit" (result of multiple dispatch, an if, etc.) would be far too much complexity and make things very difficult. You either allow B | C and it gets everywhere through implicit semantics, or you always make it A and loose some expressive power.

@ysbaddaden
Copy link
Contributor

Sigh. Too bad then.

@asterite
Copy link
Member Author

asterite commented Jul 9, 2018

My personal use case for not merging unions and go to the parent type was having an instance variable with a union type. For example a TypeDeclaration node can only have a Var, InstanceVar or ClassVar as targets, but these get condensed to ASTNode, so when dealing with this we have to do "else raise bug".

I'm thinking whether we can make at least that case work, so when you explicitly define a type declaration like that it keeps it. It would be a special type of union that doesn't go to the parent type when merging it with other types. I'll have to play with this idea, not sure it can work or it's easy.

But then, maybe it'll be too confusing, because sometimes it will get merged, sometimes not, and it will be hard to track. So initially I'd like this to get merged, and then we can think alternative solutions.

Copy link
Contributor

@ysbaddaden ysbaddaden left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Let's revert and try to explore alternatives for explicit unions.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

3 participants