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.