Incremental compilation for Crystal - Part 1
Tags: crystal, incremental, compilers, compilation
Published: 2023-01-03 14:26:35

---
title: Incremental compilation for Crystal - Part 1
published: true
description: Thoughts about how to introduce modular compilation for Crystal
tags: Crystal, incremental, compilers, compilation
series: Incremental compilation for Crystal
# cover_image: https://direct_url_to_image.jpg
# Use a ratio of 100:42 for best results.
# published_at: 2023-01-03 11:39 +0000
---

I strongly believe that the [Crystal programming language](https://crystal-lang.org/) has great potential. The only thing that, in my mind, is holding it back a bit is its slow compile times, which become more and more noticeable as your project grows.

Why is the compiler slow? And can we improve the situation? This is what I'm going to talk about here, and think about solutions as we go.

# Why the compiler is slow?

The main reason is that the compiler compiles the entire program, from scratch, every time you invoke it. Well, it at least does a full semantic analysis of your program: there is some caching going on regarding producing object files. But semantic analysis is always done, from scratch, for the entire program.

And when I say "the entire program" it's the code that you wrote, but also the code from shards you use, and even the standard library. And, well, it's not the "entire program" because only those types and methods that are effectively used need to be analyzed and compiled, but it can still be quite a lot of code.

The actual algorithms used in the compiler are good and fast. We could try to make them even faster. But, as you add more and more code to your program, inevitably, no matter how fast the algorithms, it will take more and more time to compile programs.

# Why is semantic analysis done from scratch every time?

Not doing semantic analysis from scratch means doing it by chunks, and reusing that previous knowledge.

Most, if not all, compiled programming languages will analyze and compile individual files and then link them afterwards. Can we do the same in Crystal?

Let's consider this file:

```crystal
# dependency.cr

def add(x, y)
  x + y
end
```

Well, we have **no idea** what are the types of `x` and `y`. If we call it with two ints then we can type and compile that method with that information. And the same is true if we pass it two strings. Or any object that has a `+` method with an argument. So we can't type and compile that file just like that.

That's one thing. Another thing is not knowing what types resolve to. For example in this file:

```crystal
# dependency.cr

def something
  Foo.bar
end

something
```

Here `something` doesn't take any arguments so we could try to type and compile it right away. But if we do so... what's `Foo`? And what's the class method `bar` in it? We can't know. Well, maybe a require is missing in that file:

```crystal
# dependency.cr

require "foo"

def something
  Foo.bar
end

something
```

and now if `foo.cr` defines `Foo` all is good. But Crystal (and Ruby) allow not requiring a dependency like that, and instead it can come from somewhere else. For example:

```crystal
# caller.cr

require "dependency"

class Foo
  def self.bar
    1
  end
end
```

Here `caller.cr` defines a class `Foo` with a class method `bar`, and requires `dependency` which in turns defines `something` that uses that `Foo`. And this is perfectly fine, even though there's no **explicit** mention of where does `Foo` come from in `something`.

The conclusion so far is that it's almost always impossible to look at a single file and type it without knowing the full program.

# Why Crystal allows writing programs like that?

At this point one might wonder "is it a good idea that a file can work without it specifying where do types and methods come from?" But here I'm not going to try to answer that question, which is mainly subjective, and instead try to focus on how we could improve Crystal as it is right now. Of course Ruby could be "improved" (made faster) in many ways if we changed it (like, disallow some dynamisms, force some type declarations, etc.) but Ruby is being improved while not changing the way it is, while keeping its philosophy. Ruby has a vision, and it's being improved while keeping that vision. And I think that with Crystal we should strive to do the same.

# Incremental compilation

So let's discard for now the idea of being able to compile files individually. What else can we do?

One idea is to compile the entire program first, and then try to reuse that knowledge for subsequent compilations. It would work like this:
1. We compile the entire program and build a dependencies graph: which files depend on which other files?
2. We also remember the types used in methods? For example if `add(x, y)` was called with two ints, we remember that it returns an int.
3. Next time we compile a program, if we find a call to `add(x, y)` with two ints, we check if the file where `add` was defined, or any of its dependencies (recursively) changed, and if not, we could avoid typing that method again as we would know that it returns an int.

Would that really work?

# Looking at file dependencies in real programs

I created a [branch](https://github.com/asterite/crystal-1/tree/dot-dependencies) that modifies the compiler to output a file dependencies graph for a given program. You can try it by checking out that branch, creating a compiler from it and then compiling any program. This will generate a `dependencies.dot` file which you can then turn into a PDF by using this command:

```bash
$ dot -Tpdf dependencies.dot > dependencies.pdf
```

(you'll need to install graphviz first)

Running it against this program:

```crystal
# foo.cr
puts "Hello world!"
```

will produce this graph:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/fxrqb2zcqf202f0dv8hr.png)

What a lovely tree-like graph! It's very easy to see how no cycles exist here.

They say "beauty lies in the eyes of the beholder" but I hope we can all agree that the graph above is a mess.

Still, within all that mess, we can find this:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3crx3fs73k7fna0b126j.png)

`kernel.cr` defines `puts`, so it's natural that `foo.cr` dependes on it. But what's interesting is that nobody depends on `foo.cr` (naturally.) And that also means that if next time we only change `foo.cr` then we can reuse everything else from the previous compilation.

# Trouble ahead

This looks promising. But running the tool with some bigger programs I found something. Let's take a look at this program:

```crystal
# foo.cr

class Foo
  def to_s(io : IO)
    io << "foo"
  end
end

puts Foo.new
```

The graph near `foo.cr` now looks like this:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4c4olxziop8r4jb80w1t.png)

Now `foo.cr` has more dependencies, but something curious is that someone is now depending on `foo.cr`. Who?

We could play the "trace the line" game to find it, but looking at the dot file there's this:

```dot
  "src/io.cr" -> "foo.cr"
```

The above means "src/io.cr" depends on "foo.cr". WAT? How can the file that defines `IO` depend on "foo.cr"? It should be the other way around!

Debugging this a bit, we can see that the call the program makes is this one:

```crystal
puts Foo.new
```

Next we have that the definition of `puts` is:

```crystal
def puts(*objects) : Nil
  STDOUT.puts *objects
end
```

So that's calling `puts` on an `IO` (`STDOUT`). Let's take a look at that:

```crystal
class IO
  def puts(obj : _) : Nil
    self << obj
    puts
  end
end
```

This is calling `IO#<<(obj)` where `obj` is an instance of `Foo`. Let's take a look at that `<<` method:

```crystal
class IO
  def <<(obj) : self
    obj.to_s self
    self
  end
end
```

So this is calling `obj.to_s(self)`, where `obj` is an instance of `Foo`. And where is that method defined? In `foo.cr`! Bingo!

That's why suddenly `io.cr` depends on `foo.cr`.

One way to understand this is to know that in Crystal all methods are monomorphized. Monomorwhat? It just means that if you call `IO#puts` with a type `X`, a method will be generated for that particular `X`. If you call it with a `Y`, a method will be generated for that particular `Y` (for that particular **type**.) In the example above, an `IO#<<(obj)` method was generated where `obj` is of type `Foo`.

This is one reason that, I think, explains how messy the graph above is.

In other compiled, statically typed programming languages, this doesn't happen. Usually `obj` responds to some explicit interface and then the method lies behind a virtual table and a virtual dispatch. None of this happens in Crystal.

# Does it matter?

Does it matter that `io.cr` depends on `foo.cr`? Maybe it's not a big deal. Well, it probably is. It means that changes to a file are likely to affect seemingly unrelated files. And so if we try to use the "reuse previous compilation" strategy, not a lot could be reused in the end.

# The end?

This is not the end of the story. It's just the end of this blog post. I didn't continue thinking about how to approach this problem, but hopefully these posts spark some interest and some thoughts from others about how to solve this interesting problem.