Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0006826OCamltypingpublic2015-03-31 12:272017-03-24 15:36
Reporterfrisch 
Assigned Tofrisch 
PrioritynormalSeverityfeatureReproducibilityhave not tried
StatusresolvedResolutionfixed 
PlatformOSOS Version
Product Version 
Target VersionlaterFixed in Version4.06.0 +dev/beta1/beta2/rc1 
Summary0006826: Improve compile time of opens, esp. for local opens
DescriptionEvery time an "open" is type-checked, all items from the opened signature are added to the environment. This can become problematic esp. with local opens. Consider for instance:

 module A = struct
   let x1 = 1
   ...
   let xN = N
 end
 let x = A.(x1)
 ...
 let x = A.(xN)

Type-checking this with ocamlc.opt shows a clear quadratic behavior:

  N = 1000: 1.04s
  N = 2000: 4.54s
  N = 3000: 10.98s


I don't know how bad this is in practice, since people don't often have modules with so many elements, but this show that perhaps something could be improved.

This is not related to sub-modules, so I don't think that 0005916 is relevant here. I checked manually, and all the time in Env.open_signature is spent in computing newenv, not on computing the substituted signature sg. And even more specifically, most of the time is spent in Ident.add (and a non-negligible part of it in the string comparison between id.name and k.ident.name).

This could be improved in several ways:

 - Optimize Ident tables. For instance, using a different data structure (note: it seems that allowing a height difference of 2 as in Set/Map, and not 1 as currently, actually degrades performance) or a more optimized comparison function (either precomputing a hash of names for each ident, perhaps using hash-consing to assign globally unique int to each name). Or tweaking the datatype definition to reduce allocations (e.g. merging the first level of the 'a data record into 'a tbl). This should improve type-checking performance globally, not only for opens.

 - Memoize the transformation of included signatures into a env-like representation (with quick lookup), and use a version of Ident table with an efficient merge operation. Typically, one could keep the merge symbolically (meaning that each lookup might need to be dispatched to both arguments sequentially) and only materialize it after a given number of lookups aren't found in the left argument (this number would be related to the size of this argument). The idea being that there is usually a small number of lookups done in the environment resulting from a local open, and if the included signature is large enough, it's better not to actually merge the maps. (Actually, if the depth of nested opens is not too big, it might be relevant to never merge the maps.)
TagsNo tags attached.
Attached Filesdiff file icon optim_open_envs.diff [^] (8,843 bytes) 2015-03-31 15:49 [Show Content]
diff file icon optim_open_envs2.diff [^] (13,869 bytes) 2015-03-31 16:03 [Show Content]

- Relationships

-  Notes
(0013600)
frisch (developer)
2015-03-31 15:54
edited on: 2015-03-31 16:03

I've attached a quick POC to evaluate the idea of keeping a symbolic representation merged Env.t to type-check "open" constructs. This is mostly encapsulated in the EnvTbl module, which now has an optional "previous" field.

Results are as follow:

  N = 1000: 0.07s
  N = 2000: 0.13s
  N = 3000: 0.26s

This is very lightly tested, and doesn't support warnings on open statements (unused opens, shadowing) for now. Also, one should probably use this new representation only for local opens, not global ones (EDIT: done in the second version of the uploaded patch).

(0013602)
frisch (developer)
2015-03-31 16:44

I've done some other micro-benchmarks, and already doing 1000 local opens on a module of size 150 (which is not completely unrealistic even for hand-written code) gives a x10 speedup (0.23s -> 0.02s).
(0017695)
frisch (developer)
2017-03-24 15:36

https://github.com/ocaml/ocaml/pull/834 [^]

- Issue History
Date Modified Username Field Change
2015-03-31 12:27 frisch New Issue
2015-03-31 12:28 frisch Description Updated View Revisions
2015-03-31 15:49 frisch File Added: optim_open_envs.diff
2015-03-31 15:54 frisch Note Added: 0013600
2015-03-31 16:03 frisch File Added: optim_open_envs2.diff
2015-03-31 16:03 frisch Note Edited: 0013600 View Revisions
2015-03-31 16:44 frisch Note Added: 0013602
2015-04-07 20:53 doligez Status new => acknowledged
2015-04-07 20:53 doligez Target Version => 4.03.0+dev / +beta1
2015-12-03 13:35 frisch Target Version 4.03.0+dev / +beta1 => later
2017-02-23 16:45 doligez Category OCaml typing => typing
2017-03-07 14:38 shinwell Severity minor => feature
2017-03-24 15:36 frisch Note Added: 0017695
2017-03-24 15:36 frisch Status acknowledged => resolved
2017-03-24 15:36 frisch Fixed in Version => 4.06.0 +dev/beta1/beta2/rc1
2017-03-24 15:36 frisch Resolution open => fixed
2017-03-24 15:36 frisch Assigned To => frisch


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker