0005933: Linking is slow when there are functions with large arities

Index: asmcomp/interf.ml =================================================================== --- asmcomp/interf.ml (révision 13293) +++ asmcomp/interf.ml (copie de travail) @@ -14,8 +14,14 @@ Annotate pseudoregs with interference lists and preference lists. *) module IntPairSet = - Set.Make(struct type t = int * int let compare = compare end) - + Set.Make(struct + type t = int * int + let compare ((a1, a2) : t) (b1, b2) = + match compare a1 b1 with + | 0 -> compare a2 b2 + | c -> c + end) + open Reg open Mach Index: asmcomp/cmmgen.ml =================================================================== --- asmcomp/cmmgen.ml (révision 13293) +++ asmcomp/cmmgen.ml (copie de travail) @@ -2313,10 +2313,12 @@ fun_fast = true; fun_dbg = Debuginfo.none } +let max_arity_optimized = 15 let rec intermediate_curry_functions arity num = if num = arity - 1 then [final_curry_function arity] else begin + let to_optimize = arity <= max_arity_optimized in let name1 = "caml_curry" ^ string_of_int arity in let name2 = if num = 0 then name1 else name1 ^ "_" ^ string_of_int num in let arg = Ident.create "arg" and clos = Ident.create "clos" in @@ -2329,7 +2331,7 @@ [alloc_closure_header 5; Cconst_symbol(name1 ^ "_" ^ string_of_int (num+1)); int_const (arity - num - 1); - Cconst_symbol(name1 ^ "_" ^ string_of_int (num+1) ^ "_app"); + Cconst_symbol(name1 ^ "_" ^ string_of_int (num+1) ^ (if to_optimize then "_app" else "")); Cvar arg; Cvar clos]) else Cop(Calloc, @@ -2339,7 +2341,7 @@ fun_fast = true; fun_dbg = Debuginfo.none } :: - (if arity - num > 2 then + (if to_optimize && arity - num > 2 then let rec iter i = if i <= arity then let arg = Ident.create (Printf.sprintf "arg%d" i) in @@ -2380,7 +2382,7 @@ module IntSet = Set.Make( struct type t = int - let compare = compare + let compare x y = compare (x : int) y end) let default_apply = IntSet.add 2 (IntSet.add 3 IntSet.empty)

Index: asmcomp/interf.ml =================================================================== --- asmcomp/interf.ml (révision 13293) +++ asmcomp/interf.ml (copie de travail) @@ -14,8 +14,14 @@ Annotate pseudoregs with interference lists and preference lists. *) module IntPairSet = - Set.Make(struct type t = int * int let compare = compare end) - + Set.Make(struct + type t = int * int + let compare ((a1, a2) : t) (b1, b2) = + match compare a1 b1 with + | 0 -> compare a2 b2 + | c -> c + end) + open Reg open Mach Index: asmcomp/cmmgen.ml =================================================================== --- asmcomp/cmmgen.ml (révision 13293) +++ asmcomp/cmmgen.ml (copie de travail) @@ -2283,6 +2283,7 @@ (app clos'.direct clos.vars[0] arg2 ... argN clos'))) *) +let max_arity_optimized = 15 let final_curry_function arity = let last_arg = Ident.create "arg" in let last_clos = Ident.create "clos" in @@ -2292,7 +2293,7 @@ get_field (Cvar clos) 2 :: args @ [Cvar last_arg; Cvar clos]) else - if n = arity - 1 then + if n = arity - 1 || arity > max_arity_optimized then begin let newclos = Ident.create "clos" in Clet(newclos, @@ -2324,7 +2325,7 @@ {fun_name = name2; fun_args = [arg, typ_addr; clos, typ_addr]; fun_body = - if arity - num > 2 then + if arity - num > 2 && arity <= max_arity_optimized then Cop(Calloc, [alloc_closure_header 5; Cconst_symbol(name1 ^ "_" ^ string_of_int (num+1)); @@ -2339,7 +2340,7 @@ fun_fast = true; fun_dbg = Debuginfo.none } :: - (if arity - num > 2 then + (if arity <= max_arity_optimized && arity - num > 2 then let rec iter i = if i <= arity then let arg = Ident.create (Printf.sprintf "arg%d" i) in @@ -2380,7 +2381,7 @@ module IntSet = Set.Make( struct type t = int - let compare = compare + let compare x y = compare (x : int) y end) let default_apply = IntSet.add 2 (IntSet.add 3 IntSet.empty)

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