Property cache

SpiderMonkey's property cache is an internal data structure used to speed up property accesses in the interpreter and to communicate between the interpreter and JIT.

The property cache was introduced in bug 365851.

Basics

In general, accessing a property of a native object entails:

1. a property lookup;
2. examining the Shape to see how the property can be accessed;
3. actually carrying out the property access.

The property cache is a per-thread cache of the results of steps 1 and 2. When executing certain property-accessing bytecode instructions, the interpreter populates the cache to speed future execution of the same instruction.

The JIT reads the property cache too, as it needs the same information when recording such an instruction. If there is a cache miss, the JIT performs parts 1 and 2 of the property access and fills the cache to avoid redoing that work in the interpreter. (In some cases this is necessary for correctness. When recording a GETPROP, the JIT needs to know the result type before the interpreter executes the instruction. It is crucial that JIT and interpreter get the same answer; possible pitfalls include native getters and resolve hooks. So the lookup must happen only once. The JIT ensures this by using the property cache to forward its work to the interpreter.)

For speed, the cache is a fixed-size hash table with no chaining. Collisions simply cause old entries to be overwritten.

The hash table entries are key-value pairs. The keys describe the context in which a property lookup occurs. The values consist of two word-sized members. entry->vcap caches the results of part 1 above, telling which object contains the desired property. entry->vword is described in the section Entry value words below. It caches the results of part 2, if the property is simple enough for optimized access, or a pointer to the js::Shape if not.

The opcodes that take advantage of the property cache, as of June 2009, are: GETPROP, GET{X,THIS,ARG,LOCAL}PROP, and LENGTH; NAME; SETPROP, BINDNAME, and SETNAME; CALLPROP and CALLNAME; and {INC,DEC}NAME and NAME{INC,DEC}.

ELEM opcodes do not use it. Nor do {INC,DEC}PROP or PROP{INC,DEC}. Nor do operations such as ADD that only need to look up a property (.toString) in unusual cases.

Throughout this article, phrases such as "own property" should be taken to refer to the low-level representation of properties in scopes and Shape chains. In the case of SHARED PERMANENT properties, this differs from the notion of "own property" seen by scripts via Object.prototype.hasOwnProperty.

Shape

Native objects have a shape, a 24-bit unsigned integer such that:

• Basic layout guarantee — If at time t₀ the object x has shape s and at time t₁ the object y has shape s, and no shape-regenerating GC occurred, then y at t₁ has the same JSClass, JSObjectOps, prototype, and property specs as x had at t₀. To be more precise regarding property specs, y's properties have the same names, getters, setters, property attributes, and slot offsets, and they are in the same order, as x's properties at t₀. Furthermore, y at t₁ has the same number of fixed slots that x had at t₀, and either both have a slot array or neither does. (Informally: objects with the same shape have the same prototype, class, and layout.)

• Prototype chain shadowing guarantee — If at t₀ the object x has shape s and a property x.p of x is found along the prototype chain on object x' of shape s', where x !== x', and the lookup called no resolve hooks or non-native lookup ops, and at t₁ the object x has shape s, the object x' has shape s', and no shape-regenerating GC occurred, then at t₁ the lookup for x.p still finds the same property on x'. (Informally: if another property shadows x'.p, the shape of x' will change.)

    o---->o---->o---->o
    ^x          ^x'   ^Object.prototype, perhaps
  
  (----> indicates the proto relation)
  

• Scope chain shadowing guarantee — If at time t₀ the object x has shape s and a name lookup for p starting at scope chain head x finds p on an object x' of shape s', where x !== x'; and the lookup called no resolve hooks or non-native lookup ops; and each object examined along the parent chain, except possibly the one along whose prototype chain x' was found, had no prototype or was a Block object; and at time t₁ x has shape s and x' has shape s'; and no shape-regenerating GC occurred; then at t₁ the lookup for p in x still finds the same property on x'. (Informally: if another variable or property shadows x'.p, the shape of x' will change.)

    o This object is x, perhaps a Call object.
    ↓
    o ----> o   A Block object and its proto.
    ↓
    o Another Call object.
    ↓
    o ----> o ----> o ----> o
    ^global         ^x'
  
  (----> indicates proto as before; downward arrows ↓ indicate the parent relation)

• Method guarantee — If at time t₀ the object x has shape s; and x has an own property p that is a method property (transparently joined function); and at time t₁ an object y has shape s; and no shape-regenerating GC occurred; then at time t₁ y's own property p is the same method property. (The existence of this property is guaranteed by the basic layout guarantee above.) (Informally: two objects with the same shape have the same METHOD properties.)

• Branded object guarantee — If at time t₀ the object x has shape s; and x is branded (x->branded()); and x has an own property p, which is a writable, Function-valued data property with the stub getter and setter and a slot; and at time t₁ an object y has shape s; and no shape-regenerating GC occurred; then y is x, and at time t₁ x's own property p has the same Function value it had at time t₀. (The existence of this property is guaranteed by the basic layout guarantee above.) (Informally: branded objects have unique shapes, and if x is branded, changing any of x's own methods will change its shape.)

• Extensibility guarantee — If at time t₀ an object x of shape s is extensible, and at time t₁ an object y has shape s, and no shape-regenerating GC occurred, then at t₁ y is extensible. (Informally: marking an object as not extensible changes its shape. Without this guarantee, every property assignment would have to check that the target object is extensible, even though changing an object's extensibility is rare.)

• Prototype change guarantee — If at time t₀ the object x has shape s, and the object y has prototype z, and either x is y or x is on y's prototype chain, and at time t₁ the object x has shape s, and no shape-regenerating GC occurred, then at t₁ y has prototype z. (Informally: changing an object's prototype changes its shape and the shape of every object that was on its prototype chain before the change. Without this guarantee, every access to a property via a prototype chain would have to recheck each link in the prototype chain, even though assigning to __proto__ is very rare.)

• Adding guarantee — If at time t₀ the object x has shape s, and rt->protoHazardShape is z, and x does not inherit a JSPROP_SHARED or JSPROP_READONLY property with name n from any prototype, and at time t₁ an object y has shape s and rt->protoHazardShape is z, and no shape-regenerating GC occurred, then y does not inherit a JSPROP_SHARED or JSPROP_READONLY property named n from any prototype. (Informally: adding a shared or readonly property to a prototype changes rt->protoHazardShape.)

(At the moment, XML objects and resolve hooks can trigger bugs in the implementation that break some of these guarantees. See bug 458271 and bug 507231 for example. There are probably similar bugs to do with, for example, XML objects' custom getProperty op.)

Dense arrays are shapeless.

The shape of an object does not cover:

• anything about the object's prototype other than its identity;
• anything about the object's parent;
• obj->freeslot, which can be different for same-shaped objects if they have a JSClass.reserveSlots hook (bug 535416);
• anything about the values of the object's own properties, beyond what the method guarantee and the branded object guarantee say about functions. In particular shape does not cover the types of property values; typically {a: "x"} and {a: 12} have the same shape.

Both JSObject::objShape and JSShape::shape are shape-ids. JSObject::objShape tells an object's shape. The JSShape::shape field is there so that when a property is added to or removed from an object, the JS engine can change that object's shape to match other objects with the same properties.

Shapes and GC. Occasionally, during garbage collection, all shape ids are regenerated (in order to recycle unused shape ids so that we don't run out; see calls to js_RegenerateShapeForGC). This could end up changing the shape of every object, so the property cache and JIT cache are emptied when this happens.

Unique shapes. An object may be given a unique shape using JSObject::generateOwnShape. This is usually done in order to bump the shape of one object without affecting other objects that happen to have the same properties. For example, when sealing an object, we must somehow preserve the extensibility guarantee. We do this by giving the sealed object a unique shape.

Branded objects. An object may be branded. The interpreter and JIT brand an object whenever they find that enabling the branded object guarantee (above) would make an optimization possible. A branded object always has a unique shape.

Overflow. If there come to be more than 2²⁴ objects that need distinct shapes, the shape rules can no longer be satisfied. The property cache cannot operate without them, so it is disabled permanently. See bug 440834.

Property cache entries

Each entry in the property cache hash table is either populated or not; unpopulated entries have .kpc == NULL.

If an entry is populated, the .kpc field points to the bytecode instruction at which it was populated. The entry is valid only for subsequent lookups that occur at the same instruction, for several reasons:

• The script, not the property cache entry, contains the id of the property being accessed.
• A property cache entry could be valid for a GETPROP but not a SETPROP, e.g. because the property has a setter and not a getter; or vice versa.
• Lookups for JOF_NAME instructions are quite different from ordinary property lookups: name lookups follow the scope chain and the prototype chain, whereas the others only follow the prototype chain.

There are two different types of property cache entry.

Non-adding cache entries

    {.kpc=pc,
     .kshape=kshape,
     .vshape()=vshape,
     .scopeIndex()=scopeIndex,
     .protoIndex()=protoIndex,
     .vword=vword}

This type of entry is created for all instructions that use the property cache. When the operand to the instruction at pc is an object obj with shape kshape, let pobj = the object found by walking scopeIndex steps up the parent chain and then protoIndex steps up the prototype chain. If pobj exists (that is, both the parent chain and the prototype chain are long enough) and it has the shape vshape, then it contains the desired property. Furthermore, the .vword field describes the property in detail, as described in the next section.

If a property with the same name is ever added to an object anywhere along the search path, then this cache entry becomes invalid: the property described by this property cache entry has been shadowed. The two shadowing guarantees ensure that if this happens, the shape of pobj changes, invalidating the entry.

Setting. For JOF_SET instructions, this makes two additional guarantees: first, vword.isSprop(); second, the correct behavior is to set the property described by vword.toSprop(), rather than to shadow it with a new own property.

Teleportation. The JIT handles situations where scopeIndex ≠ 0 or protoIndex > 1 specially. It walks the scope chain and prototype chain as described above only once, at compile time, and emits code containing the pointer to the object that contains the property. The emitted code guards on the identity of the object to search. Then it guards on the shape of the object containing the property. If both guards pass, there is no need to walk the chain. The JIT code "teleports" directly to the appropriate object.

Adding cache entries

    {.kpc=pc,
     .kshape=kshape,
     .vshape()=vshape,
     .scopeIndex()=0,
     .protoIndex()=0,
     .vword=vword}

    where kshape != vshape

This type of entry is only created for JSOP_SETPROP and JSOP_SETNAME instructions that create a new property. When the operand to the instruction at pc is an object obj with shape kshape, and rt->protoHazardShape == vshape, the lookup can be skipped. It is guaranteed that obj does not have an own property with the desired name and does not inherit a JSPROP_SHARED or JSPROP_READONLY property with that name from any prototype. It is guaranteed that vword.isSprop(), and vword.toSprop() describes the property that should be added to obj. With regard to property attributes, getters, setters, and so forth, the property cache entry must take into account several rules documented at JS_SetProperty. Sometimes the new property can be created simply by calling JSScope::extend, but there are many special cases and pitfalls to watch out for.

When a prototype gains a property that could invalidate an entry of this type, rt->protoHazardShape is bumped, effectively marking all such entries invalid at once.

Entry value words

For the .vword member of a non-adding property cache entry, one of the following is true:

vword.isShape()

vword.toShape() points to the js::Shape that describes the property in question. This is the default type of vword generated when neither of the two special cases below applies. A cache hit of this type saves a property lookup, but the interpreter still has to examine vword.toShape() to determine what to do next.

vword.isSlot()

The property has a slot which the interpreter can read directly.

This special kind of entry is used only for JOF_GET instructions and only when the property has a stub getter and has a slot (i.e. it is not JSPROP_SHARED). The slot index is vword.toSlot().

vword.isObject()

The property has a stub getter and its value is vword.toObject().

This special kind of entry is used only for JOF_CALL instructions and only when the result is a Function. It helps the JIT avoid extra loads and guards when calling methods.

Branded scopes exist to support this case. When a property cache entry of this type is created, the scope of the object that contains the property is branded. The "branded scope guarantee" documented above ensures that any changes to function-valued own properties of that object will bump its shape, conservatively invalidating all property cache entries of this type for that object (and JIT code that might inline a call to the function).

The JIT uses a fourth kind of PCVal, having pcval.isNull(), internally to indicate that a property lookup missed entirely. But property cache entries are never populated such that .vword.isNull().

To do

• Treat cache invalidation systematically.
• Does the global object always have a unique shape? a branded scope?
• Explain bug 554955.