A Fascinating Diversion into Compression

CommunityNews · 11 September 2024 15:40

blog/posts/2024-09-10.md at master · frankmcsherry/blog.
Some notes on things I find interesting and important. - frankmcsherry/blog

Read in full here:

github.com

frankmcsherry/blog/blob/master/posts/2024-09-10.md

## A Fascinating Diversion into Compression

I've recently been working on columnar data representations in Rust.
The intent is that if you have lists of some complex type `T`, say a `struct` or an `enum` or a list itself (`Vec`), you might have better options than storing the types themselves in a list.
The [`columnar` repository](https://github.com/frankmcsherry/columnar) contains the work, and a [previous post](https://github.com/frankmcsherry/blog/blob/master/posts/2024-08-25.md) goes in to detail about the process.

What I want to talk about today is the curious case of `Result<S, T>`.

We'll start with a pretty standard intro to how you might represent this in a columnar form, but by the end of the post we'll have developed a way to compress JSON objects.
I was suprised and delighted by the connection, which I stumbled upon more than discovered, and would love to hear more about if you understand where this came from.

### Re-orienting `Result` to columnar form

The `Result<S, T>` type is a [sum type](https://en.wikipedia.org/wiki/Tagged_union), each instance of which can either be `Ok(S)` or `Err(T)`.
That is, it is either one type or the other type, but not both. It is different from a pair `(S, T)` which always has both types.
In addition to either `S` or `T`, it also has to communicate *which* of the two it is (they might be the same, or the same size).

The size of a `Result` is determined by the sizes of `S` and `T`, but it clearly needs to be able to hold either of the two, and a spare bit to indicate which it is.
For example, the size of a `Result<u64, i64>` is 16 bytes, but the size of a `Result<u64, u8>` is also 16 bytes.
These might be larger than you expect because of [alignment](https://doc.rust-lang.org/reference/type-layout.html): types in Rust end up sized at least to an integral multiple of their alignment, which is generally at least the size of the largest member.

This file has been truncated. show original

This thread was posted by one of our members via one of our news source trackers.