Instead of caching a 32 bit identifier for an object's shape in JITs and so forth, we should cache Shape pointers themselves. This would save 4 bytes from both JSObject and Shape, remove an invariant that all objects which !hasOwnShape have objShape == lastProp->shapeid, and remove shape regenerating GCs. For objects which hasOwnShape, whenever we would have normally generateOwnShape we will need to make a new Shape for the object instead. None of the places we currently generateOwnShape without needing a new Shape anyways look hot (mutable __proto__, rebranding, ...).

Also, removing shape regenerating GCs would remove a test for gcmarker->context->runtime->gcRegenShapes when marking both native objects and shapes.

I thought about this a while back. How do you avoid having different shapes with the same pointer, as long as there are entries for these in the caches, without wasting memory?

We would manufacture new Shapes, which would use more memory in cold cases (mutable __proto__) while saving more memory in the normal case. Some optimizations (branding, prototype chain teleporting?) may also cause generateOwnShape. These optimizations are I think redundant with TI, and if they are found (by measuring) to be manufacturing new shapes they could get disabled or removed (TI already disables branding).

I guess you're assuming that we would flush the property cache and all ICs on GC? If IonMonkey didn't want to do that, maybe we could somehow make the baked-in shapes be weak pointers. Then IonMonkey code would be discarded if any of the shapes it used were GCed.

The property cache would need to be flushed, ICs already are. IonMonkey can use weak or strong references, or better yet just purge IM code on GC like we do for JM+TI. Will probably be necessary for IM+TI anyways. This would just happen on major GCs (don't alllocate cacheable shapes in the nursey).

I would love to cache shape pointers and was hoping we could skip right to doing this in IonMonkey, and not use shape numbers at all. It would simplify things a lot. Treating number removal as a separate issue, is there anything that currently prevents us from doing this now? (In reply to Brian Hackett from comment #3) > These optimizations are I think redundant with TI, and if > they are found (by measuring) to be manufacturing new shapes they could get > disabled or removed (TI already disables branding). Branding should definitely just be removed. IIRC, teleporting did not buy us much in the JIT, and we want to remove the property cache anyway (IM stubs will not use it). (In reply to Bill McCloskey (:billm) from comment #4) > I guess you're assuming that we would flush the property cache and all ICs > on GC? If IonMonkey didn't want to do that, maybe we could somehow make the > baked-in shapes be weak pointers. There are four levels of emitting property accesses in IM: (1) Direct property access, no shape guard. (2) Direct property access, shape guard which deopts. (3) IC, which may have multiple shape guards - no deopt case. (4) No special codegen. When you embed gcthings into Ion code, it automatically becomes a strong reference. That includes both embedded shape pointers, and jumps to ICs (which would be compiled as IonCode objects). There's a risk (2) would unnecessarily keep a shape live, but in theory this is for code we know is super hot, so likely it'll (a) run again and (b) if the object's shape has changed, it'll throw the code away. For either, weak references should be possible, but they are easier and probably more useful for (3). While tracing JIT code, we could identify IonCode jump targets that are ICs, and then just repatch the targets to the original C++ call. Then the IC would be collected. Worth noting, v8 attaches a HashTable<atom, IC> to every map, and each IC is a small function. This loses callsite specialization, but ICs are for profiling/baseline compilation. One benefit is you can share ICs between callsites, but I'm not sure how much this matters.

(In reply to David Anderson [:dvander] from comment #6) > I would love to cache shape pointers and was hoping we could skip right to > doing this in IonMonkey, and not use shape numbers at all. It would simplify > things a lot. Treating number removal as a separate issue, is there anything > that currently prevents us from doing this now? No, I think we could/should remove shape numbers now.

Works just enough to start JS, but not run any code. Removes shape numbers, Shape::slotSpan, and moves getter/setter into BaseShape, per bug 687788.

Passes jit-tests with JITs turned off.

Maybe the right file this time.

Update JM. Passes jit-tests=m,ma,mn,mna

Any good perf measurements?

Not yet. The main gains for this patch are memory reductions on web workloads (haven't tested this in the browser yet), allowing some object shrinking stuff (which will be done in separate bugs), and complexity reductions.

I know, and I'm a big fan of the change. I was mostly just curious about the perf effect of removing the store to objShape on the hot new-object path.

(In reply to Luke Wagner [:luke] from comment #14) > I know, and I'm a big fan of the change. I was mostly just curious about > the perf effect of removing the store to objShape on the hot new-object path. The cost of the write on the new-object path is pretty tiny in the overall scheme of things. After the shrinking stuff is done, the perf gains will be in reduced need for GCs and better cache locality, but what gain there is will be hard to see until things are done. I think I'm going to get this green and push it straight to JM without tuning, do the other object shrinking and *then* tune. It should be possible to do all the object shrinking now, even without CPG --- just move parent into BaseShape as a stopgap (and maybe keep it there even after CPG, for scope chain objects).

This was kind of green on tinderbox, so pushing to JM to unblock object-shrink work and will fix remaining stuff in place. https://hg.mozilla.org/projects/jaegermonkey/rev/ff51ddfdf5d1 Summary: Shape numbers removed entirely, along with shape regenerating GCs and protoHazardShape. Shape::slotSpan removed, getter/setter moved into BaseShape, per bug 687788. Method shape invariant weakened so that method shapes imply the object only has *some* uncloned function object, not a particular one. The full method invariant does not buy much given TI, and would require a BaseShape to be allocated for every method shape (of which there are a fair number). Branding is removed entirely. This was also allocating extra shapes and makes the method JIT strictly slower (it does not rely on branded objects, and needs extra checks to preserve branding invariants). With this plus the above, a shape check on an object never implies a particular value for the object's slot. Property cache simplified to only handle lookups of existing shapes (for either get or set). The PCVal Object case can't happen anymore due to the above changes, and the addprop case is very complicated and should be largely unnecessary now even in the interpreter, given that JSOP_NEWOBJECT and JSOP_NEW pregenerate shapes for newly constructed objects. Punting on the tracer for now (it is totally disabled). I don't know how hard it will be to fix it for these changes, in principle it shouldn't be hard but I've never really understood the symbiotic relationship the tracer and property cache seem to have.

Comment on attachment 563204 [details] [diff] [review] patch Review of attachment 563204 [details] [diff] [review]: ----------------------------------------------------------------- Wow, this is a great patch. There's still a good bit more for me to read, but I thought I'd post some questions I had so far to help me going forward. ::: js/src/jsapi.cpp @@ +3228,5 @@ > return !!obj2->methodReadBarrier(cx, *shape, vp); > } > > /* Peek at the native property's slot value, without doing a Get. */ > + if (shape->hasSlot()) { As a random example of the hasMissingSlot comment/question later in the review: here hasSlot() is tested but it seems like this fails if shape->hasMissingSlot (or is there something that prevents that from happening here?). @@ +3605,4 @@ > } else { > desc->getter = shape->getter(); > desc->setter = shape->setter(); > + if (shape->hasSlot()) ditto ::: js/src/jsobjinlines.h @@ +859,5 @@ > + JS_ASSERT(lastProp->base()->isOwned()); > + return lastProp->base()->slotSpan; > + } > + uint32 free = JSSLOT_FREE(getClass()); > + return lastProp->hasMissingSlot() ? free : JS_MAX(free, lastProp->maybeSlot() + 1); s/JS_MAX/Max/ @@ +904,5 @@ > + JSObject *obj = &nativeGetSlot(shape->slot()).toObject(); > + JS_ASSERT(obj->isFunction() && obj->getFunctionPrivate() == obj); > +#endif > + > + return (JSFunction *) &nativeGetSlot(shape->slot()).toObject(); Can you use static_cast? That way this stops compiling if (hopefully when) JSFunction stops deriving JSObject. @@ +1380,5 @@ > NULL, clasp == &ArrayClass); > > + if (clasp->isNative() > + ? !InitScopeForObject(cx, obj, clasp, type, kind) > + : !InitNonNativeObject(cx, obj, clasp)) { Can you rename these to be symmetric (e.g., InitShapeForNativeObject/InitShapeForNonNativeObject)? ::: js/src/jsscope.h @@ +302,5 @@ > + * Owned BaseShapes are used for shapes which have property tables, including > + * the last properties in all dictionaries. Unowned BaseShapes compactly store > + * information common to many shapes. > + * > + * All combinations of owned/unowned Shapes/BaseShapes are possible: This is a beautiful comment, I love the case breakdown. Question for my reviewing benefit (and perhaps to be added to this comment): It seems like an owned BaseShape is always a clone of its (unowned) base. I am also seeing several places where need to explicitly skip from an owned BaseShape to its unowned base. Could we instead have an entirely new C++ type, say, OwnedBaseShape that held slotSpan, base_, and table_? It seems like that would shrink (Unowned)BaseShape and also enforce statically that we always skipped from owned to unowned base shape. Is the reason for sharing the same data structure that we have (hot) paths that don't care whether the BaseShape is owned vs. unowned and just want to access the relevant fields? @@ +344,5 @@ > + */ > + EXTENSIBLE_PARENTS = 0x8 > + }; > + > + uint32 flags; /* Vector of above flags. */ Overall comment for BaseShape: since you are touching all its users everywhere, could we make all fields private from the start? It helps, if nothing else, to understand the mutation story. @@ +397,5 @@ > + > + bool isOwned() const { return !!(flags & OWNED_SHAPE); } > + void setOwned(BaseShape *base) { flags |= OWNED_SHAPE; this->base = base; } > + > + PropertyTable *table() const { JS_ASSERT_IF(table_, isOwned()); return table_; } Can you rename to maybeTable()? Then, if you think it'd be useful, there could be a "PropertyTable &table() { JS_ASSERT(isOwned()); return *table_; }". @@ +572,3 @@ > > + /* > + * A scope has a method barrier when some compiler-created "null closure" s/scope/shape/ ? @@ +610,5 @@ > > Value getterOrUndefined() const { > + return (hasGetterValue() && base()->getterObj) > + ? ObjectValue(*base()->getterObj) > + : UndefinedValue(); Can you align ? and : with the ( on the return line @@ +627,5 @@ > > Value setterOrUndefined() const { > + return (hasSetterValue() && base()->setterObj) > + ? ObjectValue(*base()->setterObj) > + : UndefinedValue(); ditto @@ +645,5 @@ > + /* > + * For properties which haven't been fully initialized, empty shapes and > + * slot-less properties under empty shapes. > + */ > + bool hasMissingSlot() const { return slot_ == (SHAPE_INVALID_SLOT >> (32 - SLOT_BITS)); } I thought a JSPROP_SHARED Shape has no slot and necessarily has SHAPE_INVALID_SLOT. Thus, would hasMissingSlot() imply !hasSlot? If so, can you make hasSlot == !hasMissingSlot and change what is currently hasSlot to !isShared() or remove it altogether? Unfortunately, I think it's possible to have a getter/setter (so not a data property) but not be JSPROP_SHARED (so have a physical slot). You don't feel like killing JSPROP_SHARED (defining it to be === slot_ != SHAPE_INVALID_SLOT) would you? :) ::: js/src/jsscopeinlines.h @@ +159,3 @@ > parent(NULL) > { > + JS_ASSERT(base); Perhaps have Shape::Shape take a BaseShape& instead? @@ +304,5 @@ > +Shape::initDictionaryShape(const Shape &child, Shape **dictp) > +{ > + BaseShape *base = child.base(); > + if (base->isOwned()) > + base = base->base; This pattern has come up a few times. What about adding a BaseShape::toUnowned() { return isOwned() ? base : this; }

> Unfortunately, I think it's possible to have a getter/setter (so not a data property) > but not be JSPROP_SHARED (so have a physical slot). Not only possible, but commonly used on the web: the 'location' property on Window in our current implementation is a non-configurable property that has a slot and a setter but no getter. It is not JSPROP_SHARED, obviously, since it's got a slot. ;)

(In reply to Luke Wagner [:luke] from comment #17) > It seems like an owned BaseShape is always a clone of its (unowned) base. I > am also seeing several places where need to explicitly skip from an owned > BaseShape to its unowned base. Could we instead have an entirely new C++ > type, say, OwnedBaseShape that held slotSpan, base_, and table_? It seems > like that would shrink (Unowned)BaseShape and also enforce statically that > we always skipped from owned to unowned base shape. Is the reason for > sharing the same data structure that we have (hot) paths that don't care > whether the BaseShape is owned vs. unowned and just want to access the > relevant fields? OwnedBaseShape can definitely be a subclass of BaseShape. I've been keeping it simpler for now since BaseShape will change further with object shrinking and deciding to do the subclassing will depend on (a) how much space would be saved per BaseShape, and (b) the relative populations of the two on web workloads. > Overall comment for BaseShape: since you are touching all its users > everywhere, could we make all fields private from the start? It helps, if > nothing else, to understand the mutation story. Sure. > @@ +645,5 @@ > > + /* > > + * For properties which haven't been fully initialized, empty shapes and > > + * slot-less properties under empty shapes. > > + */ > > + bool hasMissingSlot() const { return slot_ == (SHAPE_INVALID_SLOT >> (32 - SLOT_BITS)); } > > I thought a JSPROP_SHARED Shape has no slot and necessarily has > SHAPE_INVALID_SLOT. Thus, would hasMissingSlot() imply !hasSlot? If so, > can you make hasSlot == !hasMissingSlot and change what is currently hasSlot > to !isShared() or remove it altogether? > > Unfortunately, I think it's possible to have a getter/setter (so not a data > property) but not be JSPROP_SHARED (so have a physical slot). You don't > feel like killing JSPROP_SHARED (defining it to be === slot_ != > SHAPE_INVALID_SLOT) would you? :) This stuff needs more cleanup and documentation. hasSlot() means the shape is not JSPROP_SHARED, whereas hasMissingSlot() means its slot_ is invalid. Once a shape has made its way into the property tree or an object, then hasSlot() implies !hasMissingSlot(), but before that a shape can both hasSlot() and hasMissingSlot() if it still needs a slot to be allocated. (This is one reason JSPROP_SHARED can't be killed, though I would love to rename it if it weren't part of the API). The second subtlety is that a shape can both !hasSlot() and !hasMissingSlot(), if it is the property tree. In this case its slot_ stores the slot_ of its parent, so that an object's slot span can always be computed without a shape walk.

Comment on attachment 563204 [details] [diff] [review] patch Review of attachment 563204 [details] [diff] [review]: ----------------------------------------------------------------- Phew, done. This is a great patch! I am particularly pleased with jscntxt.cpp. ::: js/src/jsfun.cpp @@ +1903,5 @@ > setSlot(JSSLOT_BOUND_FUNCTION_THIS, thisArg); > setSlot(JSSLOT_BOUND_FUNCTION_ARGS_COUNT, PrivateUint32Value(argslen)); > if (argslen != 0) { > + /* > + * FIXME? We need to conver to a dictionary in order to increase the convert. Also FIXME is distracting (vim makes it stand out yellow). Could you remove it and say "For simplicity, we simply convert to a dictionary ...." ::: js/src/jsgcmark.cpp @@ +342,5 @@ > +{ > + JS_OPT_ASSERT_IF(gcmarker->context->runtime->gcCurrentCompartment, > + thing->compartment() == gcmarker->context->runtime->gcCurrentCompartment); > + > + /* We mark base shapes directly rather than pushing on the stack. */ PushMarkStack(JSString*) does the same thing, so this probably don't need a comment. However, I think it would be worth asserting in ScaneBaseShape that base == NULL || base->base == NULL to show why this doesn't allow recursive stack overflow. Alternatively, you could wrap ScanBaseShape in a do/while and avoid the recursion altogether. ::: js/src/jspropertytree.cpp @@ +178,5 @@ > return NULL; > > + BaseShape *base = child.base(); > + if (base->isOwned()) > + base = base->base; Returning to the toUnowned idea, I think it would good to have: class BaseShape { ... UnownedBaseShape *toUnowned() const { return static_cast<BaseShape *>(isOwned() ? base : this); } } struct UnownedBaseShape : BaseShape {}; and then have both the Shape and BaseShape constructors take an UnownedBaseShape. (Yes there is an annoying order-of-declaration issue here.) ::: js/src/jsscope.cpp @@ +154,5 @@ > + return true; > +} > + > +void > +Shape::handoffTable(Shape *shape) How about handoffTableTo to make directionality clear. @@ +159,5 @@ > +{ > + JS_ASSERT(inDictionary() && shape->inDictionary()); > + > + if (this == shape) > + return; That's strange. For several of the callsites, it looks impossible. If there is only one place where this can occur, can this check be hoisted out of the general method? @@ +168,5 @@ > + > + /* Update the slot span when growing dictionaries. */ > + uint32 span = nbase->slotSpan; > + if (shape->hasSlot()) > + span = JS_MAX(span, shape->slot() + 1); Max() @@ +341,5 @@ > return true; > } > > Shape * > +Shape::getChild(JSContext *cx, const js::Shape &child, Shape **listp, bool allowDictionary) Unless I'm grepping wrong, this is only called when adding a binding. I was having trouble understanding why it was correct (in particular, if 'this' was some random shape, not the lastBinding) before seeing it had only this one use. So, could you rename it to Shape::getChildBinding and s/listp/lastBinding/? Also, that makes allowDictionary === false, so you can just remove the parm. @@ +439,3 @@ > if (!shape) > return NULL; > + shape->initDictionaryShape(child, &lastProp); On a (preexisting) side note: it's creepy how shapes are inserted into the linked list in one place in a Shape:: method and the hash-table's contents are mutated somewhere in a JSObject:: method. @@ +610,5 @@ > const Shape * > JSObject::addProperty(JSContext *cx, jsid id, > PropertyOp getter, StrictPropertyOp setter, > uint32 slot, uintN attrs, > + uintN flags, intN shortid, bool allowDictionary) Can you use an enum MaybeAllowDictionary { NO_DICTIONARY = 0, ALLOW_DICTIONARY }? Also for addPropertyInternal @@ +793,2 @@ > /* > * Now that we have passed the lastProp->frozen() check at the top of this 'frozen' in comment @@ +804,5 @@ > */ > if (inDictionaryMode()) { > + bool updateLast = (shape == lastProp); > + if (!generateOwnShape(cx)) > + return NULL; It would be nice to have a comment "We can't just update lastProp in-place since the identity (not value) of lastProp must change to invalidate existing shape guards." @@ +814,5 @@ > if (!allocSlot(cx, &slot)) > return NULL; > } > > + if (shape == lastProp) { I think it would be nice to have: if (updateLast) { /* Make sure the owned base matches the new unowned base (nbase). */ JS_ASSERT(shape->base()->isOwned()); uint32 span ... @@ +946,5 @@ > /* > + * If in dictionary mode, get a new shape for the last property after the > + * removal. We need a fresh shape for all dictionary deletions, even of > + * lastProp. Otherwise, a shape number could replay and caches might > + * return deleted DictionaryShapes! See bug 595365. Do this before changing "shape number" in comment @@ +998,3 @@ > > + /* Hand off table from old to new lastProp. */ > + oldLastProp->handoffTable(lastProp); IIUC, this is only necessary if oldLastProp == shape. If so, even though the perf doesn't matter, it would be nice for the reader to prefix the handoff call with "if (oldLastProp == shape)" and replace the comment with "Don't lose the table (which is held by lastProp)." @@ +1075,5 @@ > if (TraceRecorder *tr = TRACE_RECORDER(cx)) > tr->forgetGuardedShapesForObject(this); > #endif > > + if (!inDictionaryMode() && !toDictionaryMode(cx)) I'll assume due measurement has been carried out here. @@ +1099,5 @@ > + if (spp) { > + if (SHAPE_HAD_COLLISION(*spp)) > + SHAPE_FLAG_COLLISION(spp, newShape); > + else > + *spp = newShape; I think you can use SHAPE_STORE_PRESERVING_COLLISION instead. @@ +1126,5 @@ > > /* > * Pass null to make a stub getter, but pass along shape.rawSetter to > * preserve watchpoints. Clear Shape::METHOD from flags as we are > * despecializing from a method memoized in the property tree to a comment needs update @@ +1154,5 @@ > + return generateOwnShape(cx); > +} > + > +/* static */ inline HashNumber > +JSCompartment::BaseShapeEntry::hash(const js::BaseShape *base) Could you define BaseShapeEntry in jsscope.h next to BaseShape? I suspect you put it in jscompartment.h b/c jsscope.h #includes jscompartment.h. However, there is only one dependency on jscompartment.h, and that is the inline definition of EmptyShape::create and this should be able to go in jsscopeinlines.h. Similarly, could you move this and the next 4 definitions to jsscope.cpp? @@ +1168,5 @@ > + return hash; > +} > + > +/* static */ inline bool > +JSCompartment::BaseShapeEntry::match(const BaseShapeEntry &entry, const BaseShape *lookup) Ah, this could take an UnownedBaseShape also. @@ +1202,5 @@ > + entry.empty = NULL; > + > + p = table.lookupForAdd(&base); > + if (!table.add(p, entry)) > + return NULL; if (!table.relookupOrAdd(p, &base, entry)) return NULL; @@ +1231,5 @@ > + return new (entry->empty) EmptyShape(entry->base); > +} > + > +void > +JSCompartment::sweepBaseShapeTable(JSContext *cx) Can put this definition in jscompartment.cpp? ::: js/src/jsscope.h @@ +292,5 @@ > +/* > + * Shapes encode information about both a property lineage *and* a particular > + * property. This information is split across the Shape and the BaseShape > + * at shape->base(). Both Shape and BaseShape can be either owned or unowned > + * by, respectively, the Object or Shape referring to them. Since it's somewhat key: could you say that there is only a single BaseShape for a given triple (clasp, getter, setter) hence, like atoms, BaseShape equality is testable via a single pointer comparison. @@ +300,5 @@ > + * the property tree. > + * > + * Owned BaseShapes are used for shapes which have property tables, including > + * the last properties in all dictionaries. Unowned BaseShapes compactly store > + * information common to many shapes. I would give a bit more rationalization for why owned BaseShapes contain an identical copy of their base unowned BaseShape b/c this was initially confusing. I think the relevant constraints forcing this design are: - want to hoist members out of Shape for uncommon dictionary/table paths (to keep them out of Shape) - some hot paths don't want to care about owned vs. unowned, they just want to load obj->shape->base->x - the above canonicalization property (Is that right? I feel like I'm forgetting something from Friday.) To make this concrete, it would be nice to add an assertEqualUnownedBase() that this comment references and is called from various shape routines.

Just a clarification on this patch and comment 16: in the patch, I see void JSContext::updateJITEnabled() { #ifdef JS_TRACER + traceJitEnabled = false; + /* traceJitEnabled = ((runOptions & JSOPTION_JIT) && !IsJITBrokenHere() && compartment && !compartment->debugMode() && (debugHooks == &js_NullDebugHooks || (debugHooks == &runtime->globalDebugHooks && !runtime->debuggerInhibitsJIT()))); + */ #endif This would, if I read this correctly, essentially gut tracing. Is this the intention? I'm concerned about this in PPC land because we use the tracer exclusively; I'm porting methodjit to POWER but it's not done yet. However, Brian's comment implies that he does intend to enable it for tracing once the issues are ironed out, so I just want to verify that will be the case when it lands.

I was on the fence when writing this patch, but given all the other object shrinking changes that have since gone into the JM branch and have yet to go in, I think now the tracer will need to be removed entirely before this stuff can land (targeting early in the Firefox 11 timeframe). The object shrinking work removes several optimizations which the tracer depends on (and which are unnecessary given TI), and getting the tracer running would require a massive amount of work.

JSPROP_SHARED can be renamed to JSPROP_NOSLOT any time you like. We can keep the old name #defined to the new if we want source compatibility. Great to see TI get rid of branding. /be

This is great stuff, but: I'm confused as to how this got landed without the failures noted in bug 708261 getting fixed, or at least filed as follow-up bugs. The actual issue there (PrintPropertyGetterOrSetter being passed the wrong sort of pointer) seems like something that should have been addressed in review.

The findReferences tests in bug 708261 do not actually run on the tinderbox. I only make an effort to keep the tinderbox green, not to ensure jstests.py passes. This is in large part because jstests.py does not pass, and hasn't consistently passed for a long time --- since there is no automated feedback when a test starts failing, new tests start failing at various times and keeping on top of it is a pita and not worth my time. I filed bug 685751 not long ago to fix this mess, but it hasn't had any traction (I guess I was hoping someone else would notice and do it).