Plurrrr

Gavin Guile is dying.

He'd thought he had five years left - now he's got less than one. With fifty thousand refugees, a bastard son and an ex-fiancée who may have learned his darkest secret, Gavin's got problems on every side.

As he loses control, the world's magic runs wild, threatening to destroy the Seven Satrapies. The old gods are being reborn and their army of colour wights is unstoppable.

The only salvation may be the brother whose freedom and life Gavin stole sixteen years ago.

Harry, Ron, and Hermione search for Voldemort's remaining Horcruxes in their effort to destroy the Dark Lord as the final battle rages on at Hogwarts.

If you’ve worked with data for any length of time, you’ve come across the Comma-Separated Values (CSV) format. Its simplicity and ubiquity make CSV an extremely popular way for organizations to exchange data both internally and externally. While many programs can’t read or write Excel spreadsheets, almost anything can read and write CSVs, and a human can open a CSV file in any text editor and understand roughly what it contains.

Despite this ubiquity and ease of access, CSV is a wretched way to exchange data. The CSV format itself is notoriously inconsistent, with myriad competing and mutually-exclusive formats that often coexist within a single dataset (or, if you’re particularly unlucky, a single file). Exporting a dataset as a CSV robs it of a wealth of metadata that is very hard for the reader to reconstruct accurately, and many programs’ naïve CSV parsers ignore the metadata reconstruction problem entirely as a result. In practice, CSV’s human-readability is more of a liability than an asset.

Recently, I’ve been reading through the excellent Database Internals (Alex Petrov, 2019). The first half of the book is dedicated to the implementation of database storage engines – the subsystem(s) of a DBMS that handles long-term persistence of data. A surprising amount of this section discusses the implementation and optimization of various B-Tree data structures.

This article walks through the components of a modern LZ compressor. It's amazing how rich and deep the compression field is. If you enjoy algorithms and data structures, there are not too many better places to play. I hope you enjoy reading it as much as I enjoyed writing it!

By the end, we will have a compressor that can beat gzip while decompressing at almost the same speed — in less than 1000 lines.