Hidden Classes and the Transition Tree Behind Property Writes

Two objects built by the same constructor and given the same fields in the same order have identical layouts. Two objects built by the same constructor with the fields assigned in the opposite order do not, even though they hold the same names and the same number of values. The layout is a function of the construction history, not of the final set of keys, and that single fact is what makes the descriptor approach workable and what makes it fragile.

A hidden class is a runtime object, separate from any instance, that records the property names an object has, the byte offset at which each value sits, the attributes of each property, and a link to the descriptor of the object’s prototype. Instances carry one pointer to their descriptor and nothing else about layout. Engines differ in naming: V8 documentation calls it a map, SpiderMonkey’s internals call it a shape, and the earlier prototype-based systems called it a map as well; the general literature says hidden class. The mechanism is the same in all of them.

From an empty descriptor to a full one

Allocation starts every object at a descriptor with no properties. Assigning a property to an object whose current descriptor does not contain that name creates a new descriptor containing it, and the old descriptor is left unchanged. The old descriptor gains an outgoing transition edge labelled with the property name, pointing at the new descriptor. The instance is then updated to point at the new descriptor, and the value is written at the offset the new descriptor assigns.

This is why descriptors are immutable with respect to their property set. Mutating a shared descriptor in place would silently change the layout of every instance that already points at it, including instances whose values were written at the old offsets. Copying the descriptor and repointing the one instance that was written to keeps every other instance correct without any write barrier, any rehash, or any scan.

The new descriptor is a copy of the old one plus one entry. The entry needs a name, an offset, and flags for enumerability, writability, and configurability. The offset is the old descriptor’s instance size, and the new instance size is that offset plus the width of a value slot. Properties added in sequence therefore occupy consecutive slots, which is the entire reason iteration order in these objects matches insertion order for string keys.

empty  --"x"-->  {x@0}  --"y"-->  {x@0, y@8}  --"z"-->  {x@0, y@8, z@16}
   \--"y"-->  {y@0}  --"x"-->  {y@0, x@8}

The diagram shows the branch that matters. Starting from the empty descriptor, adding x then y reaches a descriptor whose slots are ordered x, y. Adding y then x reaches a different descriptor, with x at offset 8 rather than 0. The two descriptors have the same size and the same set of names, and no code that assumes one will work on the other.

Why the tree is a tree and not a hash

The obvious alternative to a transition tree is a per-descriptor hash table mapping property names to next descriptors. It is simpler to implement and handles arbitrary name sets, but it costs a hash lookup on every property addition, and additions are the common operation during object construction. A constructor that assigns five fields would perform five hash lookups per instance, each with a string hash and a probe, which is exactly the cost the descriptor model exists to avoid.

The transition tree instead stores its outgoing edges in a small array on the descriptor, and looks up a name by scanning that array. The array is short by construction: a descriptor that has many distinct outgoing edges is a descriptor from which many different objects have been extended in many different ways, which is itself a sign that the objects do not share a layout, and a descriptor with many edges is an uncommon one that is not itself on the hot path. Engines typically keep the linear form up to a small count and then convert to a hash-backed transition table, or abandon transitions for that descriptor entirely.

The practical consequence is that the tree encodes the set of property-addition sequences that have actually occurred. It does not encode all possible sequences, and it never will. A new order creates a new path from the root, and the path is created on demand.

The insertion-order trap

Because the tree is keyed on order, a constructor whose branches assign fields in different orders produces objects with different descriptors. This is not a correctness problem; both descriptors describe valid layouts and both work. It is a performance problem, and it appears whenever the fields a function reads are assigned in an order the function’s inline caches do not expect.

The canonical shape of the problem is conditional initialization. A constructor that assigns x and y unconditionally and then assigns z only when an option is set produces two terminal descriptors: one with two properties and one with three. The two-property objects have a different descriptor from the three-property objects, and any code reading obj.x must handle both. That is one extra polymorphic case, and it is unavoidable because the objects genuinely differ.

The avoidable case is assigning the same fields in different orders on different paths. Assigning x then y on one branch and y then x on another produces two descriptors for objects that hold the same data. The fix is a convention: initialize every field in the constructor, using a default value for fields whose real value is computed later, so that all instances of the class follow one path. Setting the field to a default and later overwriting it is cheap; the overwrite does not change the descriptor because the name is already present.

Deletion breaks the invariant differently. Removing a property from a descriptor cannot be done by producing a descriptor that omits it, because the remaining properties’ offsets would have to be reassigned and every instance would have to be updated. Engines instead mark the descriptor as unsuitable for the fast path and convert the object to a dictionary-backed representation, which is the fallback described in The Dictionary Object Model and the Cost of a Name Lookup. Once converted, an object does not usually return to the fast representation, so a delete in a hot loop costs far more than the single operation suggests.

What the descriptor has to hold

The descriptor is not only a name-to-offset table. It carries everything a compiled access needs to decide whether the object in hand matches the assumption the code was built around.

The first field is the prototype link. Property access follows the chain when the own descriptor lacks the name, so a compiled access to obj.x is only valid if both the own layout and the chain behind it are unchanged. Storing the prototype object’s pointer in the own descriptor turns the first link of that check into a comparison of two pointers rather than a walk; the links above it are covered by a validity cell rather than by repeated comparison, as described in Prototype Chain Guards and Validity Cells.

The second is the instance size, which the allocator needs to reserve the right number of bytes and which the collector needs in order to know how many slots to trace. A descriptor that grows by one slot per property means the size is derivable from the property count, but storing it explicitly keeps the allocator out of the property table.

The third is a bit field of flags: whether the object is in dictionary mode, whether it has been sealed or frozen, whether any of its properties are accessors, whether it is an array with packed elements. These flags are read on every access in some designs, and the cost of a branch on a flag is smaller than the cost of a walk to discover the same fact.

The fourth is the transition table or edge array described above. A descriptor that is a leaf in the tree still needs the ability to grow, because a later assignment can extend it.

Sharing across instances and across functions

Descriptors are shared by construction, not by interning at allocation time. When a constructor runs for the second time and performs the same sequence of assignments, each assignment walks an existing edge in the tree and lands on the descriptor the first instance already has. No new descriptor is created. The tree grows only when a genuinely new sequence occurs, which in steady-state code is a bounded set.

This gives the runtime a cheap identity for layouts, and that identity is what the compiled code compares against. An inline cache does not need to know the property name at run time; the name is fixed in the instruction, and the cache holds a descriptor pointer and an offset. A load becomes: compare the object’s descriptor against the cached descriptor, and if equal, load from the cached offset. The check is one pointer comparison against a value the cache already holds.

That is the contract the transition tree exists to support, and its failure modes all reduce to the same thing: too many descriptors reaching the same access site. Conditional construction, per-instance extension, and mixing objects from different libraries that build their fields in different orders all produce that outcome. The machinery for handling more than one descriptor at a site is the subject of Monomorphic Inline Caches and the Guard That Makes Them Work, and the point at which the machinery stops paying is the megamorphic case.