Thomas Leonard's blog

Python to OCaml: Retrospective

In 2013, I spent 6 months converting 0install’s 29,215 lines of Python to OCaml (learning OCaml along the way). In this post, I’ll describe the approach I took and how it went. There will be graphs. If you don’t want to read the whole thing, the take-away is this: The new code is a similar length (slightly shorter), runs around 10x faster, and is statically type checked.

( This post also appeared on Hacker News and Reddit )

Table of Contents

Background

Several readers said they’ve been following this blog without knowing what 0install actually is. So, a quick summary!

Since 2003, 0install’s goal has been to provide secure, cross-platform, decentralised software installation.

Secure means that 0install doesn’t grant the software root access when you install it (like most package managers do), and doesn’t allow packages to conflict with each other (each version of each package goes in its own directory). It should always be safe to “install” a program with 0install, though ideally you’d use a sandbox to actually run it (we’re still waiting for a decent sandbox to turn up).

Cross-platform means it works on Linux (it’s available from the repositories of all the major Linux distributions), Unix, OS X and Windows (the Windows version is a compatible reimplementation in C#, though it does run some of the original code in a subprocess).

Decentralised means that upstream projects publish their software on their own web-sites. They still get automatic dependency handling (including dependencies on other sites), GPG signatures, automatic updates, roll-back, and support for binary and source packages. 0install can work with the native package manager (e.g. rpm or dpkg) to satisfy dependencies, in addition to downloading them as 0install packages itself.

0install was originally written in C as a Linux kernel module and user-space helper. It made other software easy to install, but getting 0install itself was rather tricky. My naive hope was that distributions would include it by default, but needless to say that didn’t happen. In 2005, it was redesigned and reimplemented in Python to simplify distribution.

OCaml migration overview

Replacing Python (Jun 2013)
The subject of rewriting 0install in a compiled language had come up a few times, but in 2013 I had just left my job to take a year off and finally had the time for it. I didn’t have any idea what language to use so I collected suggestions and tried them all. My test-case was to read the tutorial for each language and reimplement one trivial (4 line) function of 0install in each one. I looked at various factors, including start-up time, binary size, binary compatibility, safety features, diagnostics, ease of writing, support for shared libraries, and static checking.

Speed and binary size for the launch helper (dominated by start-up time).

There was no very clear conclusion. Rust seemed very promising in the long term, but it was years from being ready. ATS was the fastest and smallest, but too difficult to use. Python and C# were too slow (0install needs fast start-up time). Go did poorly in almost every area I tested. But Haskell and OCaml did surprisingly well.

Replacing Python: second round
I tried Haskell and OCaml on a larger sample, converting 576 lines of Python and comparing the code. They both did well, especially for detecting problems at compile time, but I found OCaml considerably easier to use. It also ran twice as fast.
OCaml binary compatibility (Jul)
OCaml can compile to bytecode or to native code. I’d hoped that the bytecode would allow us to distribute a single binary that would work everywhere (as with Java). In this post I did some experiments to check this. It almost worked, but in the end I gave up; we now build separate binaries for each platform.
Option handling with OCaml polymorphic variants (Aug)
Polymorphic Variants are an unusual and very powerful feature of OCaml’s type system. I found I was able to take advantage of them to check statically that all of 0install’s sub-commands handle all their options.
Experiences with OCaml objects (Sep)
Even though OCaml programmers rarely use objects, the language’s support for object-oriented programming was a big help in converting the existing Python code. This post looks at OO programming in OCaml and describes the things that confused me at first.
OCaml tips (Oct)
I go back over my first OCaml code from June, pointing out better ways to do things.
Asynchronous Python vs OCaml (Nov)
I add support for downloads to the OCaml, which requires using OCaml’s support for asynchronous code. I compare it with Python’s new asyncio system.
Polymorphism for beginners (Dec)
OCaml code is often written without explicit types, letting the compiler infer everything. However, it’s helpful to understand the details of the type system when it comes to writing interface files (describing a restricted public interface to a module) and when trying to understand compiler error messages. After muddling through for a while, I decided it was time to understand how it actually worked.

A lattice showing the subtype relationship.

OCaml: the bugs so far (Jan)
I’ve found OCaml to be very good at detecting problems at compile time and the code has been very reliable. Still, some bugs slip though. In this post, I go over each discovered bug that made it into a Git commit and try to work out why it happened and whether it could have been prevented.

Bugs found by type.

OCaml: what you gain (Feb)
When I first looked at OCaml, I was mainly focused on making sure the things I needed were still available. With the port complete, I summarise the things you gain from using OCaml.

Code size

The final OCaml code was remarkably similar in length to the original Python:

Lines of code, before and after.

The main code is slightly shorter, while the unit-tests are slightly longer (probably because I added some extra ones). The functionality is the same, except that the OCaml adds the “0install slave” command (325 lines of OCaml) and uses Lwt rather than its own asynchronous framework (483 lines of Python).

The Python code also included some XML files for the GTK user interface (shown in orange). In the OCaml, building the widgets is instead done directly in the code. The OCaml version includes some module interface files (the mli files, shown in green). These are used to control how much of a module’s implementation is visible to other modules. They make the code easier to understand, but they’re mostly optional.

Porting method

I wanted to avoid having two separate forks of 0install (Python and OCaml). Then most people would continue using the Python version until the OCaml version was finished, resulting in a sudden switch over and the risk of some major flaw in the whole idea going undiscovered until the end. Also, it would encourage people to submit bug fixes and features to the Python fork, creating extra porting work for me. Instead, I used a mix of both languages, slowly migrating functions from Python to OCaml. The two parts communicated using JSON.

I made sure the complete set of unit-tests passed for every commit and that the software remained fully functional throughout the whole process. The graph below shows the amount of Python and OCaml code over time:

Lines of code over time.

For the first couple of months I was just adding OCaml code, duplicating lots of common helper code. For example, the OCaml version needs to be able to parse the XML selections documents, so that code is ported, but parts of the Python still need that code too, so it can’t be deleted yet. Once I start deleting Python code, progress is fairly steady until it’s all gone. A nice benefit of this approach is that you can see clearly where you are in the process.

Initially, I tried doing clean implementations of the code from the specifications. However, the existing code has a lot of special cases for weird systems and backwards-compatibility hacks, and not all of them were unit-tested. Soon, I switched to translating more literally from the Python and then cleaning it up once it was in OCaml. I kept the basic structure of the Python in most places (e.g. the same classes with the same methods). That made things much easier. Once the port was complete, I did some larger refactoring (such as making the XML type immutable). I think this worked well - refactoring is very pleasant in OCaml.

Binary size

Executable image size over time.

The binary ended up a bit bigger than I’d like. Adding the GTK and OBus libraries in particular added a lot to the size (though they are optional). The main problem with GTK is that it has to be compiled as a plugin, because we don’t know if the target system will have libgtk. If we used a single binary and the library wasn’t present, it would refuse to start. By having it in a plugin we can try to load it, but fall back to console mode if that fails. However, compiling for plugins prevents OCaml from optimising the binary by removing unused library functions, since it doesn’t know which ones might be needed by the plugins.

The binary is compiled with debug symbols, but compiling without has almost no effect (binary becomes 1.5% smaller).

Build time

Build time changes over time.

A full build takes nearly a minute, which isn’t too bad. The ocamlbuild command automatically discovers dependencies and rebuilds only what is needed, so incremental builds are usually fast and are generally reliable (the exception is that it doesn’t notice if you remove or rename a file, but you always get an error message in that case rather than an incorrect build).

Most errors are picked up by the type checker immediately at the start of the build, rather than by the unit-tests at the end. That saves a lot of time.

Two things did speed it up slightly: building the tests and the main binary with a single invocation (saves having to run the dependency checker twice) and turning on parallel builds. Parallel builds didn’t help as much as I’d hoped however.

Update: edwintorok profiled the build and noticed that 25.5% of the time is spent running a bytecode version of the camlp4 pre-processor (which we use for the Lwt syntax extension and for conditional compilation) and 10.5% is spent on a bytecode version of ocamlfind (looks like an ocamlbuild bug). Why ocamlbuild’s parallelization is often disappointing today looks interesting too.

Update 2: I noticed that building while the computer is busy doing something else is much faster! Looks like this is the Linux scaling governor being strange. Echoing “performance” to /sys/devices/system/cpu/cpu[0-3]/cpufreq/scaling_governor takes the build time (on my new laptop) down from 45s to 23s!

There are some changes (module aliases) coming in OCaml 4.02 which should help. Currently, if I change one of the files in the Support module (e.g. Support.Sat) then it first rebuilds Sat, then rebuilds Support with the new Sat module, then rebuilds everything that uses Support (which is everything). In reality, it only needs to rebuild Zeroinstall.Solver when Sat changes.

If you do need to modify one of the early modules and run the unit tests quickly, a good trick is to compile to byte-code rather than to native. The byte-code compiler doesn’t do cross-module inlining optimisations, which means that as long as a module’s interface doesn’t change, it doesn’t need to recompile the things that depend on it.

One interesting feature of the graph is that during December the build time increased faster in proportion to the lines of code added. This corresponds to the time I was implementing the GTK GUI, so it looks like GUI code takes longer to compile than normal code of the same length.

Speed

And the final result: running various operations with the old and new versions:

Test Python 3 OCaml Speed-up
0install --help 103 ms 8 ms 12.9
0install select 0repo 322 ms 38 ms 8.5
0install run -w echo armagetron 120 ms 15 ms 8.0
0install run armagetron --version 153 ms 45 ms 3.4

The first (--help) shows the overhead of running 0install and producing some simple output. The extra speed here really helps with tab-completion! The second test (select) shows 0install running its SAT solver to select a compatible set of libraries to run the “0repo” application. The third shows 0install setting up the environment to run Armagetron (-w echo echos the executable path rather than actually running it) and the fourth shows it actually running the program.

Speed of 0install in Python vs OCaml.

One other nice win is the time taken to run the unit-tests, which has dropped considerably:

Time to run the unit tests (in seconds).

The spike in the middle is the effect of the JSON bridge, where many tests involved communication between the Python and OCaml parts.

In theory, OUnit should be able to run the tests in parallel on multi-core systems, which would make it even faster, but a bug in OUnit means it doesn’t work.

Conclusions

It’s surprising to me how reliable the initial tests were. Even though I only converted 4 lines of Python, the tests uncovered pretty much all of OCaml’s weaker aspects (non-portable bytecode, lack of support for shared libraries, relatively large binary size, and somewhat terse error messages from the standard library), meaning there were no nasty surprises during the migration.

However, the testing was less successful at uncovering the benefits (excellent type checking, reliability, exhaustive pattern matching, polymorphic variants, abstract types, easy GTK bindings, and API stability).

Blogging about the whole process was extremely useful, attracting many helpful comments, suggestions and corrections from experienced OCaml users.

Epilogue

The blog attracted the attention of the OCaml folks at Cambridge University, who do all kinds of interesting OCaml things. As a result, I’m now working there, adding ARM support to the Mirage unikernel - an operating system written in OCaml (the Mirage web-site is all implemented in OCaml, down to and including the TCP/IP stack!). That will have to be the subject for another blog post though…

Comments