Typechecking module takes time quadratic in the number of submodules

Learning
1

I tried to compile some generated code the other day, where there was one large file Types.ml with 3700 independent modules inside, about 190k lines of code in that file. Compilation of files depending on Types.ml took about 30 seconds each. I separated Types.ml into 3700 files and the compilation time per file was much improved (from about 2 hours to 2 minutes). Is there a nonlinear increase in typechecking time, with the number of independent modules?

You can play with this yourself by looking at the compile times for the modules in the aws-ec2 package here.

2

I haven’t looked in detail at your setup, but if you have one enormous module then whenever you compile something that depends on it you have to load the whole cmi (and cmx for the native compiler) in memory. If you split it into small components, you only have to load the relevant components.

3

I thought about this but the cmi is around 7-8Mb. The physical size of the file, I think, cannot be the primary reason it takes 30 seconds to compile something that depends on it. I used -dtiming and it seems to indicate that the typechecking specifically is taking 30 seconds

4

When importing a cmi, you need to:

  • Load the file in memory
  • Unmarshal the corresponding AST
  • Traverse the AST to freshen all unique stamps

I expect all of this to take a significant amount of time, possibly accounting for most of the 30 seconds.
And since Cmi loading occurs during typechecking, this would be consistent with the -dtiming results you have.
If you can get a perf report, try to look how much time is spent in Persistent_env.read_pers_struct and Persistent_env.find_pers_struct; I think these are responsible for most of the cmi loading logic.

5

Thank you @vlaviron!

I spent the morning investigating and I think I have a basic idea of what is happening now.

I used Claude to write a bash script that generates a source module Amin with some large number of n submodules of the form module M_k = module type t = int end and then a client module which accesses Amin.M_0.t. You can see that the compile time is quadratic with n.

Here is the code:

#!/bin/sh
# Quadratic typing time when a client touches one submodule of a file
# containing N independent submodules. OCaml 5.5.0.
OC=${OCAMLOPT:-ocamlopt.opt}
printf 'type x = Amin.M_00000.t\n' > cmin.ml
printf '%-7s %-14s %s\n' N client_typing ratio
prev=""
for N in 1000 2000 4000 8000 16000; do
  awk -v n=$N 'BEGIN{for(i=0;i<n;i++)printf "module M_%05d = struct type t = int end\n",i}' > amin.ml
  $OC -opaque -c amin.ml 2>/dev/null
  t=$($OC -opaque -dtimings -c cmin.ml 2>&1 | awk '/ typing/{gsub(/s/,"",$1);print $1;exit}')
  if [ -n "$prev" ]; then r=$(awk -v a=$t -v b=$prev 'BEGIN{printf "%.2fx",a/b}'); else r="-"; fi
  printf '%-7s %-14s %s\n' "$N" "${t}s" "$r"
  prev=$t
done

I went spelunking into the compiler code to understand what was causing this, and here is my conclusion.

A cmi contains unique stamps associated to each declaration in that compilation unit. So, for example, the module M_3 carries some unique identifier, and is represented internally as M_3/3832 or whatever.

When the module is loaded, these unique identifiers are “lazily reassigned” in order to make them globally unique among all other compilation units which have been loaded in order to compile the target. This is in rename_bound_idents (subst.ml:594) By “lazily reassigned”, we mean that a map $s$ is constructed which associates to each original unique id a new unique id, and the declaration within the module is now represented as something like a pair (original_id, s), which can be at any time evaluated to get the new globally unique id, original_id[s].

Now, the client module needs to be able to access values and submodules in the source by their path, and it also needs to be able to typecheck their usage - or, for a submodule, typecheck projections or functor applications - using paths which are intelligible to it. So if A is our upstream compilation unit, and the client wants to access A.B - either to project onto a type A.B.t,
or to use A.B as a functor argument, or whatever - it needs to know the interface of A.B, presented in such a way that all the fields are expressed using paths.

So if A has submodules M_3 and M_5, and the signature of M_3 is something like sig val v : M_5.t end, then

  • initially in the compilation unit, M_3 and M_5 both have unique stamps, say M_3/3284 and M_5/2127
  • after A is compiled, when A is loaded by the compiler for the sake of compiling some downstream module C, fresh identifiers are now introduced for all these symbols (say 5128 and 8675) and now M_3 is represented as something like an ordered pair (M_3/3284, s = { M_3/3284 |-> M_3/5128 , M_5/2127 |-> M_5/8675 })
  • also, we build a map which associates to each sub module M_3, M_5 a prefixed name (Env.prefix_idents), so we have another map s' = { M_3/5128 |-> A.M_3, M_5/8675 |-> A.M_5 }, in order that the client can refer to it
  • these maps are composed (subst.ml:741) so we combine (M_3/3284, s) with s' to get the pair
    (M_3/3284, { M_3/3284 |-> A.M_3 , M_5/2127 |-> A.M_5 })
  • this composition takes time at n log n if evaluating each value takes log time
  • this happens for every module declared in A, so it’s O(n^2 * lg n) in the number of modules in A

I don’t think this quadratic complexity is essential, and it could be eliminated in special cases.

Of course no human author is writing files with 3700 submodules. However, I think that OCaml’s language of interfaces is helpful in giving safe access to untyped tools, and I think it’s a legitimate interest to serve the use case of procedurally generated code.

I would be interested to hear if anyone involved in compiler maintenance want to weigh in.

It seems like the same compose s s' is being called repeatedly at each submodule declaration. So maybe that could just be pulled out?