Parsing, performance, and low-level programming.
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…
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…
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…
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…
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…
[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…
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…
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…
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…