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

RESOLVED FIXED

Status

()

Core
JavaScript Engine
P2
minor
RESOLVED FIXED
9 years ago
8 years ago

People

(Reporter: Jeremy, Assigned: brendan)

Tracking

({perf})

unspecified
Points:
---
Dependency tree / graph
Bug Flags:
blocking1.9.2 -

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(7 attachments, 6 obsolete attachments)

7.30 KB, application/zip
Details
20.75 KB, text/html
Details
69.90 KB, text/html
Details
338 bytes, application/x-javascript
Details
19.85 KB, text/plain
Details
14.97 KB, patch
Details | Diff | Splinter Review
128.19 KB, patch
jorendorff
: review+
Details | Diff | Splinter Review
(Reporter)

Description

9 years ago
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.
(Reporter)

Comment 1

9 years ago
Created attachment 356586 [details]
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

9 years ago
Created attachment 356698 [details]
deletetest.html with inline script

Comment 3

9 years ago
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
Keywords: perf
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...
(Reporter)

Comment 5

9 years ago
Created attachment 359935 [details]
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.
(Assignee)

Comment 6

9 years ago
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
Status: UNCONFIRMED → NEW
Ever confirmed: true
(Assignee)

Comment 7

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

/be
> 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).
Summary: JavaScript delete operation on Object properties unexpectedly slow → Setting a property after deleting another one is slow if the object has many properties
Created attachment 380569 [details]
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.
Er, I quit shark before exporting the report to attach, but I seriously doubt you actually need one given the above information.
Flags: blocking1.9.2?
(Assignee)

Comment 11

9 years ago
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
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.
Is bug 495753 related to this?  It seems like jquery tickles it, and they're using the latest trunk.
(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.)

Updated

9 years ago
Flags: blocking1.9.2? → blocking1.9.2+
Priority: -- → P3
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?
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.
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.
(Assignee)

Comment 18

9 years ago
(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
(Assignee)

Updated

8 years ago
Depends on: 511591

Updated

8 years ago
Assignee: general → brendan
Priority: P3 → P1
(Assignee)

Updated

8 years ago
Blocks: 497789
Brendan, are you on this?  Any update?
(Assignee)

Comment 20

8 years ago
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
(Assignee)

Comment 21

8 years ago
Er, AWOL.

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

/be
(Assignee)

Updated

8 years ago
OS: Windows XP → All
Priority: P1 → P2
Hardware: x86 → All

Comment 22

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

Comment 23

8 years ago
This needs a beta imo.
(Assignee)

Updated

8 years ago
Status: NEW → ASSIGNED
No longer depends on: 511591

Updated

8 years ago
Flags: blocking1.9.2+ → blocking1.9.2-

Comment 24

8 years ago
not blocking on this desirable enhancement, per discussion with brendan
(Assignee)

Comment 25

8 years ago
Created attachment 409270 [details] [diff] [review]
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
(Assignee)

Comment 26

8 years ago
Created attachment 410361 [details] [diff] [review]
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
Attachment #409270 - Attachment is obsolete: true
Attachment #410361 - Flags: review?(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)
(Assignee)

Comment 28

8 years ago
Created attachment 410443 [details]
my little Baedeker about what's going on in the patch
(Assignee)

Updated

8 years ago
Attachment #410443 - Attachment is patch: false
(Assignee)

Comment 29

8 years ago
Created attachment 410444 [details]
lost some intro text in my fine Baedeker
Attachment #410443 - Attachment is obsolete: true
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.
Attachment #410361 - Flags: review?(jorendorff)
Attachment #410361 - Flags: review?(graydon)
Attachment #410361 - Flags: review+
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}.
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.
(Assignee)

Comment 33

8 years ago
(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
(Assignee)

Comment 34

8 years ago
(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
(Assignee)

Comment 35

8 years ago
Created attachment 411357 [details] [diff] [review]
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
Attachment #410361 - Attachment is obsolete: true
Attachment #410361 - Flags: review?(jorendorff)
(Assignee)

Updated

8 years ago
Attachment #411357 - Flags: review?(jorendorff)
(Assignee)

Comment 36

8 years ago
(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
(Assignee)

Comment 37

8 years ago
(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
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.
Attachment #411357 - Flags: review?(jorendorff) → review+
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.
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.
(Assignee)

Comment 41

8 years ago
(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
(Assignee)

Comment 42

8 years ago
(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
(Assignee)

Comment 43

8 years ago
(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
(Assignee)

Comment 44

8 years ago
Created attachment 413228 [details] [diff] [review]
address all actionable review comments
Attachment #411357 - Attachment is obsolete: true
Attachment #413228 - Flags: review?(jorendorff)
(Assignee)

Comment 45

8 years ago
Created attachment 413230 [details] [diff] [review]
plain diff of last two patches
(Assignee)

Comment 46

8 years ago
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

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

Comment 48

8 years ago
confirmed failures in comment 46 with patch from comment 44 in opt/debug jstestbrowser but not shell.
(Assignee)

Comment 49

8 years ago
Created attachment 413285 [details] [diff] [review]
still fails in-browser js1_8_1/extensions/regress-520572.js; shell passes

Could use mrbkap's help here.

/be
Attachment #413228 - Attachment is obsolete: true
Attachment #413285 - Flags: review?(jorendorff)
Attachment #413228 - Flags: review?(jorendorff)
(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.
(Assignee)

Comment 51

8 years ago
Created attachment 413577 [details] [diff] [review]
passes all tests -- thanks, mrbkap

This is ready.

/be
Attachment #413285 - Attachment is obsolete: true
Attachment #413577 - Flags: review?(jorendorff)
Attachment #413285 - Flags: review?(jorendorff)
Attachment #413577 - Flags: review?(jorendorff) → review+
(Assignee)

Comment 52

8 years ago
http://hg.mozilla.org/tracemonkey/rev/6daf3a51df56

/be
Whiteboard: fixed-in-tracemonkey

Updated

8 years ago
Depends on: 530507

Comment 53

8 years ago
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.
Whiteboard: fixed-in-tracemonkey
(Assignee)

Comment 54

8 years ago
(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
> 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...
(Assignee)

Comment 56

8 years ago
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
(Assignee)

Comment 57

8 years ago
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
(Assignee)

Comment 58

8 years ago
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

8 years ago
(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

8 years ago
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

8 years ago
http://hg.mozilla.org/mozilla-central/rev/bb4f39064bf0
Status: ASSIGNED → RESOLVED
Last Resolved: 8 years ago
Resolution: --- → FIXED
(Assignee)

Updated

8 years ago
Depends on: 532096
Depends on: 533876

Updated

8 years ago
Depends on: 534493
Depends on: 536795
(Assignee)

Updated

8 years ago
Duplicate of this bug: 563286
You need to log in before you can comment on or make changes to this bug.