Revisit when to use heap based storage for messages.

[thomasvl]

Spun out of discussions on #733

The current logic for deciding if a message should use heap storage is:

// NOTE: This check for fields.count likely isn't completely correct
// when the message has one or more oneof{}s. As that will efficively
// reduce the real number of fields and the message might not need heap
// storage yet.
let useHeapStorage = isAnyMessage || descriptor.fields.count > 16 || hasSingleMessageField(descriptor: descriptor)

I believe the hasSingleMessageField is really there to handle transitive recursion back to this same message (protos making a tree structure).

[thomasvl]

I believe the only case where we have to use storage is if there is a non repeated field that is transitively recursive.

Any other limits are about how large we want to let the struct before we push it into the heap to try and cut down on the cost of the struct copying. A repeated or map field already will be using some heap space, so it probably comes down to how many of those and how many primitive fields we want.

While floating ideas - we could change things, and only put the single fields in the storage. The repeated fields and map fields already be doing similar things under the hood to avoid copies.

[Lukasa]

A relevant size constraint here is that putting a value type into an existential container will allocate if the value type is wider than 3 words (24 bytes). This means any attempt to put a message into a Message (e.g. to create [Message]) will allocate if those messages are wider than 24 bytes.

The SwiftNIO team tend to use 24 bytes as the maximum size of an inline struct when there is any risk of that structure being placed into an existential container.

A related concern is reference counting: structs with multiple refcounted fields must refcount them all separately whenever their copy operation is invoked. For wide structs with many string or bytes members (both backed by refcounted structs) this can increase the cost of copying substantially compared to boxing the backing storage, which incurs only one refcount operation per copy.

[thomasvl]

Interesting, don't String, Array, and Dictionary end up having >24 bytes per instance because of their multiple storage methods? i.e. - a message with a single field of one of those types would trip some of these cases?

It likely means we might also need to consider unknownFields and _protobuf_extensionFieldValues in deciding when to start using Storage.

[ydnar]

@Lukasa are the additional refcounts more expensive than the alloc/free operations for boxed storage?

[Lukasa]

Interesting, don't String, Array, and Dictionary end up having >24 bytes per instance because of their multiple storage methods? i.e. - a message with a single field of one of those types would trip some of these cases?

Nope. All of those types are smaller:

  1> MemoryLayout<String>.size
$R0: Int = 16
  2> MemoryLayout<Array<String>>.size
$R1: Int = 8
  3> MemoryLayout<Dictionary<String, String>>.size
$R2: Int = 8

Both Array and Dictionary are essentially simply pointers to their backing storage, hence their size: the backing storage worries about distinguishing the types.

String is a bit fancier, which is why it's wider. It holds only a _StringGuts, which holds a _StringObject, which is a UInt64 and a pointer. In practice this diagram shows that String is what Michael Ilseman called "an artisanal enum, hand-crafted using traditional bit-twiddling techniques". The goal of this is to store these multiple representations without exceeding this size limit.

This philosophy has carried into SwiftNIO: anything that gets passed around our ChannelPipeline in sufficient numbers gets stuffed into a box small enough to avoid heap-allocating an existential. Here's a selection of our types and their sizes:

MemoryLayout<ByteBuffer>.size = 23
MemoryLayout<CircularBuffer<UInt8>>.size = 24
MemoryLayout<HTTP2Frame>.size = 18
MemoryLayout<SocketAddress>.size = 8
MemoryLayout<HTTPServerRequestPart>.size = 24
MemoryLayout<HTTPClientRequestPart>.size = 24
MemoryLayout<HTTPServerResponsePart>.size = 24
MemoryLayout<HTTPClientResponsePart>.size = 24

are the additional refcounts more expensive than the alloc/free operations for boxed storage?

@ydnar The answer is "it depends". To a first order approximation, no, but in reality it depends on a number of factors, including how often the object is copied and how many copies the Swift compiler can manage to prove don't need to incur the refcounting cost. The answer can only really be determined on a per-workload basis by measuring the cost.

This is a really unfortunate trade-off, and so normally I'd focus on the existential boxing concern. However, bear in mind that there are pathological cases. If you have a protocol buffer with 100 bytes & string fields the 100 refcounting operations will be really brutal.

[ydnar]

@Lukasa thanks for the valuable context. I’ll be sure to mind the size of our structs to <= 24 bytes going forward. PR (#900) was in part inspired by earlier work I did in a Go project to reduce GC pressure. There were analogous tradeoffs (copying structs vs pointers, mark + sweep penalty for string copies).

I’d love to see the OP of #733 test this with his other pathological case (hundreds of thousands of messages).

@thomasvl maybe it makes sense to consider the number of String fields and/or the total memory size of a message in the consideration of whether to use Storage.

[thomasvl]

@thomasvl maybe it makes sense to consider the number of String fields and/or the total memory size of a message in the consideration of whether to use Storage.

Yea, what's I've done for other projects like this is make the fields compute their "cost", and then rather then using the current field cost, we actually look at the instance size, and use that for when to flip over to storage. The calc is a little more tricky with oneof since you'll need to deal with it being an enum to hold the state and value.

If we're willing to go over the 24 bytes, then it might also make sense to factor in the fields that will include a retain to put some limit on those.

The 24 is likely to be tight with unknown fields and extensions, but for all the reasons mentioned, moving those to their own storage and lazy creating it might be a good tradeoff (one pointer to hose both, with the home they they generally aren't needed, but take the hit once when either is used).

[ydnar]

The 24 is likely to be tight with unknown fields and extensions, but for all the reasons mentioned, moving those to their own storage and lazy creating it might be a good tradeoff (one pointer to hose both, with the home they they generally aren't needed, but take the hit once when either is used).

So move unknown fields and extensions to lazily-created storage? Would a message be required to support unknown fields and/or extensions? I presume this would take at least a word’s worth of space?

[thomasvl]

So move unknown fields and extensions to lazily-created storage? Would a message be required to support unknown fields and/or extensions? I presume this would take at least a word’s worth of space?

Only proto2 syntax messages support extensions, but all messages support unknown files.

Right now, I believe we are inlining the fields. By moving those into their own storage we could collapse them down to a single pointer if either is needed. And we might be able to change things so they are created on demand as part of mutations rather than always having to create them; thus avoiding the allocations/refcounts/etc. until an individual message actually needs either one.

[n8gray]

Related: #1034

In 1.10.2 many of the messages in our project end up with sizes over 200 bytes and some grow to over 5000 bytes. I have to revert to 1.7 where they were almost all 24 bytes.

[thomasvl]

#1046 won't count as a "fix" for this because it only incrementally handles singular sub message in some of the decisions.

It does start to lay the ground work for factoring in a cost to message and messages used as fields, that this issue could better improve to try and determine real costs of things, and also factor in thing like extension field storage and unknown field storage.