Maps and Dynamic Messages

Relevant source files

• src/google/protobuf/arena_align.cc
• src/google/protobuf/descriptor_lite.h
• src/google/protobuf/dynamic_message.cc
• src/google/protobuf/json/BUILD
• src/google/protobuf/json/internal/descriptor_traits.h
• src/google/protobuf/json/internal/lexer.cc
• src/google/protobuf/json/internal/lexer.h
• src/google/protobuf/json/internal/lexer_test.cc
• src/google/protobuf/json/internal/message_path.cc
• src/google/protobuf/json/internal/parser.cc
• src/google/protobuf/json/internal/parser.h
• src/google/protobuf/json/internal/parser_traits.h
• src/google/protobuf/json/internal/unparser.cc
• src/google/protobuf/json/internal/unparser.h
• src/google/protobuf/json/internal/unparser_traits.h
• src/google/protobuf/json/internal/untyped_message.cc
• src/google/protobuf/json/internal/untyped_message.h
• src/google/protobuf/json/internal/writer.cc
• src/google/protobuf/json/internal/writer.h
• src/google/protobuf/json/internal/zero_copy_buffered_stream.cc
• src/google/protobuf/json/internal/zero_copy_buffered_stream.h
• src/google/protobuf/json/internal/zero_copy_buffered_stream_test.cc
• src/google/protobuf/json/json.cc
• src/google/protobuf/json/json.h
• src/google/protobuf/json/json_enumval_custom_string.proto
• src/google/protobuf/json/json_enumval_custom_string_test.cc
• src/google/protobuf/json/json_test.cc
• src/google/protobuf/map.cc
• src/google/protobuf/map.h
• src/google/protobuf/map_field.cc
• src/google/protobuf/map_field.h
• src/google/protobuf/map_field_lite.h
• src/google/protobuf/map_field_test.cc
• src/google/protobuf/map_test.cc
• src/google/protobuf/map_test.inc
• src/google/protobuf/util/json_format.proto
• src/google/protobuf/util/json_format_proto3.proto

This page documents the Map container implementation and the DynamicMessage system in the C++ runtime. Map containers provide efficient hash-map storage for proto map fields, while DynamicMessage enables runtime construction of messages without compile-time generated code.

For information about the Reflection API used to access map fields dynamically, see Message Processing System. For details about code generation for maps, see Descriptor and Compilation Pipeline.

---

Map Container Architecture

Protocol Buffers implements maps using a hash table with separate chaining. The implementation uses a two-layer design: an untyped base class (UntypedMapBase) that handles core storage and iteration logic, and a type-safe template wrapper (Map<Key, T>) that provides the user-facing API.

Class Hierarchy and Data Flow

The core UntypedMapBase class manages the hash buckets and nodes, while the templated Map<Key, T> class adds typed key/value semantics.

• UntypedMapBase manages the underlying hash table with array of buckets (table_) and linked nodes.
• NodeBase contains a next pointer for chaining and provides access to the key memory.
• KeyNode<Key> extends NodeBase by storing the key.
• Node<Key,T> extends KeyNode<Key> by storing the key-value pair.
• KeyMapBase<Key> adds typed map operations like FindNodeAndBucket and node insertion.
• Map<Key,T> is the exposed container API providing operator[], find, insert, and erase.

Sources: src/google/protobuf/map.h253-507 src/google/protobuf/map.h726-753

Type Information and Dynamic Dispatch

UntypedMapBase stores a compact TypeInfo struct describing the key and value types for generic handling without virtual calls:

Field	Type	Purpose
uint16_t node_size	Size of node	Total size of allocated node
uint8_t value_offset	uint8 offset	Offset to value in node
uint8_t key_type_k:4	TypeKind enum	Key field kind
uint8_t val_type_k:4	TypeKind enum	Value field kind

TypeKind enum defines supported data kinds:

This allows generic operations on any key/value type recognized by protobuf's type system.

Sources: src/google/protobuf/map.h258-312

Node Memory Layout and Allocation

Nodes are aligned and structured as:

• NodeBase aligned to kMaxMessageAlignment (16 bytes) to allow predictable offset calculation.
• KeyNode adds the key storage.
• Node adds the value inside the pair kv.

Nodes are allocated via AllocNode(Arena*), using an arena allocator if available, otherwise dynamic heap allocation.

Sources: src/google/protobuf/map.h165-173 src/google/protobuf/map.h460-476

Hash Table Characteristics and Algorithm

• The map uses separate chaining for collision resolution.
• The number of buckets is always a power of two (minimum 2, max 2^31).
• Load factor is managed by resizing buckets when the number of elements approaches bucket count.
• Keys are hashed using Hash():
  • For integer keys, CRC32 is used (optimized).
  • For strings, absl::HashOf is used.
• Bucket is selected by hash & (num_buckets_ - 1).
• Lookup iterates the linked list in the bucket to find keys.

This design balances performance and binary size, and supports a wide range of key/value types.

Sources: src/google/protobuf/map.h702-712 src/google/protobuf/map.cc60-127

---

MapField Synchronization System

MapField maintains both a map container and a repeated field representation internally. The repeated field is used for serialization compatibility with proto wire format, which represents map fields as repeated key/value entry messages.

MapFieldBase and Payload Structure

• MapFieldBaseForParse stores a pointer globals_or_payload_ which either points to global default data or a dynamically allocated Payload.
• Payload contains a repeated field (of MapEntry messages), a synchronization state, and a mutex to protect concurrent access.
• TypeDefinedMapFieldBase holds the typed map map_.
• MapField<K,V> exposes the user APIs for map-like access and wraps the above components.

Sources: src/google/protobuf/map_field.h104-302 src/google/protobuf/map.h622-681

Synchronization State Machine

MapField synchronizes the state between map and repeated field representations:

State	Map State	Repeated State	Meaning
STATE_MODIFIED_MAP	Current	Stale	Map was modified, repeated field needs update
STATE_MODIFIED_REPEATED	Stale	Current	Repeated field mutated, map needs update
STATE_CLEAN	Current	Current	Both in sync

A static atomic function pointer sync_map_with_repeated is installed to handle synchronization logic, enabling separation of the full runtime from lite code.

Sources: src/google/protobuf/map.h656-659 src/google/protobuf/map_field.cc34-64

Conversion Between Representations

Synchronization logic converts between Map<Key, T> and the repeated field of MapEntry messages on demand.

• When the user requests mutable map access, a synchronization is performed if the repeated field was last modified.
• When the user requests the repeated field (e.g., for serialization), synchronization is performed if the map was last updated.
• The synchronization includes holding a mutex to protect state transitions.

Sources: src/google/protobuf/map_field.cc149-229

Lazy Payload Allocation and State Encoding

The pointer globals_or_payload_ distinguishes between global default storage and an allocated payload by using its least significant bit (LSB):

• If LSB=0: Points to global default instance (no payload allocated).
• If LSB=1: Points to dynamically allocated Payload struct (offset by 1).

This clever pointer encoding delays allocation of repeated field storage until it is actually needed.

Sources: src/google/protobuf/map_field.h234-255 src/google/protobuf/map.h674-678

---

DynamicMessage System

DynamicMessage allows construction and use of protocol buffer messages at runtime without compile-time generated message classes. This enables generic handling of arbitrary messages by interpreting their descriptors.

Memory Layout Strategy

DynamicMessage mimics the memory layout of a compiled message to allow efficient use of Reflection and other generated-message utilities.

• The layout is carefully computed in a TypeInfo structure to match generated message field offsets.
• This enables GeneratedMessageReflection to operate identically on dynamic and static messages.
• Various field types have specialized storage (inline, pointer, arena strings, repeated fields).

Sources: src/google/protobuf/dynamic_message.cc173-450

Field Storage Allocation

Different types of fields allocate storage as follows:

Field Type	Storage Type	Initialization
Singular primitives	Inline (4 or 8 bytes)	Zero initialized
Singular strings	ArenaStringPtr or MicroString	Empty string default
Singular messages	Message* pointer	nullptr
Repeated primitives	RepeatedField<T>	Empty initialized
Repeated strings	RepeatedPtrField<string>	Empty initialized
Repeated messages	RepeatedPtrField<Message>	Empty initialized
Map fields	DynamicMapField (derived from MapFieldBase)	Empty map

Sources: src/google/protobuf/dynamic_message.cc452-625

DynamicMapField Implementation

Maps inside DynamicMessage are represented by DynamicMapField, derived from MapFieldBase. It contains an UntypedMapBase instance.

• DynamicMapField is constructed dynamically using field descriptor default entries.
• It calls UntypedMapBase::GetTypeInfoDynamic() to configure its behavior based on runtime type information.
• Provides untyped map access underneath.

Sources: src/google/protobuf/dynamic_message.cc90-168

DynamicMessageFactory

The DynamicMessageFactory maintains a cache of DynamicMessage prototypes (default instances) per message descriptor.

• On first request to create a dynamic message for a descriptor, a prototype is created.
• The prototype initializes all fields and caches reflection data.
• Subsequent New() calls clone the prototype using MergeFrom() or similar.

This caching avoids repeated layout computation and improves runtime performance.

Sources: src/google/protobuf/dynamic_message.cc627-897

Integration with Reflection

DynamicMessage uses GeneratedMessageReflection configured with a detailed ReflectionSchema:

This schema enables full reflection support, including field access, unknown fields, extensions, and oneofs for generically structured messages.

Sources: src/google/protobuf/generated_message_reflection.h118-145 src/google/protobuf/dynamic_message.cc452-625

Parsing and Serialization of DynamicMessages

DynamicMessage parsing uses the fallback generic parser paths:

• Parsing is performed by TcParser::GenericFallbackLite() which interprets the wire format field-by-field via the reflection interface.
• Serialization uses WireFormat::SerializeWithCachedSizes() with reflection iteration over fields.
• These approaches do not produce the highly optimized TcParser tables used by generated code but offer full functionality and flexibility.

Therefore, dynamic messages have somewhat reduced performance compared to generated counterparts but provide runtime flexibility.

Sources: src/google/protobuf/generated_message_tctable_lite.cc74-77 src/google/protobuf/dynamic_message.cc899-1080

---

Map Entry Messages

In Protocol Buffers, map fields are syntactic sugar represented internally as repeated fields of special synthetic messages called MapEntry messages.

MapEntry Descriptor Structure

For a proto map field:

The compiler synthesizes:

• The MapEntry message has exactly two fields: key and value.
• The repeated field holds all the entries.
• The MapField class provides a higher-level map API that wraps this wire format representation.

Sources: src/google/protobuf/generated_message_reflection.cc98-101

MapEntry Serialization

• Each map entry is serialized as a length-delimited message containing two fields (key and value).
• The MapField system resynchronizes between the map container and repeated field views for serialization and parsing.
• This two-layer design accommodates protobuf wire format encoded data while allowing efficient in-memory map use.

Sources: src/google/protobuf/map_field.cc149-229

---

Summary Diagram: MapField and DynamicMessage Relation

This diagram situates the main components:

• The core Map container is wrapped by MapFieldBase/MapField which synchronize with repeated fields.
• DynamicMessage uses DynamicMapField for map fields embedded in dynamic messages.
• DynamicMessageFactory caches the prototypes and manages the runtime construction lifecycle.

---

References

• Map implementation: src/google/protobuf/map.h
• MapField synchronization: src/google/protobuf/map_field.h src/google/protobuf/map_field.cc
• DynamicMessage system: src/google/protobuf/dynamic_message.cc
• MapEntry message representation: src/google/protobuf/generated_message_reflection.cc

---

This page described the key implementation details of Protocol Buffers maps and the dynamic message system, providing insight into how runtime flexibility and efficient container semantics are achieved in the C++ runtime.