Friday, October 23, 2026

Small Slice Optimization

In gSuneido, database tables hold Records, and queries return Rows consisting of one or more records. Multiple records come from things like join operations. Simple cases, where Rows have only single Records, are common.

While working on some benchmarks I realized that constructing a Row from a single Record required allocation of a single element backing array.

That seemed wasteful. There had to be a better way.

You can partially solve it by using an interface containing either a "single" type or a "multi" type. That solves the single issue, but the problem with that is that there's nowhere to store the size of the multi type. So you end up using a slice, and then you've got an interface pointing to a slice header pointing to a backing array pointing to the data - worse than just using a slice.

What I came up with was to make my own equivalent to a slice/string header, with a length and a pointer (similar to a string header). The trick was to make the pointer dual purpose (using an unsafe.Pointer, in a safe way). If there was a single element like my common case, then the pointer is directly to the data (and length = 1). If there are multiple elements, then the pointer is to a backing array of pointers to the data. So for multiple elements, the shape is the same as a slice.

This eliminated the allocation for rows with single records, and also a level of indirection (and therefore cache misses). It also makes the size of a Row 16 bytes (pointer + length) instead of 24 bytes for a slice header (pointer + length + capacity). The cost is an extra branch between one or many.

The end result was a saving of about 10% (4 GB) of allocation on our application test suite.

The syntax row.Get(i) is not quite as nice as using slices row[i], but that's minor.

The constraints are that it only works if what you are storing is a pointer, and it only optimizes for the single element case (not a small number of elements). But it's no worse for multiple elements.

This is similar to the small string optimization that I wrote about recently and is similar to small vector optimizations in C++ and Rust.

Tuesday, October 13, 2026

Small String Optimization in Go

Go strings are "fat" pointers consisting of a pointer and a length. On 64 bit systems this makes them 16 bytes. This works well for most things.

Go interfaces (think virtual methods) are also "fat" pointers consisting of a type and a pointer.

The problem comes when you combine the two. When you store a string in an interface, the string fat pointer (16 bytes) can't be stored in the pointer part of an interface (8 bytes) so the string header (fat pointer) has to be on the heap and a pointer to it in the interface.

This has several downsides:

  • extra allocation leading to a larger heap and more garbage collection work
  • extra pointer following leading to potential CPU cache misses
  • the string header contains a pointer so it requires scanning by the garbage collector (as opposed to "noscan" allocations like the actual string data, which do not contain pointers)

Ideally, you'd store short strings right in the 8 pointer bytes of the interface (a tagged pointer). Go doesn't allow that kind of low level trick. You can encode some information as a pointer to uninitialized memory, and gSuneido does that for small integers.

The next best option is to have the interface point directly to the string data, perhaps in a struct like:

struct {
    size byte
    data [15]byte
}

This makes it the same size as the Go string header, but that's not a requirement. It could be smaller or larger.

I added some quick instrumentation to Suneido and found roughly 50% of strings were under 16 bytes. I thought it would be more. 70% were under 24 bytes, and 83% were under 32 bytes.

The tradeoff, of course, is wasted space. If you make the struct 32 bytes and only store 5 bytes, you're wasting more space than standard Go (16 header + 5 data = 21).

I pondered this. You could have multiple struct sizes. But that adds complexity and slows down the code. In C you could allocate the necessary size and still treat it as a struct. You could probably do something like that in Go but you'd have to use unsafe code and it would be ugly.

Wait a minute, why do we need a struct at all? Squint a little, and this is just a sequence of bytes with the size in the first byte. We can just store *byte in the interface, pointing to what amounts to a "Pascal string" with a leading size. This means we can have strings up to 255 bytes long, and at the same time have no wastage on tiny strings. This is what I implemented.

There is a catch to using *byte - Go doesn't allow methods on a built-in type like byte, so you have to define a new type e.g. type strp byte and then define the methods on *strp.

One subtlety is that when you are starting from a Go string, creating a small string requires allocation and copying. So even though this small string representation can handle up to 255 bytes, the allocation crossover is 15 bytes (plus a size byte = 16). Above this, creating a small string does more allocation than allocating a 16 byte Go string header. There are still advantages to small strings so the optimal threshold is a bit higher. I set it at 23.

One of the benefits of Go strings is that you can get a substring without allocation or copying. You can't do that with a size prefixed string because a substring wouldn't have the necessary size prefix. However, for small strings this is fast and has the advantage that a small substring won't stop a much larger string from being garbage collected.

On the other hand, when concatenating strings, you always have to allocate the result, so you can use the full 255 byte limit for small strings.

Another Go trick that is key to this approach is that we convert back to a Go string with no allocation or copying. We simply use unsafe.String to point to the same bytes (just past the leading size). While this uses the unsafe package, it is actually safe as long as you never modify the bytes in place because Go strings are immutable. In my implementation this use of unsafe is isolated from the bulk of the code and only exposes immutable strings.

Curiously, while AI is familiar with the small string optimization (SSO), it assumed the fixed size struct representation. It saw the benefits of the *byte approach, but it never suggested it. I assume that means it's not a common approach and therefore not in the training data. Granted, classic SSO puts the data in the string header (or even in a tagged pointer), whereas in this case we're moving from two indirections (interface to string header to data) to one indirection (interface to data).

The big question was whether this optimization was worth it. Would the benefits outweigh the extra complexity? The obvious measurable benefit was less allocation. But even there, it's hard to predict the overall effect. A lot of the potential benefits are "diffuse", things like cache misses and garbage collector overhead.

Part of what convinced me to go ahead was that gSuneido already had multiple string types, so I already had a framework for adding another type. Two types to three is a much smaller jump than one to two.

Of course, it turned out to be more work than I thought, but the process of revisiting all the string handling code was beneficial in itself since I found several inconsistencies and minor potential bugs. One thing that helped was that all of the gSuneido string types are efficiently convertible to Go strings with no allocation or copying. That meant operations can always be performed with Go strings. However, that isn't entirely free, since converting back to a gSuneido value (interface) usually involves allocation.

In the end, some simple instrumentation showed 83% small strings which seems pretty good. Some simple benchmarks showed the expected reduction in allocation. And even in Suneido code, with the overhead of byte code interpretation, I saw improvements in speed. Of course, you can make benchmarks that show whatever you want to show. It didn't have a huge impact on overall execution speed. I didn't expect it to since string handling is just one small part of the system. But the results seem positive enough to justify the change.

Saturday, September 05, 2026

Database Stats

I just landed a large commit in gSuneido to add database stats (metadata) and use them for query optimization. (It probably should have been multiple commits, but I kept thinking I almost had it finished. Typically, I was 90% finished for quite a long time!)

A while ago I had implemented several algorithms/data structures to use for this:

The first question is which table columns do you gather stats for? All of them would be too much data and much of it unused. We only need stats for commonly used columns on large tables. So the first step is to use an SS sketch weighted by table size to track these "hot" columns. This can be accumulated in memory and periodically written to disk. It could go in the database itself, but I chose to write it to a text file to keep it separate.

The next question is when do you actually collect the data stats? The obvious time for Suneido is during compaction (usually weekly) which has to process all the data anyway. So it reads the text file of hot columns and for each one collects HLL, KLL, and SS.

To avoid overhead (and complexity) I chose not to try to update the stats with data updates. This means the stats can get slightly out of date, but generally one week's changes do not substantially affect the statistics on big tables.

Once we have the stats we can actually do the functional part of this whole setup - use them to help with query optimization, in particular to help choose indexes for WHERE clauses. I ended up overhauling this part of the code so it could cleanly incorporate the extra information.

One thing that wasn't clear at first was how you actually use the HLL, KLL, and SS data to estimate a fraction of the data. This depends on whether the WHERE clause is a single value or whether it's a range. Ranges are simpler - they just use the quantiles. I collect 50 quantiles to give 2% precision. So, for example, if a range covers 3 quantiles, it's 6% of the data.

Single values are a little more involved. First you check SS to see if it's one of the known most common values. If so, that gives you the approximate count and therefore the fraction of the table. If it's not a common value, we calculate the "tail" after subtracting the common values and assume it's 1/N of the tail, where N is the total number of distinct values (from HLL) minus the number of heavy hitters (from SS).

Despite this age of AI, I ended up writing quite a bit of this code the old-fashioned way, by hand. Mostly that was because I was unclear how parts of it should work, which meant I couldn't tell an AI what I wanted. I reverted to working it out as I wrote and rewrote the code. Parts where it was clear what was needed (and explainable) I got AI to write. Even then I refactored most of the AI-written code.

As usual the code is on Github.

Friday, July 17, 2026

Programmers

Sometimes AI is so much like a human programmer.

First they tell you something is near impossible.

You point out a possible way to do it.

Then they say it might be possible but it's really hard and complicated.

You point out a simple way to do it.

Finally they admit that, ok, it's actually easy.

I guess they won't be taking my job this month :-)