My story on “worse is better”

Rui Ueyama — April 2018

The Rise of Worse is Better” is a famous essay in the software industry. It says that lazily-looking code that does not provide a consistent interface is sometimes actually better than neatly layered, consistent one. I think I've experienced this paradoxical situation, so I'd like to share that story.

I am the original author of the current version of the LLVM lld linker. A linker is a program used in conjunction with a compiler to create an executable or a shared library file. lld has been quite successful as a product; several operating systems are using it as their standard system linker. It is also a popular choice for large projects such as Chrome or Firefox because it's substantially faster than the default linker.

The current lld is version 2. The first version of lld existed before I joined the project, but we decided to rewrite it from scratch. To borrow phrases from the “worse is better” essay, I think lld v1 was written in the MIT/Stanford style (the better one) and lld v2 was written in New Jersey style (the worse one). Why did we abandon the one with the “better style” and rewrite it in the “worse style”? To see why, let's first look at the design of lld v1.

My understanding is that lld v1 was written with the following policy in mind:

  1. To provide a flexible feature set for compilers and other build tools, lld v1 was written as a collection of library features that as a whole work as a linker. The linker command, ld, was positioned as one of the library's use cases.
  2. To minimize the amount of platform-dependent code, a platform-independent intermediate representation was defined. Most of the linker code was written for the intermediate representation.
  3. The linker was designed to be robust as a program. It should never crash, and it must report any errors it finds in an input file to the caller of the library.
These design principles seemed pretty reasonable. However, after 18 months of working on the project full-time, I was still struggling to get lld to run properly. It could link most real-world programs, but it was very slow, and adding a new feature to the linker was very difficult. It was obvious that something wasn't quite right.

The problem we had was that the design was too complex. For each bullet point, let's see what was a problem:

  1. First of all, do many people really need a set of library functions and data structures that collectively work as a linker? My conclusion was “no”. There was a need to embed a linker as a whole into other programs, but it looked like we didn't have to break down the linker's functionality into fine-grained pieces and expose them as a public interface.

  2. Platform-independent intermediate representations did not work well for the linker in practice. Because the various platform-dependent features affect not only the file format but also the semantics of the linker's behavior, the intermediate representation needed to be able to represent all the features of all the supported targets (Unix, Windows and macOS). So the result of trying to “factor out” wasn't an intersection but a union of everything.

    This made programming very difficult. If you consider it as a library, you can use Windows linker functionality X in combination with Unix linker functionality Y, but there was no precedent for what the linker should behave in such a case. Even worse, in many situations, it was not obvious what would be the “right” behavior. We spent a lot of time discussing to define the semantics that would make sense for all possible feature combinations, and we carefully wrote complex code to support all targets simultaneously. However, in hindsight, this was probably not a good way to spend time because no one really wanted to use such hypothetical feature combinations. lld v1 probably didn't have any real users.

    Converting all input files, which could be multiple GiB in size, into the intermediate representation had a negative impact on performance too. It took several seconds if not minutes to convert all input into an intermediate representation.

  3. As for the robustness of the program, we had to write a lot of additional code to check the consistency of every detail of the input. That slowed down the linker, as checking several GiB of inputs takes a long time.
In the end, we decided to rewrite the program from scratch in the following “worse style”:

  1. We decided to write lld v2 simply as a command. It now has a single entry point for the program instead of allowing library users to reorganize micro linker features as they wish. This has made the program dramatically simpler. In lld v2, if someone wanted to add a new feature, they would have to modify the linker's source code directly, but that's fine; the source code is now shorter and easier to understand, so adding a new feature is much easier than it was before.
  2. In lld v2, we decided not to use an intermediate representation. Instead, we directly handle platform-dependent native file formats. lld v2 consists of virtually three different linkers for Windows, macOS and Unix. They share the same design but do not share code. Naturally, we sometimes had to write very similar code for each target. This may seem like an amateur-level programming mistake, but in reality, it's much easier to write straightforward code for each target than writing unified one that covers all the details and corner cases of all supported targets simultaneously.
  3. As to the robustness, we drew a clear line between what errors should be handled explicitly and what don't have to. Here is the rule: if a user can trigger an error condition by using the linker in a wrong way, the linker should print out a proper error message. However, if the binary of an input file is corrupted, it is OK for the linker to simply crash.

    Since the linker's input file is created not by humans but by the compiler, it is unlikely that the linker takes a corrupted file as an input. Therefore, the policy did not actually increase a crash rate. The code that trusts input was much simpler than the one that does not trust any byte of an input file.

The benefits of the new design became apparent almost immediately. Within a few weeks of starting to write lld v2, we were able to link non-trivial programs, and at that point the linker was already about 10x faster than lld v1 and 2x faster than the fastest existing linker at the time. After a few months, we were able to link fairly large programs using lld v2. The success of this rewrite attracted other open source developers to join the project. Finally, we grasped the real users' needs. Most users care only about the speed of the linker as long as it works correctly, and we simply made a linker that works correctly and is extremely fast.

Now, a few years later, lld is used in many operating systems, projects, and companies. I think it is now within reach to become one of the standard development tools for Unix, which once seemed to be a very ambitious goal.

I wouldn't go so far as to say that “worse design” was the reason of all the success of lld v2, but it was definitely a major factor. So let me emphasize my take on the “worse is better” principle here. Don't stick too much with the principles that are considered best practices in the industry if they don't fit your problem. Simplicity of implementation is very, very important, and you can sometimes sacrifice consistency and completeness for it. Similar but different things can be handled separately if it makes overall sense. Your product doesn't have to satisfy all possible needs. It is OK to not aim to minimize the amount of code; reducing the complexity is much more important. It is also important to create a small, working product with a design that you think right and gradually improve it.

[This essay was originally written in Japanese in 2018. After that, I started a new project called mold to create an even faster linker. If you are interested in shortening build time, please take a look at my new project. The English translation of this essay was published in 2021.]

Rui Ueyama — April 2018