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.
