Part V LiveFlex Mutable Memory

Book contents · Previous: Part IV Quality and Performance · Next: Appendix A Type Codes and Byte Equations

Chapters 24–30 of FlatBuffers & FlexBuffers: From Bytes to Mutable Memory. Compatibility, cells, descriptors, allocation, reclamation, containers, transactions, snapshots, and staged delivery.

This is the supplied first edition, pinned to its September 2026 source baseline. The laboratories and LiveFlex capstone are educational implementations and design proposals. The book overview explains the evidence limits; Reaktor’s performance review documents the current framework.

In this part

• Chapter 24: Capstone: choose the compatibility contract first
• Chapter 25: The 16-byte cell and the 32-byte descriptor
• Chapter 26: Allocation, roots, reclamation, and compaction
• Chapter 27: Fast containers without a declared schema
• Chapter 28: Transactions, borrows, and concurrent snapshots
• Chapter 29: Freeze and thaw without changing the standard
• Chapter 30: Build the capstone in stages, then earn its speed

Chapter 24: Capstone: choose the compatibility contract first

Mutable-memory engine design

Call the capstone LiveFlex. It is a schemaless in-memory value engine with native mutable containers and standard FlexBuffers import/export. Its primary workload is a working document that receives many small edits and repeated lookups between snapshots. Numeric arrays should support bulk computation without per-element boxing. Structural growth should not rewrite unrelated parts of the document.

The design is for a 64-bit process with a single owner of mutable state. Concurrent readers initially receive immutable snapshots, not unsynchronized access to the mutable heap. Counts and handle indices use explicit bounded integer domains; oversized inputs produce errors rather than implicit truncation. Export has a configurable size and depth budget chosen to match the intended consumers.

The supported logical domain includes null, bool, signed and unsigned 64-bit integers, floating values, UTF-8 strings, keys, blobs, vectors, and string-keyed maps. Homogeneous native arrays are an internal specialization of vectors. Application-specific timestamps or identifiers require an explicit application convention; they are not silently assigned unused wire type codes.

What compatible means here

Every successful export must be an ordinary FlexBuffer under the selected profile. No custom reader, absolute pointer, external arena lookup, or private type code is needed to read that snapshot. Import accepts the supported ordinary wire forms and normalizes them into the live value model.

The live bytes are not themselves an ordinary FlexBuffer. A native cell, descriptor, hash index, or spare-capacity region is not passed to flexbuffers::GetRoot. Compatibility exists at the explicit freeze/thaw boundary. Exact byte identity, original scalar widths, original type-table choices, and original sharing identity are not preserved unless a separate fidelity mode is implemented.

Container sharing is allowed in live memory. Cycles can be staged by the low-level laboratory API, but an exported root must be acyclic within the supported traversal limits. Export detects a cycle and fails. A stricter application can forbid cycle-creating edits or validate at transaction commit. Do not promise constant-time arbitrary graph insertion and free acyclicity checks at the same time.

Why not just add capacity to a FlexBuffer?

There is no standard capacity field. A sidecar can remember reserved free bytes, but ordinary readers still interpret count, slots, and type tables according to the current wire layout.

For a typed numeric vector with a sufficiently wide count and reserved space, append can indeed be cheap: write the new element and update the count. This is a useful bounded-mutation design. For an untyped vector, however, the type table must begin immediately after the logical slot array. Appending one slot requires moving the existing type bytes out of its way. Even with spare storage, that step is proportional to the current tag count.

An indirect append has another constraint: the new child's bytes must be before the new offset slot. A child appended after an existing parent cannot be reached by a standard backward offset from that parent. An allocator could reserve earlier space, or the parent could be moved/rebuilt later, but either choice introduces explicit capacity or relocation constraints.

Maps add lexical order. Inserting a key can shift key and value slots, requiring their relative offsets to be adjusted. Spare allocation capacity does not remove these ordered-layout obligations. A continuously compatible wire arena is possible for a defined mutation envelope; it is not a universal constant-time editing structure.

A genuine continuously compatible alternative: an append log

Another valid design appends a changed child, then appends rebuilt ancestors and a new root trailer. Old bytes remain in the buffer. The new root can point backward to both unchanged old subtrees and newly emitted children. An ordinary reader using the new published extent can read the latest snapshot.

This WireLog design preserves the standard wire grammar after each completed publication. It is attractive for infrequent edits and substantial subtree reuse. Its costs are ancestor/container rebuilding, accumulated unreachable bytes, periodic compaction, and careful ownership when the backing allocation grows. Existing views cannot survive a std::vector reallocation merely because internal offsets remain correct.

For a shared child, rebuilding only one path gives replacement semantics along that path, not automatic mutation of every alias. Identity-wide updates require finding and rebuilding all affected references or a different policy. Again, compatibility does not determine mutation semantics by itself.

LiveFlex chooses native editing because its target workload includes repeated arbitrary growth. WireLog remains a serious alternative to benchmark, not a straw man dismissed as impossible.

The non-goals keep the design small

The baseline is not a database, a garbage-collected language VM, a universal lock-free graph, or a new persistent wire standard. It does not include a query language, write-ahead log, distributed identity, or arbitrary user-defined objects. Those can be layered later if a real application requires them.

The central fast paths are simple: update an inline scalar, append within capacity, resolve a stable handle, find an interned key, scan a typed array, and export a bounded acyclic root. Everything else should preserve these paths rather than burden every cell with speculative features.

A proposed public surface

The exact C++ types can evolve, but the operations should make costs visible:

Document
  make_map(), make_vector(), make_numeric_vector(kind)
  make_string(bytes), make_blob(bytes)
  intern_key(text) -> document-scoped Key
  set(map, Key, Value), find(map, Key), erase(map, Key)
  append(vector, Value), replace(vector, index, Value)
  borrow_numbers(vector, write_guard) -> limited-lifetime span
  register_root(Value) -> RootToken
  collect()
  freeze(root, export_options) -> owning immutable buffer
  thaw(verified_buffer, import_options) -> Value

A stable handle is a logical identity, not a permanent pointer. A borrowed span is a temporary capability, not a handle. A root token keeps reachable native objects alive; a copied observer cell alone need not. These distinctions are the foundation of the following chapters.

Checkpoint

Exercise 26. Choose between LiveFlex and WireLog for a read-mostly configuration document and for a rapidly growing simulation state. Include snapshot frequency, alias semantics, memory retention, and the cost of updating one element of a large vector.

Chapter 25: The 16-byte cell and the 32-byte descriptor

Keep ordinary scalars inline

A generic value should not allocate merely to store an integer. The laboratory and proposed engine use a straightforward 16-byte cell:

struct alignas(8) Cell {
    std::uint64_t payload;
    std::uint32_t aux;
    Kind kind;                 // one byte
    std::uint8_t flags;
    std::uint16_t reserved;
};

The implementation asserts its size, alignment, and relevant field offsets. Signed and unsigned integers occupy the full payload. A floating value stores its binary64 representation. Bool and null use canonical payloads. No width changes are needed when a signed value grows from 127 to 128 or from 32-bit to 64-bit range.

This is a native layout, not a portable serialized structure. It must not be dumped to a file and called FlexBuffers. Its purpose is to make mutation simple and predictable; compression is deferred to export or to specialized native regions.

Short text uses the otherwise available bytes

A string or key of at most twelve bytes can occupy the first twelve bytes directly. Its kind and length remain in the metadata bytes. No terminator is stored in the cell; access uses the recorded length. This avoids an external allocation for many short names and labels.

The constructor must not copy beyond byte 11. It initializes the cell first, writes only the permitted content range, and leaves the kind/flags intact. The companion uses memcpy into the object representation of a trivially copyable cell, with unsigned integer storage in the overwritten fields.

Returning a view into a by-value temporary cell would dangle. The laboratory therefore returns an owning string from text(Cell). An optimized API can instead return a text-slice object that owns its inline bytes or borrows an external payload under a guard. This API issue is easy to miss when the inline layout looks appealing on paper.

External values use generational handles

For an external object, the payload packs a 32-bit slot index and a 32-bit generation. The aux field identifies the owning document. Resolving the handle checks the owner, slot range, live state, generation, and expected kind before exposing the payload.

The index gives stable logical identity across payload growth. The generation detects a stale handle after a freed slot is reused. The owner prevents a numerically identical handle from another document being interpreted in the wrong directory. These are correctness checks, not cryptographic capabilities: a raw memory-corrupting caller is outside this abstraction's safety boundary.

On generation exhaustion, retire the slot rather than wrapping to a value that could match an ancient observer. On document-identity exhaustion, fail or move to a wider identity scheme rather than silently reusing an identity. Such limits are rare but should have a defined outcome.

The proposed descriptor

The optimized design stores external-object metadata in stable descriptor blocks. On the chosen 64-bit ABI, this proposed descriptor fits in 32 bytes:

struct alignas(8) Descriptor {
    std::byte* data;            // 8
    std::uint32_t size;         // 4
    std::uint32_t capacity;     // 4
    std::uint32_t generation;   // 4
    std::uint16_t kind;         // 2
    std::uint16_t flags;        // 2
    std::uint64_t layout_epoch; // 8
};

size and capacity are measured in elements for vectors and in bytes for text/blob payloads; the kind determines the unit. A map block has a separately defined bucket layout and occupancy policy. Allocation-class metadata can live in the allocator rather than consuming another word in every descriptor.

layout_epoch changes when positions or container edges relevant to cached paths change. A document-wide content revision tracks whether a previously frozen whole-document snapshot remains current. These are different from the generation: an object can change many times without being freed.

This descriptor is a design proposal, not the layout of mutable_lab.hpp. The laboratory uses a slot containing a generation and a unique_ptr to a variant node. That simpler representation lets the semantics be tested before custom storage is introduced.

Stable descriptors, movable payloads

When a vector grows, allocate a larger payload, move or copy its live elements, then update the descriptor's pointer and capacity. Every handle still identifies the same descriptor slot. References stored in parent cells do not need to be rewritten.

A pointer or span into the old payload does become invalid. Stable identity and stable address are different promises. The API forbids growth while a conflicting borrow is active and does not expose permanent pointers as its ordinary handle type.

The extra descriptor lookup is a real cost. Direct pointers can remove one level of indirection but make relocation, stale-reference detection, and cross-language validation harder. The capstone pays the lookup for external objects while leaving scalars and short text inline and providing bulk typed borrows to amortize repeated resolution.

Account for memory honestly

A vector of N generic scalars with capacity C needs approximately 16 * C payload bytes plus one descriptor and allocator/directory overhead. It does not need a descriptor per scalar. A typed binary64 vector needs approximately 8 * C payload bytes plus the same kind of container metadata.

A long string adds an external descriptor and its allocated byte capacity. An interned map key can be stored once in the document's symbol storage and referenced by compact IDs across maps. These distinctions matter far more than reporting “16 bytes per value” as though that number included every allocation and index.

On a machine with 64-byte cache lines, four cells fit in one line when suitably placed. That is a useful illustrative packing calculation, not a universal hardware assumption or a guarantee that one lookup touches only one line.

Checkpoint

Exercise 27. Calculate the approximate payload and descriptor memory for a vector of one million integers in generic cells versus a typed 64-bit array, both with 25 percent spare capacity. State what your estimate excludes.

Chapter 26: Allocation, roots, reclamation, and compaction

Separate descriptor storage from payload storage

A descriptor directory should not require moving every descriptor when it grows. One simple design allocates fixed-size blocks and keeps pointers to those blocks in a growable directory. With a design block size of 4,096 bytes and 32-byte descriptors, each block contains 128 descriptors. This is an allocator geometry choice, not an assumption about the operating system's page size.

A handle index can be split into a block index and an in-block index. The outer directory can move because callers do not retain pointers into that vector; descriptor blocks themselves stay at stable addresses. The document owner resolves the current directory for each external access.

The laboratory obtains stable node addresses through unique_ptr instead. Replacing it with blocks is an optimization behind the same logical handle contract, which is precisely why the handle layer is useful.

Use different allocation policies for different lifetimes

Temporary builder descriptors and transaction scratch data can use bulk-lifetime storage. Long-lived mutable payloads need reuse. Small payloads can use size classes; large arrays can use geometric growth with less aggressive rounding. A reusable standard pool allocator is a reasonable first implementation before custom slabs are justified. [14]

Do not apply independent growth rounding at several layers without accounting for the combined waste. A vector that grows geometrically and then rounds into a much larger slab class can retain far more slack than intended. Derive capacity from the actual allocated byte count, and report the resulting high-water mark.

For numeric arrays, allocate correctly aligned storage and establish the lifetime of the actual element objects. Returning std::span<double> from arbitrary serialized bytes is not equivalent to returning it from a native array of live doubles. The bulk API should rest on a real typed allocation, not a convenient reinterpret cast.

Allocation must precede publication

A grow operation should reserve every resource it needs before changing the visible descriptor. Allocate the destination block, construct or copy the live elements, initialize the new element, and only then replace the descriptor's data pointer, size, and capacity. If allocation or construction fails earlier, the old object remains intact.

For trivially copyable cells and numeric payloads, the copying path is simple. For a more general future object type, exception-safe move construction becomes a separate problem. The baseline avoids arbitrary user-defined objects partly to keep this operation predictable.

After publication under exclusive ownership, retire or release the old payload. If snapshots share it, physical reclamation must wait until their ownership ends. “Update the pointer and free the old block” is correct only in the no-borrow, no-snapshot-sharing case.

A copied cell is not automatically a root

The memory manager must know which objects remain reachable from the application. The laboratory makes this explicit: collect(roots) receives the complete set of live external roots. A cell held in a local variable but omitted from that set can become a stale observer after collection.

A production interface should make root registration harder to forget. A move-only RootToken can register a cell in the document's root set and unregister it on destruction. Internal cells stored in containers are traced through their parent; they do not each need a reference count. Temporary observers are valid only while some registered root or operation guard keeps the target alive.

This avoids putting an atomic ownership counter in every scalar value. It also makes collection a deliberate operation rather than an invisible consequence of every assignment. The price is a root discipline that must be documented and tested.

Mark and sweep with generations

Marking starts from registered roots. Resolve each external handle, mark its descriptor, and traverse child cells only for container kinds. An already marked descriptor is not traversed again. This handles shared subgraphs and unreachable cycles without recursive reference-count leaks.

Sweeping releases unmarked live payloads, marks their slots free, and increments the generation before reuse. A slot whose generation is exhausted is retired. Temporary work memory should be reserved or bounded before sweeping mutates the heap, so an allocation failure does not leave reclamation half-published.

The laboratory uses an explicit worklist and a mark bitmap. Its symbol strings are retained until document destruction; they are not reclaimed by collect. The optimized design should either retain that simple bounded-interner policy or introduce a separately tested symbol-lifetime scheme. Reusing a key ID without accounting for existing maps would corrupt lookup meaning.

Cycle policy and collection policy are different

A collector can reclaim an unreachable cycle even though FlexBuffers export cannot represent that cycle as an ordinary finite value tree/DAG under this design. Supporting cycle detection in the collector does not imply cycle support in the interchange contract.

For applications requiring every committed state to be exportable, validate acyclicity at commit or restrict ownership to a tree discipline. A tree discipline can make insertion checks cheaper but changes sharing semantics. The capstone's low-level laboratory allows staging and rejects cycles at freeze; a production API must select and expose its stronger policy deliberately.

Compaction without changing handles

Payload compaction can move live payloads and update their descriptors while preserving handle indices and generations. This is an advantage over embedding raw payload pointers throughout the document. It still requires an exclusive phase or a versioned/snapshot-aware relocation scheme because active borrows point to old addresses.

Descriptor compaction is different. Moving a descriptor to another logical slot would change its handle identity unless an additional forwarding mechanism is introduced. The baseline keeps descriptor slots stable and compacts only payload storage. Free descriptor slots are reused through generations rather than renumbered.

Compaction should be triggered by measured fragmentation and retention, not run after every edit. Its pause time, peak temporary memory, and interaction with snapshots belong in the benchmark ledger.

Checkpoint

Exercise 28. A vector handle survives payload growth but becomes invalid after collection and slot reuse. Explain exactly which metadata changes in each case. Then describe what happens to a raw span obtained before each operation.

Chapter 27: Fast containers without a declared schema

Generic vectors are the baseline

A generic vector stores contiguous 16-byte cells with a size and capacity in its descriptor. Replacing an existing scalar cell does not move other elements. Appending within capacity writes one cell and increases size. When capacity is exhausted, growth allocates a larger payload and updates the stable descriptor after copying.

Geometric growth gives amortized constant-time append, not constant worst-case latency. A growth event copies the existing live array. Middle insertion and order-preserving erase move a suffix and are linear in its length. These costs should be part of the API documentation and benchmark matrix.

A stable vector handle does not make element indices stable after insertion or erasure. Nor does it make pointers to elements survive growth. Applications needing stable per-element identities should store explicit object handles or choose a different sequence structure; the baseline does not add an allocation and identity to every array element.

Homogeneity can be discovered at runtime

A vector filled with signed integers does not need a tag beside every element. The optimized design can store a homogeneous native lane such as I64, U64, F64, or byte-sized boolean storage. The descriptor carries the lane kind. The public interface can remain schemaless because the specialization is selected from observed values or an explicit runtime request.

The simplest policy is monotonic promotion during ordinary editing. Begin in a compact typed lane when the intended kind is known. Append compatible values without changing representation. On an incompatible insertion, allocate a generic cell vector, convert the existing elements, append the new value, and publish the new representation under the same handle.

Do not automatically convert signed integers to floating point merely because a float arrives. Large integers may lose exactness. Do not merge signed and unsigned domains without checking representability and the promised type semantics. Falling back to tagged cells is often the correct lossless choice.

Automatic demotion after every erase can cause representation thrashing. Make compaction or re-specialization explicit, or require sustained evidence before changing back. This is a small example of hysteresis: use different conditions to enter and leave an optimized state.

A bulk borrow resolves once

A typed numeric operation should resolve the handle, validate the lane, and obtain a bounded span once. Its inner loop then works on actual native numeric objects. The borrow contract prevents growth, reclamation, or incompatible mutation until the borrow ends.

The laboratory exposes numbers() for its F64 node and relies on the documented single-owner discipline. A production wrapper should track active borrows in debug builds and make unsafe escapes difficult. A const borrow and a mutable borrow have different permissions; neither is automatically valid across a concurrent writer.

Bit-packed booleans are an optional specialization for memory-sensitive sets or bulk bit operations. They make individual updates read-modify-write operations and complicate parallel access to neighboring bits. Byte booleans are a simpler baseline. Export to the standard boolean-vector representation may expand a packed native bitmap, so include that cost.

Tiny maps should not pay for a large index

A map with only a handful of fields can use a short array of key IDs and cells. Linear search over compact IDs avoids hashing/probing metadata and keeps iteration simple. The precise crossover to a hash table is a benchmark parameter, not a universal constant such as “always eight keys.”

The laboratory uses a linear vector of (KeyId, Cell) pairs for every map size. This is intentionally a semantic baseline, not its proposed high-performance large-map representation. It gives a clear reference for insertion, replacement, lookup, and erase.

An optimized implementation can keep separate key-ID and value arrays for dense small maps, avoiding padding between a four-byte ID and a sixteen-byte value. If it instead uses a C++ pair or struct, measure its actual sizeof; the sum of member sizes is not necessarily the stride.

A concrete group-probed hash-map design

For larger maps, the proposal uses three arrays in one allocated block: one control byte per bucket, one 32-bit key ID per bucket, and one cell per bucket. Each array is aligned for its own accesses. A control byte stores either a small fingerprint or an empty/deleted state.

The principle is inspired by Swiss-table metadata filtering, but the following is an independent baseline algorithm rather than a claim about Abseil's exact probe sequence. Choose a power-of-two number of fixed-width groups. Hash an interned key ID to a starting group and a seven-bit fingerprint. Search a group's control bytes in parallel or with a scalar fallback, then compare actual key IDs at candidate positions. [11]

The lookup rules are:

for each group in the bounded probe sequence:
    candidates = occupied controls matching the fingerprint
    for each candidate bucket:
        if stored_key_id == requested_key_id:
            return its value
    if the group contains an empty bucket:

TEXT · continued

        return missing
return table-invariant failure or missing, by policy

Deleted buckets do not terminate a search. An insertion remembers a reusable deleted bucket but continues until it finds the existing key or a genuinely empty stopping group. Otherwise a key already farther along the probe sequence could be inserted a second time.

The descriptor stores live count in size and bucket count in capacity. A proposed 16-byte map-block header stores the tombstone count and probe-policy metadata. With a bucket count that is a multiple of a 16-byte group, controls begin at block offset 16, key IDs at 16 + M, and cells at 16 + 5 * M. A suitably aligned block then occupies 16 + 21 * M bytes before allocator rounding. The header is additional to the 32-byte descriptor.

For a first implementation, use aligned full groups and a simple bounded linear group sequence. This avoids out-of-bounds wraparound SIMD loads. More elaborate probe sequences and unaligned metadata windows are later optimizations that must retain complete coverage of the table and safe readable ranges.

Rehashing is a staged operation

Track live count and deleted count separately. Too many tombstones can lengthen probes even when live occupancy is moderate. A rehash can rebuild at the same capacity to remove tombstones or grow when live occupancy requires it. A load-factor threshold such as 7/8 is a starting experiment, not a guaranteed optimum.

Allocate and initialize the new block first. Reinsert live entries into it. Only after success replace the descriptor's block pointer and capacity. Increment its layout epoch so cached bucket positions are invalidated. The logical map handle remains unchanged.

At occupancy fraction a, this direct-bucket design uses roughly 21 / a bytes of control, key-ID, and cell storage per live entry, before alignment and descriptor overhead. At a = 7/8, that is about 24 bytes per entry. It excludes interned key bytes and any child payloads. This is a layout calculation, not a measured resident-memory result.

A dense-values-plus-index design can improve full-map iteration, but it adds an index indirection and another set of storage trade-offs. Benchmark it when iteration dominates; do not add it merely because “dense” sounds faster.

Intern keys once, but bound the interner

The document interner maps a UTF-8, zero-free key to a stable ID. A public Key handle includes document identity so an ID from one document cannot silently refer to a different name in another. Repeated hot lookups should accept that handle rather than rehash the original string every time.

Store immutable key bytes in stable storage. IDs are not reused while maps can still contain them. For untrusted arbitrary keys, choose a hash policy and resource limits that address adversarial collision and memory-growth behavior. A fast fingerprint is not a cryptographic identity.

The simplest lifetime policy retains symbols until document destruction and caps their total bytes/count. More elaborate symbol reclamation requires tracing every map's IDs or maintaining separate ownership. It should not be smuggled into the initial allocator as an untested side effect.

Strings and blobs use replacement semantics initially

The baseline treats text and blob values as values to replace, while containers have stable shared identity. Assigning a longer string to one map entry does not mutate every other entry that happened to share the old text payload. A small value may become external or vice versa without changing the parent container's identity.

An optimized setter can reuse an external payload only when uniqueness and active-borrow rules make that safe. Without such evidence, allocate the replacement, publish the new cell, and reclaim the old unreachable payload later. Copy-on-write is an ownership algorithm, not an assumption that a pointer “probably has only one user.”

Checkpoint

Exercise 29. Implement the scalar fallback for the group-probed map before adding SIMD. Test collisions, deletion in the middle of a probe chain, duplicate replacement, same-capacity rehash, growth failure, and a cached bucket invalidated by a layout-epoch change.

Chapter 28: Transactions, borrows, and concurrent snapshots

Start with one mutable owner

The baseline document is single-threaded or externally protected by an exclusive lock. This removes per-cell atomic operations from ordinary mutation and makes allocation, growth, and collection easier to reason about. It does not prevent multiple threads from reading independent immutable snapshots.

A document-level write guard can establish the exclusive phase. Mutable typed borrows exist only inside a compatible guard and prevent operations that would relocate their payloads. In debug builds, active-borrow counters can catch accidental growth or collection while a borrow is live.

The laboratory documents this discipline but does not implement a complete guard type system. Its std::span<double> can be misused if retained after growth or destruction. The proposed production API must close that gap before claiming safe general-purpose borrowing.

Single-operation safety before transactions

Each primitive operation should first provide its stated exception guarantee. A scalar replacement can be non-allocating. A growth operation stages new storage before publishing it. A key insertion must not leave a half-interned symbol or a half-filled map bucket visible after failure.

A multi-operation transaction is a stronger requirement. It must restore all visible changes when a later operation fails, not merely keep each individual object internally valid. The laboratory does not provide that guarantee. A failed multi-step import can leave unreachable allocated objects that a later collection reclaims.

For a first transactional implementation, use an undo journal under exclusive ownership. Record an old cell before replacing it. For structural container edits, either record enough inverse information or stage a complete replacement payload while retaining the old one until commit. Reserve journal capacity before making a change whose rollback would otherwise need to allocate.

A practical commit protocol

A transaction stages allocations and records changes. Before publication, validate document-level invariants required by the application, including acyclicity when every committed root must be exportable. On success, increment the document revision and make the new root/version visible. On failure, replay undo records in reverse and release staged allocations.

Reclamation must not destroy the old payload before rollback is no longer possible. Likewise, newly interned symbols must either be rolled back safely or remain as harmless retained interner entries under a documented policy. Retaining unused immutable symbols can preserve logical rollback while weakening a strict memory-rollback guarantee.

Not every application needs transactions. A builder-style edit batch that is discarded wholesale on failure can be simpler. Add all-or-nothing editing when the application requires it, rather than imposing journaling overhead on every scalar update by default.

Publish immutable wire snapshots first

The simplest concurrent-reader path is to freeze a completed root into an owning immutable byte buffer, verify it, and publish shared ownership of that snapshot. Readers acquire a snapshot once per request or operation batch and keep it alive while using borrowed views.

Conceptually:

std::atomic<std::shared_ptr<const Snapshot>> published;

// Writer, after complete construction and validation:
published.store(next_snapshot, std::memory_order_release);

// Reader, retaining ownership for its complete traversal:
auto snapshot = published.load(std::memory_order_acquire);

This uses standard atomic shared-ownership facilities. It is not necessarily lock-free, and destruction/deallocation of replaced ownership can have costs outside the atomic update itself. Acquire ownership once per meaningful read session rather than incrementing a shared counter for every field access. [15]

The bytes reachable through the published snapshot must actually remain immutable. An atomic pointer to a structure whose contents are still being modified is not an immutable snapshot.

Why a naive seqlock is not enough in C++

A tempting design reads a version counter, reads ordinary non-atomic payload fields, then retries when the version changed. That can detect inconsistency at an algorithmic level, but it does not automatically make conflicting non-atomic accesses legal under the C++ memory model. A data race is not repaired retroactively by discarding the result. [13]

Use locks, appropriately atomic payloads, or immutable versioned objects with a valid reclamation scheme. Sixteen-byte cells are not universally atomic. Even when a target supports a wide atomic instruction, it does not solve variable-size payload lifetime and consistency by itself.

This is why the baseline deliberately avoids a universal lock-free mutable document. The complexity belongs in a narrowly specified later design, supported by concurrency tests and memory-model reasoning.

Native copy-on-write snapshots need versioned resolution

A future optimization can avoid serializing every snapshot by sharing immutable native payloads. But copying a payload is insufficient if an old snapshot still resolves its handles through the writer's mutable descriptor directory. Updating that shared descriptor would make the old snapshot see the new payload.

A correct design gives each snapshot its own immutable view of the descriptor directory. Directory pages can be shared until modified; a writer clones the affected directory page and payload before publication. A handle is then resolved through the snapshot's directory version, not through a global current directory.

Old generations and payloads remain valid in old snapshot directories until those snapshots are released. A slot reused in the current document can have a newer generation while an old snapshot still owns the previous descriptor version. Physical memory reuse must respect both lifetimes.

This is a substantial extension. It affects collection, directory ownership, interner storage, mutation journaling, and cached paths. The wire-snapshot baseline should be measured before paying for it.

Reclamation and latency

Reference-counted snapshot ownership is simple, but the last reader can inherit a large destruction cost. A controlled retirement queue can move bulk release into a chosen maintenance phase. Epoch-based reclamation can reduce per-read reference-count traffic, but it requires disciplined reader registration and protection against stalled readers retaining unbounded memory.

These are alternatives to evaluate, not features required in the first capstone implementation. The correct policy depends on snapshot size, reader duration, latency requirements, and the acceptable retained-memory bound.

Checkpoint

Exercise 30. Explain why a copy-on-write payload plus one globally mutable handle directory is not sufficient for immutable snapshots. Draw the two directory versions needed when one vector grows while an old reader is still active.

Chapter 29: Freeze and thaw without changing the standard

Define semantic equivalence first

The baseline import/export contract preserves null, bool, signed versus unsigned integer values, text bytes under the chosen UTF-8 policy, blob bytes, vector order, and map associations. It does not preserve insertion order for maps because the wire map is sorted. It does not promise the original choice between direct and indirect numbers, the original slot widths, fixed versus variable vector form, or sharing identity after import.

Finite numeric values and signed zero require deliberate exactness tests. NaN payload fidelity and exact physical floating width are separate optional requirements; do not infer them from a generic numeric API or ordinary equality. A bit-exact application can require a strict representation mode or use an explicitly defined bit payload.

The deprecated typed-string form is accepted only under its documented limited compatibility interpretation. A new exporter does not generate it. A successful modern export must use only the standard active forms supported by the target profile.

Postorder emission

Freeze walks children before parents. It emits text/blob payloads and nested containers, retains their construction descriptors, then emits the containing vector or map. Finally it emits the root trailer. This is the same ordering principle used by the wire writer in Chapter 16.

For external live objects, maintain a completed-object map from handle to emitted descriptor. A second reference to the same completed object can reuse its wire location. Maintain a separate active-path set to reject cycles. Check depth, work, output-size, and temporary-memory budgets before unbounded growth.

emit(value):
    if external and in completed:
        return completed[value]
    if external and in active:
        fail with cycle error
    add external value to active
    recursively emit required children
    emit this object's standard representation
    remove external value from active
    remember completed descriptor
    return descriptor

The completed key must identify the live object generation, not just a recyclable slot index. The laboratory uses the packed generation/index handle within one document for that purpose.

Native map order is not wire map order

A hash map is iterated according to its storage, not lexical key order. Freeze collects live key/value associations, sorts them by the actual encoded key bytes, and emits the key vector and corresponding values in that order. Sorting by interned numeric key ID would be wrong because ID assignment order is not lexical order.

For a map with K entries, the comparison sort costs roughly O(K log K) comparisons, with key-byte comparison cost included. Stable shapes or a cached lexical order can reduce repeated work when the key population is unchanged, but a cache must be invalidated on relevant structural edits.

This sorting cost is one of the explicit prices of using a hash-based live map with a sorted wire map. Batching many edits between freezes amortizes it. A workload that freezes after every tiny edit may prefer a different live representation or WireLog.

Typed arrays and width selection

A native 64-bit integer lane can export to a narrower typed vector when every value and the vector count fit the selected width. A binary64 lane can use a narrower floating representation only under the selected exactness policy. The count still participates in the wire width solver.

This is a scan of the array before or during emission. It is not free compression. A caller can choose an export policy that preserves a wide representation when avoiding repeated narrowing analysis matters more than a smaller snapshot. The output remains standard either way if the widths and values are encoded correctly.

The laboratory's F64 node exports as a typed floating vector. Other imported typed vectors may become generic live vectors and later export in a normalized form. Physical form preservation is intentionally outside its baseline contract.

Thawing should not confuse values with identities

The simplest thaw verifies the source and recursively constructs native values. It can duplicate a shared wire child rather than preserving the source's sharing identity. That preserves the logical tree value under the baseline contract, but later mutations of one native copy do not automatically affect another.

An identity-preserving importer can memoize by source buffer, target, type, and width. It must define how inline values, shared immutable text, and containers are treated. A lazy importer can retain immutable wire subtrees and materialize only edited regions, but then the live engine needs a dual traversal path and ownership of the original buffers.

Lazy import is especially attractive for large mostly-read documents. It is a later measured optimization, not a requirement for a clear first implementation. The companion performs eager import and states its normalization behavior explicitly.

Incremental export is not automatically zero-copy

A previously serialized subtree can be copied as a block only when all internal relative references, required prefixes, and alignment conditions remain valid after relocation. References to shared objects outside that block break the simple closed-block assumption. A buffer slice that looks like one subtree may not contain every byte it needs.

An ordinary FlexBuffer also cannot point into multiple unrelated allocations using native pointers. Standard export ultimately needs one coherent byte-addressed representation. Scatter/gather transport does not change what the receiving reader expects its offsets to mean.

The easiest cache is the whole immutable snapshot: when the document revision has not changed, return the same owned snapshot. Per-subtree caches require dependency tracking. A child mutation can invalidate every cached ancestor that embeds that child's serialized bytes, even when the ancestors' own field populations did not change. Shared graphs make this a real dependency problem.

Verification at the export boundary

During development, run the strict verifier on every emitted snapshot and compare it with the native reference model. In qualification, run the independent official readers as well. Once the writer is well tested, a production build may make redundant self-verification optional under an explicit trust policy.

Do not publish partially emitted bytes. A snapshot becomes visible only after its complete trailer and ownership are established. A failed freeze leaves the previous published snapshot intact. That simple publication rule is one of the strongest reasons to keep mutable storage and interchange storage separate.

Checkpoint

Exercise 31. A cached serialized map contains a shared child vector that another map also references. The child changes without either map's key set changing. Which caches are invalid, and why is a key-population version insufficient to decide?

Chapter 30: Build the capstone in stages, then earn its speed

Run the supplied laboratory

The companion can be built without the official runtime:

SH

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j2
ctest --test-dir build --output-on-failure
./build/flexbook_demo
./build/flexbook_fixtures fixtures

The demonstration constructs a map, creates a typed numeric vector, grows it, changes a number through a native span, replaces a short string with a longer string, and freezes the result. Its recorded output is:

frozen bytes: 79
name: A longer replacement
samples[0]: 42

That output comes from the included code, not from a hypothetical optimized engine. It establishes the essential workflow: native edits followed by a standard-layout snapshot that the teaching verifier and reader can navigate.

Read the three core files in order

flat_table_lab.hpp is a compact schema-specific example of front-root navigation, signed vtable displacement, optional field lookup, and forward child references. Its scope is deliberately one table.

flex_wire.hpp contains the complete educational wire implementation: type codes, checked arithmetic, scalar loads, UTF-8 validation, the width-solving writer, reference navigation, strict verification, re-encoding, and constrained mutation. Read the helpers before the containers. Then compare the reader and writer formulas line by line.

mutable_lab.hpp contains the native cell, document ownership checks, generational slots, interning, standard-container nodes, mutation operations, explicit-root collection, and freeze/thaw. It is short enough to understand as a whole before replacing any storage component.

What is implemented and what is proposed

This table is part of the project's contract. Do not rename the laboratory “production LiveFlex” merely because it demonstrates the same high-level workflow.

Stage one: qualify the wire layer

Complete the independent interoperability matrix before optimizing the native heap. Add official C++ tests in both directions and a second language reader. Expand the generated corpus to cover every advertised type and width combination. Add allocation-failure and byte-scan-budget tests. Keep all counterexamples as regression fixtures.

Make public construction descriptors opaque and separate verified immutable owners from raw spans. Add an iterative verifier with explicit work and byte budgets when hostile or deeply shared inputs are in scope. Test on the intended architectures and endian environments rather than assuming one x86-64 run establishes portability.

Acceptance is behavioral: valid supported input is read correctly, invalid input is rejected safely, resource limits are reported distinctly, and produced bytes are read by independent implementations. A green build is not that acceptance test.

Stage two: replace one storage component at a time

Introduce stable descriptor blocks while keeping standard payload containers. Compare all stateful tests against the laboratory. Then introduce reusable payload allocation. Then add typed lanes and promotion. Then implement the scalar group-probed map, followed by SIMD only after its probe invariants are tested.

At every step, preserve a way to run the same operation trace through the reference laboratory. A performance improvement that changes aliasing, presence, signedness, or failure behavior is not a valid optimization unless the public contract is intentionally changed.

Use benchmarks to select small-map thresholds, growth factors, slab cutoffs, and metadata group width. Keep the configuration surface small. Parameters that do not materially affect the intended workloads should not become permanent public complexity.

Stage three: add only required ownership features

Introduce root tokens and guarded borrows before general application adoption. Add transactions when multi-operation rollback is required. Add immutable wire-snapshot publication before native copy-on-write snapshots. Add epoch reclamation only if measured reference-count or destruction costs justify it.

Each new feature should have a failure story. What happens when an allocation fails halfway through a rehash? When a root is released during a pending transaction? When a reader retains a snapshot indefinitely? When a generation or version reaches its limit? When an export encounters a cycle or exceeds its budget?

The ability to answer these questions precisely is a stronger sign of implementation quality than an impressive list of data-structure techniques.

Stage four: establish the performance frontier

Publish results for defined workloads and machine configurations, including the official implementation and simple standard-container baselines. Report both speed and memory, and include freeze frequency and retained snapshots. Keep unsuccessful optimization experiments so future maintainers understand why an apparently clever design was rejected.

A good result may be conditional: LiveFlex wins on repeated structural editing and typed numerical updates, while a verified wire buffer wins on sparse reads of compact immutable data. That is not a failure of the capstone. It is the expected result of designing representations for different jobs.

The final mental model

FlatBuffers teaches how a schema can remove repeated type information while vtables preserve field discoverability and evolution. FlexBuffers teaches how a buffer can carry its own types while using widths and relative references to stay compact. LiveFlex teaches where mutability needs identity, capacity, lifetime, and synchronization that a compact wire layout does not supply.

Once those three models are clear, the design choices stop looking arbitrary. You can read the official source as a collection of mechanisms serving explicit constraints—and build your own implementation without confusing a convenient API, a valid byte format, and a fast mutable engine.

Checkpoint

Exercise 32. Choose one proposed optimization and write its acceptance gate: required invariants, reference-model comparisons, adversarial tests, benchmark workloads, and the condition under which you would remove it again.

Book contents · Previous: Part IV Quality and Performance · Next: Appendix A Type Codes and Byte Equations