I strongly believe that the Crystal programming language 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.
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.
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:
def add(x, y)
x + y
Well, we have no idea what are the types of
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:
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:
and now if
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:
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
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.
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.
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:
- We compile the entire program and build a dependencies graph: which files depend on which other files?
- 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.
- Next time we compile a program, if we find a call to
add(x, y)with two ints, we check if the file where
addwas 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?
I created a branch 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:
$ dot -Tpdf dependencies.dot > dependencies.pdf
(you'll need to install graphviz first)
Running it against this program:
puts "Hello world!"
will produce this graph:
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:
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.
This looks promising. But running the tool with some bigger programs I found something. Let's take a look at this program:
def to_s(io : IO)
io << "foo"
The graph near
foo.cr now looks like this:
foo.cr has more dependencies, but something curious is that someone is now depending on
We could play the "trace the line" game to find it, but looking at the dot file there's this:
"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:
Next we have that the definition of
def puts(*objects) : Nil
So that's calling
puts on an
STDOUT). Let's take a look at that:
def puts(obj : _) : Nil
self << obj
This is calling
obj is an instance of
Foo. Let's take a look at that
def <<(obj) : self
So this is calling
obj is an instance of
Foo. And where is that method defined? In
That's why suddenly
io.cr depends on
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
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 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.
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.