Josh Haberman

A Tail Calling Interpreter For Python (And Other Updates)

Mon, 10 Feb 2025 00:00:00 +0000

It’s been nearly four years since I published Parsing Protobuf at 2+GB/s: How I Learned To Love Tail Calls in C. In that article, I presented a technique I co-developed for how to write really fast interpreters through the use of tail calls and the musttail attribute.

While the article focused on Protocol Buffer parsers, the technique applies to many kinds of parsers and VM interpreters. I published the article in the hopes that the technique would catch on and be adopted in other projects.

In the time since that article was published, there have been many exciting developments in this space. I want to take this opportunity to share some updates.

Tail Calling Interpreter for Python

I recently learned that a tail calling interpreter was going through PR review on GitHub. Authored by Ken Jin as part of his Bachelor’s theses, it uses the techniques described in my article and claims a 9-15% improvement geomean improvement on pyperformance, the official Python benchmark suite.

Last Friday that interpreter was merged, and it is officially slated to be released in Python 3.14 (release notes).

Note that the tail call interpreter is not the default yet. It has to be enabled at configuration time with --with-tail-call-interp. Hopefully it will be the default in a future release.

I’m very excited to see this development. In my original article, I made the following prediction:

I think it’s likely that all of the major language interpreters written in C (Python, Ruby, PHP, Lua, etc.) could get significant performance benefits by adopting this technique.

I’m happy to see that this seems to have come true for Python. Congratulations to Ken on this accomplishment.

Tail Calling Interpreter for LuaJIT Remake

In 2022-2024, Haoran Xu published a series of articles and papers about an ambitious and experimental effort to automatically generate interpreters and JIT compilers from a description of the language semantics. This project is called Deegen, and Haoran used it to build LuaJIT Remake, an experimental reimplementation of the famous LuaJIT.

Deegen uses the tail call pattern for its interpreters, arguing that this the best way to get the compiler to generate good code. This conclusion aligns with my 2021 article, and his analysis cites my work.

However, he concludes that C and C++ cannot achieve optimal performance for tail calling interpreters because of limitations in the calling convention. The main problem he cites is around callee-save registers, and how the C calling convention forces all functions to preserve six registers, a steep cost given how small these functions tend to be.

He also mentions the restrictions on [[clang::musttail]], particularly on how the caller and callee must have matching function signatures, which can be inconvenient. As a result, Deegen targets LLVM IR instead of C or C++.

The first issue has been largely addressed by the preserve_none attribute (discussed below). Promising developments are also occurring regarding the second complaint, as detailed below in the “Nonportable Musttail” section.

LuaJIT Remake’s interpreter claims a 31% performance advantage over LuaJIT 2.1, an impressive result given that LuaJIT already has one of the fastest interpreters of any mainstream programming language. It is still an experimental project (for example, garbage collection is unimplemented, so the performance comparison disables GC for LuaJIT too); it would be cool if Deegen or something like it was eventually productionized and used in a mainstream language interpreter. Congratulations to Haoran on this accomplishment.

GCC Support

When I published my original article, GCC had no support for musttail. I floated the idea of adding musttail to the GCC maintainers in 2021, which generated some interesting discussion, but no clear plan.

I’m happy to report that this received renewed attention since then. GCC added support for a musttail attribute in C and in C++ in July of 2024. Thanks to the GCC team for this work.

GCC appears to be more strict than Clang in analyzing whether any pointers to locals are referenced across the tail call. I posted some analysis of this issue in the Clang bug tracker.

Standard C Proposal: “return goto”

I recently heard that there is a proposal to add guaranteed tail calls to the C standard as return goto. The proposal is given in n3266. The proposed syntax is:

int a (int, int);

int b (int x, int y) {
    return goto a (y, x);  // Proposed syntax.
}

It’s very exciting to think that guaranteed tail calls might eventually be added to standard C. It is unclear whether it will be included in C2Y, but I am hopeful.

The rationale given in n2920 does not mention the use case of tail call interpreters, even though this was the primary motivation for adding musttail to both Clang and GCC. The use case envisioned by the committee is that C is being used as a code generation target for a language like Scheme that guarantees tail call optimization. The document goes so far as to say they do not expect the feature to see significant use in user-written C code.

But even though they are not designing for the interpreter use case, the proposed feature looks like a perfect fit for tail calling interpreters, so I’m happy for that.

Interestingly, the proposed C standard is more lax than [[clang::musttail]] about whether the caller and callee have to match in argument types. For various ABI reasons, some calls are impossible to tail call optimize. Clang enforces a set of rules that are intended to be “portable”, so that the tail call can be performed on “any” architecture:

int g();

// Valid according to the proposed standard C feature,
// but the implementation is allowed to fail if this
// cannot be tail-call optimized for an implementation-specific
// reason.
int f(int x) { return goto g(); }

// Always rejected by Clang currently, because the caller
// and callee do not perfectly match in function signature.
// This is rejected even if the implementation is capable of
// tail call optimizing the call, because Clang is trying to
// provide a "portable" guarantee:
int f(int x) { [[clang::musttail]] return g(); }

I think the standard is making a good call here. Clang attempts to ensure “portable” tail calls, but in retrospect, I believe this approach has limitations. We will discuss this further in the next section.

Clang: “Nonportable” Musttail?

When I implemented [[clang::musttail]] in Clang, it merely exposed to C and C++ some functionality that already existed in the LLVM backend. The musttail attribute for LLVM had been added years earlier, and it already had a set of semantics which dictated many things. In particular, it dictated that the caller and callee prototypes must match.

This disallowed code like the following, even though this can be successfully tail call optimized on many platforms:

int g();

// Always rejected by Clang currently, because the caller
// and callee do not perfectly match in function signature.
// This is rejected even if the implementation is capable of
// tail call optimizing the call, because Clang is trying to
// provide a "portable" guarantee:
int f(int x) { [[clang::musttail]] return g(); }

To follow LLVM’s rules, we had to make Clang reject this code.

In theory, we are trading off flexibility for predictability. Even though some platforms are able to tail-call-optimize code like the above, some are not, and it would be surprising if your program worked fine on some platforms but failed to compile on others. So we have a set of rules that, if followed, should guarantee that the code can be tail call optimized on all platforms.

However, once the feature was launched, we started receiving complaints about these rules. There were two main complaints. First, users were understandably frustrated that a tail call would fail to compile on a platform where the tail call was totally possible to optimize. It seems a bit unhelpful for the compiler to reject your program just because it might fail on a different platform.

Users also raised the point that this “guarantee” isn’t really a guarantee at all. Some platforms fundamentally do not support tail calls, like WASM without the Tail Call Extension.

What this means is that the predictability that Clang/LLVM are trying to provide is fundamentally impossible. We’ve traded off flexibility, but we didn’t even get predictability in return.

In response, users have proposed two possible resolutions:

We could relax [[clang::musttail]] so that it only fails if the tail call is impossible on this platform.
We could leave the [[clang::musttail]] attribute the way it is, and introduce a new [[clang::nonportable_musttail]] which has the desired semantics.

I believe option (1) is preferable, though I’m unable to implement it currently. Hopefully, someone will address this bug. Since it requires changes to both Clang and LLVM, it will be a more substantial undertaking than my initial [[clang::musttail]] implementation. However, as it primarily involves relaxing constraints, it should ultimately simplify the implementation.

Calling Convention Improvements

In the original article, I described some limitations where the tail calling technique could result in really bad code. In these scenarios, you could get tons of register spills that were bad for performance and code size. At the time, there weren’t great options to mitigate these problems except to contort the code to never make a non-tail call.

I am happy to report that this problem has been largely solved, at least in Clang. There are two calling conventions that can help. preserve_none optimizes the main interpreter functions that tail-call each other, while preserve_most benefits functions called in non-tail positions.

// preserve_none on tail calling functions optimizes register usage.
__attribute__((preserve_none)) const char *Next(PARAMS);

// preserve_most on non-tail-called functions can help optimize
// the caller.
//
// Caution: preserve_most adds overhead to the target function,
// and may not be worthwhile if the function is hot.
__attribute__((preserve_most)) const char *RegularFunc();

__attribute__((preserve_none)) const char *Parse(PARAMS) {
  if (!ptr) {
    ptr = RegularFunc();
  }
  ptr++;
  __attribute__((musttail)) return Next(ARGS);
}

preserve_most

If we use __attribute__((preserve_most)) on regular functions, it saves the caller from having to shuffle or spill any of its registers prior to the call, which generally will make our tail calling functions smaller and more efficient.

The preserve_most attribute existed when I wrote the original article, but I noted that it seemed to cause unexplainable crashes. This turned out to be a bug in Clang, which was fixed in 2023.

While preserve_most can theoretically solve the register shuffling/spilling problem, it has a major weakness. To get the desired effect, you have to apply it to all functions that you call in non-tail position. Whenever you are modifying your interpreter, if you start calling a new function, you have to add preserve_most to it.¹

But what if you are calling a standard library function like strlen()? You can’t modify the calling convention of a function you don’t own. You would have to create a separate wrapper function like my_strlen() and put preserve_most on the wrapper. If you don’t – if you forget this discipline for even a single function – then you get these horrible pessimized prologues and epilogues in the fast path.

While helpful, preserve_most introduces overhead to the target function and should be used judiciously, particularly in hot code paths.

preserve_none

I had always felt that it was more promising to have a special calling convention for the tail calling functions. After all, they are all under our control and they are “special” already: they all use a consistent set of arguments, and we have to call them with the musttail attribute.

To pursue this opportunity, in 2021 I prototyped a new calling convention I called reverse_call. The calling convention was designed to be applied to the tail calling functions, allowing us to get rid of all those gratuitous prologues and epilogues.

The basic idea was to have no callee-saved registers, so our interpreter functions are freed of the burden of preserving any registers. And critically, we also want our argument registers to be allocated in the opposite order from a normal function (starting with callee-save registers, which are normally never used as arguments at all).² The net effect is that when a reverse_call function calls a normal function, the argument registers for caller and callee do not overlap, and moreover the caller’s argument registers will be preserved by the callee. This allows the interpreter to keep its arguments in registers across the call, without any register shuffling or spilling required. The results from my prototype were good, and I was pretty excited about this idea.

While my initial reverse_call proposal didn’t gain traction, subsequent discussions on Clang mailing list led to the preserve_none convention, addressing the same issue. Implementations for x86 and for aarch64 landed in Clang 19.1.0, though I haven’t found a corresponding release note for them.

Shortly after, another LLVM contributor re-discovered my idea of assigning arguments to registers starting with the normally callee-save registers, and created a PR to implement it. So in the end, the preserve_none convention in Clang turned out to be almost exactly what I had envisioned with reverse_call. Thanks to all of the Clang contributors who made this happen.

// Uses preserve_none (landed in Clang in 19.1.0).

#define CC __attribute__((preserve_none))

CC const char *Next(PARAMS);
const char *Fallback(PARAMS);

CC const char *Parse(PARAMS) {
  if (!ptr) {
    ptr = Fallback(ARGS);
  }
  ptr++;
  __attribute__((musttail)) return Next(ARGS);
}

The Python tail call interpreter uses preserve_none, and I think that all tail call interpreters would benefit from doing the same.

Conclusion

All of these developments have been exciting to see. I hope that in several more years, we’ll see more progress towards standardizing musttail into return goto, more support for preserve_none across compilers, and hopefully even more programming language interpreters will adopt the technique.

It also pessimizes the target function by forcing its prologue and epilogue to be bigger and slower. This is fine if the function is a fallback function, but if it is called in a reasonably hot path, this could slow down the code. ↩
I have seen it claimed that the GHC calling convention in LLVM does the same thing, but I was not able to independently confirm this. ↩

No-Panic Rust: A Nice Technique for Systems Programming

Mon, 03 Feb 2025 00:00:00 +0000

Can Rust replace C? This is a question that has been on my mind for many years, as I created and now am tech lead for upb, a C library for Protocol Buffers. There is an understandable push to bring memory safety to all parts of the software stack, and this would suggest a port of upb to Rust.

While I love the premise of Rust, I have long been skeptical that a port of upb to Rust could preserve the performance and code size characteristics that I and others have fought so hard to optimize. In fact, this blog entry was originally going to be an argument for why Rust cannot match C for upb’s use case.

But I recently discovered a technique that shifted my thinking a lot. I call it “No-Panic Rust”, and while the technique is clearly not new¹, I was not able to find any in-depth discussion of how it works or what problems it solves. This article is my attempt to fill that gap.

I believe that No-Panic Rust is the key to making Rust a compelling option for low-level systems programming. I now am optimistic about the possibility of porting upb to Rust.

What are Panics?

Panics are Rust’s mechanism for unrecoverable errors. Anytime our program encounters an error, we have three basic options for how to handle it:

Handle the error immediately (eg. retry the operation or fall back to plan B).
Propagate the error to the caller, who can decide how to handle it.
Immediately abort execution.

In Rust, we use Result for (2) and panic!() for (3). When we use Result, it is considered a “recoverable error”, because the caller can test for the error and decide how to respond.

With recoverable errors, the potential for error is reflected in the function signature; a function that returns Result is fallible from the perspective of the caller. Panics on the other hand present the illusion of infallibility from an API perspective, but then proceed to handle errors by simply aborting.

There is a lot of standard guidance for when to use panic!() vs Result (for example, here and here), which largely boils down to the idea that panics should only be used for bugs in the code. I especially like the framing given in this Reddit post:

[If] your library is the source of a panic, then one of the following should be true:

Your library has a bug.

Your library documents a precondition of a public API item that, when not met, causes a panic. Therefore, the user of your library has misused your library, and their code has a bug.

If your Rust application panics in response to any user input, then the following should be true: your application has a bug, whether it be in a library or in the primary application code.

In this article we are focused on the library case.

Why Are Panics Bad For Systems Libraries?

If we are trying to port a C library to Rust, we really do not want to introduce panics in the code, even for unusual error conditions. They cause many practical problems:

Code Size: The runtime to handle a panic pulls in about 300Kb of code.² We pay this cost if even a single panic!() is reachable in the code. From a code size perspective, this is a severe overhead, given that the upb core is only 30Kb.
Unrecoverable exit: If a panic is triggered, it takes down the entire process.³ In many applications, this is a severe failure mode that libraries should never invoke. Instead, we should return all errors to the caller using status codes.
Runtime overhead: A potential panic implies some kind of runtime check. In many cases, the cost of this check will be minimal, but for very small and frequently invoked operations, the cost of this check could be significant.

In the case of upb, I was concerned about all three of these factors. Ideally we could port upb to Rust without users even noticing. To do that, we want to maintain the same performance, code size footprint, and error reporting behavior that the C code has now. Panics get in the way of this ideal.

At some point I realized that it might be possible to ban panics from the library entirely, which would solve all of these problems at once. That is when I started getting much more optimistic about porting upb to Rust.

What is No-Panic Rust?

No-Panic Rust is a subset of Rust for which panic!() is unreachable. Programs written in no-panic Rust are guaranteed never to panic under any circumstances.

For a library, this means we should be able to build a cdylib that does not have a panic handler linked into it at all.⁴

We can experiment on godbolt.org to see if we have succeeded or not. Using my tool Bloaty, we can see if the cdylib binary is >300Kb (suggesting that the panic handler has been linked in) or <10Ki (suggesting it has not).⁵

Let’s explore this subset a bit. Is “Hello, World” no-panic?

#[no_mangle]
pub extern "C" fn hello_world() {
    println!("Hello, World!")    // Can panic
}

No, per the documentation for println!():

Panics if writing to io::stdout fails.

And indeed, if we try this on Godbolt, we see a big binary:

So println!() is out. If we want to print to stdout, we’ll need to use an API that does not advertise that panic is possible.

The stdout API looks promising, because it has a write_all() API that returns a Result, which should allow us to handle errors explicitly:

use std::io::{self, Write};

#[no_mangle]
pub extern "C" fn hello_world() -> bool {
    io::stdout().write_all(b"Hello, World!\n").is_ok()
}

This seems like it should be no-panic. We are only calling two APIs, stdout() and write_all(), neither of which documents a potential panic.

But if we try it, we’ll see that panic is indeed reachable in this program somehow.

From this we have learned that we unfortunately cannot rely on panic annotations in API documentation to determine a priori whether some Rust code is no-panic or not. We have to actually try it and observe the results.

How can we diagnose what went wrong? On macOS, the linker has a very handy option called -why_live, which will print the chain of symbol references that prevented a symbol from being dead-stripped. We can’t access it on Godbolt unfortunately, but on macOS we can run this command:

$ RUSTC_LOG=rustc_codegen_ssa::back::link=info \
  RUSTFLAGS="-C link-arg=-Wl,-why_live,_rust_panic" \
  cargo build --release 2>&1 | rustfilt

This results in the following output, with extraneous details removed:

_core::panicking::panic from [...]
  _core::ops::function::FnOnce::call_once from [...]
    l_anon.56b0c16dbe4596c74313e318a3dfaa78.520 from [...]
      _std::sync::once_lock::OnceLock<T>::initialize from [...]
        _std::io::stdio::stdout from [...]
          _hello_world from [...]

The panic reference apparently comes from _core::ops::function::FnOnce::call_once, which is called from _std::io::stdio::stdout.

This seems to suggest that Rust’s standard library does not meet the criteria given above, because it is capable of panicing even in APIs like std::io::stdout() that do not document a panic-worthy precondition.

This also implies that we need tests that check for the no-panic property. It’s not enough to check once that the code is no-panic, we need to make sure it stays no-panic over time, even as our project and our dependendencies evolve.

To get a fully no-panic version of “Hello, World”, we have to reach for the C library libc. This makes sense, since the C library is generally written to return all errors as status codes or errno. Unfortunately this means turning to unsafe:

extern crate libc;

#[no_mangle]
pub extern "C" fn hello_world() -> bool {
    const MSG: &'static str = "Hello, World!\n\0";
    let result = unsafe {
        libc::printf(MSG.as_ptr() as *const _)
    };
    result >= 0
}

And checking on Godbolt, we see the small binary that confirms that this library is indeed no-panic:

Opt No-Panic

What about adding two numbers? Is this no-panic?

#[no_mangle]
pub extern "C" fn hello_world(a: i32, b: i32) -> i32 {
    a + b
}

This is a trick question: this is no-panic in opt mode only. For numeric operations like addition, Rust introduces overflow checks (which panic on failure) in debug mode, but leaves them out of opt builds.

We can observe this on Godbolt if we add separate panes for opt and non-opt builds:⁶

This essentially creates a new class of code, which is “no-panic in opt, but can panic in dbg”.

For the case of upb, this seems like a great option, because it gives us extra consistency checks in debug mode without suffering the problems of panic in release builds. It is essentially the Rust equivalent of assert() in C. Overflow by itself does not represent a safety issue, so we are not giving up safety by leaving the panics out of opt builds.

Rust’s Standard Library

What about using standard containers like Vec?

use std::hint::black_box;

#[no_mangle]
pub extern "C" fn hello_world() {
    let vec: Vec<u32> = Vec::new();
    black_box(vec);
}

It turns out this is also “opt no-panic” code (perhaps Vec is internally performing some arithmetic which can overflow):

But once we try to actually push elements into the Vec, we’re squarely out of no-panic Rust:

Vec does have a few APIs that will surface allocation errors instead of panicking. Theoretically, this code should be no-panic:

#![feature(vec_push_within_capacity)]

use std::hint::black_box;

#[no_mangle]
pub extern "C" fn hello_world() -> bool {
    let mut vec: Vec<u32> = Vec::new();
    if !vec.try_reserve(1).is_ok() {
        return false;
    }
    if !vec.push_within_capacity(1).is_ok() {
        return false;
    }
    black_box(vec);
    true
}

This requires the nightly compiler, but I was able to make this work as no-panic on macOS. For some reason, it did not work with the nightly compiler on Godbolt, which appears to always include the panic runtime no matter what I do, even for a trivial library. I was not able to figure out why.

The Rust standard library was not really designed to be no-panic. For example, memory allocation failure will panic in most cases. If we want to be no-panic, we will probably have to avoid most of the standard library. Realisticaly we will probably want to go fully #![no_std].

A Dance With The Optimizer

Here is another trick question: is this no-panic Rust?

#[no_mangle]
pub extern "C" fn hello_world(data: &[u8]) -> u8 {
    if data.len() < 1 {
        return 0;
    }
    data[0]
}

On one hand, the slice index operation clearly documents that it may panic. On the other hand, the docs say that this panic will only be triggered if the index is out of bounds, and we have inserted a guard to ensure that it never is. So is the panic reachable?

If we use our minds to reason about the code, we would conclude that panic is unreachable. The compiler is capable of reaching the same conclusion, but only if we run the optimizer, which can prove through a series of optimizations that the bounds check will never fail.

So this example ends up being “opt no-panic”, just like our arithmetic operation, but for an entirely different reason!

This is quite an interesting result that totally changed my thinking about Rust’s bounds checks.

My previous perspective was that Rust will insert all of these unnecessary bounds checks, bloating the code and slowing it down for no reason. But our pre-existing C code is not throwing caution to the wind and hoping for the best. Every place that we perform an index operation in C, it’s because we believe we have a proof that the index is in bounds. To avoid the bounds checks in Rust, we just need to express this proof in a way that the Rust optimizer can understand. This is what I call the “dance with the optimizer.”

A Slightly More Dangerous Dance

In the example above, the bounds check is eliminated using only safe code, but there are other cases where we might need to use unsafe code to help the optimizer know about program invariants that cannot be easily derived from the program flow.

For example, consider this (admittedly contrived) program:

pub struct S<'a> {
    data: &'a[u8],
    ofs: usize,   // Invariant: ofs < data.len()
}

impl<'a> S<'a> {
    pub fn new(data: &[u8]) -> Option<S> {
        match data.len() {
            0 => None,
            n => Some(S{data: data, ofs: n - 1}),
        }
    }

    pub fn get(&self) -> u8 {
        self.data[self.ofs]
    }
}

#[no_mangle]
pub extern "C" fn hello_world(s: &S) -> u8 {
    s.get()
}

In this program, our struct S has an invariant that the offset S::ofs will always be in bounds. This invariant effectively guarantees that the bounds check in S::get() will never fail. And we can strongly guarantee that the invariant holds, because it is enforced by our new() function which is the only code that sets these struct members.

But the optimizer isn’t capable of reasoning at this level, so it thinks that the panic is reachable, and keeps the bounds check in the program, even in opt mode:

To make this no-panic, we need to help the compiler out by reminding it that this struct invariant holds in the critical path:

use std::hint::assert_unchecked;

pub struct S<'a> {
    data: &'a[u8],
    ofs: usize,   // Invariant: ofs < data.len()
}

impl<'a> S<'a> {
    fn check_invariant(&self) {
        unsafe { assert_unchecked(self.ofs < self.data.len()) }
    }

    pub fn new(data: &[u8]) -> Option<S> {
        match data.len() {
            0 => None,
            n => {
                let s = S{data: data, ofs: n - 1};
                s.check_invariant();
                Some(s)
            }
        }
    }

    pub fn get(&self) -> u8 {
        self.check_invariant();
        self.data[self.ofs]
    }
}

#[no_mangle]
pub extern "C" fn hello_world(s: &S) -> u8 {
    s.get()
}

This makes use of std::hint::assert_unchecked, a very sharp tool for making soundness promises to the compiler. Here we use it to inform the compiler of our struct invariant. This has the desired effect of making this “opt no-panic”:

This definitely requires care; we have to be very sure that the predicate we pass to assert_unchecked is true. Luckily we can fuzz against this assertion to increase our confidence (in debug mode, assert_unchecked will panic if the condition is not true). Used judiciously, it can be a powerful tool for explicitly expressing to Rust the invariants we were relying on to make index operations safe in C.

Conclusion

No-Panic Rust is not for the faint of heart. It requires a lot of careful, detailed work, and forces you to give up some niceties of Rust, like the standard library. But if we are diligent, it can give us the performance, code size, and error reporting behavior of a C library with the extra safety that comes from Rust.

This extra safety comes from the fact that Rust will automatically insert bounds checks anywhere it cannot prove that an access is safe. This puts the burden on us to justify to the compiler in every case why the bounds check is safe to elide. In some cases this will mean detecting a bounds violation explictly and reporting the error to the caller (especially in parsers, where we do not know whether the input is valid or not). In other cases, we may know through a program invariant that the index will always be in-bounds, and we will need to communicate this invariant to Rust.

I should be clear that I have not yet attempted this technique at scale, so I cannot report on how well it works in practice. For now it is an exciting future direction for upb, and one that I hope will pay off.

To make this technique practical, we need a tool that can diagnose where a panic handler was reachable from. The main technique we used in this article (looking at binary size) does not give us any information about where a panic came from. On macOS, the -why_live linker option is perfect for this. I hope other linkers like LLD will add support for this option also. If not, a standalone tool could be written that analyzes a binary after it’s linked to find the chain of references that lead to a panic handler.

It would be nice if Rust made it easier to stay within the no-panic subset. It’s clear that writing no-panic code is not a core use case that the language focuses on, but there are many situations (embedded, Linux Kernel, etc) where we want to avoid panics. It would be nice if functions or even crates could advertise themselves as no-panic and have the compiler enforce this transitively. Changing a function from no-panic to panicking would then be an API-breaking change.

There is some interesting discussion in Enforcing no-std and no-panic during build, which links to some relevant Linux kernel mailing list threads. Another interesting thread is Negative view on Rust: panicking. ↩
If we are willing to go #![no_std], we can mitigate this code size overhead by writing our own panic handler, which we could engineer to be much smaller than the std one. This does address the code size concern, but it does not compose well, as there can only be one panic handler for an entire binary, so it doesn’t make sense for a library to provide one. ↩
Some Rust panics can technically be caught with catch_unwind, but this is full of caveats and is not designed as an error recovery mechanism. ↩
We choose cdylib instead of staticlib for this exercise, because cdylib will invoke the linker to produce a .so. This will perform a garbage-collection pass that discards unreachable code, so that we only count code that would actually get pulled in if you statically linked the library into a binary. ↩
There are some crates specifically designed to test directly for the no-panic condition, including no_panic, panic_never, and no_panics_whatsoever. None of them are ideal for our purposes (the second two are only for binaries, not libraries, and the first has to be applied to every relevant function individually), and anyway none of them are available in Godbolt. These generally work by trying to create linker errors if the panic handler is linked in. ↩
Unfortunately this does not appear to work with the nightly Rust compiler. On nightly, the resulting binary is >300Kb, indicating that the panic runtime was linked in. This seems like a regression, and I have not been able to diagnose why this is. ↩

An Ode to Header Files

Mon, 27 Jan 2025 00:00:00 +0000

C and C++ have a somewhat distinctive feature that almost no language since has decided to replicate, which is to put public API declarations into separate files called header files:

// square.h: defines public API

void SquareArray(int* p, size_t n);

// square.c: defines implementation

// Internal-only helper.
static int SquareNumber(int x) { return x * x; }

// Implementation of public API.
void SquareArray(int* p, size_t n) {
  for (size_t i = 0; i < n; i++) {
    p[i] = SquareNumber(p[i]);
  }
}

More “modern” languages almost universally choose to collapse header and source into a single file, where public functions are marked in some special way:

// Rust: functions are exported with "pub"

fn square_number(x: i32) -> i32 { x * x }

pub fn square_array(arr: &mut [i32]) {
    for i in arr.iter_mut() {
        *i = square_number(*i);
    }
}

// Java: functions are exported with "public"

class Square {
  static int squareNumber(int x) { return x * x; }

  public static void squareArray(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
      arr[i] = squareNumber(arr[i]);
    }
  }
}

I think this move away from header files is unfortunate. Separating public API declarations into their own files offers many benefits that cut to the heart of good software engineering practice. In this blog post I will articulate what these benefits are. My hope is that modern languages might consider adopting something like header files (a few do to some extent, which I will explain later).

An Obsolete Mechanism, Repurposed

You may find it strange that I would advocate for header files, given that they are effectively obsolete, at least compared to their original purpose. Header files were initially designed to solve a technical problem for the compiler, which is how to share macros and function declarations between translation units in a way that supports separate compilation.

But newer languages have convincingly demonstrated that separate compilation can be achieved without header files, and especially without the primitive and problematic paradigm of textual inclusion (via #include), which is not hygienic, meaning it can lead to namespace collisions, unbalanced scopes, and numerous other practical problems.

So why do I advocate for an obsolete language feature? Because I believe that putting a module’s public API into a separate file is a genuinely good practice on the merits. Even if the machine no longer needs us to do it, it is good for humans.

I’m arguing for an updated, “modern” version of header files. This implies two clear breaks with C and C++:

We should obviously not use textual inclusion, but instead make headers hygienic and modular, a la C++20 modules.
We should allow headers to contain precisely the parts of a module’s API that are public, no more and no less. They should contain no implementation details whatsoever

C and C++ both traditionally violate (1), but C++ has tackled this problem head-on with C++20 modules, which should theoretically solve the problem.¹

C and C++ also violate (2) in many ways. For example, C++ requires private member variables and functions to be declared in the class body (which will go into the header file for any public class), even though they are not part of the public API. Template functions also have to be defined in header files if users will instantiate them, even though the function definitions are implementation details. C and C++ both require a function to be defined in a header if you want it to be inlinable. For these reasons and others, C and C++ force a lot of implementation details into headers, which goes against my vision of what header files should be.

The Case for Header Files

The case for header files boils down to this: the split between interface and implementation is our primary tool in the struggle against software complexity. It is how we break software down into pieces that can be implemented, tested, and evolved separately from each other. A header file is a place to specify the interface contract between one component and the outside world.

The header file describes the user’s view of a software module, which is comprised of both the formal function declarations and the comments describing the semantics of those functions. Together these form the contract of the module’s API. If there is disagreement about whether a particular behavior is a bug or a feature, the header file is the contract we use to litigate what is promised vs what is not.

Without header files, where is this interface specified? It is sprinkled across a mound of implementation details. There is no way to focus specifically on the parts of the API that are public. It’s like going to a restaurant and being presented with a menu that has full recipes for each item, and trying to glean from each recipe what the dish will be like.

The public interface can be extracted from this jumble by a tool like a documentation generator, which filters out the non-public functions and methods and generates some HTML. Indeed, a tool like Javadoc or rustdoc is the closest we can get to header files in many modern languages, and this does allow us to view the public API as a unified thing.

But generated docs are not integrated into the software authoring, versioning, and review process. They aren’t source files, so you can’t easily diff, blame, or comment on changes to them during code review. You probably won’t see them in your IDE or in the GitHub source browser. Doc generators are useful, but they cannot offer a versioned record of the public API the way header files can.

Auto-Generated Headers?

One of the main objections to header files is that they violate the principle of don’t repeat yourself. A header file must be updated whenever the corresponding source file changes (if a public API was affected). This is busy work, which is tedious and a drag on developer productivity.

What if we take inspiration from doc generators and make a tool do the work for us? What if we tweaked a doc generator to spit out code instead of HTML?

Let’s take the following example in Rust:

// example.rs: a normal Rust source file.

struct Foo {
  a: i32,
  b: i32,
}

/// The Bar type.
#[repr(C)]
pub struct Bar {
  a: i32,
  pub b: i32,
}

impl Foo {
  pub fn new() -> Foo { Foo { a: 0, b: 0 } }
}

impl Bar {
  /// Constructs a new Bar.
  pub fn new() -> Bar { Bar { a: 0, b: 0 } }

  fn add(&mut self, v: i32) {
    self.a += v;
    self.b += v;
  }
}

You could imagine the compiler generating the following header file which specifies the public API:

// example.api.rs: A header file describing the public API.

// The compiler has removed all non-public APIs and all implementation.  It has
// kept the rustdoc comments, because those comments are part of the API
// contract.

/// The Bar type.
pub struct Bar {
  pub b: i32,
}

impl Bar {
  /// Constructs a new Bar.
  pub fn new() -> Bar;
}

For projects that care about ABI stability, you could even imagine the compiler generating a separate “ABI Header” file:

// example.abi.rs: A header file describing the public ABI.

// The compiler has emitted ABI information about all public APIs. We only
// need to include ABI information that is not specified in the API itself;
// this includes:
//   - struct members offsets.
//   - enum constant numbers.
//   - definitions of any function that is allowed to be inlined.
//
// Rust only supports a stable ABI for `#[repr(C)]`, so ABI information is
// only emitted for types that use the C ABI.

#[abi(size=8, align=4)]
pub struct Bar {
  #[abi(offset=4)],
  pub b: i32
}

This (hypothetical) compiler has done quite an interesting thing for us. It has extracted all aspects of our source file that are API- or ABI-impacting into a readable and parseable form. As we change the source file, we can monitor these generated header files to see if our changes affected the API or ABI.

Suppose we change Bar::a (a private member) from i32 to bool. Does it change the public API? No, because Bar::a is private, so example.api.rs will be unchanged.

Does changing Bar::a from i32 to bool change the public ABI? Again no, because padding will cause Bar::b’s offset to remain 4. So this change will not result in any diff to example.abi.rs.

But what if we changed Bar::a to i64? Then Bar::b’s offset will change to 8, which is an ABI break, and this will be reflected by a corresponding change in example.abi.rs.

This is useful information for humans, but it could also be a signal to the build system. How do we know if dependent modules need to be recompiled? Only if our API or ABI changed, which we can detect by monitoring changes to example.api.rs and example.abi.rs.²

We will want to generate these files as eagerly as possible, so we get early feedback. API headers should definitely be checked into source control, so that they are versioned and visible to code review. Checking in ABI headers will probably be overkill for projects that do not care about ABI stability.

Benefits

There are many practical examples of cases where header files help with software engineering. I will argue this case with some specific examples.

Deep Modules

In John Ousterhout’s book A Philosophy of Software Design, he argues that one of the most important design principles in software is to make modules deep, such that a relatively small interface hides a large amount of implementation.

He illustrates this point in the following diagram, which is taken from the book:

Over the years I have come to solidly agree with this principle. The best designs are ones where the ratio of interface size to implementation size is kept as low as possible. The motivation is to hide complexity, so that a user of your module does not have to see all of the implementation details.

How can we keep tabs on how deep our modules are? If we have some code open in an editor, or in a code review, how can we tell how well we are doing?

If we are using header files, the answer to this question is pretty simple: just compare the size of the header file to the size of the source file. The deepest modules will have very small header files – maybe only a single function! – and much larger source files. We should get a good feeling when our header files are small, and a sense of dread when they are large and sprawling. Big header files are a code smell.

For languages that do not use headers, it is much more difficult to eyeball how deep a module is. A deep module would be one where the public keyword appears only a few times in a file that is hundreds or thousands of lines long. But this is not easy to measure visually, and it is not easy to spot in code review.

Searching for the public keyword doesn’t even really answer the question, because a public method could be a public API of a private type, in which case it is not truly exported from the module. For example, consider the following code in Java:

class Square {
  private class Squarer {
    private int[] arr;

    // These are public methods, but on a private type, so not truly
    // part of the module's public API!
    public Squarer(int[] arr) { this.arr = arr }
    public square() {
      for (int i = 0; i < arr.length; i++) {
        arr[i] = squareNumber(arr[i]);
      }
    }
  }

  // This is the only truly public API.
  public static int squareArray(int[] arr) {
    new Squarer(arr).square();
  }
}

The public keyword shows up three times in this source file, but only one of these is actually visible outside of this file. So it is actually quite hard to gauge how deep a module is in most programming languages. With header files, it is trivial.

Software Versioning

For people who maintain software libraries, one of the key questions we have to ask is whether a given change will break users or not. Breaking changes are intrusive, because they force users to change their code.

This principle is built into versioning schemes like SemVer, which requires that any breaking API change be accompanied by a major version bump.

How can we quickly evaluate whether a given change might be breaking or not? If we are using header files, we can look at whether a given change modifies a header file or not. If no header files are changing, it guarantees that we are not changing the API contract (the change could introduce a bug that violates the API contract, but that is a separate issue). Conversely, if header files are changing, there is a high likelihood that public APIs are being either added or changed.²

As an illustration, let’s play a little game. Here are the Git diffstats for four different changes in the Protobuf repository. Two of them are breaking changes and two are not. Can you guess which is which?

$ git diff --stat 63623a688c0f4329cfe4161bbaa2666f34c2be33^ 63623a688c0f4329cfe4161bbaa2666f34c2be33
 .../main/java/com/google/protobuf/Descriptors.java | 10 +--------
 .../com/google/protobuf/util/ProtoFileUtil.java    | 21 +++++++++++++++++++
 .../google/protobuf/util/ProtoFileUtilTest.java    | 24 ++++++++++++++++++++++
 3 files changed, 46 insertions(+), 9 deletions(-)

$ git diff --stat e3cc31a12eaddcfaaa5a27c272e240b6cbd985c8^ e3cc31a12eaddcfaaa5a27c272e240b6cbd985c8
 .../com/google/protobuf/AbstractMessageLite.java   | 10 +++++++--
 .../com/google/protobuf/ProtobufArrayList.java     | 26 ++++++++++++++++++----
 2 files changed, 30 insertions(+), 6 deletions(-)

$ git diff --stat e2eb0a19aa95497c8979d71031edbbab721f5f0a^ e2eb0a19aa95497c8979d71031edbbab721f5f0a
 src/google/protobuf/util/json_util.h | 3 ---
 1 file changed, 3 deletions(-)

$ git diff --stat f549fc3ccc4ea096fcbc66f74c763880cd26e451^ f549fc3ccc4ea096fcbc66f74c763880cd26e451
 src/google/protobuf/descriptor.cc | 14 +++++---------
 1 file changed, 5 insertions(+), 9 deletions(-)

C++ has an unfair advantage in this game. When a C++ change only touches .cc files, we are guaranteed that the API contract is not changing, so we know that change #4 does not break API or ABI. When a change touches .java files, we get no hint about whether the change affects the API, implementation, or both. It turns out that change #1 is API-breaking and change #2 merely changes internal implementation details, but the Git diffstats offer no clue about this.³

Rust has tools for checking for breaking changes: I found cargo-semver-checks, cargo-public-api, and rust-semverver. These tools can be set up to run in CI workflows, and will raise errors if a public API was added or changed without a corresponding version bump. A tool like this can arguably solve the problem, without any need for header files.

But there is a price to making the API checker a separate tool. It means that people need to opt in by manually setting up the tool in their workflow, which few projects actually do. A 2023 study found that 17.2% of Rust crates have at least one semver violation. And this only counts the violations that cargo-semver-checks is able to detect; the tool is known to be incomplete and will miss some issues.

The authors of the study argue that “This is a failure of tooling, not humans”, and I agree. It is not up to humans to be perfectly diligent about API breaks, it is up to the tooling to surface these issues as conveniently as possible. What better way to do this than to make interface definition a part of the language itself, as code that can be viewed in your editor and in version control?

If you are changing a public API, you want to get this feedback as early as possible. The ideal time to get that feedback is in your source code editor, the moment when you type the change. The second-best time is when you run the compiler. The third-best time is in CI. The fourth-best time is in code review. The fifth-best time is when you go to actually perform a release. The worst time is from a user, once you have broken their build. Early feedback is key, and header files provide early feedback by surfacing API/ABI changes as file diffs at the source code editing stage.

Header files also let you view API diffs and versions using a normal git diff, rather than having to invoke a special tool. So it’s very cool that tools like cargo-semver-checks exist, but I think header files could take it to the next level by versioning the API declarations themselves.

Precompiled Libraries

Suppose you are shipping precompiled libraries (.a, .so, .dll, .dylib etc). What can you ship along with the compiled library that will describe the APIs that are contained in that library?

Header files have always been a natural fit for this, because they contain the API definition without any associated implementation. For example, let’s look at the Ubuntu package for zlib (filtering out examples and manpages):

$ dpkg -L zlib1g-dev | grep -v share
/.
/usr
/usr/include
/usr/include/zconf.h
/usr/include/zlib.h
/usr/lib
/usr/lib/aarch64-linux-gnu
/usr/lib/aarch64-linux-gnu/libz.a
/usr/lib/aarch64-linux-gnu/pkgconfig
/usr/lib/aarch64-linux-gnu/pkgconfig/zlib.pc
/usr/lib/aarch64-linux-gnu/libz.so

The header and the precompiled library are a natural pair: the header describes the API, while the .a/.so implements it.

How does one distribute precompiled libraries in a language without headers? Looking at the few languages we opened the article with:

Java: Compiled .jar files do not contain a human-readable description of the interface. You have to go looking for Javadoc somewhere, and hope it matches the version of the library you have installed.
Rust: Rust does not have a stable ABI, and therefore does not support distributing precompiled libraries. For the C ABI, you would probably just distribute a C header file.

This is another use case for header files, which can represent an API/ABI without including any implementation.

Honorable Mentions

While no modern language has fully embraced header files, there are a few that deserve partial credit.

Python & Ruby: Interface Files

Python and Ruby have both evolved some static typing infrastructure that augments the native dynamic typing of the language. As part of this trend, both languages allow you to declare APIs in a separate file from the implementation.

In Python, these are .pyi files:

# Python uses .pyi files for static API declarations.
# These are called "stub files" and are standardized in PEP 484:
#    https://peps.python.org/pep-0484/#stub-files

def square_list(ls: Sequence[int]): ...

In Ruby, these are .rbs files:

# Ruby uses .rbs files for static API declarations.
# These are known as type signatures, and are standardized in:
#    https://github.com/ruby/rbs

def square_array(arr: Array[int])

This design ticks a lot of the boxes I’m arguing for. But what it lack is completeness: there is no guarantee that all public APIs will be listed in these files. An API can be called even if it is in the source file (.py or .rb) only.

This means we do not get the guarantee we want, which is that changes affecting source files only are perfectly API-preserving.

Kotlin: `expect`/`actual`

Kotlin is aimed at cross-platform development, and it has a language feature designed to let you specify an API that will have different implementations on different platforms.

// Kotlin Common API can contain "expect" declarations, which soecify an API
// without providing any implementation.
expect fun squareArray(arr: Array<Int>)

fun squareNumber(x: Int): Int {
  return x * x;
}

// Implementation for a given platform.
actual fun squareArray(arr: Array<Int>) {
  for (i in arr.indices) {
    arr[i] = squareNumber(arr[i])
  }
}

This bears some similarity to my preferred solution. But this mechanism does not attempt to separate interface from implementation for all APIs, only for APIs that have different implementations on different platforms. APIs that define a single implementation for all platforms do not use expect and actual:

// Kotlin Common code can define function implementations without using
// `expect` or `actual`.
fun squareNumber(x: Int): Int {
  return x * x;
}

fun squareArray(arr: Array<Int>) {
  for (i in arr.indices) {
    arr[i] = squareNumber(arr[i])
  }
}

This is of course assuming that people actually adopt C++20 modules. I do not have much experience with modules myself, so I can’t guess how this will go. ↩
If we are tracking ABI, the same is also true of ABI stability: any commit that changes a foo.abi.rs file would imply an ABI break. ↩ ↩²
In reality, many non-breaking changes in C++ touch .h files, due to the shortcomings of C++ headers I described earlier. But the ideal I am arguing for does not suffer this problem, since I argue that header files should only contain public APIs. ↩

Arenas and Rust

Sun, 19 Dec 2021 00:00:00 +0000

For a while I’ve been wondering what it would be like to use arenas in Rust. In C and C++ I have been turning to arenas more and more as a fast alternative to heap allocation. If you have a bunch of objects that share a common lifetime, arenas offer cheaper allocation and much cheaper deallocation than the heap. The more I use this pattern, the more it feels downright wasteful to use heap allocation when an arena would do.

I’ve been wanting to know how arenas would play with Rust’s lifetime semantics. An arena must always outlive all the objects allocated from that arena. Rust’s lifetime system seems ideal for expressing a condition like this. I was curious to see how this plays out in practice.

Arena APIs

C and C++

First I will present the arena APIs I am familiar with in C and C++. Here is a simplified version of the C++ Arena API for protobuf:

// The C++ Arena is thread-safe (Functions taking Arena* may be called
// concurrently, except the destructor).
class Arena {
 public:
  Arena();
  ~Arena();  // Frees all objects in the arena.

  // Creates an object on the arena. The object is freed when the arena is
  // destroyed.  The destructor will be run unless it is trivial.
  template <class T, class... Args>
  static T* Create(Arena* arena, Args&&... args);
}

void Test() {
  Arena arena;
  int* i1 = Arena::Create<int>(&arena);
  int* i2 = Arena::Create<int>(&arena);
  int* i3 = Arena::Create<int>(&arena);

  // Use i1, i2, i3...

  // When the arena is destroyed, the individual objects are freed.
}

Here is a similar but somewhat different example in C, from the upb protobuf library:

// The C arena is thread-compatible, but not thread-safe (functions that take
// upb_arena* may not be called concurrently).
upb_arena *upb_arena_new(void);

// Frees all memory in the arena.
void upb_arena_free(upb_arena *a);

// Allocates so memory from the arena.
void *upb_arena_malloc(upb_arena *a, size_t size);

void test() {
  upb_arena *arena = upb_arena_new();

  int* i1 = upb_arena_malloc(arena, sizeof(*i1));
  int* i2 = upb_arena_malloc(arena, sizeof(*i2));
  int* i3 = upb_arena_malloc(arena, sizeof(*i3));

  // Use i1, i2, i3...

  upb_arena_free(arena);  // All the individual objects are freed.
}

In both the C and C++ versions, it is the user’s responsibility to make sure that arena-allocated objects are not used past the lifetime of the arena. C and C++ are not memory safe languages, and they offer no lifetime checking that would help us avoiding dangling pointers here.

Even techniques like unique_ptr can’t help us here since the objects cannot be freed independently. We could get dynamic checking by using unique_ptr with a custom deleter that decrements a refcount on the arena, and then panic if an arena is destroyed with a non-zero refcount. This would be better than nothing, but it’s still a runtime check (not compile time). In any case neither arena uses this technique at the moment, so respecting the arena’s lifetime is entirely the responsibility of the user.

The C and C++ versions above have different thread-safety properties: the C++ arena is thread-safe (concurrent allocations are allowed), while the C arena is thread-compatible (concurrent allocations are not allowed, because they access a mutable pointer). This means the C++ API is paying an efficiency/complexity overhead to allow concurrent mutable access.

Rust

The most established Rust Arena library I could find was called Bumpalo. Its API is slightly different than both of these:

pub struct Bump { /* ... */ }

impl Bump {
    pub fn new() -> Bump { /* ... */ }

    /// Allocate an object in this `Bump` and return an exclusive reference to
    /// it.
    pub fn alloc<T>(&self, val: T) -> &mut T { /* ... */ }
}

// Bump cannot be shared between threads!
impl !Sync for Bump {}

impl Drop for Bump {
    /// Frees all the objects in the arena, without calling their Drop.
    fn drop(&mut self) { /* ... */ }
}

fn Test() {
    let bump = Bump::new();

    let i1 = bump.alloc(1);
    let i1 = bump.alloc(2);
    let i1 = bump.alloc(3);

    // When bump is dropped, the integers are freed.
}

The Bump::alloc() function returns a mutable reference &mut T. Rust’s lifetime system will statically ensure that the reference doesn’t outlive the arena. We will explore some consequences of this below.

From a thread-safety perspective, Rust’s Bump is distinct from both the C and C++ arenas above. Like the C arena, Bump does not perform any internal synchronization, so it avoids the overheads of the C++ thread-safe arena. But unlike the C arena, Bump allows allocation through an immutable reference; in other words it uses “interior mutability.” To ensure that it is not used concurrently, it expressly forbids sharing between threads by being !Sync.

If we use the analysis in my previous article, Bump lives in the upper right quadrant with Cell (indeed Bump internally uses Cell, which is what prevents it from being Sync).

Why is Rust’s “Bump” not “Sync”?

An interesting question is why Bump in Rust chooses not to implement Sync. If we want to avoid synchronization overhead, our two main choices are:

Avoid interior mutability (use &mut self), and implement Sync.
Use interior mutability (use &self), and do not implement Sync (likely using Cell internally).

(1) is safe because it only mutates through a &mut reference, which is guaranteed to be unique and therefore cannot race with anything. (2) is safe because while mutation can happen from any reference, all references are bound to a single thread, so this cannot create a data race.

Bump chooses (2), but we could imagine an alternate world where it had chosen (1) instead:

pub struct SyncBump { /* ... */ }

// Alternate version of Bump that is sync, but stil avoids syncronization
// overhead:
impl SyncBump {
    pub fn new() -> Bump { /* ... */ }

    /// NOTE: takes a &mut self instead of &self.
    pub fn alloc<T>(&mut self, val: T) -> &mut T { /* ... */ }
}

Unfortunately this will not actually work. Due to a limitation in Rust’s syntax, any call to alloc() will mutably borrow SyncBump for the lifetime of the returned object. The net effect is that you can only allocate a single object from the arena at a time, a limitation so severe that it makes SyncBump useless.

This means that, for the time being, interior mutability (a la Bumpalo) is the only feasible way to implement a non-thread-safe arena in Rust.

Ergonomics of Arenas in Rust

What’s it like to use Arenas in Rust? Let’s take a simple struct that doesn’t use arenas:

struct Foo {
    str: String,
    vec: Vec,
}

fn main() {
    let foo = Foo {
        str: "ABC".to_string(),
        vec: Vec::new(),
    };
}

If we want to put the string/vec data on an arena instead, it looks like this:

use bumpalo::collections::String as BumpString;
use bumpalo::collections::Vec as BumpVec;
use bumpalo::Bump;

struct ArenaFoo<'a> {
    str: BumpString<'a>,
    vec: BumpVec<'a, i32>,
}

fn main() {
    let bump = Bump::new();
    let foo = ArenaFoo {
        str: BumpString::from_str_in("ABC", &bump),
        vec: BumpVec::new_in(&bump),
    };
}

We have to use different, arena-aware variations of containers like String and Vec. This is intended to be a temporary situation which will eventually be remedied by adding allocator support to the standard containers.

More interesting and more fundamental is that our struct now has a lifetime parameter 'a that constrains the struct in a way that the original struct was not constrained. This makes sense, as it expresses the fact that our struct must be outlived by the arena bump. Rust will require that we propagate this lifetime parameter to any other struct that contains ArenaFoo.

In my experience trying this out on a hobby project PDF parser, this all worked out reasonably well. I had to put lifetime parameters on most of my types, but it didn’t really cause a problem in my testing.

Having the compiler automatically check the lifetimes was very satisfying; it was a level of static safety checking that I have never gotten to experience in C or C++.

Hiding the lifetime parameter

Things changed once I tried to expose my parser to Python through the PyO3 Python bindings for Rust. A Rust struct exposed as a Python class through #[pyclass] cannot have type parameters. Here is my attempt at a basic “Hello, World” of exposing ArenaFoo to Python:

use pyo3::prelude::*;
use bumpalo::collections::String as BumpString;
use bumpalo::collections::Vec as BumpVec;
use bumpalo::Bump;

#[pyclass]
struct ArenaFoo<'a> {
    str: BumpString<'a>,
    vec: BumpVec<'a, i32>,
}

#[pymodule]
fn arena_test(_py: Python, m: &PyModule) -> PyResult<()> {
    Ok(())
}

The compiler rejects this:

error: #[pyclass] cannot have generic parameters: arena_test
 --> src/lib.rs:9:11
  |
9 | struct ArenaFoo<'a> {
  |           ^

This naturally led me to brainstorm how I could put my ArenaFoo<'a> inside of a struct with no lifetime constraints. This question is not specific to my problem of trying to bind to Python, it is a more general question: is it possible for a type to use arenas internally, in a way that is invisible to the user? Can we hide the lifetime parameter, so that our usage of arenas can be a purely internal concern that does not impose any extra constraints on users of the type?

My first thought was to bundle the Bump inside of the same struct, thereby guaranteeing that it will have the same lifetime:

#[pyclass]
struct ArenaFoo {
    bump: Bump,
    str: BumpString<'a>,
    vec: BumpVec<'a, i32>,
}

By itself this does nothing to convince the compiler that the 'a is unnecessary on ArenaFoo<'a>.

I asked about this on Rust’s Discord, and I was informed that this pattern is known as the “self-referential struct”, and it is notorously difficult to make sound. The problem is that str and vec would have references to bump in the steady state. Rust’s normal rules would allow anyone with &mut ArenaFoo to get &mut Bump, but this would be unsound if other members of the struct have &Bump references.

I was referred to the ouroboros and owning_ref crates, which can help users construct self-referencing structs in a reasonably sound way (I was told that both have soundness holes, but that these are apparently fixable).

Using ouroboros for self-referencing structs

With ouroboros, things were looking promising:

use pyo3::prelude::*;
use bumpalo::collections::String as BumpString;
use bumpalo::collections::Vec as BumpVec;
use bumpalo::Bump;
use ouroboros::self_referencing;

#[pyclass]
#[self_referencing]
struct ArenaFoo {
    bump: Bump,
    #[covariant]
    #[borrows(bump)]
    str: BumpString<'this>,
    #[covariant]
    #[borrows(bump)]
    vec: BumpVec<'this, i32>,
}

#[pymodule]
fn arena_test(_py: Python, m: &PyModule) -> PyResult<()> {
    Ok(())
}

However the Rust compiler threw errors:

error[E0277]: `NonNull<i32>` cannot be sent between threads safely
   --> src/lib.rs:8:1
    |
8   | #[pyclass]
    | ^^^^^^^^^^ `NonNull<i32>` cannot be sent between threads safely
    |
   ::: /Users/haberman/.cargo/registry/src/github.com-1ecc6299db9ec823/pyo3-0.14.5/src/class/impl_.rs:328:33
    |
328 | pub struct ThreadCheckerStub<T: Send>(PhantomData<T>);
    |                                 ---- required by this bound in `ThreadCheckerStub`
    |
    = help: within `SelfReferencingFoo`, the trait `Send` is not implemented for `NonNull<i32>`
    = note: required because it appears within the type `bumpalo::collections::raw_vec::RawVec<'static, i32>`
    = note: required because it appears within the type `bumpalo::collections::Vec<'static, i32>`
note: required because it appears within the type `SelfReferencingFoo`
   --> src/lib.rs:10:8
    |
10  | struct SelfReferencingFoo {
    |        ^^^^^^^^^^^^^^^^^^
    = note: this error originates in the attribute macro `pyclass` (in Nightly builds, run with -Z macro-backtrace for more info)


error[E0277]: `Cell<NonNull<bumpalo::ChunkFooter>>` cannot be shared between threads safely
   --> src/lib.rs:8:1
    |
8   | #[pyclass]
    | ^^^^^^^^^^ `Cell<NonNull<bumpalo::ChunkFooter>>` cannot be shared between threads safely
    |
   ::: /Users/haberman/.cargo/registry/src/github.com-1ecc6299db9ec823/pyo3-0.14.5/src/class/impl_.rs:328:33
    |
328 | pub struct ThreadCheckerStub<T: Send>(PhantomData<T>);
    |                                 ---- required by this bound in `ThreadCheckerStub`
    |
    = help: within `bumpalo::Bump`, the trait `Sync` is not implemented for `Cell<NonNull<bumpalo::ChunkFooter>>`
    = note: required because it appears within the type `bumpalo::Bump`
    = note: required because of the requirements on the impl of `Send` for `&'static bumpalo::Bump`
    = note: required because it appears within the type `bumpalo::collections::raw_vec::RawVec<'static, i32>`
    = note: required because it appears within the type `bumpalo::collections::Vec<'static, i32>`
note: required because it appears within the type `SelfReferencingFoo`
   --> src/lib.rs:10:8
    |
10  | struct SelfReferencingFoo {
    |        ^^^^^^^^^^^^^^^^^^
    = note: this error originates in the attribute macro `pyclass` (in Nightly builds, run with -Z macro-backtrace for more info)

The main problem here is that Bump is not Sync. This unfortunately prevents SelfReferencingFoo from being Send; a significant limitation.

For the PyO3 case, while PyO3 does allow you to specify #[pyclass(unsendable)] to indicate a class that doesn’t support Send, this will cause a runtime panic if a Python user accesses the object from a different Python thread than the one that created it. This might be ok for a library that is just for experimentation, but it would not be an acceptable limitation for a production-quality Python library.

Conclusion

Rust’s lifetime system offers the very attractive possibility of having the type system automatically check lifetimes of arena-allocated objects. And indeed, this lifetime checking worked great in the scenarios where I was able to use it.

I was able to use ouroboros to make my usage of arenas an internal concern of my type. A self-referencing struct can allow the arena to be packaged together with the references, such that we do not need to impose a lifetime parameter on users of the struct.

I was unfortunately not able to find a satisfactory solution to using arenas in Rust while supporting Send, which hampered my ability to wrap my library in Python. The combination of (1) !Sync on Bump and (2) arena-aware containers that store &Bump resulted in types that are not Send, which for my case was too big a limitation to move forward with.

This led me to conclude that, for the time being, we will need to avoid storing Bump& in any structure if we need it to support Send.

The only other idea that came to mind was to make Bump truly thread-safe. Then it could support allocation through &self but also support Sync. Protobuf’s C++ thread-safe allocator has been optimized extensively to keep the synchronization overhead low: a thread-local is used as a cache to quickly resolve to a structure specific to that arena and thread, from which allocations can happen without synchronization. There is definitely some significant complexity and a bit of overhead to this, but it is one option that could potentially solve the issue.

Thread Safety in C++ and Rust

Sat, 18 Dec 2021 00:00:00 +0000

Lately I’ve been experimenting with Rust, and I want to report some of what I’ve learned about thread-safety. I am an enthusiastic dabbler in Rust: I spend most of my time in C and C++, but I’m always looking for an excuse to learn more about Rust’s approach to the techniques I use every day in C and C++.

When studying Rust’s threading model, I came to see some correspondence between C++ and Rust terminology that I had not seen published previously. Here are my findings, which hopefully can help people with C++ background understand Rust (or vice-versa).

C++

The C++ standard does not define the term “thread-safe”, but it is common practice now within the C++ community to define it in the following way:

thread-safe: A type is thread-safe if it is is safe to invoke any of its methods concurrently. To provide this guarantee, a type must generally take some special measures to avoid data races, eg. using a mutex or atomic operations internally. This generally comes with performance and/or complexity costs, so most types will not be thread-safe.
thread-compatible: A type is thread-compatible if it is safe to invoke const methods concurrently. Any concurrent call to a non-const method must be synchronized by the caller. Most types in C++ are thread-compatible, as this guarantee comes mostly comes for free: it happens naturally for any type that is const-correct (ie. avoids mutable members or const_cast).

Thread-compatible types compose nicely and avoid synchronization overheads. Suppose you have 10 thread-compatible objects that you want to access concurrently together. You can wrap a Mutex around all 10 and pay only a single synchronization cost. If you have 10 thread-safe objects, you pay 10 separate synchronization costs as each of them perform their own internal synchronization. If you are using an object in only one thread, you may not need synchronization at all, but the thread-safe type won’t know this and will pay the cost regardless. For all of these reasons, thread-compatible types are generally preferred.

Here is an example of a thread-safe type in C++. It achieves thread-safety by using std::atomic:

// C++ Usage of thread-safe type.
#include <atomic>
#include <thread>
#include <vector>
#include <iostream>

// A very simple thread-safe type.
class ThreadSafeCounter {
 public:
  ThreadSafeCounter() : counter_(0) {}
  void Increment() { counter_.fetch_add(1); }
  int GetCount() const { return counter_; }

 private:
  std::atomic_int32_t counter_;
};

int main() {
  ThreadSafeCounter counter;
  const int n = 10;
  std::vector<std::thread> threads;

  // Spawn `n` threads that all share a single counter.
  for (int i = 0; i < n; i++) {
    threads.push_back(std::thread([&counter] {
      // Unsynchronized call of a non-const method.
      // Only safe because the type is thread-safe.
      counter.Increment();
    }));
  }
  for (auto& thread : threads) { thread.join(); }

  // This will ultimately print `n`.
  std::cout << counter.GetCount() << "\n";
  return 0;
}

Rust

Rust’s model for thread-safety has some notable differences. Rust’s thread-safety story centers around two traits:

The Sync trait indicates that a type can be safely shared between threads.
The Send trait indicates that a type can be safely moved between threads.

The Sync trait ends up mapping closely to the C++ concept of thread-compatible. It indicates that concurrent access of a type is safe, as long as neither of the concurrent operations operates on a mutable reference. Just as most types in C++ are thread-compatible, most types in Rust are Sync.

However, Rust and C++ differ far more when we talk about thread-safe types. Rust forbids shared mutable access at the language level. That means that the C++ way of modeling thread-safety won’t work at all in Rust. Even if we tried to make a Rust type that offered the C++ thread-safety guarantee, safe Rust code would never be able to take advantage of this guarantee, because the code would fail to compile.

For example, let’s try to port the C++ code above to Rust:

use std::thread;
use std::sync::atomic::{AtomicI32, Ordering};

struct ThreadSafeCounter {
    count: AtomicI32,
}

impl ThreadSafeCounter {
    fn increment(&mut self) { self.count.fetch_add(1, Ordering::SeqCst); }
}

pub fn main() {
    let n = 10;
    let mut counter = ThreadSafeCounter { count: AtomicI32::new(0) };
    let mut threads = Vec::new();
    for _ in 0..n {
        threads.push(thread::spawn( || {
            // Rust won't allow this.  We are attempting to mutably borrow
            // the same value multiple times.
            counter.increment();
        }));
    }
    for thread in threads { thread.join(); }
    println!("{}", counter.count.load(Ordering::SeqCst));
}

This fails to compile with:

error[E0499]: cannot borrow `counter` as mutable more than once at a time
  --> <source>:18:37
   |
18 |           threads.push(thread::spawn( || {
   |                        -              ^^ `counter` was mutably borrowed here in the previous iteration of the loop
   |  ______________________|
   | |
19 | |             // Rust won't allow this.  We are attempting to mutably borrow
20 | |             // the same value multiple times.
21 | |             counter.increment();
   | |             ------- borrows occur due to use of `counter` in closure
22 | |         }));
   | |__________- argument requires that `counter` is borrowed for `'static`

Because Rust fundamentally allows only a single mutable reference to any given object, we have to express the C++ concept of thread-safety in a different way.

The Rust answer to thread-safety is to allow mutation on an immutable reference. Rust calls this “interior mutability.” With one small change, the previous example compiles and works as expected:

use std::thread;
use std::sync::atomic::{AtomicI32, Ordering};

struct ThreadSafeCounter {
    count: AtomicI32,
}

impl ThreadSafeCounter {
    // increment() uses "interior mutability": it accepts an immutable
    // reference, but ultimately mutates the value.
    fn increment(&self) { self.count.fetch_add(1, Ordering::SeqCst); }
}

pub fn main() {
    let n = 10;
    let mut counter = ThreadSafeCounter { count: AtomicI32::new(0) };
    let mut threads = Vec::new();
    for _ in 0..n {
        threads.push(thread::spawn( || {
            counter.increment();
        }));
    }
    for thread in threads { thread.join(); }
    println!("{}", counter.count.load(Ordering::SeqCst));
}

As a C++ programmer, interior mutability strikes me as a bit of a fib: an operation that is in fact mutable, both logically and physically, is allowed on an immutable reference. This is very similar to mutable and const_cast in C++, which are both frowned on.

I found a nice explanation of the Rust perspective in this Stack Overflow answer:

In a way, Rust’s mut keyword actually has two meanings. In a pattern it means “mutable” and in a reference type it means “exclusive”. The difference between &self and &mut self is not really whether self can be mutated or not, but whether it can be aliased.

This helps explain the rationale behind interior mutability. When applied to a reference, “immutable” in Rust doesn’t really mean “immutable”, it means “non-exclusive.” This point is covered in more depth in another article, Accurate mental model for Rust’s reference types.

There was even a proposal several years back to rename &mut to &my, &only, or &uniq, to emphasize that the key property of such references is not that they are mutable, but that they are unique.

A type we would consider thread-safe in C++ will need to use interior mutability in Rust and implement the Sync trait. It will need to allow mutating operations to be performed through an immutable reference.

This difference is reflected in the API of the atomics we were using above:

In C++, std::atomic_int32_t::fetch_add() is a non-const operation. This makes sense, as the operation does in fact mutate the atomic. Callers have to read the documentation to know that concurrent calls to this non-const method are safe.
In Rust, std::sync::atomic::AtomicI32::fetch_add() is an immutable operation (takes a non-mut reference). This is the interior mutability “fib” (as fetch_add() will in fact mutate the atomic), but it has the benefit of expressing the the type’s thread-safety guarantee within the type system, which allows the compiler to automatically check it.

Rust has the obvious advantage of having thread-safety modeled within the type system, and checked by the compiler. Rust even allows a single type to have both thread-safe and non-thread-safe methods. An example is std::sync::Mutex, which provides both Mutex::lock(&self), a thread-safe method that locks the mutex, and Mutex::get_mut(&mut self), which allows access to the mutex’s data without any synchronization costs. If the caller holds a unique reference, synchronization is unnecessary, and Rust lets us avoid this overhead. This is all modeled within the type system and checked automatically.

Mapping between C++ and Rust terminology

The analysis above leaves us with the following mapping between terms:

C++	Rust	Example
thread-compatible	implements `Sync`	most types (eg. `Vec` or `vector`)
thread-safe	implements `Sync` with interior mutability	`AtomicI32`
thread-unsafe	doesn’t implement `Sync`	`Cell`, `RefCell` in Rust

We can also put things in quadrants like so:

	`Sync`	`!Sync`
interior mutability	thread-safe (`AtomicI32`)	thread-unsafe (`Cell`)
no interior mutability	thread-compatible (`Vec`)	thread-unsafe (`proc_macro`)

The two quadrants under !Sync are both labeled “thread-unsafe.” The C++ terminology does not distinguish between these two cases, and neither does the type system. In Rust there are interesting differences between them. With interior mutability come types like Cell and RefCell that can provide safe interior mutability by constraining the circumstances under which mutation can occur. The “no interior mutability” case here initially seems not useful, but as pointed out to me on lobste.rs, it can actually be quite useful when combined with !Send, as it allows one to create a handle to thread-local data that can only be safely used within a single thread.

Thanks to Matt Brubeck for reading a draft version of this article. Matt has an article that delves more deeply into unique vs shared references.

Parsing Protobuf at 2+GB/s: How I Learned To Love Tail Calls in C

Wed, 21 Apr 2021 00:00:00 +0000

[Note: there have been several developments in this space since this article was published. See A Tail Calling Interpreter For Python (And Other Updates) for the latest information about this technique.]

I just landed an exciting feature in the main branch of the Clang compiler. Using the [[clang::musttail]] or __attribute__((musttail)) statement attributes, you can now get guaranteed tail calls in C, C++, and Objective-C.

While tail calls are usually associated with a functional programming style, I am interested in them purely for performance reasons. It turns out that in some cases we can use tail calls to get better code out of the compiler than would otherwise be possible—at least given current compiler technology—without dropping to assembly.

Applying this technique to protobuf parsing has yielded amazing results: we have managed to demonstrate protobuf parsing at over 2GB/s, more than double the previous state of the art. There are multiple techniques that contributed to this speedup, so “tail calls == 2x speedup” is the wrong message to take away. But tail calls are a key part of what made that speedup possible.

In this blog entry I will describe why tail calls are such a powerful technique, how we applied them to protobuf parsing, and how this technique generalizes to interpreters. I think it’s likely that all of the major language interpreters written in C (Python, Ruby, PHP, Lua, etc.) could get significant performance benefits by adopting this technique. The main downside is portability: currently musttail is a nonstandard compiler extension, and while I hope it catches on it will be a while before it spreads widely enough that your system’s C compiler is likely to support it. That said, at build time you can compromise some efficiency for portability if you detect that musttail is not available.

Tail Call Basics

A tail call is any function call that is in tail position, the final action to be performed before a function returns. When tail call optimization occurs, the compiler emits a jmp instruction for the tail call instead of call. This skips over the bookkeeping that would normally allow the callee g() to return back to the caller f(), like creating a new stack frame or pushing the return address. Instead f() jumps directly to g() as if it were part of the same function, and g() returns directly to whatever function called f(). This optimization is safe because f()’s stack frame is no longer needed once the tail call has begun, since it is no longer possible to access any of f()’s local variables.

While this may seem like a run-of-the-mill optimization, it has two very important properties unlock new possibilities in the kinds of algorithms we can write. First, it reduces the stack memory from from ++O(n)++ to ++O(1)++ when making ++n++ consecutive tail calls, which is important because stack memory is limited and stack overflow will crash your program. This means that certain algorithms are not actually safe to write unless this optimization is performed. Secondly, jmp eliminates the performance overhead of call, such that a function call can be just as efficient as any other branch. These two properties enable us to use tail calls as an efficient alternative to normal iterative control structures like for or while.

This is by no means a new idea, indeed it goes back to at least 1977 when Guy Steele wrote an entire paper arguing that procedure calls make for cleaner designs than GOTO, and that tail call optimization can make them just as fast. This was one of the “Lambda Papers” written between 1975 and 1980 that developed many of the ideas underlying Lisp and Scheme.

Tail call optimization is not even new to Clang: like GCC and many other compilers, Clang was already capable of optimizing tail calls. In fact, the musttail attribute in our first example above did not change the output of the compiler at all: Clang would already have optimized the tail call under -O2.

What is new is the guarantee. While compilers will often optimize tail calls successfully, this is best-effort, not something you can rely on. In particular, the optimization will most likely not happen in non-optimized builds:

Here the tail call was compiled to an actual call, so we are back to ++O(n)++ stack space. This is why we need musttail: unless we can get a guarantee from the compiler that our tail calls will always be optimized, in all build modes, it isn’t safe to write algorithms that use tail calls for iteration. It would be a pretty severe limitation to have code that only works when optimizations are enabled.

The Trouble With Interpreter Loops

Compilers are incredible pieces of technology, but they are not perfect. Mike Pall, author of LuaJIT, decided to write LuaJIT 2.x’s interpreter in assembly rather than C, and he cites this decision as a major factor that explains why LuaJIT’s interpreter is so fast. He later went into more detail about why C compilers struggle with interpreter main loops. His two most central points are:

The larger a function is, and the more complex and connected its control flow, the harder it is for the compiler’s register allocator to keep the most important data in registers.
When fast paths and slow paths are intermixed in the same function, the presence of the slow paths compromises the code quality of the fast paths.

These observations closely mirror our experiences optimizing protobuf parsing. The good news is that tail calls can help solve both of these problems.

It may seem odd to compare interpreter loops to protobuf parsers, but the nature of the protobuf wire format makes them more similar than you might expect. The protobuf wire format is a series of tag/value pairs, where the tag contains a field number and wire type. This tag acts similarly to an interpreter opcode: it tells us what operation we need to perform to parse this field’s data. Like interpreter opcodes, protobuf field numbers can come in any order, so we have to be prepared to dispatch to any part of the code at any time.

The natural way to write such a parser is to have a while loop surrounding a switch statement, and indeed this has been the state of the art in protobuf parsing for basically as long as protobufs have existed. For example, here is some parsing code from the current C++ version of protobuf. If we represent the control flow graphically, we get something like this:

But this is incomplete, because at almost every stage there are things that can go wrong. The wire type could be wrong, or we could see some corrupt data, or we could just hit the end of the current buffer. So the full control flow graph looks more like this.

We want to stay on the fast paths (in blue) as much as possible, but when we hit a hard case we have to execute some fallback code to handle it. These fallback paths are usually bigger and more complicated than the fast paths, touch more data, and often even make out-of-line calls to other functions to handle the more complex cases.

Theoretically, this control flow graph paired with a profile should give the compiler all of the information it needs to generate the most optimal code. In practice, when a function is this big and connected, we often find ourselves fighting the compiler. It spills an important variable when we want it to keep it in a register. It hoists stack frame manipulation that we want to shrink wrap around a fallback function invocation. It merges identical code paths that we wanted to keep separate for branch prediction reasons. The experience can end up feeling like trying to play the piano while wearing mittens.

Improving Interpreter Loops With Tail Calls

The analysis above is mainly just a rehash of of Mike’s observations about interpreter main loops. But instead of dropping to assembly, as Mike did with LuaJIT 2.x, we found that a tail call oriented design could give us the control we needed to get nearly optimal code from C. I worked on this together with my colleague Gerben Stavenga, who came up with much of the design. Our approach is similar to the design of the wasm3 WebAssembly interpreter which describes this pattern as a “meta machine”.

The code for our 2+GB/s protobuf parser was submitted to upb, a small protobuf library written in C, in pull/310. While it is fully working and passing all protobuf conformance tests, it is not rolled out anywhere yet, and the design has not been implemented in the C++ version of protobuf. But now that musttail is available in Clang (and upb has been updated to use it), one of the biggest barriers to fully productionizing the fast parser has been removed.

Our design does away with a single big parse function and instead gives each operation its own small function. Each function tail calls the next operation in sequence. For example here is a function to parse a single fixed-width field. (This code is simplified from the actual code in upb; there are many details of our design that I am leaving out of this article, but will hopefully cover in future articles).

#include <stdint.h>
#include <stddef.h>
#include <string.h>

typedef void *upb_msg;
struct upb_decstate;
typedef struct upb_decstate upb_decstate;

// The standard set of arguments passed to each parsing function.
// Thanks to x86-64 calling conventions, these will be passed in registers.
#define UPB_PARSE_PARAMS                                          \
  upb_decstate *d, const char *ptr, upb_msg *msg, intptr_t table, \
      uint64_t hasbits, uint64_t data
#define UPB_PARSE_ARGS d, ptr, msg, table, hasbits, data

#define UNLIKELY(x) __builtin_expect(x, 0)
#define MUSTTAIL __attribute__((musttail))

const char *fallback(UPB_PARSE_PARAMS);
const char *dispatch(UPB_PARSE_PARAMS);

// Code to parse a 4-byte fixed field that uses a 1-byte tag (field 1-15).
const char *upb_pf32_1bt(UPB_PARSE_PARAMS) {
  // Decode "data", which contains information about this field.
  uint8_t hasbit_index = data >> 24;
  size_t ofs = data >> 48;

  if (UNLIKELY(data & 0xff)) {
    // Wire type mismatch (the dispatch function xor's the expected wire type
    // with the actual wire type, so data & 0xff == 0 indicates a match).
    MUSTTAIL return fallback(UPB_PARSE_ARGS);
  }

  ptr += 1;  // Advance past tag.

  // Store data to message.
  hasbits |= 1ull << hasbit_index;
  memcpy((char*)msg + ofs, ptr, 4);

  ptr += 4;  // Advance past data.

  // Call dispatch function, which will read the next tag and branch to the
  // correct field parser function.
  MUSTTAIL return dispatch(UPB_PARSE_ARGS);
}

For a function this small and simple, Clang gives us code that is basically impossible to beat.

upb_pf32_1bt:                           # @upb_pf32_1bt
        mov     rax, r9
        shr     rax, 24
        bts     r8, rax
        test    r9b, r9b
        jne     .LBB0_1
        mov     r10, r9
        shr     r10, 48
        mov     eax, dword ptr [rsi + 1]
        mov     dword ptr [rdx + r10], eax
        add     rsi, 5
        jmp     dispatch                        # TAILCALL
.LBB0_1:
        jmp     fallback                        # TAILCALL

Note that there is no prologue or epilogue, no register spills, indeed there is no usage of the stack whatsoever. The only exits are jmps from the two tail calls, but no code is required to forward the parameters, because the arguments are already sitting in the correct registers. Pretty much the only improvement we could hope for is to get a conditional jump for the tail call, jne fallback, instead of jne followed by jmp.

If you were looking at a disassembly of this code without symbol information, you would have no reason to know that this was an entire function. It could just as easily be a basic block from a larger function. And that, in essence, is exactly what we are doing. We are taking an interpreter loop that is conceptually a big complicated function and programming it block by block, transferring control flow from one to the next via tail calls. We have full control of the register allocation at every block boundary (well, for six registers at least), and by using the same set of parameters for each function, we eliminate the need to shuffle any values around from one call to the next. As long as the function is simple enough to not spill those six registers, we’ve achieved our goal of keeping our most important state in registers throughout all of the fast paths.

We can optimize every instruction sequence independently, and crucially, the compiler will treat each sequence as independent too because they are in separate functions (we can prevent inlining with noinline if necessary). This solves the problem we described earlier where the code from fallback paths would degrade the code quality for fast paths. If we put the slow paths in entirely separate functions from the fast paths, we can be guaranteed that the fast paths will not suffer. The nice assembly sequence we see above is effectively frozen, unaffected by any changes we make to other parts of the parser.

If we apply this pattern to Mike’s example from LuaJIT, we can more or less match his hand-written assembly with only minor code quality defects:

#define PARAMS unsigned RA, void *table, unsigned inst, \
               int *op_p, double *consts, double *regs
#define ARGS RA, table, inst, op_p, consts, regs
typedef void (*op_func)(PARAMS);
void fallback(PARAMS);

#define UNLIKELY(x) __builtin_expect(x, 0)
#define MUSTTAIL __attribute__((musttail))

void ADDVN(PARAMS) {
    op_func *op_table = table;
    unsigned RC = inst & 0xff;
    unsigned RB = (inst >> 8) & 0xff;
    unsigned type;
    memcpy(&type, (char*)&regs[RB] + 4, 4);
    if (UNLIKELY(type > -13)) {
        return fallback(ARGS);
    }
    regs[RA] += consts[RC];
    inst = *op_p++;
    unsigned op = inst & 0xff;
    RA = (inst >> 8) & 0xff;
    inst >>= 16;
    MUSTTAIL return op_table[op](ARGS);
}

The resulting assembly is:

ADDVN:                                  # @ADDVN
        movzx   eax, dh
        cmp     dword ptr [r9 + 8*rax + 4], -12
        jae     .LBB0_1
        movzx   eax, dl
        movsd   xmm0, qword ptr [r8 + 8*rax]    # xmm0 = mem[0],zero
        mov     eax, edi
        addsd   xmm0, qword ptr [r9 + 8*rax]
        movsd   qword ptr [r9 + 8*rax], xmm0
        mov     edx, dword ptr [rcx]
        add     rcx, 4
        movzx   eax, dl
        movzx   edi, dh
        shr     edx, 16
        mov     rax, qword ptr [rsi + 8*rax]
        jmp     rax                             # TAILCALL
.LBB0_1:
        jmp     fallback

The only opportunity for improvement I see here, aside from the jne fallback issue mentioned before, is that for some reason the compiler doesn’t want to generate jmp qword ptr [rsi + 8*rax]. Instead it prefers to load into rax and then follow with jmp rax. These are minor code generation issues that could hopefully be fixed in Clang without too much work.

Limitations

One of the biggest caveats with this approach is that these beautiful assembly sequences get catastrophically pessimized if any non tail calls are present. Any non tail call forces a stack frame to be created, and a lot of data spills to the stack.

#define PARAMS unsigned RA, void *table, unsigned inst, \
               int *op_p, double *consts, double *regs
#define ARGS RA, table, inst, op_p, consts, regs
typedef void (*op_func)(PARAMS);
void fallback(PARAMS);

#define UNLIKELY(x) __builtin_expect(x, 0)
#define MUSTTAIL __attribute__((musttail))

void ADDVN(PARAMS) {
    op_func *op_table = table;
    unsigned RC = inst & 0xff;
    unsigned RB = (inst >> 8) & 0xff;
    unsigned type;
    memcpy(&type, (char*)&regs[RB] + 4, 4);
    if (UNLIKELY(type > -13)) {
        // When we leave off "return", things get real bad.
        fallback(ARGS);
    }
    regs[RA] += consts[RC];
    inst = *op_p++;
    unsigned op = inst & 0xff;
    RA = (inst >> 8) & 0xff;
    inst >>= 16;
    MUSTTAIL return op_table[op](ARGS);
}

This leads to the very unfortunate:

ADDVN:                                  # @ADDVN
        push    rbp
        push    r15
        push    r14
        push    r13
        push    r12
        push    rbx
        push    rax
        mov     r15, r9
        mov     r14, r8
        mov     rbx, rcx
        mov     r12, rsi
        mov     ebp, edi
        movzx   eax, dh
        cmp     dword ptr [r9 + 8*rax + 4], -12
        jae     .LBB0_1
.LBB0_2:
        movzx   eax, dl
        movsd   xmm0, qword ptr [r14 + 8*rax]   # xmm0 = mem[0],zero
        mov     eax, ebp
        addsd   xmm0, qword ptr [r15 + 8*rax]
        movsd   qword ptr [r15 + 8*rax], xmm0
        mov     edx, dword ptr [rbx]
        add     rbx, 4
        movzx   eax, dl
        movzx   edi, dh
        shr     edx, 16
        mov     rax, qword ptr [r12 + 8*rax]
        mov     rsi, r12
        mov     rcx, rbx
        mov     r8, r14
        mov     r9, r15
        add     rsp, 8
        pop     rbx
        pop     r12
        pop     r13
        pop     r14
        pop     r15
        pop     rbp
        jmp     rax                             # TAILCALL
.LBB0_1:
        mov     edi, ebp
        mov     rsi, r12
        mov     r13d, edx
        mov     rcx, rbx
        mov     r8, r14
        mov     r9, r15
        call    fallback
        mov     edx, r13d
        jmp     .LBB0_2

To avoid this, we tried to follow a discipline of only calling other functions via inlining or tail calls. This can get annoying if an operation has multiple points at which an unusual case can occur that is not an error. For example, when we are parsing protobufs, the fast and common case is that varints are only one byte long, but longer varints are not an error. Handling the unusual case inline can compromise the quality of the fast path if the fallback code is too complicated. But tail calling to a fallback function gives no way of easily resuming the operation once the unusual case is handled, so the fallback function must be capable of pushing forward and completing the operation. This leads to code duplication and complexity.

[Update 2025-01-27]: Since this article was written, more solutions became available for solving this problem through the use of different calling conventions:

__attribute__((preserve_most)) is a calling convention we can use on our fallback functions that we perform non-tail calls to. The preserve_most attribute makes the callee responsible for preserving nearly all registers, which moves the cost of the register spills to the fallback functions where we want it. There was previously a Clang bug that led to crashes when using this attribute, but it was fixed in 2023.
__attribute__((preserve_none)) is a calling convention we can use on our tail calling functions, which frees them of the burden of preserving any registers. It also uses more registers for arguments, and uses the traditional callee-save registers first, which leads to fewer register shuffles when calling fallback functions that use the regular calling convention.

Between the two of these, I think preserve_none is a better option. It’s less intrusive, as it only needs to be added to the interpreter functions themselves, rather than every function they might call (good luck changing the calling convention on standard library functions like strlen()). So overall, I would recommend it over preserve_most.

The other major limitation is that musttail is not portable. I very much hope that the attribute will catch on, spreading to GCC, Visual C++, and other popular compilers, and even get standardized someday. But that day is far off, so what to do in the meantime?

When musttail is not available, we need to perform at least one true return, without a tail call, for every conceptual loop iteration. We have not yet implemented this fallback in upb, but I expect it will involve a macro that either tail calls to dispatch or just returns, based on the availability of musttail.

Hoare’s Rebuttal and Bubble Sort’s Comeback

Fri, 29 May 2020 00:00:00 +0000

Editor’s note: For this blog entry I welcome my friend and colleague Gerben Stavenga as a guest author.

Recently Andrei Alexandrescu published an interesting post about optimizing QuickSort using the Lomuto partition scheme. The essence of that post is that for many situations the performance of QuickSort is completely dominated by branch mispredicts and that a big speed up can be achieved by writing branchless code. This has been observed by many, and various branchless sorting routines have been proposed. Andrei observed that from the two well known QuickSort partitioning schemes Lomuto is easily implemented branchless, and this indeed performs much better for sorting small primitives. I recently experimented with similar ideas but took them in a different but interesting direction. I discovered that a hybrid of the Hoare and Lomuto schemes can deliver a large improvement even compared with branchless Lomuto. And the final surprise is that Bubble Sort takes the crown for small arrays. The key to all these wins is exploiting instruction-level parallelism and reducing dependency chains.

Basic QuickSort fundamentals

Quicksort refers to a class of algorithms for sorting an array that all share the same outline

void QuickSort(T* left, T* right) {
  if (right - left > kCutOff) {
    auto pivot = ChoosePivotElement(left, right);  // Important but not focus here
    auto p = Partition(pivot, left, right);  // The main work loop
    QuickSort(left, p);
    QuickSort(p, right);  // Tail call, ideally the largest sub-interval
  } else {
    SortSmallArray(left, right);
  }
}

Countless variations exist varying in the choice of kCutOff, choice of the sorting algorithm for the small arrays and choice of pivot element. These are important for performance but the main work QuickSort performs is done in the Partition function. There are two canonical schemes for implementing Partition: the original Hoare scheme and the Lomuto scheme. The Hoare partition scheme works by swapping elements that violate the partition property from the front of the array with elements from the back of the array, processing the array from the outside inwards converging on the partition point somewhere in the middle.

T* HoarePartition(T pivot, T* left, T* right) {
  while (left < right) {
     left = ScanForward(pivot, left, right);
     if (left == right) break;
     right = ScanBackward(pivot, left, right);
     if (left == right) break;
     swap(*left, *right);
  }
  return left;
}

In contrast the Lomuto scheme processes the array from front to back, maintaining a properly partitioned array for the elements processed so far at each step.

T* LomutoPartition(T pivot, T* left, T* right) {
  T* p = left;
  for (auto it = left; it < right; it++) {
    if (*it < pivot) {
      std::swap(*it, *p);   // Could be a self-swap
      p++;
    }
  }
  return p;
}

A remarkably simple loop, with an additional property that it’s stable with respect to the ordering of the elements smaller than the pivot. It’s easy to see that the above loop can be implemented without conditional branches. The conditional swapping can be implemented by conditional moves and the conditional pointer increase could be implemented as a unconditional p += (*it < pivot). Andrei’s blog shows the performance gain of this simple branchless loop over production quality implementations in various standard libraries.

Performance analysis of branchless Lomuto partitioning

Here I want to take the optimizations further and dive deeper into the performance analysis of sorting algorithms. When conditional branching is removed the performance of code tends to become much more stable and easier to understand, data dependencies become key. We are going to analyse the code in terms of a self explanatory pseudo-assembly code, where named variables should be thought of as CPU registers and loads/stores to memory are made explicit. In this notation the basic loop above becomes

loop:
val = Load(it)              // 1
prev_val = Load(p)          // 2
is_smaller = val < pivot    // 3
valnew = cmov(is_smaller, prev_val, val)   // 4
prev_val = cmov(is_smaller, val, prev_val) // 5
Store(it, valnew)           // 6
Store(p, prev_val)          // 7
p += is_smaller             // 8
it++                        // 9
if (it < right) goto loop

How would it run on a parallel out-of order CPU? As a first approximation we can pretend that the CPU is arbitrarily parallel, ie. it can execute unlimited instructions in parallel as long as the instructions are independent. What is important to understand is the loop carried dependency chains. They determine the minimum latency a loop could possibly run. In the above code you see that the dependency between iterations of the loop are carried by it and p. Only line 8 and 9 participate on the loop carried chain and both are single cycle instructions. So we determine that the loop could potentially run at a throughput of 1 cycle per iteration.

However this dependency analysis is not quite correct. There are also loads and stores to memory. If you store something to a certain memory address and later load from that address you must read the value of the previous store. That means loads have dependencies on stores, or at least if the address overlaps. Here it and p are dynamic values and for sure they can overlap, depicted by the dashed lines in the diagram above. So let’s add the fact that there is a dependency between the loads at line 1 and 2 on the stores of line 6 and 7.

This completely changes the game, now there is a long loop carried data dependency, lines 6 and 7 depend on lines 4 and 5, which both depend on line 3 , which depend on the loads at lines 1 and 2, which potentially depend on the stores at lines 6 and 7 of the previous iteration. If we count the cycles, we get 5 cycles for the loads (loads itself can be done in parallel), 1 cycle for the comparison, 1 cycle for the conditional move and 1 cycle for the store, hence this loop will run ~8 cycles. A far cry from the 1 cycle iterations our cursory discussion indicated.

Although it’s not possible to reorder stores and loads in general it’s essential for performance of a CPU to do so. Let’s take a simple memcpy loop

loop:
val = Load(it)
Store(it + delta, val)
it++
if (it < end) goto loop

If the load cannot be reordered with the previous store, this is a 5 + 1 = 6 cycle latency loop. However in memcpy it’s guaranteed that loads and stores never overlap. If the CPU would instead reorder, the above loop would execute with a throughput of one iteration per cycle. It’s execution would look like, ignoring the instructions needed for control flow.

val_0 = Load(it_0); it_1 = it_0 + 1;    // Cycle 1
val_1 = Load(it_1); it_2 = it_1 + 1;    // Cycle 2
val_2 = Load(it_2); it_3 = it_2 + 1;    // Cycle 3
val_3 = Load(it_3); it_4 = it_3 + 1;    // Cycle 4
// The value of the load at cycle 1 becomes available.
// From this point all instructions of the loop are executed each cycle.
val_4 = Load(it_4); it_5 = it_4 + 1; Store(val_0);    // Cycle 5
val_5 = Load(it_5); it_6 = it_5 + 1; Store(val_1);    // Cycle 6

In practice most of the stores preceding a load in the instruction stream are in fact to different addresses and it is possible to reorder loads in front of stores. Therefore CPU’s do reorder loads in front of stores, which is called speculative loading, however the effects of the load are only committed when it’s verified no store has invalidated the speculative load. If a preceding store, in effect, invalidates the load, execution is rolled back to the load and the CPU starts over. One can imagine that this is very costly and very akin to branch mispredicts. While a lot of stores and loads are to different addresses, there are also plenty of stores and loads to the same address, think about register spills for example. Therefore the CPU uses a prediction model based on instruction address to determine if a load has a dependency on previous stores. In general the CPU is pretty conservative, the cost of a wrong reordering is very high. In the code above the CPU will encounter loads from the same address as recent stores and will be hesitant to do the necessary re-ordering.

Revisiting the Lomuto partition scheme

Looking closer it’s the load from p that is problematic. The load from it is in fact always from a different address than the previous stores. Furthermore the load at p is also responsible for a lot of extra work in the loop. It is necessary as otherwise the store at p will corrupt values in the array. The values that are overwritten are values previously encountered in the scan and are those elements that are larger than the pivot. If instead we would save these values in a temporary buffer there is no need to swap.

// Distributes the elements [left, right) into begin of left and from end of
// scratch buffer 
T* DistributeForward(T pivot, T* left, T* right, T* scratch) {
  auto scratch_end = scratch + kScratchSize - 1;
  ptrdiff_t offset = 0;
  for (auto it = left; it < right; it++) {
    auto val = *it;
    bool is_larger = val >= pivot;
    auto dst = is_larger ? scratch_end : it;
    dst[offset] = val;
    offset -= is_larger;
  }
  return right + offset;
}

T* ModifiedLomutoPartition(T pivot, T* left, T* right, T* scratch) {
  auto p = DistributeForward(pivot, left, right, scratch);
  // To complete the partition we need to copy the elements in scratch
  // to the end of the array.
  auto size = right - p;
  memcpy(p, scratch + kScratchSize - size, size * sizeof(T));
  return p;
}

This is a much simpler loop, only one load and one store per iteration. More importantly the load will never clash with a previous store. This loop runs much faster than the original loop, it’s not 1 cycle per iteration but 2.5 cycles on my machine. This is indicative that it’s saturating the ILP of the CPU. Unfortunately the above code is not in-place anymore, it requires O(n) additional memory for the scratch buffer.

The elegant hybrid

If instead we use a smallish fixed size temporary buffer, we can still use the above code except we need to abort when the fixed buffer is full. What do we do then? The function returned the partition point p where it left the loop. At this point [left, p) have the correct elements smaller than pivot at the front of the array. The scratch buffer is full with elements larger or equal to pivot and [p, p + kScratchSize) contains information we don’t need anymore. The idea is that we can do the same algorithm but backwards, we can use [p, p + kScratchSize) as a temporary buffer. Notice how DistributeForward() fills the scratch buffer from back to front; the backwards version would fill the scratch from front to back. So performing DistributeBackwards() using the interval [p, p + kScratchSize) as scratch will neatly pack all smaller elements encountered to the correct place. This continues until the scratch space is full, but now a new scratch space at the end of the array opened up. Wait, this looks like Hoare’s algorithm but hybridized with the Lomuto-inspired distribute function.

T* ModifiedHoarePartition(T pivot, T* left, T* right, T* scratch) {
  auto pleft = DistributeForward(left, right, pivot, scratch);
  if (right - pleft <= kScratchSize) {
    auto size = right - pleft;
    std::memcpy(pleft, scratch + kScratchSize - size, size * sizeof(T));
    return pleft;
  }
  left = pleft + kScratchSize;
  T* res;
  while (true) {
    right = DistributeBackward(left, right, pivot, left - kScratchSize)
        - kScratchSize;
    if (right <= left) {
      res = right;
      break;
    }
    left = DistributeForward(left, right, pivot, right) + kScratchSize;
    if (right <= left) {
      res = left - kScratchSize;
      break;
    }
  }
  std::memcpy(res, scratch, kScratchSize * sizeof(T));
  return res;
}

What we are ending up with is an in-place algorithm that’s almost branchfree. The precise number of iterations in the modified Lomuto partitioning scheme depend on the outcome of the comparisons and will be difficult to predict exactly right. However the loop is guaranteed to iterate at least kScratchSize times. This basically amortises the cost of branch mispredictions over many elements making them irrelevant for performance. I consider this to be a truly elegant design.

Fallback for sorting short arrays

The next step is the fallback for short arrays where the overhead of recursion starts dominating. In the literature insertion sort is most often recommended together with countless micro-optimizations applied. I found that at this point partitioning was so fast that QuickSort beat insertion sort all the way down to just a few elements. The problem is that insertion sort has unpredictable branches, basically 1 miss per insert. The solution is Bubble sort. Bubble sort has a very predictable access pattern and the swap can be implemented branchless. A little more optimizing you discover you don’t need a swap. One can keep the maximum in register and store the minimum.

void BubbleSort(T* arr, size_t n) {
  for (size_t i = n; i > 1; i--) {
    auto max = arr[0];
    for (size_t j = 1; j < i; j++) {
      auto y = arr[j];
      arr[j - 1] = (max <= y ? max : y);
      max = (max <= y ? y : max);
    }
    arr[i - 1] = max;
  }
}

In the above inner-loop max is the variable that participates on the longest loop carried data chain, with a compare and conditional move on it. This makes the above loop execute in 2 cycles per iteration. However we can do better. If instead of bubbling the max, we’re bubbling up the two largest elements we only need to iterate the bubbling stage ++n/2++ times, instead of ++n++ times. It turns out that using a clever implementation one can bubble two elements in the same 2 cycles.

void BubbleSort2(T* arr, size_t n) {
  for (size_t i = n; i > 1; i -= 2) {
    auto x = arr[0];
    auto y = arr[1];
    if (y < x) std::swap(x, y);
    for (size_t j = 2; j < i; j++) {
      auto z = arr[j];
      bool is_smaller = y <= z;
      auto w = is_smaller ? y : z;
      y = is_smaller ? z : y;
      is_smaller = x <= z
      arr[j - 2] = (is_smaller ? x : z);
      x = is_smaller ? w : x;
    }
    arr[i - 2] = x;
    arr[i - 1] = y;
  }
}

The benchmarks verify that indeed this makes a difference.

BM_SmallSort<exp_gerbens::BubbleSort>/2            2 ns          2 ns  400700000
BM_SmallSort<exp_gerbens::BubbleSort>/8            5 ns          5 ns  155200000
BM_SmallSort<exp_gerbens::BubbleSort>/32          14 ns         14 ns   52600000
BM_SmallSort<exp_gerbens::BubbleSort2>/2           1 ns          1 ns  514500000
BM_SmallSort<exp_gerbens::BubbleSort2>/8           3 ns          3 ns  256700000
BM_SmallSort<exp_gerbens::BubbleSort2>/32          9 ns          9 ns   78400000
BM_SmallSort<InsertionSort>/2                      4 ns          4 ns  183600000
BM_SmallSort<InsertionSort>/8                     11 ns         11 ns   63500000
BM_SmallSort<InsertionSort>/32                    17 ns         17 ns   42000000

In fact it’s possible to generalize this, one can bubble up the top ++N++ in constant cycles per iteration in the model where the CPU has arbitrary ILP.

Bringing it all together

What are the results? The results are nothing short of spectacular. The following is a simple benchmark on sorting 100000 int’s. The time is normalized by the number of elements, so it’s the amount of time spent per element. I’m using clang + libc++ here, as gcc is dramatically worse in emitting branch free code.

CPU: Intel Skylake Xeon with HyperThreading (36 cores) dL1:32KB dL2:1024KB dL3:24MB
Benchmark                         Time(ns)        CPU(ns)     Iterations
------------------------------------------------------------------------
BM_Sort<std_sort>                       51.6           51.6     10000000
BM_Sort<std_stable_sort>                65.6           65.6     10000000
BM_Sort<lib_qsort>                      90.4           90.5      7800000
BM_Sort<andrei_sort>                    32.6           32.6     21500000
BM_Sort<exp_gerbens::QuickSort>         16.4           16.4     43200000

We’re talking about a 2x win over Andrei’s implementation as copied from his github. The code is available at my GitHub, although it doesn’t contain benchmarks for the code as published by Andrei as it didn’t contain a license.

We’ve seen how crucial it is to understand data dependencies in order to optimize code. Especially hidden memory dependencies between load and stores can greatly influence performance of work loops. Understanding the data dependency graph of code is often where the real performance gains lie, yet very little attention is given to it in the blogosphere. I’ve read many articles about the impact of branch mispredictions, importance of data locality and caches, but much less about data dependencies. I bet that a question like “why are linked lists slow?” is answered by many in terms of locality, caches or unpredictable random memory access. At least I’ve heard those reasons often, even Stroustrup says as much. Those reasons can play a part, but it’s not the main reason. Fundamentally iterating a linked list has a load-to-use on the critical path, making it 5 times slower than iterating a flat array. Furthermore accessing flat arrays allow loop unrolling which can further improve ILP.

Why is QuickSort fast compared to merge and heap sort?

This brings us to answer why QuickSort is fast compared to other sorts with good or even better theoretical complexity. It’s all about data dependencies. The quick sort partition loop above demonstrates a distinctive feature. The element it will process next does not depend on the outcome of the comparisons in previous iterations. Compare this to merge sort. In merge sort the two head elements are compared, however the next elements that need to be compared depend on the outcome of this comparison. It’s trivial to implement merge sort branch free. It will look like

val1 = Load(left + k - right_idx)  // 1
val2 = Load(right + right_idx)
is_smaller = val2 < val1   // 2
tmp = cmov(is_smaller, val2, val1)
Store(out + k, tmp);
k++;
right_idx += is_smaller  // 3

This is about 8 cycles per iteration to update right_idx, we have a load and non-trivial indexing at line 1 (6 cycles), and line 2 and 3 both being 1 cycle. Similar analysis holds for heap sort, restoring the heap property requires comparing the two children and recurse on the subtree of the biggest child.

left = Load(2 * idx)
right = Load(2 * idx + 1)
is_smaller = left < right
tmp = cmov(is_smaller, right, left)
Store(idx, tmp);
idx = 2 * idx + is_smaller

Again this is 8 cycles on the loop carried data chain. This goes to the heart of the matter of why QuickSort is fast even though theoretically it has inferior behavior compared to heap and merge sort. By construction heap and merge sort divide the data very evenly in the implied tree structure, the heap structure is a binary tree of minimum depth as is the recursive subdivision that merge sort performs. This means that the number of comparisons they do is ++n \lg(n)++ which tightly hugs the information theoretical lower bound of ++\lg(n!)++.

In contrast, QuickSort bets on obtaining a reasonably balanced tree with high probability. The bits of information extracted from a comparison with the pivot depends on its rank in the array. Only pivots that are close to the median will result in obtaining 1 bit of information per comparison. Solving the recurrence equation of QuickSort with a uniform pivot choice, gives ++2n \ln{n}++ as the number of comparisons on average. Hence QuickSort does a factor ++2 \ln(2) = 1.4++ more comparisons than heap sort or merge sort on average, or equivalently more iterations in the inner work loop. However the enormous speed difference in the basic work loop more than compensates for this information theoretical factor.

Also, when partitioning big arrays spending a little amount of work improving the choice of pivot by a median of three brings this factor down to ~1.2. Further improvements can get this factor rather close to 1. The main point here is that this factor is dominated by the differences in throughput of the work loop.

We can significantly speed up merge sort with a simple trick. Due to the large dependency chain, merge sort loop runs at a very low IPC. This basically means we can add more instructions for free. In particular merge sort has a backwards equivalent. We can merge forward and backward in a single loop while keeping the latency of the loop body the same. It also eliminates an awkward exit condition as now you can unconditionally iterate n/2 times. This reduces the number of iterations roughly by 2x.

BM_Sort<exp_gerbens::QuickSort>                       10.7           10.7     65011712
BM_MergeSort<MergeSort>                               23.4           23.4     29884416
BM_MergeSort<MergeSortDouble>                         13.2           13.2     52756480

Another trick is preloading values for the next iteration,

next_val1 = Load(left + k - right_idx + 1)
next_val2 = Load(right + right_idx + 1)
is_smaller = val2 < val1
tmp = cmov(is_smaller, val2, val1)
val1 = cmov(is_smaller, val1, next_val1)
val2 = cmov(is_smaller, next_val2, val2)
Store(out + k, tmp);
k++;
right_idx += is_smaller

You see that in a single iteration the increase of right_idx does not depend on a load as val1 and val2 are already available at the start of the iteration. Over two iterations one can see that right_idx depends on itself. This chain is ~8 cycles long but spread over 2 iterations which gives a throughput of ~4 cycles per iteration. Combining these two tricks could lead to merge sort on par with the simple partition loop of QuickSort. However it’s just a mitigation. If instead of sorting a simple primitive value we would sort pointers to a struct. The comparison operator would have an extra load which immediately adds to the critical path. QuickSort is immune to this, even rather costly comparisons do not influence the ability to make progress. Of course if the comparison itself suffers from frequent branch misses, then that will limit the ability to overlap different stages of the iteration in the CPU pipeline.

A lot of thanks to Josh for discussions, helpful suggestions, his insights and for providing space on his blog for this post.

Discuss this article on Hacker News.

Optimizing UTC → Unix Time Conversion For Size And Speed

Tue, 12 May 2020 00:00:00 +0000

How do you convert a UTC timestamp to Unix Time (seconds since the epoch)?

 "2020-04-29 04:48:15" → 1588135695

Of course the right answer is “you use a standard library function.” But what if you don’t have one available? Or what if you’re the person implementing that library?

Converting the time portion is trivial. Unix Time pretends that leap seconds do not exist and makes every day exactly 86,400 seconds long. This is a fib on systems that implement UTC leap second insertion¹, but it makes the algorithm very simple:

time_t hms_to_time(int h, int m, int s) {
  return (h * 3600) + (m * 60) + s;
}

But the calendar part is more challenging. Months have unequal lengths, and leap years complicate everything. Leap years insert an extra day at the end of February whenever:

the year is divisible by four
excluding years divisible by 100
but including years divisible by 400

Surprisingly, no version of C includes a UTC → Unix Time conversion function in the standard library. There is a non-standard function timegm(), but its use is discouraged. The Linux manpage says:

  These functions are nonstandard GNU extensions that are also present
  on the BSDs.  Avoid their use.

And on BSD:

  The timegm() function is not specified by any standard; its function
  cannot be completely emulated using the standard functions described above.

I needed an algorithm to perform this UTC→UnixTime conversion for the JSON parser in upb. The JSON mapping for Protocol Buffers says that timestamps are formatted using strings like:

1972-01-01T10:00:20.021Z

Once we have parsed the individual numbers out of such a timestamp string, we need a way of translating to seconds since the Unix Epoch, which is the internal representation of the google.protobuf.Timestamp type.

Since upb is written in C and intended to be portable, I needed to roll my own. Since upb aims to be as small and fast as possible, I became very interested in the problem of how far this algorithm could be pushed in size and speed.

A Fortran Solution from 1968

Several leads pointed me to a Letter to the Editor published in Communications of the ACM in October 1968 (Volume 11, Number 10). In this letter Henry F. Fliegel and Thomas C. Van Flandern offered the following Fortran function for performing this conversion. This function uses integer math (all divisions round down):

JD (I, J, K) = K - 32075 + 1461*(I + 4800 + (J - 14)/12)/4
        + 367*(J - 2 - (J - 14)/12*12)/12 - 3
             *((I + 4900 + (J - 14)/12)/100)/4

JD here refers to the Julian Date, the number of days that have passed since the Julian Date Epoch. This epoch is very long ago, in 4713 BC, but it’s a simple matter to convert it to the Unix epoch of 1970-01-01 by subtracting 2440588, the Julian Day number of the Unix Epoch. The variables I, J, and K are the year, month, and day, respectively.

Once we have mapped a Y/M/D to a total number of days, it is easy to multiply this by 86,400 seconds and add hms_to_time() to get a full Unix Time result.

The function above is remarkable. It does not use any lookup table, and yet it somehow encodes the irregular pattern of month lengths and leap year rules. It is trivial to convert this Fortran function to C using the int data type, which also rounds down for positive numbers (the algorithm ensures that all numbers being divided are positive, as long as year >= -4800).

Improving Readability With A Lookup Table

In the interest of having an algorithm that is easier to understand than the Fortran algorithm above, I wrote the following algorithm for upb’s old JSON parser. All of the general techniques used here are published in various places, I just condensed them into the smallest and simplest algorithm I could. This uses the Unix epoch instead of a Julian Day.

/* https://github.com/protocolbuffers/upb/blob/22182e6e/upb/json/parser.rl#L1697
 * epoch_days(1970, 1, 1) == 1970-01-01 == 0 */
int epoch_days_table(int year, int month, int day) {
  static const uint16_t month_yday[12] = {0,   31,  59,  90,  120, 151,
                                          181, 212, 243, 273, 304, 334};
  uint32_t year_adj = year + 4800;  /* Ensure positive year, multiple of 400. */
  uint32_t febs = year_adj - (month <= 2 ? 1 : 0);  /* Februaries since base. */
  uint32_t leap_days = 1 + (febs / 4) - (febs / 100) + (febs / 400);
  uint32_t days = 365 * year_adj + leap_days + month_yday[month - 1] + day - 1;
  return days - 2472692;  /* Adjust to Unix epoch. */
}

This algorithm uses a lookup table to determine the number of days for each month. Like the Fortran algorithm, it requires that division rounds down. But C rounds towards zero² so like the Fortran algorithm above, we start by adding 4800 so the year is always positive.

This algorithm is nice and readable. It is small and fast. There is only one noticeable downside if we are being performance-obsessed: it relies on a lookup table, which adds a bit of latency in the best case, or a lot of latency if the lookup table is not in cache.

Eliminating the Lookup Table

More recently I came across the following algorithm published by Howard Hinnant. Like the Fortran algorithm, it avoids the lookup table. But its logic is a bit easier to follow, and Howard includes an extensive explanation for how it works.

// Returns number of days since civil 1970-01-01.  Negative values indicate
//    days prior to 1970-01-01.
// Preconditions:  y-m-d represents a date in the civil (Gregorian) calendar
//                 m is in [1, 12]
//                 d is in [1, last_day_of_month(y, m)]
//                 y is "approximately" in
//                   [numeric_limits<Int>::min()/366, numeric_limits<Int>::max()/366]
//                 Exact range of validity is:
//                 [civil_from_days(numeric_limits<Int>::min()),
//                  civil_from_days(numeric_limits<Int>::max()-719468)]
template <class Int>
constexpr
Int
days_from_civil(Int y, unsigned m, unsigned d) noexcept
{
    static_assert(std::numeric_limits<unsigned>::digits >= 18,
             "This algorithm has not been ported to a 16 bit unsigned integer");
    static_assert(std::numeric_limits<Int>::digits >= 20,
             "This algorithm has not been ported to a 16 bit signed integer");
    y -= m <= 2;
    const Int era = (y >= 0 ? y : y-399) / 400;
    const unsigned yoe = static_cast<unsigned>(y - era * 400);      // [0, 399]
    const unsigned doy = (153*(m + (m > 2 ? -3 : 9)) + 2)/5 + d-1;  // [0, 365]
    const unsigned doe = yoe * 365 + yoe/4 - yoe/100 + doy;         // [0, 146096]
    return era * 146097 + static_cast<Int>(doe) - 719468;
}

This algorithm replaces the month lookup table with the clever expression:

  DayOfYear(adjusted_month) = (153 * adjusted_month + 2) / 5

This formula describes a line with slope of 153/5, or 30.6, which is between 30 and 31 days in each month. But it is cleverly chosen to exploit truncating integer division to step in the same pattern that months do.

My colleague Gerben Stavenga realized that there are many such expressions of this form that will calculate the same value. If we use a variant where the divisor is a power of two, the compiler can optimize the division to a right shift. Specifically we can use:

  DayOfYear(adjusted_month) = (62719 * adjusted_month + 769) / 2048

With some help from Gerben I arrived at this formulation for the current version of upb:

/* https://github.com/protocolbuffers/upb/blob/22182e6e/upb/json_decode.c#L982
 * epoch_days_fast(1970, 1, 1) == 1970-01-01 == 0. */
int epoch_days_fast(int y, int m, int d) {
  const uint32_t year_base = 4800;    /* Before min year, multiple of 400. */
  const uint32_t m_adj = m - 3;       /* March-based month. */
  const uint32_t carry = m_adj > m ? 1 : 0;
  const uint32_t adjust = carry ? 12 : 0;
  const uint32_t y_adj = y + year_base - carry;
  const uint32_t month_days = ((m_adj + adjust) * 62719 + 769) / 2048;
  const uint32_t leap_days = y_adj / 4 - y_adj / 100 + y_adj / 400;
  return y_adj * 365 + leap_days + month_days + (d - 1) - 2472632;
}

Note that the although this algorithm has some ternary operators, it compiles into fully branchless code with one cmov in it. In fact, all the algorithms given in this article compile to branchless code (on x86-64 using recent versions of Clang).

Semantics and Correctness

Before we compare these algorithms for size and speed, a few notes about their semantics and correctness.

Supported Input Range

I verified all the algorithms in this article across a wide range of dates (-4712-01-01 to 22666-12-20, or Julian Date 1 to 10,000,000). For every day in this range I checked that the outputs match each other, and that they match the results of timegm(). There was a snag on macOS, as its timegm() function fails for all years prior to 1900, so I disabled it for those years.

The interval [-4712, 22666] is a very wide range of years, and likely to be far beyond what is needed in practice. That said, these algorithms effectively support much wider bounds than this. All of them support to at least the date 1000000-01-01 (year 1 Million).

Most of the algorithms given here use the year -4800 as their base, and will return incorrect results for years before that. However the days_from_civil() algorithm is coded to support over 10 million years into the past (assuming 32-bit integers). I think any of these algorithms could likely be adjusted to support whatever window of years is desired. The year -4800 is frequently chosen as a base out of convention, as it is before the Julian Day epoch, which is before any recorded historical events.

Input Normalization

Unlike the algorithms in this article, the timegm() function normalizes its input. For example, if you pass a month of -1 to timegm(), that indicates December of the previous year. The algorithms given here can return incorrect results if the month is out of range, or can even crash with out-of-bounds array access if you are using the epoch_days_table() function. So any normalization/checking of the month value must happen prior to calling the function.

Similarly timegm() will write the normalized values back to the input struct tm, including tm_yday (day of year) and tm_wday (day of week) values that it calculated from the day, month, and year. The algorithms in this article do not calculate day of week or day of year.

I did not need these features for my use case, so for me these represent unnecessary overhead. But it is worth noting that this is not a completely apples-to-apples comparison. It could be an interesting exercise to add these features so that the algorithms given here could be a drop-in replacement for timegm().

Leap Seconds

When we use the hms_to_time() function above, these algorithms return correct results around leap seconds. The primary test case for this is to verify:

  UnixTime(1998, 12, 31, 23, 59, 60) -> 915148800
  UnixTime(1999,  1,  1,  0,  0,  0) -> 915148800

These values follow the table given in the Wikipedia Article about Unix Time around leap seconds. These algorithms handle leap seconds correctly without any special code. The correct answers for seconds=60 fall out of the algorithm “for free”, as we are simply summing seconds.

Size and Speed Benchmarks

Here are microbenchmarks of the algorithms above, using the google/benchmark framework. Code for these benchmarks is available here.

I added the hms_to_time() code to each algorithm so they would be more comparable to the timegm() function. I also put the functions in a separate .cc file from the benchmark loop so that they could not be inlined, to make the comparison with libc more fair. I also translated the 1968 algorithm from Fortran into C++.

On my Linux Desktop i7-8700K with glibc 2.30, I get:

Running bazel-bin/date-algorithms
Run on (12 X 4700 MHz CPU s)
CPU Caches:
  L1 Data 32K (x6)
  L1 Instruction 32K (x6)
  L2 Unified 256K (x6)
  L3 Unified 12288K (x1)
------------------------------------------------------------------
Benchmark                           Time           CPU Iterations
------------------------------------------------------------------
BM_YMDToUnix_Fortran                5 ns          5 ns  148069867
BM_YMDToUnix_Table                  2 ns          2 ns  288071123
BM_YMDToUnix_DaysFromCivil          4 ns          4 ns  176474060
BM_YMDToUnix_Fast                   3 ns          3 ns  269155478
BM_timegm_libc                     46 ns         46 ns   15360235

All of the algorithms from this article are in the same general ballpark. The algorithm in libc is noticeably slower.

On my Mac Laptop running macOS 10.15.4, the disparity is even more stark:

Running bazel-bin/date-algorithms
Run on (12 X 2600 MHz CPU s)
CPU Caches:
  L1 Data 32K (x6)
  L1 Instruction 32K (x6)
  L2 Unified 262K (x6)
  L3 Unified 9437K (x1)
------------------------------------------------------------------
Benchmark                           Time           CPU Iterations
------------------------------------------------------------------
BM_YMDToUnix_Fortran                6 ns          6 ns  116857534
BM_YMDToUnix_Table                  3 ns          3 ns  213395767
BM_YMDToUnix_DaysFromCivil          5 ns          5 ns  147238851
BM_YMDToUnix_Fast                   3 ns          3 ns  211537241
BM_timegm_libc                   5421 ns       5413 ns     122749

I looked at a profile and cross-referenced the Darwin code in localtime.c. It appears that almost all of the time is attributable to the gmtsub() function, of which about 70% is mutex lock/unlock to lazily load time zone data for the “GMT” time zone. The timesub() function appears to take most of the remainder.

It is surprising that a lock would add this much overhead, as Jeff Dean’s Latency Numbers Every Programmer Should Know tells us to expect only 25ns for a mutex lock/unlock. Note that the benchmarks above are single-threaded; under contention timegm() on macOS degrades even more, while the others are unaffected (as they do not access any global state):

Running bazel-bin/date-algorithms
Run on (12 X 2600 MHz CPU s)
CPU Caches:
  L1 Data 32K (x6)
  L1 Instruction 32K (x6)
  L2 Unified 262K (x6)
  L3 Unified 9437K (x1)
----------------------------------------------------------------------------
Benchmark                                     Time           CPU Iterations
----------------------------------------------------------------------------
BM_YMDToUnix_Fortran/threads:6                1 ns          6 ns  119878410
BM_YMDToUnix_Table/threads:6                  1 ns          3 ns  206599374
BM_YMDToUnix_DaysFromCivil/threads:6          1 ns          5 ns  139911858
BM_YMDToUnix_Fast/threads:6                   1 ns          3 ns  208116546
BM_timegm_libc/threads:6                  14795 ns      86855 ns       8178

YMDToUnix_Table and YMDToUnix_Fast are basically tied, though as mentioned before the table-based algorithm can slow down drastically (on the order of 100ns) if the table is not in cache, and is vulnerable to crashes if the month is out of range.

For size profiling I used my tool Bloaty McBloatface. I display VM size only, so we see the parts of the binary that will actually be loaded into memory:

$ bloaty -d symbols,sections '--source-filter=^YMD|yday' --domain=vm \
  bazel-bin/date-algorithms
     VM SIZE
 -------------- 
1%     236    YMDToUnix_Fortran()
4%     204    .text
2%      24    .eh_frame
4%       8    .eh_frame_hdr
7%     210    YMDToUnix_DaysFromCivil()
0%     170    .text
2%      32    .eh_frame
8%       8    .eh_frame_hdr
0%     152    YMDToUnix_Fast()
9%     120    .text
8%      24    .eh_frame
3%       8    .eh_frame_hdr
1%     137    YMDToUnix_Table()
6%     105    .text
5%      24    .eh_frame
8%       8    .eh_frame_hdr
2%      24    epoch_days_table()::month_yday
0%      24    .rodata
0%     759    TOTAL
Filtering enabled (source_filter); omitted  128Ki of entries

All these functions have nearly the same .eh_frame overhead (this is unwind information, used for debugging and stack traces), so we can set that aside. When we account for the table size, YMDToUnix_Fast ends up smallest, narrowly beating YMDToUnix_Table. But these differences are very minor. All of these algorithms are very small and fast.

UTC days tick 86,401 seconds whenever a leap second occurs. Maintaining the fib that every day is 86,400 seconds long requires Unix Time to be discontinuous around a leap second. To avoid this complication, some systems have started “smearing” seconds around the leap second instead, so that every day is still exactly 86,400 seconds long, and it’s merely the length of each second that changes. This deviates from UTC, but solves lots of practical problems. ↩
Round-to-zero was standardized in C99. Before that the results for negative numbers were implementation-defined). ↩

Bloaty McBloatface 1.0

Tue, 07 Aug 2018 00:00:00 +0000

Today I am releasing Bloaty McBloatface 1.0. Bloaty is a size profiler for binaries. It helps you peek into ELF/Mach-O binaries to see what is taking up space inside.

Bloaty has gotten lots new features, bugfixes, and overall improvements since I announced it in 2016. I listed these changes briefly on the release page, but I wanted to go into a bit more detail here.

Improving Data Quality

Perhaps the biggest overall improvement to Bloaty is its data quality. When I first announced Bloaty, I got very understandable complaints like this one:

I ran it and it gives an awful lot of “[None]”:

    $ ~/d/bloaty/bloaty builder/virt-builder -d compileunits
         VM SIZE                            FILE SIZE
     --------------                      --------------
      75.5%  1.96Mi [None]                3.67Mi  85.2%
       8.7%   232Ki guestfs-c-actions.c    232Ki   5.3%
       8.2%   219Ki guestfs.ml             219Ki   5.0%
       2.0%  52.4Ki [Other]               52.4Ki   1.2%
       1.3%  33.7Ki _none_                33.7Ki   0.8%
       0.7%  17.5Ki customize_cmdline.ml  17.5Ki   0.4%
       0.6%  17.3Ki builder.ml            17.3Ki   0.4%
       0.4%  11.8Ki customize_run.ml      11.8Ki   0.3%
       0.4%  10.4Ki cmdline.ml            10.4Ki   0.2%
       0.3%  7.08Ki firstboot.ml          7.08Ki   0.2%
       0.2%  6.21Ki index-scan.c          6.21Ki   0.1%
       0.2%  5.90Ki index_parser.ml       5.90Ki   0.1%
       0.2%  5.15Ki sigchecker.ml         5.15Ki   0.1%
       0.2%  4.87Ki getopt-c.c            4.87Ki   0.1%
    [...]

It’s a mixed OCaml/C executable, but I ran it on a build from the local directory and all debug symbols are still available.

Indeed, a profiler tool that has no idea what to say about 85.2% of the binary is not going to be very useful. This was Bloaty’s biggest weakness when I first released it.

At first I misunderstood the nature of this problem. Bloaty’s design at the time was simple: it was reading .debug_aranges to assign ranges of the binary to compilation units. DWARF’s .debug_aranges section is an {address range -> compileunit} map that debuggers use to decide what compile unit a given function or data variable is from, given its address.

The output above indicates that .debug_aranges was only covering about 15% of the binary. What gives? My theory at the time was that .debug_aranges should theoretically be covering the whole binary, but was pretty incomplete for some reason. It seemed like a compiler problem that I was going to have to work around somehow.

Later I realized that .debug_aranges is only meant for identifying addresses of functions or data. Large portions of the binary are not functions or program data! For example, ELF/Mach-O binaries have all sort of stuff in them like:

symbol tables
relocations
debug information
unwind information

To get better results, I needed to find a way to break down these sections. I needed to determine which parts of the unwind information, for example, I could attribute to each function.

To achieve this, I had to parse the binary more thoroughly than I had before. I had to learn to parse unwind information (.eh_frame and .eh_frame_hdr sections), which is a really esoteric and low-level thing to be doing. I’ll quote my comment in the code about how tricky this is to do correctly:

// Code to read the .eh_frame section.  This is not technically DWARF, but it
// is similar to .debug_frame (which is DWARF) so it's convenient to put it
// here.
//
// The best documentation I can find for this format comes from:
//
// * http://refspecs.linuxfoundation.org/LSB_5.0.0/LSB-Core-generic/LSB-Core-generic/ehframechpt.html
// * https://www.airs.com/blog/archives/460
//
// However these are both under-specified.  Some details are not mentioned in
// either of these (for example, the fact that the function length uses the FDE
// encoding, but always absolute).  libdwarf's implementation contains a comment
// saying "It is not clear if this is entirely correct".  Basically the only
// thing you can trust for some of these details is the code that actually
// implements unwinding in production:
//
// * libunwind http://www.nongnu.org/libunwind/
//   https://github.com/pathscale/libunwind/blob/master/src/dwarf/Gfde.c
// * LLVM libunwind (a different project!!)
//   https://github.com/llvm-mirror/libunwind/blob/master/src/DwarfParser.hpp
// * libgcc
//   https://github.com/gcc-mirror/gcc/blob/master/libgcc/unwind-dw2-fde.c

Once I implemented this parser, I could attribute the .eh_frame and .eh_frame_hdr sections properly, and they would no longer show up as [None].

I did the same thing for all the different kinds of DWARF debug info, for the symbol/string table and relocations. All of these are somewhat easier since they at least have clear standards that describe them.

But even that wasn’t enough. After implementing all of the above, I still found that some parts of the data section don’t have symbol table entries or debug info at all. Data like string constants or other anonymous data can resist being properly analyzed and attributed. To combat this, Bloaty will actually disassemble the binary looking for references to the data section. If a function references part of .data or .rodata, then we can attribute that part of the binary to the function that references it.

This was hard and detailed work, but it paid off. We can see the fruits of this labor if we do a hierarchical profile:

$ ./bloaty bloaty -d compileunits,sections
     VM SIZE                                                      FILE SIZE
 --------------                                                --------------
  44.9%  2.07Mi [136 Others]                                    8.72Mi  33.7%
   6.0%   281Ki protobuf/src/google/protobuf/descriptor.cc      4.07Mi  15.7%
       0.0%       0 .debug_str                                      1.16Mi  28.4%
       0.0%       0 .debug_info                                     1.01Mi  24.8%
       0.0%       0 .debug_loc                                       766Ki  18.4%
       0.0%       0 .debug_pubnames                                  383Ki   9.2%
      69.6%   195Ki .text                                            195Ki   4.7%
       0.0%       0 .debug_line                                      177Ki   4.3%
       0.0%       0 .debug_pubtypes                                  158Ki   3.8%
       0.0%       0 .debug_ranges                                    131Ki   3.2%
       0.0%       0 .strtab                                         44.6Ki   1.1%
      14.6%  41.2Ki .dynstr                                         41.2Ki   1.0%
       7.1%  19.8Ki .eh_frame                                       19.8Ki   0.5%
       4.6%  12.8Ki .rodata                                         12.8Ki   0.3%
       0.0%       0 .symtab                                         9.45Ki   0.2%
       3.1%  8.62Ki .dynsym                                         8.62Ki   0.2%
       1.0%  2.79Ki .eh_frame_hdr                                   2.79Ki   0.1%
       0.0%      88 .bss                                                 0   0.0%
   6.5%   306Ki protobuf/src/google/protobuf/descriptor.pb.cc   2.38Mi   9.2%
       0.0%       0 .debug_info                                      660Ki  27.1%
       0.0%       0 .debug_loc                                       620Ki  25.4%
       0.0%       0 .debug_str                                       256Ki  10.5%
       0.0%       0 .debug_pubnames                                  166Ki   6.8%
       0.0%       0 .debug_line                                      163Ki   6.7%
      53.2%   163Ki .text                                            163Ki   6.7%
       0.0%       0 .debug_ranges                                    154Ki   6.3%
       0.0%       0 .strtab                                         71.1Ki   2.9%
      22.3%  68.3Ki .dynstr                                         68.3Ki   2.8%
      10.0%  30.8Ki .eh_frame                                       30.8Ki   1.3%
       0.0%       0 .symtab                                         27.2Ki   1.1%
       8.6%  26.4Ki .dynsym                                         26.4Ki   1.1%
       0.0%       0 .debug_pubtypes                                 17.6Ki   0.7%
       2.5%  7.63Ki .eh_frame_hdr                                   7.63Ki   0.3%
       2.3%  6.91Ki .rodata                                         6.91Ki   0.3%
       1.0%  3.13Ki .bss
  [...]

Here we can see that Bloaty has figured out what part of each section (.debug_*, .text, ehframe, etc) it can attribute to each source file. Bloaty has constructed a very granular look into this binary, where each part of the file is attributed to the code that produced it.

I generally see 2% or less of the binary attributed to [None] now. Actually Bloaty never spits out a literal [None] anymore, because if we can’t figure out what function/compileunit/etc. some part of the binary comes from, we at least report its section. So if we’re stumped by some file range, we’ll report something like [section .rodata] instead of the very unhelpful [None].

Debugging Stripped Binaries

People often want to profile stripped binaries. Very often the binaries you ship to customers don’t have full debug info in them, and you want to profile what you are shipping. But some of Bloaty’s more useful data sources (compileunits especially) require debug information. What to do?

Bloaty now supports reading symbols and debug info from separate files. That way you can profile the thing you’re actually trying to shrink, instead of having your results skewed with the overhead of debugging information.

Bloaty uses build IDs to make sure that the debug information always exactly matches the file you are profiling.

First-class Mach-O Support

When Bloaty was first released, it parsed ELF and DWARF directly, but shelled out to command-line programs to parse Mach-O. This was slow and didn’t give us as much info as we would have liked. As of Bloaty 1.0, we now have first-class Mach-O support. Both fat and single-arch binaries are supported.

DWARF is fortunately a cross-platform standard, which means that Mach-O and ELF can share all of the code that parses DWARF. The code to parse DWARF is about the same size as the ELF and Mach-O parsers combined, so it’s great that so much of this code can be shared.

Experimental WebAssembly Support

I am really excited about WebAssembly. I wanted to learn more about it, so I wrote a basic parser for Bloaty. It can handle sections and functions so far.

I am excited to see that this has been getting some use already!

Using Bloaty as a Presubmit

Some people might wonder how to integrate Bloaty into their workflow. One thing I’ve seen that’s very cool is the way some projects like grpc integrate Bloaty with their pull requests. Here is an example.

This gives quick and useful feedback about how a given PR will affect the binary size of your artifacts. For size-sensitive projects, this is a nice way of keeping tabs and making sure PR’s don’t cause unexpected or disproportionate growth.

Post 1.0

Bloaty has become quite capable, but there is always more to do. Maybe the biggest thing on my wishlist is PE/COFF support so people on Windows can benefit.

I would also like to make Bloaty understand references between symbols. This would make it easier to answer questions like “could I shrink the binary a lot by avoiding calls to this one particular function?” It could also show you the the benefit you could get by compiling with -ffunction-sections and -fdata-sections if you’re not doing that already. These are options that let the linker strip individual functions if they are unreachable.

I’d also like to do a better job of mapping inlines. The idea of the “inlines” data source is to know if the inlining of a particular function is bloating your binary a lot. If it is, maybe it would be helpful to un-inline it. Right now the “inlines” data source uses the .debug_line section, which is what a debugger uses to decide what source file:line to place the cursor on when your problem is stopped at a given address. It would be more convenient to report inlines by function name instead, but .debug_line doesn’t know anything about functions. If I get my inlining info from .debug_info instead, I should be able to report inlines by function instead.

I’m happy with Bloaty 1.0 and look forward to improving it further!

Josh Haberman

A Tail Calling Interpreter For Python (And Other Updates)

Tail Calling Interpreter for Python

Tail Calling Interpreter for LuaJIT Remake

GCC Support

Standard C Proposal: “return goto”

Clang: “Nonportable” Musttail?

Calling Convention Improvements

preserve_most

preserve_none

Conclusion

No-Panic Rust: A Nice Technique for Systems Programming

What are Panics?

Why Are Panics Bad For Systems Libraries?

What is No-Panic Rust?

Opt No-Panic

Rust’s Standard Library

A Dance With The Optimizer

A Slightly More Dangerous Dance

Conclusion

An Ode to Header Files

An Obsolete Mechanism, Repurposed

The Case for Header Files

Auto-Generated Headers?

Benefits

Deep Modules

Software Versioning

Precompiled Libraries

Honorable Mentions

Python & Ruby: Interface Files

Kotlin: expect/actual

Arenas and Rust

Arena APIs

C and C++

Rust

Why is Rust’s “Bump” not “Sync”?

Ergonomics of Arenas in Rust

Hiding the lifetime parameter

Using ouroboros for self-referencing structs

Conclusion

Thread Safety in C++ and Rust

C++

Rust

Mapping between C++ and Rust terminology

Parsing Protobuf at 2+GB/s: How I Learned To Love Tail Calls in C

Tail Call Basics

The Trouble With Interpreter Loops

Improving Interpreter Loops With Tail Calls

Limitations

Hoare’s Rebuttal and Bubble Sort’s Comeback

Basic QuickSort fundamentals

Performance analysis of branchless Lomuto partitioning

Revisiting the Lomuto partition scheme

The elegant hybrid

Fallback for sorting short arrays

Bringing it all together

Why is QuickSort fast compared to merge and heap sort?

Optimizing UTC → Unix Time Conversion For Size And Speed

A Fortran Solution from 1968

Improving Readability With A Lookup Table

Eliminating the Lookup Table

Semantics and Correctness

Supported Input Range

Input Normalization

Leap Seconds

Size and Speed Benchmarks

Bloaty McBloatface 1.0

Improving Data Quality

Debugging Stripped Binaries

First-class Mach-O Support

Experimental WebAssembly Support

Using Bloaty as a Presubmit

Post 1.0

Kotlin: `expect`/`actual`