Hacker News Reader

Comment by fnord123 | Hacker News Reader

OCaml compile speeds are not particularly fast.

I'm curious do you have concrete data for this? I would love to see compile times for representative codebases of various sizes across languages and how they've changed across compiler versions.

From anecdotal experience I view OCaml's bytecode compile speeds to be on par with Go's (as a rule of thumb I expect about 1 second per 10k lines). Far slower than something like TCC, but quite fast among other languages.

I do not have concrete data for a comparison of like for like projects being compiled with comparable lines of code, and complexity of the type system usage, running on identical machines.

As for your view of OCaml byte code compilation speed being on par with Go seems rather unlikely or I'm misunderstanding what you mean. Go is not dealing with anywhere as near a complex type system as OCaml and generates a lot more potato machine code (usually not using -mnative so you can know you can copy a binary to arbitrary machines).

Hindley-Milner typechecking in practice is quite fast (as evidenced by ocamlc and Elm's compiler) and easily on par or faster than Go's typechecker (my rule of thumb for Elm code is usually 1 second per 100k lines).

In general HM-based type systems are both conceptually quite simple and can have quite fast implementations. What makes them seem "complex" is that languages with HM-based type systems also tend to make it hard to "go around" the type system and enforce much more rigid discipline around how your code can be written.

One thing that helps OCaml here is that it requires definitions to precede usage (like C/C++). Go and most other languages don't have this requirement. Perhaps, this results in faster symbol table lookups. Moreover, OCaml boxes everything and doesn't produce monomorphized code for generic types. OCaml's code generation is also much simpler than the likes of LLVM or GCC.

> One thing that helps OCaml here is that it requires definitions to precede usage (like C/C++).

I think this is due to the influence of Pascal and/or Modula on the language.

Isn’t pattern-matching alone combinatorial?

What is 'mnt pattern-matching'?

If you're asking about OCaml's pattern matching, it's compiled quite efficiently: https://www.cs.tufts.edu/comp/150FP/archive/luc-maranget/jun...

Apple autocorrects poorly. I meant “isn’t pattern-matching”. And I was asking about checking exhaustiveness at compile time specifically, not about the compiled code.

Unless you generate code with very large pattern matches it's an absolute non issue in practice :-)

There's all sorts of terrifying exponential things that affect HM typechecking in theory (e.g. pattern matching exhaustivity checking as you mention is directly equivalent to SAT, although this is technically not a part of HM typechecking, it is a feature in practice for most HM-inspired languages).

In practice it is actually very rare that they significantly affect compile times because it is very rare for the `n`-size to increase as the size of your codebase increases (these exponential blowups are generally limited to a single expression) for non-pathological code. Basically while you can have exponential blowups inside a single expression, I can't think of a time where you'll have exponential blowups across multiple expressions, which is what counts in a large codebase.

One of the times where big-O analysis doesn't accurately predict real-world runtimes.

I agree that the Ns are typically small, but I don’t know how the implementation could type check as quickly as Go’s considerably simpler type system.

Go's type system is actually of significant implementation complexity (in its details it's actually probably even more complex than Elm although less so than OCaml). In a typical implementation of HM the only nontrivial step (i.e. that isn't just a lookup and then checking if two constants are equal to each other) is union-find, i.e. a couple of set operations, but Go also has set operations it needs to do for type checking interfaces. So there isn't a clear performance win at a high level.

I’m talking about computational complexity. Go might have more edge cases than Ocaml, but I don’t believe it doesn’t have to exhaustively check match statements, for example.

To be clear, I think pattern matching is a good thing.

Indeed I was talking about computational complexity as well there when it came to set operations.

Go and HM-style type systems both have set operations they need to do that are of comparable practical computational complexity.

Exhaustivity checking without pattern matching (e.g. inserting wildcard expressions in every argument to a pattern other than the outermost tag) is computationally very straightforward and is at worst linear in the number of constructors a given type has. This is similar in computational complexity to Go's type checking of interfaces, which is also linear in the number of methods (since Go doesn't have any explicit interfaces it cannot simply do a name lookup).

  // This still checks for exhaustivity and is at worst 
  // linear in the number of `Case0`, `Case1`, etc.
  case thing of {
    Case0 x -> ...
    Case1 y -> ...
    Case2 z -> ...
  }

  // This is how you get equivalent to SAT, but is also 
  // comparatively rare
  case thing of {
    Case0 True False True -> ...
    Case1 True True True -> ...
    Case0 True True False -> ...
    // etc.
  }

Exhaustivity checking in the presence of pattern matching is only non-linear in the number of parameters to the constructor, which in most code is only one (because beyond one usually you would use a record instead). So in practice there aren't any obvious computational edges that Go typechecking has.

The HM type system is designed to be as fast and efficient as possible. And the OCaml typechecker is quite optimized (sometimes to the detriment of readability). Outside of GADTs heavy code, it feels unlikely to me that the exhaustiveness check matters much to the compilation time.

To add some data to the discussion, I have been recently measuring the compilation profile of some OCaml libraries, and the average time spent in the typechecker is around 40% (https://www.polychoron.fr/ocaml/2021/08/19/measuring_compila...).

Thus the complexity of the OCaml type system can only have a limited effect on OCaml compilation time.

And this measure does include interface files, where the compilation pipeline is reduced to just parsing, typechecking, and dumping the computed file to the disk.

OCaml is much faster than Go in the bytecode mode, as you have interfaces files which drastically simplify the typing process.

The compiling pipeline of bytecode is basically typing -> lambda -> bytegen

Bytegen is really close to what Zinc does.

> OCaml is much faster than Go in the bytecode mode

But doesn't the compiled code run slower in bytecode mode? I think that counts.

Sure it does, bytecode is meant for development not for production builds.

The healthy mix of interpreter/JIT/AOT backends is what many languages miss on their toolchains.

OCaml is really good at building in parallel. So even without that many files it can still compile using 32 threads.

Making so that a project with 20k loc is less than a second in debug mode. And recompile time in native(debug) mode is almost 100% linking time.

For bytecode you can have wild rebuild times, in the milisecond range.

Pyre[1] is about 20k loc of ocaml[2].

    $ time make -C source -j8
    make: Entering directory '/home/fnord123/src/download/pyre-check/source'
    ../scripts/setup.sh --configure
    Build info: Linux x86_64 @ Mon Aug 23 2021 (development build)
    abort: no repository found in '/home/fnord123/src/download/pyre-check/source' (.hg not found)!
    Git commit: 1e4dd5a39db1631fd13a3a8df74d6e0f5d801fbc
    dune build @install -j auto --profile dev
           menhir parser/generator.{ml,mli}
    Warning: 31 states have shift/reduce conflicts.
    Warning: 5 states have reduce/reduce conflicts.
    Warning: 77 shift/reduce conflicts were arbitrarily resolved.
    Warning: 75 reduce/reduce conflicts were arbitrarily resolved.
    make: Leaving directory '/home/fnord123/src/download/pyre-check/source'

    real 0m43.700s
    user 4m3.030s
    sys 0m41.005s

I must be doing something wrong.

[1] https://github.com/facebook/pyre-check [2]

    $ tokei
    -------------------------------------------------------------------------------
     Language            Files        Lines         Code     Comments       Blanks
    -------------------------------------------------------------------------------
     Autoconf                2          235          204            3           28
     C                      15       242641       165361        60669        16611
     C Header               10        14267         2617        11094          556
     Coq                    10         2391         1968          220          203
     CSS                     5          713          540           44          129
     Dockerfile              2           71           42           11           18
     HTML                    2           35           30            0            5
     INI                     1           12            9            0            3
     Java                   31         2654         2080          267          307
     JavaScript              7          867          752           61           54
     JSON                   17          939          939            0            0
     Makefile                5          229          145           45           39
     Markdown               47         7213         7213            0            0
     OCaml                 791       229096       198302        10455        20339
     Python                398        61909        50119         2917         8873
     Shell                   5          111           59           34           18
     SVG                     2            2            2            0            0
     TeX                     4          929          642          129          158
     Plain Text              5          457          457            0            0
     TOML                    1            2            2            0            0
     TypeScript              2          130           84           20           26
    -------------------------------------------------------------------------------
     Total                1362       564903       431567        85969        47367
    -------------------------------------------------------------------------------

> Pyre[1] is about 20k loc of ocaml[2].

Reading your table, there are 198302 lines of OCaml code. That's about 10x larger than the 20k you claim. The 20339 in that row is the count of blank lines. I doubt they matter much here.

Argh I misread the number of digits.

I'd be curious if the pyre-check compilation is any faster for you either by removing the inlining optimization flag (the `-Oclassic` here https://github.com/facebook/pyre-check/blame/36243764ab81a82...) or whether there's a way to compile pyre-check to bytecode instead of the native compilation step (which unfortunately it looks like there's no easy way to modify pyre-check's build config to do so).

compared to what? it's definitely one of the fastest-compiling languages i use.

Compared to what?

On par with Java but without maven startup time.

Admittedly I’m not citing actual numbers (but then again neither is anyone else here), but subjectively based on past experience, I highly doubt that. The OCaml compile is super parallelizable, with no forward references i.e. potential dependency cycles like in Java. My feeling is it blows Java out of the water.

You don't need Maven to compile Java code, additionally when using Eclipse incremental compiler, files are compiled on save.

Reply on news.ycombinator.com