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
Linking is slow when there are functions with large arities #5933
Comments
Comment author: @jhjourdan This issue appeared quite recently in the OCaml compiler (4.0 or so). It is interesting to avoid quadratic behavior with respect to arities in the case of Coq extracted code : it is not rare to have inductive types with dozens of constructors, and the induction predicates for those types have a big arity. |
Comment author: @gasche I see that the patch actually does two different thing:
The first change is subtle and needs careful review. The second seems easy to merge, provided there is evidence that it actually helps. Could you report changes in compilation times due only to the second change, on realistic programs? |
Comment author: @sliquister I don't remember measuring the second specialization by itself, but if I remember right, the first specialization made the linking of core and core_extended take 5s instead of 8.5s. |
Comment author: @xavierleroy I guess this is a consequence of the change proposed first in #5287. I agree we must avoid code size quadratic in the arity of a curried function, at all costs. |
Comment author: @sliquister Turns out the previous patch was not quite right. |
Comment author: @gasche I reviewed this later patch and trust it is correct. I applied it in the SVN trunk. |
Original bug ID: 5933
Reporter: @sliquister
Assigned to: @gasche
Status: closed (set by @xavierleroy on 2015-12-11T18:24:02Z)
Resolution: fixed
Priority: normal
Severity: minor
Version: 4.00.1
Category: back end (clambda to assembly)
Related to: #4077
Child of: #5287
Monitored by: @lefessan @hcarty
Bug description
A file containing only a function of arity 67 takes roughly 9s to link (see attached file, which also contains what I used to test). Most of the time is spent compiling the caml_curryX_Y_app functions.
I provide a patch that replaces the uses of caml_curryX_Y_app by caml_curryX_Y when the arity is higher than 15, because the optimization doesn't seem to too useful past this point. I am not familiar with this part of the compiler but I think the behaviour should be the same as before the "_app" functions were introduced. The patch also specializes a couple of Pervasives.compare that showed up during profiling.
On the function of arity 67, linking time goes from 8.5s to 0.2s.
On a real example (linking jane street's core and core_extended), the time goes from 8.5s to 1s.
File attachments
The text was updated successfully, but these errors were encountered: