absl::Cord Chunks Memory Overhead and Copy-on-Write Triggers

Every absl::Cord chunk carries a 16-byte CordRep header, with total node sizes ranging from 16 bytes for flat data to 72 bytes for B-tree nodes, and copy-on-write triggers whenever a mutation is attempted on a node whose reference count exceeds one.

The absl::Cord class in the abseil/abseil-cpp repository provides a rope-like data structure for managing large strings efficiently. Understanding its memory overhead characteristics is crucial for performance-critical applications that process multi-gigabyte text or binary data. This analysis examines the per-chunk memory layout across different Cord node types and identifies exactly when the copy-on-write mechanism activates during mutation operations.

Memory Overhead of absl::Cord Chunk Types

The absl::Cord implementation uses a tree of nodes, each beginning with a CordRep header defined in absl/strings/internal/cord_internal.h. Every chunk type inherits this base overhead and adds type-specific fields.

Flat and External Chunks

Flat and External chunks represent the most memory-efficient storage. The CordRep header occupies approximately 16 bytes on 64-bit platforms, containing size_t length, RefcountAndFlags refcount, uint8_t tag, and uint8_t storage[3]. Flat nodes append the user data payload immediately after this header with zero additional overhead, while External nodes store a pointer and base pointer in the payload area. This makes these chunk types ideal for storing large contiguous blocks where the per-byte overhead approaches zero.

Substring Chunks

Substring chunks add metadata to reference a portion of another node. In addition to the standard CordRep header, CordRepSubstring includes size_t start and CordRep* child fields, adding approximately 16 bytes of overhead. The total node size reaches roughly 32 bytes. This structure allows absl::Cord to share underlying data when taking prefixes or suffixes without copying bytes, though each substring operation consumes additional memory for the wrapper node.

B-tree Nodes

B-tree nodes, defined in absl/strings/internal/cord_rep_btree.h, represent the highest per-node overhead but enable efficient concatenation of many small pieces. These nodes include the 16-byte CordRep header plus three bytes of packed bookkeeping (height, begin, end stored in the storage array) and an edge array of six pointers (CordRep* edges_[kMaxCapacity]). The edge array contributes 48 bytes (6 × 8 bytes), bringing the total to approximately 67 bytes, which rounds to 72 bytes after 8-byte alignment. When building a Cord from many small fragments, these B-tree nodes dominate the memory footprint.

CRC Nodes

CRC nodes add integrity checksums to the Cord tree. These nodes contain the standard CordRep header plus a pointer to the child node and a small crc_cord_state struct. The total overhead is approximately 24 bytes, making them lightweight metadata carriers for validation purposes.

When Copy-on-Write Triggers in absl::Cord

absl::Cord implements copy-on-write (COW) semantics where underlying data is shared between Cord instances until mutation requires exclusive access. The trigger mechanism relies on the RefcountAndFlags::IsOne() method defined in absl/strings/internal/cord_internal.h.

The implementation checks refcount.IsOne() before attempting in-place modifications. This method returns true only when a single owner holds a reference to the node. If the reference count exceeds one, indicating shared ownership, the operation triggers a copy by allocating a new node and duplicating the data before applying changes.

Append and Prepend Operations

The PrepareAppendRegion helper function in absl/strings/cord.cc demonstrates the COW check for mutating operations. Before reusing the last flat node or requesting a writable buffer from a B-tree leaf, the code verifies root->refcount.IsOne() or dst->refcount.IsOne(). If the check fails, Cord::AppendArray (used by Append, Prepend, and assignment operators) falls back to allocating a new flat or B-tree node and copying existing data thereto.

Removal Operations (RemovePrefix/RemoveSuffix)

When removing bytes from the beginning or end of a Cord, operations like RemovePrefix and RemoveSuffix check the ownership of affected nodes. If the operation would modify a shared node, the implementation creates a new CordRepSubstring node rather than altering the existing shared structure. This preserves the immutability guarantee for other Cords referencing the same underlying data.

Direct Buffer Access (GetAppendBuffer)

The fast path for GetAppendBuffer strictly requires unique ownership of the entire tree. The code checks root->refcount.IsOne() before returning a writable span. If the Cord shares its underlying representation, the fast path aborts and the implementation allocates a fresh buffer through the slower fallback path, ensuring no accidental writes affect shared nodes.

Practical Example Showing COW Behavior

The following example demonstrates memory sharing and the copy-on-write trigger:

#include "absl/strings/cord.h"
#include <iostream>

int main() {
  // Build a Cord from concatenated strings - creates a B-tree internally.
  absl::Cord a = absl::StrCat("hello", " world");
  
  // Create a copy - shares the same underlying tree, refcount becomes 2.
  absl::Cord b = a;
  
  std::cout << "Shared state: a and b point to same nodes (refcount == 2)\n";

  // Mutating b triggers COW because refcount.IsOne() returns false.
  b.Append("!");
  
  std::cout << "b after append: " << std::string(b) << "\n"; // "hello world!"
  std::cout << "a unchanged: " << std::string(a) << "\n";    // "hello world"
  
  // Now b has unique ownership; further mutations avoid copying.
  b.Prepend("Start: "); // Fast path: refcount.IsOne() is true.
}

In this example, the assignment b = a increments the reference count on the underlying CordRepBtree node. When b.Append("!") executes, PrepareAppendRegion detects the shared state and allocates new storage, copying the existing data before appending the exclamation mark.

Summary

• Base overhead: Every Cord chunk incurs a 16-byte CordRep header for length, reference count, and type tagging.
• Flat/External chunks: Add only user payload with no per-node metadata beyond the header.
• Substring chunks: Add 16 bytes for offset and child pointers, totaling approximately 32 bytes.
• B-tree nodes: Consume approximately 72 bytes per node due to six child pointers and bookkeeping fields.
• COW trigger: Any mutation operation calls refcount.IsOne(); if false (shared ownership), the implementation copies data to a new node before modifying.
• Key files: absl/strings/internal/cord_internal.h defines headers and reference counting, absl/strings/internal/cord_rep_btree.h defines tree nodes, and absl/strings/cord.cc implements the COW logic in PrepareAppendRegion.

Frequently Asked Questions

How does absl::Cord memory overhead compare to std::string?

std::string typically stores small strings internally (SSO) with zero heap allocation, while absl::Cord always allocates nodes on the heap with a minimum 16-byte header per chunk. For small strings under 15 characters, std::string is more memory-efficient. However, for large or fragmented data, Cord eliminates duplication through sharing and avoids reallocation during concatenation, often yielding better overall memory usage despite the per-node overhead.

When should I use absl::Cord versus flat strings?

Use absl::Cord when you need efficient concatenation, substring operations without copying, or shared ownership of large immutable data. The B-tree structure excels when building strings from many small pieces or when multiple threads need read-only views of the same large payload. For simple, short-lived local strings, std::string or std::string_view provides lower latency and better cache locality.

Does copy-on-write affect thread safety in absl::Cord?

Copy-on-write ensures thread safety for readers but requires careful handling for writers. Multiple threads can safely read from shared Cord instances simultaneously. However, mutation operations may trigger a copy if the reference count exceeds one, making writes potentially expensive. For high-concurrency scenarios where one thread writes while others read, consider using absl::Mutex or ensuring the writing thread has unique ownership before mutation to avoid unexpected allocations.

What is the minimum memory overhead for an empty absl::Cord?

An empty absl::Cord contains no allocated nodes and therefore incurs no per-chunk overhead, consuming only the size of the Cord object itself (typically a single pointer). The overhead characteristics described above apply only when the Cord actually stores data, with the first insertion triggering allocation of at least one node with its 16-byte header.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}