Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0005933OCamlOCaml backend (code generation)public2013-02-25 03:032013-09-03 17:20
Reportersliquister 
Assigned Togasche 
PrioritynormalSeverityminorReproducibilityalways
StatusresolvedResolutionfixed 
PlatformOSOS Version
Product Version4.00.1 
Target VersionFixed in Version 
Summary0005933: Linking is slow when there are functions with large arities
DescriptionA 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.
TagsNo tags attached.
Attached Filespatch file icon link.patch [^] (2,179 bytes) 2013-02-25 03:03 [Show Content]
? file icon a.ml [^] (4,944 bytes) 2013-02-25 03:04 [Show Content]
patch file icon link2.patch [^] (2,136 bytes) 2013-03-19 04:53 [Show Content]

- Relationships
related to 0004077acknowledged Specialisation des primitives 
child of 0005287closedxleroy optimization of partial applications 

-  Notes
(0008912)
jacques-henri.jourdan (manager)
2013-02-25 09:52

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.
(0008913)
gasche (developer)
2013-02-25 10:19

I see that the patch actually does two different thing:

1. the _app business
2. turning polymorphic compare into specialized int comparisons

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?
(0008915)
sliquister (reporter)
2013-02-25 15:07

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.
The impact of the specialization should be less noticeable if the rest of the patch is applied though.
(0008924)
xleroy (administrator)
2013-02-25 19:45

I guess this is a consequence of the change proposed first in PR#5287. I agree we must avoid code size quadratic in the arity of a curried function, at all costs.
(0008992)
sliquister (reporter)
2013-03-19 04:55

Turns out the previous patch was not quite right.
I attached a better one which mirrors the patch that introduced the _app functions in the first place: in the few places where the initial
patch added 'if some condition then apply optimization else do normal stuff', it now becomes 'if same condition and arity is not too big then ... else ...'.
I checked that when the optimization is always deactivated (max_optimized_arity = 0), the compiler bootstraps (instead of segfaulting with my first patch).
(0008993)
gasche (developer)
2013-03-19 08:18

I reviewed this later patch and trust it is correct. I applied it in the SVN trunk.

- Issue History
Date Modified Username Field Change
2013-02-25 03:03 sliquister New Issue
2013-02-25 03:03 sliquister File Added: link.patch
2013-02-25 03:04 sliquister File Added: a.ml
2013-02-25 09:52 jacques-henri.jourdan Note Added: 0008912
2013-02-25 10:19 gasche Note Added: 0008913
2013-02-25 15:07 sliquister Note Added: 0008915
2013-02-25 19:43 xleroy Relationship added child of 0005287
2013-02-25 19:45 xleroy Note Added: 0008924
2013-02-25 19:45 xleroy Status new => acknowledged
2013-03-19 04:53 sliquister File Added: link2.patch
2013-03-19 04:55 sliquister Note Added: 0008992
2013-03-19 08:18 gasche Note Added: 0008993
2013-03-19 08:22 gasche Status acknowledged => resolved
2013-03-19 08:22 gasche Resolution open => fixed
2013-03-19 08:22 gasche Assigned To => gasche
2013-09-03 17:20 doligez Relationship added related to 0004077


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker