Backtrace Engineering

Note that you said “likely” and not “equally likely”. Therein lies your answer.

There are applications where hashes are used as identifiers, where it would be impossible to use the original data to resolve possible collisions. One example would be in RTTI (Run Time Type Information), when you want to check if two objects (of unknown-at-compile-time type) are instances of the same type. The only performant way to achieve this is if the compiler emits each type’s RTTI with a unique integer key to efficiently compare against, and this key must be unique across all object files and shared objects. In practice, this is done using hashing. If there is a collision, then the program behavior is undefined, so it is ideal to minimize probability of collision. You can see this issue in the Rust compiler project where there is ongoing discussion about how to handle this hashing, trying to balance compiler speed and collision likeliness:

https://github.com/rust-lang/rust/issues/129014

Another scenario would be like what Backtrace does: a hash is used to identify certain classes of errors in application code. The cost of analyzing each error is quite high (you have to load objects into memory, source maps (if available), perform symbolification, etc), so comparing any two errors every time you want to perform any metrics or retrieve associated data (like issue tracker identifiers) would reduce the performance to a point that any such application would be too slow to be useful. So a lot…

> I think you're confusing proving that the hash function is collision resistant with the other goal which is hashing speed. If you really need a collision resistant hash you need to use a cryptographic hash function.

I wish this misconception would die. There is a great theory of algorithmic probabilistic hash functions, completely distinct from cryptographic hash functions. If you are designing a hash table, or a different algorithm using a hash function, you nearly always want the former kind.

The idea is that `Pr[h(x) = h(y)]` is small _no matter the inputs x and y_.
Here the probability is over the random seed of h.
Lots of good hash functions, like UMASH (https://engineering.backtrace.io/2020-08-24-umash-fast-enough-almost-universal-fingerprinting/) has this guarantee.
Other fast hash functions, like MURMUR don't.

When a function doesn't have this guarantee, it means I can find sets of values x1, x2, ... that will likely collide under _any_ or most seeds!
Sure, if your inputs are basically random, this probably won't happen, but people can still use this to DDoS your hash table, or whatever you are coding.

Notice again, this has nothing to do with cryptography. It is all about probabilistic guarantees.
You can't just test the hash function on a fixed number of inputs and say it's good, since you may just have moved the "bad set" to somewhere else.

In this day and age there are super fast algorithmic hash functions with guaranteed low expected collisions. It's just…

Location: Seattle

Remote: Yes

Willing to relocate: No

Technologies: Rust, C/C++, Python, SQL, Kubernetes, many others

Résumé/CV: https://ahicks.io/files/resume.pdf

Email: ahicks@ahicks.io

My first resume-worthy project was working with Mozilla on the Rust compiler for 6 months [0], implementing the ability to reorder fields in structs to eliminate padding. My work here was primarily a cleanup project which also unblocked many other Rust layout features that people benefit from today. I then detoured into Python/Django on top of Kubernetes, writing scalable infrastructure such as a giant media transcoding cluster. After that, I pivoted back to C/C++ working at Backtrace I/O. If you play a lot of videogames, our software is probably on your system, as we indexed and processed native crashes for many of the largest videogame publishers. This was big data on the order of tens to hundreds of terabytes per day. I was able to attain exposure to the concerns at that scale--including custom database design. While there, I spearheaded the adoption of Rust in the org, initially for microservices and later as part of our C codebase. I'm now one of the most experienced Rust engineers you'll find. We did neat things some of which are open source, for example our feature flag system that rewrote code at runtime [1] and our Sqlite VFS that replicates to S3 [2]. As a benchmark of our success, we managed to be acquired by Sauce Labs, a company easily 10 times our…

This is one of the other three secret blends that I think could bring memory safety to C++!

I wrote a bit about using type-after-type as the basis for an entire language (Arrrlang, with a parrot mascot) in my last article [0] and a little bit in a post about memory safety for unsafe languages [1] which we eventually talked about at Handmade Seattle.

The downside is the extra memory usage, but I think we can combine it with temporary regions [2] to reduce it pretty drastically.

TIL the phrase type-after-type! I've also heard it referred to as type stability. [3] [4] If you squint, this is what we often do manually with Rust when the borrow checker influences us to use indices/IDs into central collections.

[0] https://verdagon.dev/blog/myth-zero-overhead-memory-safety

[1] https://verdagon.dev/blog/when-to-use-memory-safe-part-1#the-safer-way-to-use-mmm-languages

[2] https://verdagon.dev/blog/zero-cost-borrowing-regions-overview

[3] https://www.usenix.org/legacy/publications/library/proceedings/osdi96/full_papers/greenwald/node2.html

[4] https://engineering.backtrace.io/2021-08-04-slitter-a-slab-allocator-that-trusts-but-verifies/

Surprisingly backtrace apparently uses self-modifying code in production for feature flags:

https://engineering.backtrace.io/2021-12-19-bounded-dynamicism-with-cross-modifying-code/

This is basically to make it zero cost (as far as I remember)

Google uses a similar system of feature flags, but as far as I know there's no self-modifying code. I guess Backtrace wants to put the flags in tight inner loops.

dtrace and I believe systemtap patch the executable at runtime, for similar performance reasons. But those are kernel features and not user applications.