String Count and Flags

Strings in Swift are 16 bytes. I learned from the stdlib that a String is just a wrapper around _StringGuts which is just a wrapper for _StringObject.

My goal is to try to represent native Swift Strings (not NSString) in a single 8-byte word (32 bit is beyond scope). I also don't need to represent inlined/small strings.

struct _StringObject {
  internal var _countAndFlagsBits: UInt64
  internal var _object: Builtin.BridgeObject
}

I found that there are 4 flags:

On 64-bit platforms, the discriminator is the most significant 4 bits of the
  bridge object.

  β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β•₯─────┬─────┬─────┬─────┐
  β”‚ Form                β•‘ b63 β”‚ b62 β”‚ b61 β”‚ b60 β”‚
  β•žβ•β•β•β•β•β•β•β•β•β•β•β•β•β•β•β•β•β•β•β•β•β•¬β•β•β•β•β•β•ͺ═════β•ͺ═════β•ͺ═════║
  β”‚ Immortal, Small     β•‘  1  β”‚ASCIIβ”‚  1  β”‚  0  β”‚
  β”œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β•«β”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€
  β”‚ Immortal, Large     β•‘  1  β”‚  0  β”‚  0  β”‚  0  β”‚
  β•žβ•β•β•β•β•β•β•β•β•β•β•β•β•β•β•β•β•β•β•β•β•β•¬β•β•β•β•β•β•ͺ═════β•ͺ═════β•ͺ═════║
  β”‚ Native              β•‘  0  β”‚  0  β”‚  0  β”‚  0  β”‚
  β”œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β•«β”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€
  β”‚ Shared              β•‘  x  β”‚  0  β”‚  0  β”‚  0  β”‚
  β”œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β•«β”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€
  β”‚ Shared, Bridged     β•‘  0  β”‚  1  β”‚  0  β”‚  0  β”‚
  β•žβ•β•β•β•β•β•β•β•β•β•β•β•β•β•β•β•β•β•β•β•β•β•¬β•β•β•β•β•β•ͺ═════β•ͺ═════β•ͺ═════║
  β”‚ Foreign             β•‘  x  β”‚  0  β”‚  0  β”‚  1  β”‚
  β”œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β•«β”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€
  β”‚ Foreign, Bridged    β•‘  0  β”‚  1  β”‚  0  β”‚  1  β”‚
  β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β•¨β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”˜

But I can't find anything about what the other 60 bits are for in the _countAndFlagsBits word. I assume they are counts, but I can't find anything. Any documentation link? Thanks!

Those flags are stored in the the _object field, not in _countAndFlagsBits. That's what it means when it says "the discriminator is the most significant 4 bits of the bridge object."

Further down:

For large native strings, it is worth noting that their storage (the thing pointed to by _object) also contains a copy of the count and flags. So you could get the data from there.

2 Likes

Ah that clears up a lot, thanks!

What is _countAndFlagsBits used for then? Specifically for native Swift large strings

I believe (and @Michael_Ilseman might be able to confirm) that the motivation behind _StringObject being 16 bytes is that we wanted to have larger small strings.

Since large and small strings must have the same inline size, that means large strings have an extra 8 bytes to use for... something. Might as well stick a copy of the count and flags there. I think it also makes some access patterns slightly more efficient.

But yeah, if you have an enormous array containing only large native strings, you could technically halve the memory cost by only storing the _object field (as an AnyObject). Then you could losslessly recreate the _StringObject by extracting the flags from it. The reconstructed _StringObject can then be wrapped in a _StringGuts, and then in a String.

4 Likes

This is amazing! Do you know if this is the case for all large strings? It would be possible to shrink it down?

So the reason I'm doing this is because I'm working on my Swift interpreter. The VM uses a single word to represent all possible values, so usually I'll have a tagged pointer for things that need to be in the heap. I have my own small string solution, but I'm only able to give it 6 bytes (2 others for identifying the runtime type and such).

For immortal strings (literals), _object is just a pointer to a constant C string; there's no object containing its count-and-flags if you lose them. If you want to turn the pointer back in to _StringObject, at a minimum you'd need to call strlen to recompute its count. The flags are not critical.

For bridged strings, I don't know :slight_smile:.

Hmm, I don't know enough about what you're doing to say whether any of this information would help you or what pitfalls you might encounter. But the easiest solution which comes to mind if you want all kinds of values to have the same size would be to box them in a class.

1 Like

I'm trying to keep it a little more optimized, so I'm using tagged unions to represent all values. I choose to use 8 bytes to represent values so I'd have enough room to squeeze in a pointer, but now you can see my problem with supporting String.

One solution I like for it's simplicity is simply casting all Strings to NSString (which is just an object pointer). I can then use Unmanaged<NSString> to be able to control its reference count myself.

My main hesitation is that I don't know the performance cost very well between converting between String and NSString.

For example

var swiftString = "a long swift string which doesn't fit into small str"
swiftString += "add some other string"
let nsString = swiftString as NSString // probably has some cost?
let anotherSwiftString = nsString // probably different representation in StringGuts?

The cost can be significant in some cases. For example, NSString's count is in terms of UTF16, which String doesn't store normally, so finding the count requires scanning all bytes of the contents. We do cache UTF8->UTF16 offset mappings above a certain length, but that in turn requires a malloc.

1 Like

Good to know! I think I'll end up storing both words of the Swift String in my VM's heap. A little slower than having it contained in the tagged union, but it seems to be the most simple solution for now.