# Josh Haberman Parsing, performance, and low-level programming. This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles. ## A Tail Calling Interpreter For Python (And Other Updates) DevFeed: [A Tail Calling Interpreter For Python (And Other Updates)]() Original publisher: [Read original article]() Author: Haberman Published: 2025-02-10T00:00:00Z Content type: opinion Language: en Sources: [Josh Haberman]() Topics: [Parsing](), [Python 3.14](), [Python](), [Lua](), [JIT](), [Compiler]() Tags: [compiler](), [jit](), [lua](), [parsing](), [python](), [python-3-14]() ### AI overview The article updates readers on tail-call interpreter developments following the author's earlier work. It reports that Python's tail-calling interpreter was merged and is slated for Python 3.14, with an opt-in configuration requirement, and discusses the experimental LuaJIT Remake project and its use of tail-call techniques. ### Source excerpt 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 ## No-Panic Rust: A Nice Technique for Systems Programming DevFeed: [No-Panic Rust: A Nice Technique for Systems Programming]() Original publisher: [Read original article]() Author: Haberman Published: 2025-02-03T00:00:00Z Content type: article Language: en Sources: [Josh Haberman]() Topics: [Rust](), [systems](), [Memory Safety](), [Programming]() Tags: [api](), [code](), [memory-safety](), [programming](), [rust](), [systems]() ### AI overview This article examines "No-Panic Rust," a technique for using Rust in low-level systems programming while avoiding panics as a response to errors. The author argues that the approach could make porting the upb C library to Rust more practical while preserving performance and code-size goals. ### Source excerpt 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 new1, 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 lar ## An Ode to Header Files DevFeed: [An Ode to Header Files]() Original publisher: [Read original article]() Author: Haberman Published: 2025-01-27T00:00:00Z Content type: article Language: en Sources: [Josh Haberman]() Topics: [C](), [C++](), [Software Engineering](), [modules]() Tags: [blog-post](), [c](), [c-plus-plus](), [compiler](), [software-engineering]() ### AI overview The article argues that separating a module's public API into dedicated header files remains beneficial for human-readable software engineering, even though newer languages can support separate compilation without traditional textual inclusion. It proposes hygienic, modular headers containing only public API declarations and no implementation details. ### Source excerpt 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 ## Arenas and Rust DevFeed: [Arenas and Rust]() Original publisher: [Read original article]() Author: Haberman Published: 2021-12-19T00:00:00Z Content type: article Language: en Sources: [Josh Haberman]() Topics: [Rust](), [C](), [C++](), [Library]() Tags: [arena](), [c](), [c-plus-plus](), [concurrent](), [efficiency](), [memory](), [rust](), [safety]() ### AI overview This article examines arena allocation in Rust and compares it with arena APIs in C and C++. It explains how Rust lifetimes can statically ensure that arena-allocated references do not outlive their arena, and discusses differences in thread-safety, efficiency, and complexity. ### Source excerpt 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 static T* Create(Arena* arena, Args&&... args); } void Test() { Arena arena; int* i1 = Arena::Create(&arena); int* i2 = Arena::Create(&arena); int* i3 = Arena::Create(&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 ## Thread Safety in C++ and Rust DevFeed: [Thread Safety in C++ and Rust]() Original publisher: [Read original article]() Author: Haberman Published: 2021-12-18T00:00:00Z Content type: article Language: en Sources: [Josh Haberman]() Topics: [C++](), [Rust](), [Concurrency](), [Concurrent Programming]() Tags: [atomic](), [c-plus-plus](), [concurrent](), [mutex](), [rust](), [safety](), [synchronization](), [thread]() ### AI overview The article compares thread-safety terminology and models in C++ and Rust. It explains C++ distinctions between thread-safe and thread-compatible types, including synchronization costs, and introduces Rust traits for safely sharing or moving types between threads. ### Source excerpt 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, thr ## Parsing Protobuf at 2+GB/s: How I Learned To Love Tail Calls in C DevFeed: [Parsing Protobuf at 2+GB/s: How I Learned To Love Tail Calls in C]() Original publisher: [Read original article]() Author: Haberman Published: 2021-04-21T00:00:00Z Content type: article Language: en Sources: [Josh Haberman]() Topics: [Parser](), [C](), [C++](), [Compiler](), [Optimization](), [Programming]() Tags: [c](), [c-plus-plus](), [compiler](), [optimization](), [parsing](), [performance](), [programming]() ### AI overview The article explains how guaranteed tail calls through Clang's musttail extension can improve performance in C, C++, and Objective-C. It describes applying the technique to protobuf parsing, which demonstrated throughput above 2GB/s, while noting that multiple techniques contributed to the result and that portability is the main drawback. ### Source excerpt [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 optimizat ## A Hybrid Hoare-Lomuto Partition Scheme and Bubble Sort for Small Arrays DevFeed: [A Hybrid Hoare-Lomuto Partition Scheme and Bubble Sort for Small Arrays]() Original publisher: [Read original article]() Author: Gerben Stavenga Published: 2020-05-29T00:00:00Z Content type: article Language: en Sources: [Josh Haberman]() Topics: [Sorting](), [Algorithms, Complexity](), [Programming]() Tags: [parallelism](), [partition](), [partitioning](), [performance](), [sorting]() ### AI overview This article examines QuickSort performance, focusing on branch mispredicts, branchless Lomuto partitioning, and a hybrid Hoare-Lomuto scheme. It reports that Bubble Sort performs best for small arrays in the discussed experiments, attributing the gains to instruction-level parallelism and shorter dependency chains. ### Source excerpt 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 parti ## Optimizing UTC -\> Unix Time Conversion For Size And Speed DevFeed: [Optimizing UTC -\> Unix Time Conversion For Size And Speed]() Original publisher: [Read original article]() Author: Haberman Published: 2020-05-12T00:00:00Z Content type: article Language: en Sources: [Josh Haberman]() Topics: [Algorithm](), [C](), [JSON](), [Unix](), [Parser](), [Fortran]() Tags: [algorithm](), [c](), [function](), [json](), [library](), [linux](), [speed](), [standard](), [systems](), [time](), [unix]() ### AI overview This article examines converting UTC calendar timestamps to Unix Time without relying on non-standard library functions. It explains leap-year handling and discusses a compact, portable C algorithm used for the upb JSON parser, including its size and speed characteristics. ### Source excerpt 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 insertion1, 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 Solutio ## Bloaty McBloatface 1.0 DevFeed: [Bloaty McBloatface 1.0]() Original publisher: [Read original article]() Author: Haberman Published: 2018-08-07T00:00:00Z Content type: release Language: en Sources: [Josh Haberman]() Topics: [Data Quality](), [Parser](), [OCaml](), [C](), [Compiler]() Tags: [binaries](), [bugfixes](), [c](), [code](), [compiler](), [data-quality](), [ocaml](), [release](), [symbols]() ### AI overview The article announces Bloaty McBloatface 1.0, a size profiler for ELF and Mach-O binaries. It explains that the release improves data quality by parsing binary sections such as unwind information, DWARF debug information, symbol and string tables, and relocations more thoroughly. ### Source excerpt 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