Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0005546OCamlOCaml backend (code generation)public2012-03-20 10:372012-12-14 03:54
Reporterlefessan 
Assigned Tofrisch 
PrioritynormalSeverityfeatureReproducibilityalways
StatusresolvedResolutionfixed 
PlatformOSOS Version
Product Version4.00.0+dev 
Target Version4.00.2+devFixed in Version4.01.0+dev 
Summary0005546: moving a function into an internal module slows down its use
DescriptionToplevel functions and functions defined in submodules are compiled differently. The first ones can be accessed directly as globals (when their closure is static), whereas the later ones are never accessed directly (their closure always contains the environment, so is not static). As a consequence, moving a function from toplevel to a submodule can decrease performances dramatically.

This can be easily fixed by using the same compilation mode for toplevel functions and submodules values (see patch for trunk attached).
 
TagsNo tags attached.
Attached Filespatch file icon transl-store-flatten-modules-trunk.patch [^] (11,956 bytes) 2012-03-20 10:37 [Show Content]
patch file icon transl-store-flatten-modules-trunk-2.patch [^] (12,088 bytes) 2012-11-29 15:42 [Show Content]

- Relationships
related to 0005537resolvedfrisch reducing repeated indirections to access variables in nested modules 
related to 0004074acknowledged Patch for in-place compilation of structures 
related to 0005573resolvedfrisch Access to values in nested modules 

-  Notes
(0007109)
frisch (developer)
2012-03-20 10:48

My guess is that this patch (using "transl_store" compilation scheme also for sub-modules) has the potential of avoiding some bad cases with the register allocator (because it can reduce the dramatically the size of the interference graph). Did you observe such compile-time improvements?
(0007153)
frisch (developer)
2012-03-26 10:13
edited on: 2012-03-26 10:16

Ok, let's consider the following:

    let f1 x = x
    let f2 x = x
    ...
    let fN x = x


Compilation time (ocamlopt on trunk, with or without the patch; in seconds):

N=
 125           0.07
 250           0.10
 500           0.20
 1000          0.32
 2000          0.66
 4000          1.26
 8000          2.62


Now, let's consider the following variant:


  module X = struct
    let f1 x = x
    let f2 x = x
    ...
    let fN x = x
  end


Compilation time:

N=      without patch  with patch
 125           0.25           0.07
 250           0.89           0.10
 500          14.14           0.30
 1000         63.90           0.60
 2000        312.50           1.17
 4000           ...           2.45
 8000           ...           4.75


The patch avoids a quadratric behavior of ocamlopt. There is still a factor of 2 between the nested and non-nested version, which could be worth investigating.

(0007179)
frisch (developer)
2012-03-27 08:03
edited on: 2012-03-29 09:35

What about always using transl_store for compiling structures (and get rid of transl_module)? Even for inline functor arguments, local modules, etc. And also in bytecode. This would probably not improve runtime performances, but it simplifies the code (only one compilation scheme) and the life of the register allocator.

Fabrice: do you have benchmarks showing the runtime performance benefits of your patch?

(0007221)
frisch (developer)
2012-03-29 09:36

> What about always using transl_store for compiling structures

I knew I did such a patch, but I completely forgot I actually submitted it: 0004074. Note that even hand-written code benefits from the patch (cf compilation time for some Camlp4 module).
(0007633)
frisch (developer)
2012-07-04 18:47

This is an intrusive, potentially risky patch, which does not address a bug. I don't see any reason to delay 4.00 for it.
(0008292)
Boris Yakobowski (reporter)
2012-10-22 23:43

Does anyone have a version of this patch that applies cleanly to a recent OCaml? (My own merge efforts failed spectacularly...) I would like to see if the slowdown is visible on Frama-C's codebase.
(0008538)
Tom Hvitved (reporter)
2012-11-21 12:22

I have experienced this problem in practice, where compile time has increased from 1 minute to 5 minutes as the result of adding extra values to a module (the module contains approx. 2000 values, and it will continue to increase). This patch is therefore highly anticipated by me, and my colleagues.

Tom Hvitved
SimCorp A/S
(0008539)
ygrek (reporter)
2012-11-21 16:57

IIUC this issue concerns the runtime penalty, not compile time..
(0008540)
frisch (developer)
2012-11-21 17:53

> this issue concerns the runtime penalty, not compile time..

It addresses both, as the timings I posted on the second note shows.
(0008545)
frisch (developer)
2012-11-29 15:48
edited on: 2012-11-29 15:52

I've attached an updated version of the patch, compatible with the current trunk. My initial experiments confirm that the patch improves accesses to deeply nested functions (probably solving 0005537), but not to nested variables (0005573). To support this, we probably need to do something similar to the patch I proposed in 0004074. Moreover, this patch does not apply to internal structured (local module, functor body), so the example given in 0004074 is not fixed.

(0008546)
frisch (developer)
2012-11-29 18:27

I've tested the impact of this patch on our global unit test suite. I cannot observe any noticeable impact on runtime. That said, memory consumption is reduced for many tests (typically a 3% gain on the number of allocated bytes for many tests). I don't immediately understand the reason. Since each test is relatively short-lived (and runs in a stand-alone process), this reduced pressure on the GC does not translate into observable runtime improvements. Maybe with a long running application, this would be more visible.
(0008547)
frisch (developer)
2012-11-30 10:47

I also confirm that the patch fixes the performance issue for SimCorp reported by Tom.
(0008603)
frisch (developer)
2012-12-13 16:42

The patch as been pushed to the trunk (rev 13130).
(0008608)
hongboz (developer)
2012-12-14 03:54

I confirm that I also have a noticable speedup, previously comping a native version of camlp4 takes 30s, not it goes down to 20s. Thanks!

- Issue History
Date Modified Username Field Change
2012-03-20 10:37 lefessan New Issue
2012-03-20 10:37 lefessan File Added: transl-store-flatten-modules-trunk.patch
2012-03-20 10:44 gasche Relationship added related to 0005537
2012-03-20 10:48 frisch Note Added: 0007109
2012-03-26 10:13 frisch Note Added: 0007153
2012-03-26 10:15 frisch Note Edited: 0007153 View Revisions
2012-03-26 10:16 frisch Note Edited: 0007153 View Revisions
2012-03-26 10:16 frisch Note Edited: 0007153 View Revisions
2012-03-26 14:31 lefessan Status new => acknowledged
2012-03-27 08:03 frisch Note Added: 0007179
2012-03-29 09:29 frisch Relationship added related to 0004074
2012-03-29 09:35 frisch Note Edited: 0007179 View Revisions
2012-03-29 09:36 frisch Note Added: 0007221
2012-04-04 22:17 gasche Relationship added related to 0005573
2012-07-04 18:47 frisch Note Added: 0007633
2012-07-04 19:43 xleroy Target Version 4.00.0+dev =>
2012-07-06 16:15 doligez Target Version => 4.01.0+dev
2012-07-31 13:36 doligez Target Version 4.01.0+dev => 4.00.1+dev
2012-09-06 19:32 frisch Target Version 4.00.1+dev => 4.00.2+dev
2012-10-22 23:43 Boris Yakobowski Note Added: 0008292
2012-11-21 12:22 Tom Hvitved Note Added: 0008538
2012-11-21 16:57 ygrek Note Added: 0008539
2012-11-21 17:53 frisch Note Added: 0008540
2012-11-29 15:42 frisch File Added: transl-store-flatten-modules-trunk-2.patch
2012-11-29 15:48 frisch Note Added: 0008545
2012-11-29 15:52 frisch Note Edited: 0008545 View Revisions
2012-11-29 15:52 frisch Note Edited: 0008545 View Revisions
2012-11-29 18:27 frisch Note Added: 0008546
2012-11-30 10:47 frisch Note Added: 0008547
2012-12-13 16:42 frisch Note Added: 0008603
2012-12-13 17:07 frisch Status acknowledged => resolved
2012-12-13 17:07 frisch Fixed in Version => 4.01.0+dev
2012-12-13 17:07 frisch Resolution open => fixed
2012-12-13 17:07 frisch Assigned To => frisch
2012-12-14 03:54 hongboz Note Added: 0008608


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker