1
State machines are wonderful tools
I love when my current problem can be solved with a state machine. They’re fun to design and implement, and I have high confidence about correctness. They tend to:
Chris Wellons
Buffered output typically comes in two flavors: fully buffered and line buffered. If output goes to a terminal then the implementation automatically selects line buffering, flushing its buffer when a line is completed so that it reaches the user immediately. Otherwise it fully buffers, holding output until the buffer…
- Popular posts
- 74
- Total points
- 14,949
- HN comments
- 7,192
- Rank
- #45 personal
Visit nullprogram.com → RSS feedOn Hacker News Dec 2014 – Oct 2026
Software Engineering 64Systems & Performance 21Programming Languages 17Tools & Productivity 15Math & Algorithms 8Security & Privacy 7
2
A Branchless UTF-8 Decoder
This week I took a crack at writing a branchless UTF-8 decoder: a function that decodes a single UTF-8 code point from a byte stream without any if statements, loops, short-circuit operators, or other sorts of conditional jumps. You can find the source code here along with a test suite and benchmark:
3
Rolling Shutter Simulation in C
The most recent Smarter Every Day (#172) explains a phenomenon that results from rolling shutter . You’ve likely seen this effect in some of your own digital photographs. When a CMOS digital camera captures a picture, it reads one row of the sensor at a time. If the subject of the picture is a fast-moving object…
4
An easy-to-implement, arena-friendly hash map
My last article had tips for for arena allocation . This next article demonstrates a technique for building bespoke hash maps that compose nicely with arena allocation. In addition, they’re fast, simple, and automatically scale to any problem that could reasonably be solved with an in-memory hash map. To avoid…
5
Inspecting C's qsort Through Animation
The C standard library includes a qsort() function for sorting arbitrary buffers given a comparator function. The name comes from its original Unix implementation, “quicker sort,” a variation of the well-known quicksort algorithm. The C standard doesn’t specify an algorithm, except to say that it may be unstable (C99…
6
Prospecting for Hash Functions
Update 2022 : TheIronBorn has found even better permutations using a smarter technique. That thread completely eclipses my efforts in this article.
7
Solving “Two Sum” in C with a tiny hash table
I came across a question: How does one efficiently solve Two Sum in C? There’s a naive quadratic time solution, but also an amortized linear time solution using a hash table. Without a built-in or standard library hash table, the latter sounds onerous. However, a mask-step-index table , a hash table construction…
8
Zero-allocation Trie Traversal
As part of a demonstration in an upcoming article , I wrote a simple trie implementation. A trie is a search tree where the keys are a sequence of symbols (i.e. strings). Strings with a common prefix share an initial path down the trie, and the keys themselves are stored implicitly by the structure of the trie. It’s…