473228 - Setting a property after deleting another one is slow if the object has many properties

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect, P2)

Description

[Jeremy]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2a1pre) Gecko/20090112 Minefield/3.2a1pre
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2a1pre) Gecko/20090112 Minefield/3.2a1pre

Running a JSLitmus test (see attached, the library repeats a user defined operation over and over until ops per second can be estimated) on the delete function produced surprisingly slow results.

In a normalized test, the delete operation performs between 30 and 80 ops a second on Minefield (3.2pre) as well as FF 3.0.5 on my Windows XP system.

Is the delete operator supposed to be that slow?

Reproducible: Always

Steps to Reproduce:
1. Unzip the attached file and run deletetest.html.
2. Click on the Run Tests button.

Actual Results:  
I didn't know what sort of performance I would get from delete, but I was awfully surprised to run into problems in my test, hence my submittal of this bug.

Expected Results:  
I didn't have specific results, but I did expect more than at least 100 ops (deletes) a second.

Will be attaching a zip file containing:
- JSLitmus.js
- deletetest.html

These files are what I used to determine the performance of delete. I haven't had a chance to thoroughly check and see what could potentially be going on behind the scenes, but I figured you might wish to know about this issue.

I'm rating this as a minor problem as there is a workaround called don't put yourself in the situation of needing to call delete a lot.

Comment 1

[Jeremy]

Attachment: Example that reproduces the problems

Reproduce my results in a handful of clicks:

Unzip the zip
Open up the html file
Click the Run Tests button

Comment 2

[Bob Clary [:bc] (inactive)]

Attachment: deletetest.html with inline script

Comment 3

[Bob Clary [:bc] (inactive)]

Intel Mac OS X 10_5_6

minefield
_callbackArray current method: Array object with number indexes         325798
_callbackArray proposed method: JS Object as hash, clearing with delete     48

Safari 3.2.1
_callbackArray current method: Array object with number indexes	        212041
_callbackArray proposed method: JS Object as hash, clearing with delete	236701

Comment 4

[Nochum Sossonko [:Natch]]

Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US; rv:1.9.2a1pre) Gecko/20090123 Minefield/3.2a1pre
fwiw on trunk:

_callbackArray current method: 432470
_callbackArray proposed method: 51

3.0.5

_callbackArray current method: 326385
_callbackArray proposed method: 48

So trunk is faster in both instances, although I'm not exactly sure what exactly the code does for the tests. I found that using an object with delete was faster for me than iterating over an array, but I guess the reason there was less looping and checking, not necessarily for the delete operator itself.

Are these numbers bad (for delete)? It seems that Safari is much better at it.

Even IE gives me 55314 for the latter test...

Comment 5

[Jeremy]

Attachment: Isolated delete oparations inline

As the originator of this confusing (to me) bug, I decided to retry the test outside of the JSLitmus testing suite.

This test seems to debunk the idea that it's just the delete operation that is the problem: I had to insert 1100 tests to register a millisecond duration for this test. Making the object global pushed the test to 2 ms on my system, presumable for the additional global scope lookup of the variable.

Perhaps it's the delete operation in conjunction with something else, but if delete alone ran at 40 ops/sec, we should have noticed it here.

I've never cracked open the Mozilla source code, but my first question from here would be does delete perform some sort of blocking or forced/immediate garbage collection at the time of operation? I'm ignorant and surprised again at these unexpected results.

Comment 6

[Brendan Eich [:brendan]]

We're not delete-optimized, more the reverse. Don't overuse delete -- make a new object and throw away the old rather than deleting all properties. But this is a real bug, which should be fixed. Confirming.

/be

Comment 7

[Brendan Eich [:brendan]]

Need hierarchical profiler (e.g. shark, oprofile) results.

/be

Comment 8

[Boris Zbarsky [:bzbarsky]]

> Need hierarchical profiler (e.g. shark, oprofile) results.

I sharked the attached testcase.  I'll attach a report, but the summary is pretty simple.  This function:

  function(count) {
    var doShark = (count > 100);
    if (doShark) { 
      document.body.appendChild(document.createTextNode(count));
      connectShark(); startShark() 
    }
    while( count-- ) {
        var index = Math.floor(Math.random()*1000000);
        _callbackArray[index] = function(){};
        delete _callbackArray[index];
    }
    if (doShark) { stopShark(); disconnectShark; }
}

is called.  In this case, |count| was 640.  The resulting shark profile has 85k samples, and I was using a 20us timer.  So that's 85k * 0.02 == 1700ms, which means about 3ms per iteration.  Shark overhead at that sampling rate is typically about 20-50% of total runtime, so figure 1-2ms per iteration.  Deathly slow.

85% of the time is spent in (not under, _in_) js_AddScopeProperty, called by js_SetPropertyHelper.  8% was spent doing GC of the DOM operation callback.  5% was under the GetPropertyTreeChild call from js_AddScopeProperty (locking, unlocking, generating shapes, etc).

The time in js_AddScopeProperty, if I'm going to believe shark's line-by-line numbers is mostly spent on the:

  if (sprop->id == id)

line in the SCOPE_HAS_MIDDLE_DELETE(scope) case.

Now the thing is, that test isn't testing what it thinks it's testing.  In particular, the "array object with number indices" part is bogus, since that code runs up front, the real testcase code is effectively as follows:

1)  Create a JSObject.
2)  Set a few hundred thousand properties on it (with random names that are
    integers from 0 to 1e6) to null.  These are set in some random order.
3)  Start setting and deleting properties with such names.  After the first
    delete of something that's not the last prop that was added, the sets get
    really slow, since we have several hundred thousand possible shapes that we
    have to walk through on every set, right?

Resummarizing bug to reflect what's really being tested here.

Note that some obvious consequences of this can be seen in the testcase:

A) Hitting "Run Tests" again after running them once but without reloading
   shows the "array" test being just as slow as the "delete" test.
B) Running the "delete" test without ever running the "array" test shows
   ops/sec in the 600k range (since in this case we never end up in a
   middle-delete situation).

Comment 9

[Boris Zbarsky [:bzbarsky]]

Attachment: js shell testcase

Some notes on this testcase:

1)  Removing the |delete o[0]| line makes the time needed to do the 100 prop
    sets tiny (in fact, gives me numbers on the order of 0.5us per property
    set).
2)  If the |delete o[0]| is kept, the time per set after the delete is
    approximately linear in total number of properties set (as expected).  With
    the same setup as for note 1, I get about 4.4ms per property set.
3)  jit on or off does not affect the results, as expected.

Comment 10

[Boris Zbarsky [:bzbarsky]]

Er, I quit shark before exporting the report to attach, but I seriously doubt you actually need one given the above information.

Comment 11

[Brendan Eich [:brendan]]

Graydon, is this a dup of another bug you've dealt with?

This is not a real-world workload. But we should handle it better. Probably when we detect too much "set after middle-delete", we should stop using the property tree and switch to a private set of JSScopeProperty nodes hashed by the object's scope.

/be

Comment 12

[Graydon Hoare :graydon]

It's thematically similar to bug 489636 and bug 489637, but tickles the problem from a different angle. 

I'm tempted to agree with your suggestion: detect in general when the property tree assumptions -- ("delete is rare" || "delete happens only at the end") -- have failed, and kick the object out of the property-tree regime altogether. "De-optimize" in order to fit the user's mental model. 

However, two points: #1 that is a lot of effort that will touch many parts of spidermonkey, I think, and #2 it's still only something we're hitting on pretty "synthetic" cases. The assumption holds up pretty well in real code.

Given these two points, particularly #1, I'd defer from blocking 1.9.1.

Comment 13

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

Is bug 495753 related to this?  It seems like jquery tickles it, and they're using the latest trunk.

Comment 14

[Graydon Hoare :graydon]

(In reply to comment #13)
> Is bug 495753 related to this?  It seems like jquery tickles it, and they're
> using the latest trunk.

Perhaps. jquery has found its way to this family of bugs in the past, it's true, though usually it does so when trying to detach itself from a page or DOM object on page-close or navigate-away or such. I don't know what path would lead it here, but it seems plausible.

(It produces a "unique identifier" for every DOM object in the document and puts them all in a "cache" by UID; then "purges the cache" by looping and deleting each entry when it decides it's done with the cache. You can test this hypothesis by modifying the jquery in question to *not* delete anything in its cache purging loop.)

Comment 15

[Jason Orendorff [:jorendorff]]

This has been marked blocking. I think I agree with comment 12 though.

The ability to delete entries from a dictionary is useful, in my experience, and that the obvious way to do it costs O(N) in our implementation is admittedly embarrasing. But are we aware of any real-world sites suffering from this?

Comment 16

[Jason Orendorff [:jorendorff]]

If the "quick scan" fingered in comment 8 is really the culprit, maybe we can fix it internal to JSScope. What if we never entirely delete anything from the hash table, but only mark entries as deleted?  IIUC this change would render the collision bit useless, so we could use that bit to mean "deleted" instead.  Then the "quick scan" for true conflicts could be a hash lookup.

Comment 17

[Graydon Hoare :graydon]

I think "never delete anything from a hashtable" is going further down the "violating the user's mental model" path we're already too far down here. It'll almost certainly cause some further unflattering performance comparisons against engines that do this the simple way.

I'd strongly prefer working out a way to gracefully opt an object out of the property-tree system entirely, and behave like a "normal hashtable" when code starts using it as such. I'd even try removing all the middle-delete-handling logic from the property tree altogether, using "middle delete" as the event that triggers de-optimizing an object back to a simple hashtable.

Comment 18

[Brendan Eich [:brendan]]

(In reply to comment #17)
> I'd strongly prefer working out a way to gracefully opt an object out of the
> property-tree system entirely, and behave like a "normal hashtable" when code
> starts using it as such. I'd even try removing all the middle-delete-handling
> logic from the property tree altogether, using "middle delete" as the event
> that triggers de-optimizing an object back to a simple hashtable.

This is what SFX does, FWIW. I'm thinking about it to solve a problem in the work for bug 497789 -- seriously.

/be

Comment 19

[Damon Sicore (:damons)]

Brendan, are you on this?  Any update?

Comment 20

[Brendan Eich [:brendan]]

It's behind two other bugs in my queue -- sayrer is helping clear one up (its patch bounced, not sure why -- Windows unit test hang, and that box is AWAL from the try-server tinderbox page!): bug 518448.

/be

Comment 21

[Brendan Eich [:brendan]]

Er, AWOL.

The other bug is bug 511591, which blocks this bug.

/be

Comment 22

[Robert Sayre]

I don't think we can block 1.9.2 on this. thoughts?

Comment 23

[Andreas Gal :gal]

This needs a beta imo.

Comment 24

[Robert Sayre]

not blocking on this desirable enhancement, per discussion with brendan

Comment 25

[Brendan Eich [:brendan]]

Attachment: proposed fix

I need to test a bit more, clean up a few things, and comment the tricky bits, but this is passing js/src/tests, js/src/trace-test, and `make jstestbrowser`.

/be

Comment 26

[Brendan Eich [:brendan]]

Attachment: patch to review

Still not sure of a few tryserver boxes, hoping sayrer can help clarify. This is ready for review, I'll ask graydon since he has been in the relevant jsscope.cpp code before; jorendorff would be excellent too but he's traveling today IINM.

I'll attach a narrative tour of the patch later today.

/be

Comment 27

[Graydon Hoare :graydon]

Narrative tour will be much appreciated. This is the most challenging-looking thing anyone's ever asked me to review, I think!

(However: bravo! Much needed, awesome work &c)

Comment 28

[Brendan Eich [:brendan]]

Attachment: my little Baedeker about what's going on in the patch

Comment 29

[Brendan Eich [:brendan]]

Attachment: lost some intro text in my fine Baedeker

Comment 30

[Graydon Hoare :graydon]

Comment on attachment 410361 [details] [diff] [review]
patch to review

Phew! With discussion on IRC and your write-up, I think I understand most of this. Don't see any obvious bugs; refactoring ::add is delightful. Death to forking!

Figure it could use Yet More Eyes -- particularly those of someone with better sprop intuitions -- so handing to jorendorff for a further look.

Comment 31

[Jeff Walden [:Waldo]]

Comment on attachment 410444 [details]
lost some intro text in my fine Baedeker

>    the js_AddNativeProperty internal API allowos "adding" an existing id with

allows, in case this makes its way into a comment some{time,where}.

Comment 32

[Jason Orendorff [:jorendorff]]

I read the Baedecker, but haven't read the patch yet. A few preliminary questions:

>    So not only do we here flag the scope as inDictionaryMode(), we clear the
>    OWN_SHAPE flag -- a dictionary-mode scope doesn't need to regenerate its
>    shape on every shape-changing operation, since each lastProp update will
>    reference a property with a unique shape (see newDictionaryProperty).

Currently, the OWN_SHAPE bit is only tested during shape regeneration, but I guess at other times, we use something like (lastProp && shape != lastProp->shape) to mean the same thing... is that right?

The patch as described here sounds exactly right, just having trouble remembering why the existing code is the way it is. (Lack of sleep may be a factor here.)

>    JSScope::changeProperty: as noted in the watchpoint discussion earlier,
>    this method takes an sprop param which must be in this scope. After some
>    assertions (including a new one, that we're not changing a SPROP_IS_METHOD
>    sprop) comes another watchpoint issue:
> 
>+    if (IsWatchPointSetter(setter, attrs) && !inDictionaryMode() && !toDictionaryMode(cx, sprop))
>+        return NULL;

Why do we need special code for watchpoints here? If you just deleted
this, wouldn't we end up in putProperty which would do the right thing?

>    JSScope::clear: not much to say here, except we can clearDictionaryMode()
>    and clearOwnShape() when clearing all props from a scope.

This is similar to a comment you made on my patch in bug 505523. It's
mostly right. We can't *unconditionally* clearOwnShape() because that
might give this scope the same shape as a scope of a different class
(bug 505523); but I think we can in the usual case.

Comment 33

[Brendan Eich [:brendan]]

(In reply to comment #32)
> >    So not only do we here flag the scope as inDictionaryMode(), we clear the
> >    OWN_SHAPE flag -- a dictionary-mode scope doesn't need to regenerate its
> >    shape on every shape-changing operation, since each lastProp update will
> >    reference a property with a unique shape (see newDictionaryProperty).
> 
> Currently, the OWN_SHAPE bit is only tested during shape regeneration, but I
> guess at other times, we use something like (lastProp && shape !=
> lastProp->shape) to mean the same thing... is that right?

Here's a grep of tm tip, without the patch:

$ grep 'lastProp->shape' *.h *.cpp
jsscopeinlines.h:    shape = (!lastProp || shape == lastProp->shape)
jsops.cpp:                      scope->shape == scope->lastProp->shape);
jsscope.cpp:             * followed to update both scope->shape and lastProp->shape.

The jsscopeinlines.h match is JSScope::extend, and it's old code. Probably it should change to test hasOwnShape() to decide to generate a new shape, else it should assert the condition shown and use sprop->shape to update the scope's shape. Comments?

The jsops.cpp bit is from this assertion in the code for JSOP_INIT{PROP,METHOD}:

            JS_ASSERT(!scope->lastProp ||
                      scope->shape == scope->lastProp->shape);

so this is more like it: we know we are extending a newborn that can't escape yet, so we are extending.

Here now is the grep output with the patch:

jsscope.h:     * lastProp->shape after they finish updating the linked list in the case
jsscopeinlines.h:    shape = (hasOwnShape() || !lastProp) ? js_GenerateShape(cx, false) : lastProp->shape;
jsscope.cpp:        shape = lastProp->shape;
jsscope.cpp:             * followed to update both scope->shape and lastProp->shape.

The jsscopeinlines.h match is in JSScope::updateShape, factored out of JSScope::extend and called in other places that are editing a scope but not extending it. It wants to update this scope's shape from lastProp->shape so it must null-test, and of course regenerate instead of !hasOwnShape(). The latter is non-controversial but the refactoring to updateShape() with null lastProp (and therefore regenerating) should be examined closely.

The non-comment jsscope.cpp match is at the bottom of JSScope::toDictionaryMode where it wants to updateShape only if there are any properties in the scope. In this case of a dictionary-mode scope, we don't need to generate a shape for the scope since each dprop gets a fresh shape, so we can use the last one. If the scope is empty, we didn't reshape it (dictionary-mode on empty scope keeps the empty scope's shape).

The jsops.cpp assertion is still there, but it uses scope->lastProperty(). Here is a grep:

$ grep 'lastProperty()->shape' *.h *.cpp
jsops.cpp:                      scope->shape == scope->lastProperty()->shape);

so that's the only such lastProp->shape in disguise.

> >    JSScope::changeProperty: as noted in the watchpoint discussion earlier,
> >    this method takes an sprop param which must be in this scope. After some
> >    assertions (including a new one, that we're not changing a SPROP_IS_METHOD
> >    sprop) comes another watchpoint issue:
> > 
> >+    if (IsWatchPointSetter(setter, attrs) && !inDictionaryMode() && !toDictionaryMode(cx, sprop))
> >+        return NULL;
> 
> Why do we need special code for watchpoints here? If you just deleted
> this, wouldn't we end up in putProperty which would do the right thing?

JSScope::changeProperty does not remove and then add (not put if it knows it is not there), it instead tries to change lastProp if that's 

> >    JSScope::clear: not much to say here, except we can clearDictionaryMode()
> >    and clearOwnShape() when clearing all props from a scope.
> 
> This is similar to a comment you made on my patch in bug 505523. It's
> mostly right. We can't *unconditionally* clearOwnShape() because that
> might give this scope the same shape as a scope of a different class
> (bug 505523); but I think we can in the usual case.

JSScope::clear already goes on to do this, unchanged by the patch:

    JSClass *clasp = object->getClass();
    JSObject *proto = object->getProto();
    uint32 newShape = 0;
    if (proto && clasp == proto->getClass()) {
#ifdef DEBUG
        bool ok =
#endif    
        OBJ_SCOPE(proto)->getEmptyScopeShape(cx, clasp, &newShape);
        JS_ASSERT(ok);
    } else {
        newShape = js_GenerateShape(cx, false);
    }
    initMinimal(cx, newShape);

So my Baedeker's "not much to say here" didn't mean to suggest *removing* the above code, or anything of the sort!

Hope you can find time (putting your family first -- sick kids lately at my house too) to read the patch. Much appreciated!

/be

Comment 34

[Brendan Eich [:brendan]]

(In reply to comment #33)
> > >    JSScope::changeProperty: as noted in the watchpoint discussion earlier,
> > >    this method takes an sprop param which must be in this scope. After some
> > >    assertions (including a new one, that we're not changing a SPROP_IS_METHOD
> > >    sprop) comes another watchpoint issue:
> > > 
> > >+    if (IsWatchPointSetter(setter, attrs) && !inDictionaryMode() && !toDictionaryMode(cx, sprop))
> > >+        return NULL;
> > 
> > Why do we need special code for watchpoints here? If you just deleted
> > this, wouldn't we end up in putProperty which would do the right thing?
> 
> JSScope::changeProperty does not remove and then add (not put if it knows it is
> not there), it instead tries to change lastProp if that's 

Oops, cut off text here. I went off to look at the code and forgot to come back! But it was worth it -- you're right, there's no good reason for this code. It is left over from a (bad) intermediate state. Removing it regressed

js1_5/extensions/regress-454142.js

which pointed to a flaw in jsdbgapi.cpp's DropWatchPointAndUnlock: it tries to restore the original setter saved when obj_watch ran, but does not worry about a new property with attributes incompatible with that setter having come along in the mean time. Yikes.

New patch soon.

/be

Comment 35

[Brendan Eich [:brendan]]

Attachment: patch to review

The Baedeker lies about obj.watch watching (obj, id) no matter what. If you define a getter or setter, which replaces any previous definition, the watchpoint does not survive. If you delete and re-create, it does. This is how it was and is, not necessarily how it should be. Accordingly, DropWatchPointAndUnlock now insists that wp->sprop matches the result of scope->lookup(wp->sprop->id), if you follow my meaning.

All tests pass. With this bug fixed, bug 335700 is now in striking distance.

/be

Comment 36

[Brendan Eich [:brendan]]

(In reply to comment #35)
> Created an attachment (id=411357) [details]
> patch to review
> 
> The Baedeker lies about obj.watch watching (obj, id) no matter what. If you
> define a getter or setter, which replaces any previous definition,

Correction: defining a setter blows away the watchpoint, in effect, but defining a getter where the watched property had a (function object, not JSPropertyOp) setter just adds the setter.

The low-level implementation details interfere (watchpoints predate user-defined setters). This could be fixed, I'll file a separate bug in a bit.

/be

Comment 37

[Brendan Eich [:brendan]]

(In reply to comment #36)
> (In reply to comment #35)
> > Created an attachment (id=411357) [details] [details]
> > patch to review
> > 
> > The Baedeker lies about obj.watch watching (obj, id) no matter what. If you
> > define a getter or setter, which replaces any previous definition,
> 
> Correction: defining a setter blows away the watchpoint, in effect, but
> defining a getter where the watched property had a (function object, not
> JSPropertyOp) setter just adds the setter.

s/adds the setter/adds the getter/

More later today, I'll be back after 2pm PST.

/be

Comment 38

[Jason Orendorff [:jorendorff]]

I'm still looking at the details. It seems very solid though. Even jsfunfuzz isn't finding anything, so far.

In jsapi.cpp:
> AlreadyHasOwnProperty(JSContext *cx, JSObject *obj, JSAtom *atom)
> {
>-    JSScopeProperty *sprop;
>-    JSScope *scope;
>-
>     JS_ASSERT(OBJ_IS_NATIVE(obj));
>     JS_LOCK_OBJ(cx, obj);

The assertion is redundant, since JS_LOCK_OBJ calls OBJ_SCOPE which
asserts the same thing.

(Really it ought to read more like,
      JSAutoObjectLock locked(cx, obj);
      return locked.scope->hasProperty(ATOM_TO_JSID(atom));
but that can wait...)

In jsbuiltins.cpp:
> js_AddProperty(JSContext* cx, JSObject* obj, JSScopeProperty* sprop)
> {
>     JS_ASSERT(OBJ_IS_NATIVE(obj));
>     JS_LOCK_OBJ(cx, obj);

Same redundant assertion.

>+    if (!scope->table && sprop->parent == scope->lastProperty() && slot == scope->freeslot) {

I think this is now always true, so the else branch never executes.

>-        JSScopeProperty *sprop2 = scope->add(cx, sprop->id,
>-                                             sprop->getter, sprop->setter,
>-                                             SPROP_INVALID_SLOT, sprop->attrs,
>-                                             sprop->flags, sprop->shortid);
>+        JSScopeProperty *sprop2 = scope->addDataProperty(cx, sprop->id, SPROP_INVALID_SLOT,
>+                                                         sprop->attrs);

If this is reachable, the change in behavior here makes me nervous. It
seems like sprop->getter and ->setter could be non-null and non-stub in
certain cases; if they can't, the code could assert that.

I think it's unreachable though.

>-            for (JSScopeProperty *sprop = SCOPE_LAST_PROP(scope);
>+            for (JSScopeProperty *sprop = scope->lastProperty();
>                  sprop;
>                  sprop = sprop->parent) {

This would fit on one line. (And again, about 35 lines below, same code.)

In jsscope.h:
>+    JSScopeProperty *getChildProperty(JSContext *cx, JSScopeProperty *parent,
>+                                          JSScopeProperty &child);

Indentation nit.

>+    /* Add an accessor property whose id is not yet in this scope. */
>+    JSScopeProperty *addAccessorProperty(JSContext *cx, jsid id,

This isn't used anywhere.

In jsscope.cpp, JSScope::toDictionaryMode:
>+    lastProp = NULL;

Here and in other places, lastProp is assigned directly rather than call setLastProperty. setLastProperty(NULL) wouldn't work in a DEBUG build anyway, so maybe this is intentional.

In JSScope::removeDictionaryProperty:
>+    JS_ASSERT(inDictionaryMode());
>+
>+    JS_ASSERT(sprop->flags & SPROP_IN_DICTIONARY);
>+    JS_ASSERT(sprop->childp);
>+    JS_ASSERT(!JSVAL_IS_NULL(sprop->id));
>+
>+    JS_ASSERT(lastProp->flags & SPROP_IN_DICTIONARY);
>+    JS_ASSERT(lastProp->childp == &lastProp);
>+    JS_ASSERT_IF(lastProp != sprop, !JSVAL_IS_NULL(lastProp->id));
>+    JS_ASSERT_IF(lastProp->parent, !JSVAL_IS_NULL(lastProp->parent->id));

Might as well add JS_ASSERT_IF(table, hasProperty(sprop)) here.

Comment 39

[Jason Orendorff [:jorendorff]]

Comment on attachment 411357 [details] [diff] [review]
patch to review

This is a really great patch. Just a few nits.

Middle deletes still result in an ever-growing dslots, according to the
(unmodified) comment in js_AllocSlot. Once you get past 2^16 add
operations, regardless of how many deletes there have been, we do O(N^2)
copying. To fix that, we could store a "slot freelist" in the unused slots
left by deleted properties; or JSScope::changeTable could occasionally
compact this->object->dslots. Followup bug, if anyone cares.

In jsscope.cpp, CheckAncestorLine:
>         if (sprop) {
>-            entryCount++;
>+            ++entryCount
>             for (aprop = ancestorLine; aprop; aprop = aprop->parent) {

Missing semicolon.

In JSScope::changeProperty:
>+    if (inDictionaryMode()) {
>+        removeDictionaryProperty(sprop);
>+        newsprop = newDictionaryProperty(cx, child, &lastProp);
>+        if (newsprop) {
>+            if (table) {
>+                JSScopeProperty **spp = search(sprop->id, false);
>+                SPROP_STORE_PRESERVING_COLLISION(spp, newsprop);
>+            }
>+            updateShape(cx);
>         }

This code could modify *sprop in place and move it to the end of the
linked list--maybe more code than it's worth.

In toDictionaryMode:
>+        if (!dprop) {
>+            entryCount = saveEntryCount;
>+            table = oldTable;
>+            lastProp = oldLastProp;
>+            METER(toDictFails);
>+            return false;
>+        }

This should js_Free the newly allocated table.

Comment 40

[Jason Orendorff [:jorendorff]]

It's a shame to waste a shape-id on every property in a dictionary-mode scope. Maybe in the future we can make them shapeless, and the JIT can fall back on generic code to operate on such objects. Same goes for non-dense arrays.

Comment 41

[Brendan Eich [:brendan]]

(In reply to comment #39)
The slot freelist idea is good, we've talked about it for ages but AFAIK it was never filed. Will file today.

(In reply to comment #40)
> It's a shame to waste a shape-id on every property in a dictionary-mode scope.

Only for really big dictionaries. Agreed this is a potential issue. I will study it a bit more and probably file a bug.

> Maybe in the future we can make them shapeless, and the JIT can fall back on
> generic code to operate on such objects. Same goes for non-dense arrays.

Small-ish dictionaries want to be fast, they want and deserve PICs for slot loads, method caching, etc.

/be

Comment 42

[Brendan Eich [:brendan]]

(In reply to comment #41)
> (In reply to comment #39)
> The slot freelist idea is good, we've talked about it for ages but AFAIK it was
> never filed. Will file today.

On second thought (gal agreed spontaneously) we should avoid scrambling slots and simply compress slot vectors when we need to by some measure, during GC (or even in JSScope::changeTable if that makes sense -- that would force a shape change, as certain GCs can force too, currently only on rt->shapeGen 24-bit overflow).

/be

Comment 43

[Brendan Eich [:brendan]]

(In reply to comment #39)
> In JSScope::changeProperty:
> >+    if (inDictionaryMode()) {
> >+        removeDictionaryProperty(sprop);
> >+        newsprop = newDictionaryProperty(cx, child, &lastProp);
> >+        if (newsprop) {
> >+            if (table) {
> >+                JSScopeProperty **spp = search(sprop->id, false);
> >+                SPROP_STORE_PRESERVING_COLLISION(spp, newsprop);
> >+            }
> >+            updateShape(cx);
> >         }
> 
> This code could modify *sprop in place and move it to the end of the
> linked list--maybe more code than it's worth.

It would also preserve for-in enumeration order. But the proptree case does not and so I claim the dictionary-mode case must not, either.

The interesting case is defining a setter for an id with a getter, or vice versa, using the old __define{G,S}etter__ or the new ES5 Object.defineProperty API (called twice), with another prop added in between. What's the for-in order supposed to be? ES5 doesn't say, it leaves enumeration order implementation-dependent (as ES1-3 did) but we have our precedent based on the proptree.

> >+        if (!dprop) {
> >+            entryCount = saveEntryCount;
> >+            table = oldTable;
> >+            lastProp = oldLastProp;
> >+            METER(toDictFails);
> >+            return false;
> >+        }
> 
> This should js_Free the newly allocated table.

Ouch, good catch. Thanks,

/be

Comment 44

[Brendan Eich [:brendan]]

Attachment: address all actionable review comments

Comment 45

[Brendan Eich [:brendan]]

Attachment: plain diff of last two patches

Comment 46

[Brendan Eich [:brendan]]

bclary, mrbkap: I get a pass on this in the shell, but jstestbrowser fails with the patch on this test:

REFTEST TEST-UNEXPECTED-FAIL | file:///Users/brendaneich/Hacking/hg.mozilla.org/tracemonkey/js/src/tests/jsreftest.html?test=js1_8_1/extensions/regress-520572.js | watch should innerize the object being watched Expected value '2', Actual value '0'  item 1

I'll retest on tm tip to confirm it's not due to the patch here.

/be

Comment 47

[Bob Clary [:bc] (inactive)]

tm tip mac passes jstestbrowser opt/debug without this patch for me.

Comment 48

[Bob Clary [:bc] (inactive)]

confirmed failures in comment 46 with patch from comment 44 in opt/debug jstestbrowser but not shell.

Comment 49

[Brendan Eich [:brendan]]

Attachment: still fails in-browser js1_8_1/extensions/regress-520572.js; shell passes

Could use mrbkap's help here.

/be

Comment 50

[Blake Kaplan (:mrbkap) (inactive)]

(In reply to comment #49)
> Could use mrbkap's help here.

I brute-forced my way to understanding here by repeatedly applying and unapplying the patch to get a sense of what's actually happening. As expected, this is caused by the bizzarro way that wrappers interact with split objects. Here's the sequence of events that causes things to break (by the way, this points, yet again, to using non-native objects for wrappers and outer objects, but that's another bug for another time):
  - We call xow(outer(inner)).watch('x', ...)
  -> This defines a property on the inner window thanks to bug 520572 with js_watch_set as a setter.
  - We do xow(outer(inner)).x = 4;
  -> This creates a new property on the xow, which forwards to the outer (with default getter/setter), which forwards to the inner (with default getter/setter).
  -> Because this forwarding happens in the addProperty hook, we're calling JS_DefineProperty*, which means we end up overriding the watchpoint-created property.

Now, on trunk, this is OK, because we call JSScope::add, which has some code to deal with __defineSetter__ on a watchpointed property.
With the patch, though, we call JSScope::putProperty which doesn't have the same watchpoint-saving code, leading to the watchpoint not working.

The easiest way to fix this would be to call the watchpoint-saving code from JSScope::putProperty. The most correct way to fix this would be to have our own JSObjectOps for our wrappers/outer objects that don't duplicate all of this work.

Comment 51

[Brendan Eich [:brendan]]

Attachment: passes all tests -- thanks, mrbkap

This is ready.

/be

Comment 52

[Brendan Eich [:brendan]]

http://hg.mozilla.org/tracemonkey/rev/6daf3a51df56

/be

Comment 53

[Robert Sayre]

looks like this has been failing a mochitest-browser-chrome test on windows since it was checked in. I think we should back it out. There is a small conflict that I'm not too sure about, so leaving a comment here.

Comment 54

[Brendan Eich [:brendan]]

(In reply to comment #53)
> looks like this has been failing a mochitest-browser-chrome test on windows
> since it was checked in. I think we should back it out. There is a small
> conflict that I'm not too sure about, so leaving a comment here.

Which test? I thought I fixed this already in bug 530507...

I'll fix a followup if you file it, rather than back out and spend more overhead rebasing and so on. Pretty please?

/be

Comment 55

[Boris Zbarsky [:bzbarsky]]

> I thought I fixed this already in bug 530507

The windows mochitest-browser-orange is still very much there on t-m.  So yes, we need a followup.  Or something.  And probably closing the tree until it's actually green...

Comment 56

[Brendan Eich [:brendan]]

No fair not pointing to the new TraceMonkey-Unittest page -- I did not know about it, bz said it was a "recent development; not well-announced".

Looking into it...

/be

Comment 57

[Brendan Eich [:brendan]]

Based on

http://tinderbox.mozilla.org/showlog.cgi?log=TraceMonkey-Unittest/1259625209.1259628890.21622.gz&fulltext=1#err0

I tested

python runtests.py --browser-chrome --test-path=toolkit/mozapps/extensions/test/browser_bug510909.js

and (after fixing bug 532041 to get past it) I get a big fat pass. Any advice?

/be

Comment 58

[Brendan Eich [:brendan]]

Duh, of course I'm on a Mac.

Windows tomorrow, I was waiting for Windows 7 to wipe the Vista install on my new desktop PC but I don't need to wait for that.

/be

Comment 59

[Robert Sayre]

(In reply to comment #56)
> No fair not pointing to the new TraceMonkey-Unittest page -- I did not know
> about it, bz said it was a "recent development; not well-announced".

Sorry. I actually didn't spot this until today, when most of the other stuff got cleared up. I only suggest the backout because we have blockers that need to get merged to m-c.

Comment 60

[Robert Sayre]

So, this bug and its follow-up still back out cleanly.

What I'm going to do is this:

back out those two patches for the morning, so I can merge to m-c.
work can continue in bug 532096. run "hg pull -u -r 57a6ad20eae9" to get the rev before my backouts.
I should have things back in place before lunch pacific time.

Comment 61

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/bb4f39064bf0