Swift: O(n²) array concatenation in postcard/CBOR encoding

[fasterthanlime]

Summary

The Swift runtime's postcard and CBOR encoding functions use repeated array concatenation (+=), which creates a new allocation and copies all bytes on each append. This is O(n²) in output size.

Affected code

Postcard (hot path - every message payload):

• Postcard.swift: encodeString, encodeBytes, encodeVec, etc. all return [UInt8] and callers concatenate with +
• Schema.swift: encode() methods on schema types

CBOR (cold path - once per type per connection):

• Cbor.swift: cborEncodeText, cborEncodeBytes, etc.
• Schema.swift: encodeCbor() methods

Example

// Current - O(n²)
public func encodeVec<T>(_ values: [T], encoder: (T) -> [UInt8]) -> [UInt8] {
    var result = encodeVarint(UInt64(values.count))
    for v in values {
        result += encoder(v)  // copies entire result array each iteration
    }
    return result
}

Proposed fix

Add into: inout [UInt8] variants:

public func encodeVec<T>(_ values: [T], encoder: (T, inout [UInt8]) -> Void, into out: inout [UInt8]) {
    encodeVarint(UInt64(values.count), into: &out)
    for v in values {
        encoder(v, &out)  // appends in place
    }
}

Priority

Postcard encoding is on the hot path for every RPC message. CBOR is only used for schema exchange (once per type per connection), so lower priority.

Expect significant performance improvement - potentially 5-10x for large payloads.