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

Bad worst-case performance for pattern match compiler #1362

Closed
evancz opened this Issue May 3, 2016 · 7 comments

Comments

Projects
None yet
7 participants
@evancz
Member

evancz commented May 3, 2016

When you have large, complex pattern matches, it can trigger bad performance during the optimization phase. This issue is for organizing http://sscce.org/ that illustrate this problem:

The solution is known. If you suggest another example for some reason, please link it as a gist. We may delete your comment to keep this issue simple and clear.


Update: This is dramatically improved in the draft for 0.19. Read about that here.

@treeowl

This comment has been minimized.

Show comment
Hide comment
@treeowl

treeowl May 10, 2016

Where is the known solution? A non-invasive change that I suspect would likely improve matters substantially (although perhaps not enough) would be to switch from Map Int to IntMap.

treeowl commented May 10, 2016

Where is the known solution? A non-invasive change that I suspect would likely improve matters substantially (although perhaps not enough) would be to switch from Map Int to IntMap.

@gbaz

This comment has been minimized.

Show comment
Hide comment
@gbaz

gbaz May 14, 2016

So I skimmed the "When Do Match-Compilation Heuristics Matter" paper cited in the Optimizer source. It describes that the Small Branching Factor heuristic is unusably slow. Here it is used apparently as a tiebreaker when Small Defaults doesn't suffice. So -- if you have something where Small Defaults generates lots of ties, you will be tossed into the pessimal case and things will grind to a halt.

It seems to me that the Elm compiler should simply avoid heuristics, even as fallbacks, which have such terrible worst-case performance, as it makes the compiler unpredictable.

gbaz commented May 14, 2016

So I skimmed the "When Do Match-Compilation Heuristics Matter" paper cited in the Optimizer source. It describes that the Small Branching Factor heuristic is unusably slow. Here it is used apparently as a tiebreaker when Small Defaults doesn't suffice. So -- if you have something where Small Defaults generates lots of ties, you will be tossed into the pessimal case and things will grind to a halt.

It seems to me that the Elm compiler should simply avoid heuristics, even as fallbacks, which have such terrible worst-case performance, as it makes the compiler unpredictable.

@Ryan1729

This comment has been minimized.

Show comment
Hide comment
@Ryan1729

Ryan1729 Oct 30, 2016

If you change a flat pattern match to a series of nested pattern matches, the (0.17.1) compiler has a much easier time of it. Would having the compiler perform a pass to convert pattern matches of tuples into this form be a good way to address this problem?

Here's a faster to compile version of the month example linked above.

And here's a slow and a fast version of a different example.

Ryan1729 commented Oct 30, 2016

If you change a flat pattern match to a series of nested pattern matches, the (0.17.1) compiler has a much easier time of it. Would having the compiler perform a pass to convert pattern matches of tuples into this form be a good way to address this problem?

Here's a faster to compile version of the month example linked above.

And here's a slow and a fast version of a different example.

@pyladune

This comment has been minimized.

Show comment
Hide comment
@pyladune

pyladune Jan 29, 2017

Is there a simple to identify during compilaiton which part of the code creates such situation ? or at least file ?

pyladune commented Jan 29, 2017

Is there a simple to identify during compilaiton which part of the code creates such situation ? or at least file ?

@JoeyEremondi

This comment has been minimized.

Show comment
Hide comment
@JoeyEremondi

JoeyEremondi Jan 29, 2017

Contributor
Contributor

JoeyEremondi commented Jan 29, 2017

@cscalfani

This comment has been minimized.

Show comment
Hide comment
@cscalfani

cscalfani Mar 6, 2017

Here's an example of the bug in 0.18. Hopefully, this helps: https://gist.github.com/cscalfani/8c84015c4ce34a31c06776b67cd57ef1

cscalfani commented Mar 6, 2017

Here's an example of the bug in 0.18. Hopefully, this helps: https://gist.github.com/cscalfani/8c84015c4ce34a31c06776b67cd57ef1

@evancz

This comment has been minimized.

Show comment
Hide comment
@evancz

evancz Mar 10, 2017

Member

I fixed this. You can read about it some here. The faster version will be out with 0.19, so I'll close for now.

If any folks reading this issue see new ones pop up reporting the same thing, please refer them here or the elm-dev posts that follow up on that status report.

Member

evancz commented Mar 10, 2017

I fixed this. You can read about it some here. The faster version will be out with 0.19, so I'll close for now.

If any folks reading this issue see new ones pop up reporting the same thing, please refer them here or the elm-dev posts that follow up on that status report.

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