Hidden classes (shapes)

Deep dive

How it works

In: object, property name (read) or name plus value (write) · Out: value, or a transition to a new shape · State: shape tree (parent, key, slot, children) shared by all objects of a runtime; per object a shape id and a value array · Cost: read O(1) with a cached or per-shape table, add O(1) amortized.

1. Objects start at the root shape with an empty value array.
2. Add k at shape S: look up edge (S, k). Found: reuse the child. Missing: create a child with parent = S, key = k, slot = S.len, record the edge.
3. The object's shape becomes the child; the value is appended at the new slot. Overwriting an existing property changes only the value.
4. Read k: find its slot from the shape (parent-chain walk, or a descriptor array or table built lazily per shape), then load slots[slot].
5. Same keys in the same order reach the same node; a different order, or an extra key in between, takes another branch.
6. Fallback: past a bound of properties, or after a delete, the object leaves the tree for dictionary mode: its own hash table, nothing shared, nothing for caches to key on.
7. Prototypes: the shape records the prototype (V8 hidden classes store a reference to it), so equal properties with different prototypes mean different shapes.

root --a--> S1{a} --b--> S2{a,b} --c--> S3{a,b,c}
                    \--c--> S4{a,c}            slots: shape S3 -> [va, vb, vc]
 obj1: S3 + [1,2,3]    obj2 (a,c order): S4 + [1,3]

In-object vs out-of-line slots. V8 fixes the in-object property count from the object's initial size; further properties go to a separate properties store that grows independently, at the cost of one indirection (V8 blog). The shape only decides which slot; where the slot lives differs.

Elements. Integer-indexed properties live outside the shape tree in a separate elements store. V8 tracks an "elements kind": packed or holey, small-integer, double or generic, plus dictionary elements for sparse arrays; 20 kinds in all, including typed arrays (V8 blog).

Engines. V8: maps, transition trees, descriptor arrays; "slow" properties use a per-object dictionary. SpiderMonkey Shape and JavaScriptCore Structure: same idea (from memory). CPython: PEP 412 key-sharing dictionaries share keys across instances of a class and 3.11 creates namespaces lazily; layout is per class, not per history. Ruby 3.2 added object shapes (Feature #18776); shape.h in Ruby master defines SHAPE_MAX_VARIATIONS as 8 (its exact role: from memory).

Origin. Self's "maps" (Chambers, Ungar, Lee, 1989) gave prototype-based objects a shared description so compiled code could be shared across them.

Code

Shape tree, shared and distinct shapes, dictionary fallback; asserts in main.

use std::collections::HashMap;
type Key = u32; // interned property name
type ShapeId = u32;
const MAX_FAST: usize = 8; // demo bound; engines pick their own

struct Shape {
    parent: Option<ShapeId>,
    key: Key,    // property added by the edge parent -> this
    slot: usize, // index of that property's value
    len: usize,  // number of properties on this path
}
struct Shapes {
    nodes: Vec<Shape>,
    children: HashMap<(ShapeId, Key), ShapeId>, // transition table
}
enum Repr {
    Fast { shape: ShapeId, slots: Vec<i64> },
    Dict(HashMap<Key, i64>), // own table, no shared shape, ICs cannot key on it
}
struct Object { repr: Repr }
impl Shapes {
    const ROOT: ShapeId = 0;
    fn new() -> Self {
        let root = Shape { parent: None, key: 0, slot: 0, len: 0 };
        Shapes { nodes: vec![root], children: HashMap::new() }
    }
    fn transition(&mut self, shape: ShapeId, key: Key) -> ShapeId {
        if let Some(&c) = self.children.get(&(shape, key)) { return c; }
        let len = self.nodes[shape as usize].len;
        let id = self.nodes.len() as ShapeId;
        self.nodes.push(Shape { parent: Some(shape), key, slot: len, len: len + 1 });
        self.children.insert((shape, key), id);
        id
    }
    fn lookup(&self, mut shape: ShapeId, key: Key) -> Option<usize> {
        while let Some(p) = self.nodes[shape as usize].parent {
            let n = &self.nodes[shape as usize];
            if n.key == key { return Some(n.slot); }
            shape = p;
        }
        None
    }
    fn keys(&self, mut shape: ShapeId) -> Vec<(Key, usize)> {
        let mut v = Vec::new();
        while let Some(p) = self.nodes[shape as usize].parent {
            let n = &self.nodes[shape as usize];
            v.push((n.key, n.slot));
            shape = p;
        }
        v
    }
}
impl Object {
    fn new() -> Self { Object { repr: Repr::Fast { shape: Shapes::ROOT, slots: vec![] } } }
    fn shape(&self) -> Option<ShapeId> {
        if let Repr::Fast { shape, .. } = &self.repr { Some(*shape) } else { None }
    }
    fn get(&self, sh: &Shapes, key: Key) -> Option<i64> {
        match &self.repr {
            Repr::Fast { shape, slots } => sh.lookup(*shape, key).map(|s| slots[s]),
            Repr::Dict(d) => d.get(&key).copied(),
        }
    }
    fn set(&mut self, sh: &mut Shapes, key: Key, val: i64) {
        match &mut self.repr {
            Repr::Fast { shape, slots } => {
                if let Some(s) = sh.lookup(*shape, key) { slots[s] = val; return; }
                if slots.len() >= MAX_FAST { self.to_dict(sh); return self.set(sh, key, val); }
                *shape = sh.transition(*shape, key); // new slot = old len
                slots.push(val);
            }
            Repr::Dict(d) => { d.insert(key, val); }
        }
    }
    fn delete(&mut self, sh: &Shapes, key: Key) {
        self.to_dict(sh); // delete leaves the transition tree for good
        if let Repr::Dict(d) = &mut self.repr { d.remove(&key); }
    }
    fn to_dict(&mut self, sh: &Shapes) {
        if let Repr::Fast { shape, slots } = &self.repr {
            let d = sh.keys(*shape).into_iter().map(|(k, s)| (k, slots[s])).collect();
            self.repr = Repr::Dict(d);
        }
    }
}
fn main() {
    let mut sh = Shapes::new();
    let (x, y, z) = (1, 2, 3);
    fn build(sh: &mut Shapes, order: &[Key]) -> Object {
        let mut o = Object::new();
        for (i, &k) in order.iter().enumerate() { o.set(sh, k, 10 + i as i64); }
        o
    }
    let a = build(&mut sh, &[x, y]);
    let (b, c) = (build(&mut sh, &[x, y]), build(&mut sh, &[y, x]));
    assert_eq!(a.shape(), b.shape()); // same order -> same shape
    assert_ne!(a.shape(), c.shape()); // different order -> different shape
    assert_eq!(c.get(&sh, y), Some(10)); // y sits in slot 0 on c's shape
    let mut d = build(&mut sh, &[x, y]);
    let n = sh.nodes.len();
    d.set(&mut sh, x, 99); // overwrite: no transition
    assert_eq!(sh.nodes.len(), n);
    d.set(&mut sh, z, 5); // add: transition to a child shape
    assert_ne!(d.shape(), a.shape());
    assert_eq!(sh.nodes[d.shape().unwrap() as usize].parent, a.shape());
    d.delete(&sh, y); // delete -> dictionary mode, values survive
    assert!(d.shape().is_none());
    assert_eq!((d.get(&sh, x), d.get(&sh, y), d.get(&sh, z)), (Some(99), None, Some(5)));
    let mut big = Object::new(); // too many properties -> dictionary mode
    for k in 0..=MAX_FAST as Key { big.set(&mut sh, 100 + k, 1); }
    assert!(big.shape().is_none());
    assert_eq!(big.get(&sh, 100), Some(1));
}

Compiled and run. lookup walks the parent chain; engines cache a table per shape.

Complexity and constants

• Add: one transition lookup (hash probe on (shape, key)) plus a push; a shape is allocated only the first time a path is seen.
• Read through an inline cache: one shape-id compare plus one load. Without one: a per-shape table lookup, or a chain walk as long as the property count.
• Per object: a shape pointer plus one 8-byte word per property (64-bit values, arithmetic); a dictionary-mode object also carries its own keys.
• Cost drivers: cache misses on the header and out-of-line array, the indirection past in-object slots, tree growth, dictionary-mode objects.

Efficiency

• Cost: a monomorphic access is a compare and a load; the first object of a shape pays shape creation, later ones only the edge lookup. Bound: memory latency and bytes per object, not arithmetic. No cross-engine figures; they differ per engine.
• Levers:
  • share the layout across instances — per object only values, no keys (PEP 412 motivation) — many small objects of one class
  • add properties in a fixed order — one shape, so one transition path (V8 blog) — hot constructors and literals
  • dictionary fallback after a bound — stops tree growth from delete and keyed objects (V8 blog) — map-like objects
  • attributes in an array, __dict__ created lazily — about 30% less memory for a typical object (CPython 3.11 changelog, bpo-45340) — attribute-less and read-only instances
• Naive -> standard -> state of the art: per-object hash map · keys and table overhead repeated per object; shared shapes with transitions · values plus one pointer; shapes plus inline caches and JIT guards · layout checks shrink to one compare and constant-offset loads. PEP 412 reports gcbench about 10 % faster, likely an upper limit.

Implementation notes

• Shape ids are a pointer or small integer: one compare must identify a layout.
• Build name-to-slot tables lazily, only for shapes that are read.
• Attributes (read-only, frozen) belong in the shape or a transition, so a cached shape fixes mutability.
• Dictionary mode is one-way per object.
• Make unused tree edges weak, or a long-lived tree leaks.

Pitfalls

• Initializing fields in different or conditional order makes sibling shapes and polymorphic sites.
• delete and very many properties push objects into dictionary mode, where inline caches do not work (V8 blog); assign undefined instead.
• Computed, unbounded keys explode the tree; use a Map.
• A changed prototype must invalidate every cache that depends on it.
• Thresholds are engine-specific; do not carry one engine's bounds to another.

Variants and alternatives

In production

• Browsers: V8 maps, transition trees, descriptor arrays, in-object and out-of-line properties, dictionary mode (blog); JavaScriptCore Structure (WebKit blog); SpiderMonkey guards on an object's shape in Warp (Mozilla Hacks).
• Server and tooling runtimes: Node.js and Deno run on V8, so the same maps.
• Scripting languages: CPython key-sharing dictionaries (PEP 412) and, from 3.11, attributes in an array with a lazily created __dict__; Ruby 3.2+ object shapes, which YJIT exploits (release notes).

Implementations

Sources

• Craig Chambers, David Ungar, Elgin Lee, An Efficient Implementation of SELF, a Dynamically-Typed Object-Oriented Language Based on Prototypes, OOPSLA 1989.
• Camillo Bruni, Fast properties in V8, V8 blog 2017. post
• Mathias Bynens, JavaScript engine fundamentals: Shapes and Inline Caches. article
• Mark Shannon, PEP 412 - Key-Sharing Dictionary. pep
• Changelog, Python 3.11, bpo-45340 (attributes in an array, lazy __dict__). docs
• Feature #18776: Object Shapes, Ruby issue tracker. issue