Devon H. O'Dell

Software Engineer @Fastly. Performance nerd, debugging ninja, and concurrency nut.

Latest Entries

The QP-Trie

I was recently pointed to an article about a new kind of trie, the QP trie. “QP” stands for “quadbit-popcount patricia”, and the QP trie combines techniques from DJB’s critbit trees and Bagwell’s hash array mapped tries. In previous posts, I explored shortcomings of a particular implementation of a critbit tree versus a red-black tree for construction time and lookup. To summarize, it turns out that red-black trees can be significantly more efficient than critbit trees for string lookups if you sort your tree by length and reduce the number of comparisons done at each level.

Strangeloop 2015

I’m speaking today at Strangeloop 2015 on a subject I hold dear: concurrent systems programming. The title of the talk is “Racing to Win: Using Race Conditions in Correct Concurrent Software” and the subject matter is effectively how we can use the property of linearization in concurrent software in conjunction with racy state snapshotting to make our software perform predictably under concurrent load. You can find my slides on speakerdeck. Check out uslab and Concurrency Kit.

Debugging the Internet

Yesterday, we were doing some tests to try to ensure that some changes we had made fixed some problems we were seeing with particular request types. What we noticed was that occasionally, a request would sit around forever and could not be destroyed, despite the associated connection for that session being in CLOSE-WAIT. We had noticed this behavior before, but were entirely unclear what to chalk it up to, and it didn’t seem like that big of a problem.

Efficient String Searching with Binary Search Trees: Part 2

In my previous post, I discussed tries and what seemed to me like a novel way to efficiently search for strings in a balanced binary search tree. Usually, using a binary search tree to search for strings is ineffectual; other data structures are used. This is largely because of the key comparison overhead. First, nodes must store their keys (this isn’t always necessary for e.g. hash tables with known inputs). Second, to traverse the tree, keys need to be compared at each level.

Efficient String Searching with Binary Search Trees

For some time, I’ve been a fan of the trie as an efficient string searching data structure. A trie is a tree-like data structure in which every node represents some piece of a string. Many variants exist; perhaps the most popular is the radix tree. Tries have a couple of neat properties: They have a low RAM impact compared to some other tree structures. They only require O(k) operations to search, insert, or remove (where k is the key length) a particular key.


I’ve tried numerous blog platforms and been unsatisfied with all of them. I’m testing out Hugo along with the Hugo-Uno theme. So far, it seems to be working really well. And I do like the idea of a static site generator. Maybe one of these days I’ll get to finishing up ASCIIToSVG work and incorporate it into the markdown parser. In the near future, I’m hoping to blog about a few more things related to work.

Passwords are Not Obsolete

I’m not a security researcher, so I always feel a little silly writing or talking about it. I try to keep up-to-date on security protocols and encryption algorithms, at least at a high level. But I’m not a security guru: I don’t write exploits, I don’t reverse-engineer protocols and analyze the feasibility of their security, I don’t design whole cryptosystems like PKI. But I do understand all these things, and I’m confident that I could get into any of these activities if I wanted to spend a few years getting up to speed.

Interviewing in Software Engineering

I’ve recently been asked several times for tips on how to “ace an interview” or how to “wow folks” during an interview. Having interviewed many times over the past 13 years, I’ve had a number of successes and failures. This post isn’t necessarily useful only for those looking for jobs in software engineering, but it is tailored to that crowd. How do you get that job? Software engineers are in very high demand these days, and that demand extends into virtually every field of engineering.

Explaining DKIM to Your Grandmother

Email systems have grown increasingly complex since they first appeared in the early 1970s. The growth of the Internet (as measured by users of internet-enabled services) is largely responsible for this complexity. Spam, phishing, and forgery attacks have plagued email users across the world in recent years. The fundamental problem with modern email systems is that, although we ascribe identity to individual email addresses, that identity is generally not enforced. To this day, it is common to find poorly configured email servers and web email forms that allow malicious users to forge emails.