The Dictionary Object Model and the Cost of a Name Lookup

The expression p.x in a language without static types does not compile to a load at a fixed offset. The compiler does not know what p is, so it emits a request: given this object and this name, produce the value. Everything that follows in a dynamic object model is an answer to that request, and the first answer, the one every runtime starts with, is a table.

A dictionary-backed object stores its fields in a hash table keyed by name. The object header holds a pointer to that table, and the table maps interned strings to values. Property access becomes a hash lookup: compute the hash of the name, probe the table, compare the stored key with the requested name, and read the value at the matching slot. This is the model CPython uses for instance attributes by default, the model V8 falls back to for objects with unusual property histories, and the model that a hand-written interpreter reaches for first because it is correct for every sequence of additions and deletions.

The interesting question is why the model is not good enough, and the answer is not asymptotic complexity. A hash lookup is expected constant time, which is the same complexity class as the array indexing that fast engines achieve. The difference is entirely in the constant: what instructions execute, what memory is touched, and what the object has to carry.

A property access is a lookup keyed by a string

The name is data. p.x and p.y differ only in a string constant embedded in the instruction stream, so the runtime needs a function from names to storage positions. The minimal implementation has an entry per property holding the key, its length, and the value.

typedef struct value *Value;          /* tagged or boxed, opaque here */
uint32_t hash_bytes(const char *name, size_t len);   /* name hash, cached on the string */

struct entry {
    const char *name;
    size_t len;
    Value value;
};

struct object {
    struct object_header hdr;
    size_t cap;                 /* power of two */
    size_t count;
    struct entry *slots;
};

static Value *lookup(struct object *o, const char *name, size_t len) {
    size_t mask = o->cap - 1;                 /* capacity is a power of two */
    uint32_t h = hash_bytes(name, len);
    for (size_t i = h & mask;; i = (i + 1) & mask) {
        struct entry *e = &o->slots[i];
        if (e->name == NULL)
            return NULL;                           /* empty slot terminates the probe */
        if (e->len == len && memcmp(e->name, name, len) == 0)
            return &e->value;
    }
}

Linear probing over a power-of-two table is the cheapest correct scheme here, but the shape of the code is what matters. Each access pays for a hash of the name bytes unless the hash was cached in the string object, one or more probes, and a length check plus a byte comparison on each occupied slot. The comparison cannot be replaced by pointer equality in general, because the name may arrive as a freshly built string that was never interned. Interned strings make the common case a pointer compare, which is why runtimes intern property names at parse time and reuse the same string object for every occurrence of an identifier.

Two accesses to the same property in the same function perform this work twice. Nothing in the instruction stream remembers that p.x was resolved a moment ago, and nothing can, because p may be a different object with a different table on the second execution.

What the table costs per object

The per-access cost is only half the bill. The other half is paid at allocation and in memory footprint.

A table has to be allocated with spare capacity, or every addition would reallocate and rehash. At a load factor of one half, a three-property object needs a power-of-two table of eight slots. Each slot in the structure above holds a name pointer, a length, and a value, which is twenty-four bytes on a 64-bit machine. Eight slots is 192 bytes, plus the header and the table pointer, for an object that logically holds three values. The values themselves are scattered wherever the hash function put them, so a loop reading three fields touches three separate cache lines instead of one.

Rehashing on growth moves every value, which means the addresses of values are not stable across an addition. A runtime that hands out interior pointers into the table, or that caches such a pointer, has to invalidate them whenever the object grows. That instability is the reason a compiled access cannot simply keep the address of a slot and forget how it found it.

Deletion is the operation that keeps the table in the model. Removing a key from an open-addressed table requires backward-shift deletion or tombstones; either way the table keeps working, and the object keeps working, with no change to any compiled code, because no compiled code exists.

The alternatives, and what each one gives up

There are three ways to map a name to a position, and they differ in where the work happens.

A linear search over an array of entries is the simplest: compare the requested name against each entry in turn. It costs O(n) comparisons per access and needs no hash function, but a ten-property object averages five string comparisons per read, and each comparison touches a different cache line. It is viable only for very small objects and is what a minimal prototype implementation tends to produce.

A hash table, as above, is O(1) expected with a small constant. It handles arbitrary key sets, arbitrary insertion orders, and deletion without recompilation. It is the right structure when the key set is open, which is exactly the situation of an object whose fields are chosen by the program at run time: a record loaded from JSON, a namespace of configuration values, an object populated by setattr or by computed keys.

The third option moves the mapping out of the object and into a shared descriptor. If every object built by the same code has the same fields in the same order, then one descriptor can record that the third field lives at byte offset 24, and every instance of that descriptor can be read with a single load. The descriptor is what Smalltalk-80 implementations called a map and what modern JavaScript engines call a hidden class or shape; the layout itself is covered in Hidden Classes and Transition Trees. The cost of that option is that the descriptor must be discovered, shared, and checked, and that mutations which break the sharing have to be detected.

The dictionary has one property the descriptor does not: it is local. Adding a property to one object touches only that object. Under a shared-descriptor model, adding a property to one object either creates a new descriptor for that object alone, or, if the object is a prototype, invalidates every access that depended on the old one.

Where the dictionary survives in real runtimes

No production engine uses per-object hash tables for everything, and no production engine has eliminated them either. The dictionary is retained because it is the only structure that supports the full property protocol without help.

V8 keeps a dictionary representation for objects whose properties are added and removed in patterns that would make descriptor sharing pointless, and for objects that acquire accessor properties through the reflective API. Python’s type objects carry an implementation detail named tp_version_tag for a related purpose: it changes when the type’s attribute lookup changes, so an inline cache in the interpreter can check the tag and discard its cached lookup when it no longer matches. CPython has always exposed a dictionary per instance in its data model. From the 3.3 series onward the attribute values of an instance live in a slots array on the object while the name-to-offset mapping is held in a key-sharing dictionary attached to the class, so instances of the same class share their key table and allocate a full dictionary only when an instance needs one. Both arrangements preserve the same contract: an attribute can be added, replaced, or removed at any time, and the resulting behaviour is defined by the language rather than by the layout.

Computed access forces the dictionary path in every engine. When the property name is an expression, obj[key], the compiler cannot emit a fixed offset even if it knows the object’s descriptor, because it does not know which name will be requested. Some engines specialize the case where the same key expression has produced the same name repeatedly, but the general form requires a lookup.

Reflection and serialization also land here. Enumerating an object’s properties requires a stable order and a complete list, both of which a descriptor provides more cheaply than a table, but modifying attributes at run time, defining a getter on an existing data property, or sealing an object changes the rules in ways that the fast layout does not represent.

What has to be true before an offset is safe

The dictionary model is not slow because hashing is expensive in the abstract. It is slow because the address of a value is computed rather than known, and because the computation depends on data the compiler cannot see.

Three conditions have to hold before an access can become a constant offset. The object’s layout must be known to the code, which requires that layouts be shared rather than per-object. The layout must be cheaply verifiable at the point of use, because the code still receives values of unknown provenance; a single pointer comparison against an expected descriptor is the cheapest such check available. And the layout must remain valid for as long as the code assumes it, which requires that any change to the object or to its prototype chain be visible to the code, either by changing the descriptor or by invalidating the compiled assumption.

Those three conditions are the whole design space of fast property access. The descriptor that satisfies the first is the hidden class; the check that satisfies the second is the guard described in Monomorphic Inline Caches and the Guard That Makes Them Work; the invalidation that satisfies the third is the validity cell and the descriptor invalidation mechanism. The dictionary remains underneath all of it as the fallback for the cases where the three conditions cannot be met, which is why an object can change from fast to slow and, in most engines, never change back.