Pre-computed encoded size for buffer pre-allocation

[SeanTAllen]

The problem

When encoding a msgpack message, the Writer starts with a small internal buffer and grows it as data is appended. Each time the buffer's capacity is exceeded, the runtime allocates a larger array and copies the existing contents into it. For small messages this cost is negligible — a few resizes of a sub-KB buffer. For large messages with many values, the cumulative cost of repeated allocations and copies becomes significant.

The msgpack wire format makes encoded sizes fully deterministic. Given a value (for integers) or a byte length (for strings, binary, extensions), the exact number of bytes the encoder will write is known before encoding begins. This means the total encoded size of a message can be computed in advance, allowing the caller to pre-allocate the writer's buffer — reducing or eliminating intermediate reallocations.

Where it matters

The benefit scales with message size and complexity:

• A message with 1,000 small integer fields: ~1,000 calls to the encoder, each writing 1-9 bytes. Without pre-allocation, the writer resizes its buffer multiple times as it grows from empty to several KB.
• A message containing many medium-sized values: each value adds header bytes plus payload to the writer's internal buffer. Without pre-allocation, the buffer resizes repeatedly as it accumulates data.
• Deeply nested structures (arrays of maps of arrays): each container header and element adds bytes. The total is predictable but only knowable by walking the structure.

The trade-off

Pre-computing the size requires the caller to traverse their data twice — once to compute the total size, once to encode. For simple flat messages this is trivial. For deeply nested or dynamically constructed messages, the double traversal adds CPU work. Whether this is a net win depends on the workload: if the avoided reallocations (which involve both allocation and memcpy) outweigh the size computation pass, pre-allocation wins.

This is explicitly opt-in. Callers who don't compute sizes get exactly the behavior they have today — dynamic buffer growth with no API changes.

How other libraries handle this

tinylib/msgp (Go)

The msgp code generator produces a Msgsize() method on every Go type that implements the Sizer interface. Msgsize() returns the worst-case encoded size of the value. The library provides constants for fixed-size types and prefix sizes for variable-length types:

const (
    Int64Size           = 9
    Float64Size         = 9
    BoolSize            = 1
    NilSize             = 1
    MapHeaderSize       = 5   // worst-case map header
    ArrayHeaderSize     = 5   // worst-case array header
    BytesPrefixSize     = 5   // worst-case bin header
    StringPrefixSize    = 5   // worst-case str header
    ExtensionPrefixSize = 6   // worst-case ext header
)

Callers use Msgsize() to pre-allocate buffers via make([]byte, 0, msg.Msgsize()). The constants are worst-case rather than exact — a uint that fits in a fixint still reports Int64Size (9 bytes). This simplifies the API at the cost of slight over-allocation.

General pattern

Most msgpack libraries (Python, Ruby, JS, C#, Java) do not provide size pre-computation. They rely on dynamic buffer growth internally. The Go library is the notable exception, driven by Go's performance culture and the code generation approach that makes per-type Msgsize() methods free to maintain.

Design

A new primitive: MessagePackSize

A stateless primitive that mirrors MessagePackEncoder's compact methods. Each method computes the exact byte count that the corresponding encoder method would write, without actually writing anything.

primitive MessagePackSize
  fun nil(): USize => 1

  fun bool(): USize => 1

  fun uint(v: U64): USize =>
    if v <= _Limit.positive_fixint().u64() then 1
    elseif v <= U8.max_value().u64() then 2
    elseif v <= U16.max_value().u64() then 3
    elseif v <= U32.max_value().u64() then 5
    else 9
    end

  fun int(v: I64): USize =>
    if v >= 0 then uint(v.u64())
    elseif v >= -32 then 1
    elseif v >= I8.min_value().i64() then 2
    elseif v >= I16.min_value().i64() then 3
    elseif v >= I32.min_value().i64() then 5
    else 9
    end

  fun float_32(): USize => 5

  fun float_64(): USize => 9

  fun str(data_len: USize): USize ? =>
    if data_len <= _Limit.fixstr() then
      1 + data_len
    elseif data_len <= U8.max_value().usize() then
      2 + data_len
    elseif data_len <= U16.max_value().usize() then
      3 + data_len
    elseif data_len <= U32.max_value().usize() then
      5 + data_len
    else
      error
    end

  fun bin(data_len: USize): USize ? =>
    if data_len <= U8.max_value().usize() then
      2 + data_len
    elseif data_len <= U16.max_value().usize() then
      3 + data_len
    elseif data_len <= U32.max_value().usize() then
      5 + data_len
    else
      error
    end

  fun array(count: U32): USize =>
    if count <= _Limit.fixarray().u32() then 1
    elseif count <= U16.max_value().u32() then 3
    else 5
    end

  fun map(count: U32): USize =>
    if count <= _Limit.fixmap().u32() then 1
    elseif count <= U16.max_value().u32() then 3
    else 5
    end

  fun ext(data_len: USize): USize ? =>
    if data_len == _Size.fixext_1() then 3
    elseif data_len == _Size.fixext_2() then 4
    elseif data_len == _Size.fixext_4() then 6
    elseif data_len == _Size.fixext_8() then 10
    elseif data_len == _Size.fixext_16() then 18
    elseif data_len <= U8.max_value().usize() then
      3 + data_len
    elseif data_len <= U16.max_value().usize() then
      4 + data_len
    elseif data_len <= U32.max_value().usize() then
      6 + data_len
    else
      error
    end

  fun timestamp(sec: I64, nsec: U32): USize ? =>
    if nsec > _Limit.nsec() then
      error
    end
    if (nsec == 0) and (sec >= 0)
      and (sec <= U32.max_value().i64())
    then
      6   // timestamp_32: fixext_4
    elseif (sec >= 0)
      and (sec.u64() <= _Limit.sec_34())
    then
      10  // timestamp_64: fixext_8
    else
      15  // timestamp_96: ext_8 header + 12 bytes
    end

Why a separate primitive

The encoder already has ~46 methods. Adding a parallel set of size methods would double its surface and mix two concerns — writing bytes and computing byte counts. A separate MessagePackSize primitive keeps each focused:

• MessagePackEncoder writes bytes to a Writer.
• MessagePackSize computes how many bytes would be written.

The two are companions, not competitors. Callers who want pre-allocation use both; callers who don't use only the encoder, as they do today.

Exact sizes, not worst-case

Unlike Go's tinylib/msgp which uses worst-case constants, MessagePackSize computes exact sizes. The branching logic mirrors the encoder's format selection — same thresholds, same conditions. This means the computed size is always exactly the number of bytes the encoder will write, with zero over-allocation.

The cost is that the caller must pass values (for integers) or data lengths (for strings, binary, extensions) to the size methods, rather than using constant values. This is the right trade-off for a library where the caller controls encoding directly.

Variable-length methods take lengths, not data

The encoder's str, bin, and ext methods take the actual data (ByteSeq) because they need to write it. The size methods only need the byte length to determine the wire format and compute the total size. Taking USize instead of ByteSeq is more flexible — the caller might know the length before the data is constructed.

Container sizes are header-only

array and map return only the header size, not the total size of the container. The library writes only headers for containers — the caller writes each element individually. The same split applies to sizes: the caller computes element sizes individually and sums them with the header size. See the usage examples below.

Error cases mirror the encoder

Methods that can error on the encoder (str, bin, ext, timestamp) can also error on the size primitive, for the same reasons — data too large, or invalid timestamp values. Methods that are infallible on the encoder (uint, int, array, map, nil, bool, float_32, float_64) are also infallible on the size primitive.

Format-specific sizes

For callers using format-specific encoding methods, the sizes are trivially derivable from the msgpack spec:

Method	Size
nil	1
positive_fixint	1
negative_fixint	1
uint_8 / int_8	2
uint_16 / int_16	3
uint_32 / int_32 / float_32	5
uint_64 / int_64 / float_64	9
fixstr(len)	1 + len
str_8(len) / bin_8(len)	2 + len
str_16(len) / bin_16(len)	3 + len
str_32(len) / bin_32(len)	5 + len
fixarray / fixmap	1
array_16 / map_16	3
array_32 / map_32	5
fixext_1	3
fixext_2	4
fixext_4	6
fixext_8	10
fixext_16	18
ext_8(len)	3 + len
ext_16(len)	4 + len
ext_32(len)	6 + len
timestamp_32	6
timestamp_64	10
timestamp_96	15

Since these are constants (or constant + data length), format-specific size methods would add API surface with minimal value. A table in the documentation (like the one above) may be sufficient. Whether to also expose them as methods on MessagePackSize is an implementation decision that can be deferred.

Documentation and usage guidance

Pre-allocation is a performance optimization. The documentation should make clear when it helps, when it doesn't, and how to use it correctly.

When to use pre-allocation

Pre-allocation helps most when:

• Messages are large — hundreds of fields, large binary payloads, or deeply nested structures where the writer would resize multiple times.
• Message structure is known in advance — the caller can walk their data to compute sizes before encoding.
• Encoding is on a hot path — the allocation savings matter when encoding thousands of messages per second.

When to skip it

Pre-allocation adds complexity with little benefit when:

• Messages are small — a few fields totaling under 1 KB. The writer handles this with one or two resizes at most.
• Structure is dynamic — if the caller doesn't know what they'll encode until they're encoding it, a separate size pass isn't practical.

Usage pattern

The flow is: compute total size, reserve buffer, encode.

use "buffered"
use "msgpack"

// Data to encode
let name: String = "Alice"
let age: U64 = 30
let scores: Array[U64] = [95; 87; 92]

// Step 1: Compute total size
var total: USize = 0
total = total + MessagePackSize.map(3)   // 3 key-value pairs
total = total + MessagePackSize.str(4)?  // "name" key
total = total + MessagePackSize.str(name.size())?
total = total + MessagePackSize.str(3)?  // "age" key
total = total + MessagePackSize.uint(age)
total = total + MessagePackSize.str(6)?  // "scores" key
total = total + MessagePackSize.array(scores.size().u32())
for s in scores.values() do
  total = total + MessagePackSize.uint(s)
end

// Step 2: Reserve buffer
let w: Writer ref = Writer
w.reserve_current(total)

// Step 3: Encode (same order as size computation)
MessagePackEncoder.map(w, 3)
MessagePackEncoder.str(w, "name")?
MessagePackEncoder.str(w, name)?
MessagePackEncoder.str(w, "age")?
MessagePackEncoder.uint(w, age)
MessagePackEncoder.str(w, "scores")?
MessagePackEncoder.array(w, scores.size().u32())
for s in scores.values() do
  MessagePackEncoder.uint(w, s)
end

Without pre-allocation, the code is just step 3 — the encoding calls. Pre-allocation adds step 1 (a parallel traversal computing sizes) and step 2 (a single reserve_current call). The encoding itself is unchanged.

How Writer.reserve_current works

Writer.reserve_current(n) pre-allocates space in the writer's current internal array. This is the buffer that accumulates format bytes, length prefixes, integer values, and small payloads (strings and binary data up to 64 bytes). For payloads larger than 64 bytes, Writer.write() pushes the data directly to the writer's chunk list as a separate entry — these large payloads are not affected by reserve_current.

This means pre-allocation is most effective for messages composed of many small-to-medium values (integers, short strings, headers, small binary data). For messages dominated by a few large payloads, the large payloads bypass the internal buffer regardless, and the pre-allocation benefit is limited to the surrounding headers and metadata.

Container sizing

Container sizes deserve explicit attention in documentation because they're the most common source of confusion. The array and map size methods return the header size only — they don't include the sizes of contained elements. The caller must sum the element sizes separately:

// Size of an array with 3 uint elements:
let header_size = MessagePackSize.array(3)  // header: 1 byte
let elem_1 = MessagePackSize.uint(100)      // fixint: 1 byte
let elem_2 = MessagePackSize.uint(200)      // uint_8: 2 bytes
let elem_3 = MessagePackSize.uint(70000)    // uint_32: 5 bytes
let total = header_size + elem_1 + elem_2 + elem_3  // 9 bytes

This mirrors how encoding works — MessagePackEncoder.array writes only the header, and the caller writes each element. The size computation follows the same structure.

Helper pattern for application types

For applications that encode the same type repeatedly, a natural pattern is to write a size method alongside the encode method:

class UserMessage
  let name: String
  let age: U64

  new val create(name': String, age': U64) =>
    name = name'
    age = age'

  fun encoded_size(): USize ? =>
    var total: USize = MessagePackSize.map(2)
    total = total
      + MessagePackSize.str(4)?
      + MessagePackSize.str(name.size())?
    total = total
      + MessagePackSize.str(3)?
      + MessagePackSize.uint(age)
    total

  fun encode(w: Writer) ? =>
    MessagePackEncoder.map(w, 2)
    MessagePackEncoder.str(w, "name")?
    MessagePackEncoder.str(w, name)?
    MessagePackEncoder.str(w, "age")?
    MessagePackEncoder.uint(w, age)

This keeps the size computation and encoding logic adjacent, making it easy to verify they stay in sync. If a field is added to encode, forgetting to add it to encoded_size will result in under-allocation (the writer falls back to dynamic growth — correctness is preserved, but the pre-allocation benefit is lost for that message).

Scope

This proposal covers:

• A MessagePackSize primitive with compact size methods mirroring MessagePackEncoder's compact encoding methods.
• Documentation explaining when and how to use pre-allocation.
• The interaction with Writer.reserve_current for buffer pre-allocation.

This proposal does not cover:

• Format-specific size methods (can be added later if there's demand, but the table in documentation may suffice).
• Automatic size tracking or validation (the library does not verify that the computed size matches the actual encoded size — this is the caller's responsibility).
• Changes to Writer or any other stdlib type.