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

Performance bottleneck in parmatch.ml #6883

Closed
vicuna opened this issue May 29, 2015 · 4 comments
Closed

Performance bottleneck in parmatch.ml #6883

vicuna opened this issue May 29, 2015 · 4 comments
Milestone

Comments

@vicuna
Copy link

vicuna commented May 29, 2015

Original bug ID: 6883
Reporter: dwight.guth
Status: closed (set by @xavierleroy on 2017-02-16T14:16:43Z)
Resolution: fixed
Priority: normal
Severity: major
OS: Ubuntu
OS Version: 14.04
Version: 4.02.1
Target version: 4.03.0+dev / +beta1
Fixed in version: 4.03.0+dev / +beta1
Category: typing
Monitored by: @gasche

Bug description

I am currently working on creating code which automatically generates OCAML code. The automatically generated code contains a large number of quite complex match clauses in a single match statement, and when I scale my input data up to the full size that I intend, it takes over an hour for ocamlopt to run, which is unacceptable if I am going to be doing iterative development on my code generation process. I can make some progress by using smaller input sets, but even these take significant time to compile.

To evaluate this, I have taken the attached file, which represents a representative example of the code I am generating, for a relatively small data set, and profiled its execution by compiling ocamlopt.opt with the ocamlopt -p flag. The resulting data set reported two major bottlenecks: the first, a call to compare_val in simple_match and le_pat, was relatively easy to fix and I can provide a patch for this if you are interested.

The second bottleneck, however, I have not been able to figure out how to resolve. Namely, even after removing the poor-performance calls to compare_val, calls to le_pat account for over 90% of the total time of compilation. This is spread across the self-time of filter_one, simple_match, le_pat, le_pats, and satisfiable.

I was hoping someone with more familiarity with the code could use my example to reproduce the issue and either provide a faster implementation of these functions, or else determine if it is possible to provide an option to ocamlopt which bypasses some of this functionality in favor of a less-well-optimized code generation. The time spent in this portion of the compilation is prohibitive for me and significantly impairs my ability to develop in a timely fashion.

Steps to reproduce

Run ocamlopt.opt -c def.ml on the attached file, and observe the significant compilation time involved.

File attachments

@vicuna
Copy link
Author

vicuna commented Jun 1, 2015

Comment author: @maranget

Hi,

I have tried to reproduce the misbehaviour under trunk. The issue
has apparently disappeared, as compilation of def.ml takes about 50sec
with 4.02.1 and less then 2 seconds with trunk.

The issue is not related to standard usage of PM diagnostics, as disabling
the warnings (-w A) does not change compilation time significantly.
I suspect GADT or polymorphic variant typing...

--Luc

@vicuna
Copy link
Author

vicuna commented Nov 20, 2015

Comment author: @xavierleroy

Can someone please re-check whether the problem is still there with the current OCaml trunk? Especially when J. Garrigue's "path compression" code is in (#294), as it can speed up type-checking dramatically.

@vicuna
Copy link
Author

vicuna commented Nov 20, 2015

Comment author: @gasche

I re-tested with trunk and trunk+path-compression, and they both run in slightly more than 2 seconds on my machine. I don't know if the original issue was path-compression-related, but it has disappeared from trunk.

@vicuna
Copy link
Author

vicuna commented Nov 21, 2015

Comment author: @xavierleroy

Marking this PR as resolved in 4.03.

@vicuna vicuna closed this as completed Feb 16, 2017
@vicuna vicuna added the typing label Mar 14, 2019
@vicuna vicuna added this to the 4.03.0 milestone Mar 14, 2019
@vicuna vicuna added the bug label Mar 20, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant