Josh Haberman, a systems programmer who works on Protobuf, writes about parsing, interpreters, JITs, and low-level performance.
Commenters cite his posts on tail-call interpreters, the bubble sort comeback, and LL/LR parsing, calling the parsing explanations helpful for people without a CS background.
Yeah, they both solve the same problem -- turning text into a structured "parse tree".
At the core of each parsing tool is a particular parsing algorithm. The details of this algorithm determine what kind of text the parser can parse, how efficiently it can parse it, and what kind of error messages you get if something goes wrong.
There's a huge variety of these algorithms, but nearly all of them are variations on two basic types: "LL" and "LR" parsers. For example, ANTLR uses an "LL(*)" parsing algorithm. This is a great blog post about the difference between the two basic types: http://blog.reverberate.org/2013/07/ll-and-lr-parsing-demystified.html.
Owl is unique because its algorithm isn't a variation of either of these. It works more like a regular expression parsing algorithm. This makes it more limited than a tool like ANTLR, but it can solve some problems that have been difficult with the existing algorithms.
For example, most programming languages allow expressions like "1 - 2" to be used as statements. If you don't use a semicolon or anything to separate the statements, there's an ambiguity -- is "1 - 2" a single expression, or is it the two expressions "1" "-2" in sequence?
ANTLR (at least with the default settings I tried) doesn't tell you about this ambiguity at all. It just picks one of the two options ("1 - 2" in this case). This may or may not have been what you were expecting! The problems with ambiguity checking are quite deep (this followup to…
I haven't used the CryEngine but often times if you think you "need" a higher bit coordinate system (don't you mean 128-bit? ala long double? Doubles are already 64-bits and 80-bits internally.) you may be thinking of the problem in the wrong way.
There's no reason you can't (in most games) have a segregated coordinate system. For example, where each star is the center, the (0,0,0) point. And when you warp from one star system to another, the new star is the new (0,0,0) point.
Floats are great for huge distances, and tiny distances. They are horrific at BOTH at the same time... like say... adding a tiny fractional velocity vector per frame to an object millions or billions of units away. (There is a minimum amount you can add to a float without rounding down to the same original number, and the minimum change gets bigger the bigger the number is.)
http://blog.reverberate.org/2014/09/what-every-computer-programmer-should.html
IIRC, KSP does the same thing and coordinates are to the nearest "planet of influence"--which has the affect of removing Lagrangian points for orbits but otherwise works great without needing custom math types which are much much slower than native types, and it doesn't require ripping out all of the assumptions that an entire engine (Unity in the case of KSP) runs on.
When I created my own 2-D KSP, I ended up encountering all of these issues first-hand, and simply adding more precision didn't help nearly as much as segregating my coordinate system…
I'd have to look more closely at those examples, but I find it hard to believe that every runtime invariant violation manifests as one of those error codes. It certainly isn't true for PCRE2.
> Rust brings safety by forcing (safe) code to use dynamic checks when a safety property cannot be statically guaranteed, which addresses (1). But there's still a degree of freedom for whether failures are reported as panics or as recoverable errors to the caller.
Sure, you can propagate an error. I just don't really see a compelling reason to do so. Like, maybe there are niche scenarios where maybe it's worthwhile, but I do not see how it would be compelling to suggest it as general practice.
You might point to C libraries doing the same, but I'd have to investigate what exactly those error codes are actually being used for and _why_ the C library maintainers added them. And the trade-offs in C land are totally different than in Rust. Those error codes might not exist if they had a panicking mechanism available to them.
> I wrote down some of my thinking in this recent blog entry, which actually quotes your excellent summary of when panics are appropriate: https://blog.reverberate.org/2025/02/03/no-panic-rust.html
Yes, I've read that. It's a nice blog, but I don't think it's broadly applicable. Like, I don't see why I would write no-panic-Rust outside of extremely niche scenarios. My blog on unwraps is meant to be more broadly applicable: https://burntsushi.net/unwrap/ (It even…
The immediate context for this is this post https://v8.dev/blog/v8-release-80 on the v8 blog, where they announced that in v8 version 8, they saved an average of 40% memory, and (unlike usual memory-time tradeoffs) also got good performance improvements. (Design doc: https://docs.google.com/document/d/10qh2-b4C5OtSg-xLwyZpEI5ZihVBPtn1xwKBbQC26yI/edit) So pointer compression is clearly a good thing. I don't know much about the history of pointer compression, but I know the following.
In 2008, Don Knuth posted on his then "news" page (https://cs.stanford.edu/~knuth/news08.html):
> A Flame About 64-bit Pointers
> It is absolutely idiotic to have 64-bit pointers when I compile a program that uses less than 4 gigabytes of RAM. When such pointer values appear inside a struct, they not only waste half the memory, they effectively throw away half of the cache.
> The gcc manpage advertises an option "-mlong32" that sounds like what I want. Namely, I think it would compile code for my x86-64 architecture, taking advantage of the extra registers etc., but it would also know that my program is going to live inside a 32-bit virtual address space.
> Unfortunately, the -mlong32 option was introduced only for MIPS computers, years ago. Nobody has yet adopted such conventions for today's most popular architecture. Probably that happens because programs compiled with this convention will need to be loaded with a special version of libc.
> Please, somebody, make that…
It doesn't make sense to me that an embedded VM/interpreter could ever outperform direct code
You're adding a layer of abstraction and indirection, so how is it possible that a more indirect solution can have better performance?
This seems counterintuitive, so I googled it. Apparently, it boils down to instruction cache efficiency and branch prediction, largely. The best content I could find was this post, as well as some scattered comments from Mike Pall of LuaJIT fame:
https://sillycross.github.io/2022/11/22/2022-11-22/
Interestingly, this is also discussed on a similar blogpost about using Clang's recent-ish [[musttail]] tailcall attribute to improve C++ JSON parsing performance:
https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html
Exciting!
I have been on a similar odyssey making a 'zero copy' Java library that supports protobuf, parquet, thrift (compact) and (schema'd) json. It does allocate a long[] and break out the structure for O(1) access but doesn't create a big clump of object wrappers and strings and things; internally it just references a big pool buffer or the original byte[].
The speed demons use tail calls on rust and c++ to eat protobuf https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html at 2+GB/sec. In java I'm super pleased to be getting 4 cycles per touched byte and 500MB/sec.
Currently looking at how to merge a fast footer parser like this into the Apache Parquet Java project.