322889 - (native-arrays) Array implementation should specialize its own nearly-native JSObjectOps

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect, P2)

Description

[Brendan Eich [:brendan]]

See bug 322135 comment 5, bug 101964, bug 171262, bug 253138, and probably others.

/be

Comment 1

[Brendan Eich [:brendan]]

I think mrbkap is on this already.

/be

Comment 2

[Mike Schroepfer]

Hey BKap - are you workin on this one?

Comment 4

[Brian Crowder]

No word from mrbkap and no patch == no blocker?  This is probably a good perf bug, though (this and Shaver's array-literal bug, whose number I cannot remember).  I might be able to hack on this one, though, if mrbkap cannot, and we do think it's high-priority?

Comment 5

[Mike Schroepfer]

(In reply to comment #4)
> No word from mrbkap and no patch == no blocker?  This is probably a good perf
> bug, though (this and Shaver's array-literal bug, whose number I cannot
> remember).  I might be able to hack on this one, though, if mrbkap cannot, and
> we do think it's high-priority?
> 

You got time Crowder?   We need to crank on js perf!   

Comment 6

[Mike Schroepfer]

Moving to blocker list since we are doing a perf push.   If you disagree let me know ...

Comment 7

[Mike Shaver (:shaver emeritus)]

So I was thinking that in order to support non-indexed properties without too much hassle, we'd add a reserved slot and hang the dense jsval vector there with a mark hook to traverse them.  A custom mark hook and we're away?

Do we want to have some threshold at which we fall back to the current model, to support very-sparse arrays?  |(new Array)[bignum] = 1;| will otherwise cause us to malloc a pretty big chunk of memory, though the OS won't commit it until it's dirtied, so maybe that's fine.

I was thinking that a bitmap of set properties would let us track which properties were present, such that we could uneval efficiently and not need to fill the world with JSVAL_HOLE.  We could also do a cheap test to see if we should shrink the slots vector, by just testing the last word of the bitmap against zero when we delete a property or adjust adjust .length downwards.

Comment 8

[Mike Shaver (:shaver emeritus)]

Attachment: WIP

Basics are working here, though some things are clearly not quite right yet.  (My last chunk of work broke toString-after-gc, as it appears that array_toString is being called as a non-JSFUN_GENERIC native, which confuses it quite substantially.)  Mostly checkpointing in case it helps crowder in some way, and so that I don't lose any more work to pointing rsync --delete in the wrong direction. :/  Not sure when I'll have time to work on it more.

Comment 9

[Mike Shaver (:shaver emeritus)]

Attachment: WIP 2: now with better GC

Hot tip: have to actually mark the slots!  Might be worth adding the bit-noise to store LENGTH at FASTSLOTS[-1] and keep FASTSLOTS/BITMAP tagged as JSVAL_INT, so that I can just reuse js_TraceObject without having to skip those slots by hand.

(Also need to store CAPACITY somewhere, I suppose BITMAP[-1] would suffice.)

Comment 10

[Jeff Walden [:Waldo]]

Comment on attachment 295077 [details] [diff] [review]
WIP 2: now with better GC

I suspect this needs a smattering of casts for the |bmap = JSVAL_TO_PRIVATE(...)| and |fast = JSVAL_TO_PRIVATE(...)| statements to compile as C++, perhaps within ARRAY_BITMAP/ARRAY_SLOTS macros.

Comment 11

[Mike Shaver (:shaver emeritus)]

Attachment: WIP 3: fix fastslots/bitmap/length accessor use and array_enumerate

Doesn't crash on sunspider, but doesn't do much else either -- something still busted in enumeration or iteration, probably obvious to someone CC'd on this bug!

Gonna fix array_length_setter and do thresholding for fastslot use so I can run more of the JS test suite next.

Comment 12

[Mike Shaver (:shaver emeritus)]

Attachment: WIP 4: passes ecma/Array and ecma_3/Array, less the regress-322135-* cases

Nowhere near done, SunSpider still doesn't do anything interesting, but things are a bit better.  Hacked around bug 410540 by checking enumerate as well in JS_NewPropertyIterator.  The logic in array_enumerate embarrasses me and there are many other badnesses around as well, but it passes more tests than previous WsIP, and I wanted to checkpoint before I disappear for a while.

Comment 13

[Mike Shaver (:shaver emeritus)]

Attachment: WIP 5: fix enumeration and off-the-end property access

This runs sunspider now, though it's by no means done.  Still have to fix enumeration, do the load-factor faulting we discussed in IRC, and then -- the fun part -- let the array methods take advantage of the new optimizable structure.

Encouraging early results, though; I'll attach a sunspider compare.

Comment 14

[Mike Shaver (:shaver emeritus)]

Attachment: Sunspider vs. branch-point js/src trunk

** TOTAL **:           1.129x as fast    4861.9ms +/- 0.4%   4306.1ms +/- 0.2%     significant

Crypto especially liked this work.

Comment 15

[Mike Shaver (:shaver emeritus)]

(In reply to comment #14)
> Crypto especially liked this work.

Crypto especially likes it when you have a bug that makes them shortcircuit the crypto, cutting out most of the work, ahem.  The MD5 and SHA gains were somewhat juiced; there will be an asterisk in the archives.

Comment 16

[Mike Shaver (:shaver emeritus)]

Attachment: WIP 6: incorporating constructor-for-literal patch, optimizing InitArrayElements, and fixing some bugs

This runs sunspider, and doesn't put its fist through the crypto logic in quite as gruesome a way, meaning that the numbers are probably meaningful.  I've incorporated the use-Array-constructor-for-literals patch from that other bug I can't remember now, and made InitArrayElements a memcpy and some bitmath.

Time to do the load-factor-based faulting to map-based arrays, and then we can go write fast-paths for whatever Array methods sayrer tells us will make a difference on anything we care about.

Waldo: the decompiler wants your love, for the change to Array(1, 2, 3) codegen.

Comment 17

[Robert Sayre]

Attachment: screenshot of crypto-aes in kcachegrind

Comment 18

[Robert Sayre]

Attachment: kcachegrind without the patch

Comment 19

[Mike Shaver (:shaver emeritus)]

Learning as I go here, refining the plan:

/*
 * JS array class.
 *
 * Array objects begin as "dense" arrays, optimized for numeric-only property
 * access over a vector of slots (obj->dslots) with high load factor.  Array
 * methods optimize for denseness by testing that the object's class is
 * &js_ArrayClass, and can then directly manipulate the slots for efficiency.
 * 
 * We track these pieces of metadata for arrays in dense mode:
 *  - the array's length property as a uint32, in JSSLOT_ARRAY_LENGTH,
 *  - the number of indices that are filled (non-holes), in JSSLOT_ARRAY_COUNT,
 *  - the highest index set (MAXINDEX), in dslots[-1] if dslots is non-NULL
 * 
 * In dense mode, holes in the array are represented by JSVAL_HOLE.  The final
 * slot in fslots (JSSLOT_ARRAY_LOOKUP_HOLDER) is used to store the single jsid
 * "in use" by a lookupProperty caller.
 * 
 * Arrays are converted to use js_SlowArrayClass when any of these conditions
 * are met:
 *  - the load factor (MAXINDEX / COUNT) is less than 0.85, and there are
 *    more than 10 empty slots (MAXINDEX - COUNT > 10); or
 *  - a property is set that is non-numeric (and not "length"); or
 *  - a hole is filled below MAXINDEX (possibly implicitly through methods like
 *    |reverse| or |splice|).
 *
 * In the latter two cases, property creation order is no longer index order,
 * which necessitates use of a structure that keeps track of property creation
 * order.  (ES4, due to expectations baked into web script, requires that
 * enumeration order be the order in which properties were created.)
 * 
 * An alternative in the latter case (out-of-order index set) would be to
 * maintain the scope to track property enumeration order, but still use 
 * the fast slot access.  That would have the same memory cost as just using
 * a js_SlowArrayClass, but have the same performance characteristics as
 * a dense array for slot accesses, at some cost in code complexity.
 */

Going to figure out which Array methods share the curse of |reverse| and |splice|, and will cause enumeration order to differ from index order, to get a better sense how much that last paragraph's alternative might be worth.

Comment 20

[Mike Shaver (:shaver emeritus)]

unshift and sort (in the presence of holes in some positions; likewise for reverse, I should have added) also cause orders to diverge.

Comment 21

[Mike Shaver (:shaver emeritus)]

Attachment: WIP 7: implement the new model

I present unto you the 7th incarnation!

Features a total lack of bitmap, switching back to scope-based storage in the non-numeric-property case, allocation-free lookup for dense arrays, and a lack of fixed limits on dense array length.  Pleased to report that the flowers remain standing after the swapping of clasp!

I am not yet faulting in the set-out-of-order case or load-factor-too-low case, which latter will keep it from passing the JS test suite.  Looks to be a little bit faster (mostly in morph and nsieve) than WIP-6, and should churn a lot less memory.  Haven't run any tools on it to make sure that it uses that less memory _safely_, but baby steps.

Comment 22

[Mike Shaver (:shaver emeritus)]

Attachment: WIP 8: as before, merged to trunk

Comment 23

[Mike Shaver (:shaver emeritus)]

Comment on attachment 297989 [details] [diff] [review]
WIP 8: as before, merged to trunk

Nurr, still learning to drive hg, sorry.

Comment 24

[Mike Shaver (:shaver emeritus)]

Attachment: WIP 8: as before, merged to trunk (really)

Now vs. current trunk, not my baseline trunk.

Comment 25

[Mike Shaver (:shaver emeritus)]

Attachment: WIP 9: now with compiling

A post-test change to add JSOP_HOLE accidentally crept into my rebased diff, tee hee.  This should have 100% fewer compilation errors.

Comment 26

[Mike Shaver (:shaver emeritus)]

Attachment: WIP 10: tracking load factor, arrayInfo helper, JSOP_HOLE

Reusing JSOP_PUSH wasn't going to work, because we use its JSVAL_VOID-pushing powers in places like "return;".  Could parameterize JSOP_PUSH, trading a larger bytecode stream for saving increasingly-scarce single-byte bytecodes; JSOP_NEWARRAY will eat another in a future patch.  (Don't recommend decompiling functions with array literals in the interim; shouldn't crash, but won't round trip if there are holes.)

The load-factor tracking is still really basic, and I just made up the numbers.

Comment 27

[Mike Shaver (:shaver emeritus)]

Attachment: WIP 11: better slow array handling

- Added -Z option to js.c to set zeal early and without script modification.
- Fixed precedence error in ReallocSlots that manifested as memory unsafety -- thanks, Valgrind!
- Remove extra check for enumerate method's nativeness in JS_NewPropertyIterator.
- Add assertion to catch JS_NEW_ENUMERATE with stubbed enumerate class hook.
- Don't create properties in slow arrays for JSVAL_HOLEs in dense.
- Preserve property attributes on slowifying non-indexed property definition.
- Streamline slow impl and clean up dense tracing code.

Might be some fuzz against current trunk, I haven't rebased since Igor landed some things.

Comment 28

[Mike Shaver (:shaver emeritus)]

Attachment: WIP 13: passes all array tests

Only support -Z <zeal> if JS_GC_ZEAL, and fix some slowification.

We now pass all the ecma_3/Array and ecma/Array tests, including the slow ones (which aren't slow any more!), provided that this counts as a pass for regress-322135-03.js:

PASSED! Array.prototype.splice on Array with length 2^32-1: RangeError

I haven't changed splice's logic to be optimized for dense arrays yet, but it could be tripping some latent bug in my get/set/delete paths.

Kicking off a full test run now...

Comment 29

[Mike Shaver (:shaver emeritus)]

Looks like I broke regexps pretty good!  Working on it.

Comment 30

[Mike Shaver (:shaver emeritus)]

Attachment: WIP 14: fix regexp tests.

js_SetElement takes a jsid, which is an integer.  JS_SetElement takes an untagged index, which is an integer.  Discuss.

Comment 31

[Brian Crowder]

Attachment: WIP 15: pass js/test suite

We now pass everything in js/test which is passed by the trunk source, as of this moment.

Comment 32

[Brian Crowder]

TODOs:
a)  Need new bugs to track array functions that can be improved in the new world, like array_splice and friends -- need to revisit some of the slow-n bugs that shouldn't be slow-n in the new world, especially, for example bug 322135.
b)  Need to consider/fix thread-safety issues.
c)  Need test-cases and code fixes to handle mutating from dense arrays to slowarrays at Bad Times, such as during an enumeration.

I know there's a good deal more to be done here, but I didn't want to forget these, so I'm noting them now.

Comment 33

[Brian Crowder]

Here's a testcase that kills us in the enumeration/mutation situation:

var a = [ 1, 2, 3, 4, 5 ];
for (let i in a) {
    print(i)
    if (i == 3)
        a[500] = "fail"
}

Comment 34

[Mike Shaver (:shaver emeritus)]

Attachment: WIP 16: handles faulting during enumeration, some method optimizations

Key changes:
- handle the case where we fault to becoming slow during enumeration
- defining a setter or getter makes an array become slow
- require a load factor of < 25%, and a length > 32, for faulting to slowness
- optimize InitArrayElements, array_slice, array_concat (a little) for dense arrays

Passes all tests, time for the try server!

Comment 35

[Mike Shaver (:shaver emeritus)]

Attachment: WIP 17: whoops, rolled back some tuning-constant changes

While reviewing with Brendan, I noticed that I had rolled back some constant tuning in the previous patch.

Comment 36

[Mike Shaver (:shaver emeritus)]

Comment on attachment 299901 [details] [diff] [review]
WIP 17: whoops, rolled back some tuning-constant changes

Some notes from a first review pass with Brendan:

- rewrap macros
- static assert that the memory math works in favour of the load factor constants
- remove XXXshaver above ReallocSlots or make FIXME
- ReallocSlots' sizeof math can overflow
- Rename ReallocSlots to GrowSlots?
- invert denseness test in array_length_setter
- need a threadsafety protocol

Comment 37

[Mike Schroepfer]

Shaver are we going to try for this for b3 today?

Comment 38

[Brian Crowder]

I have hit the following points and pushed to my hg repo, and will do a full run of the test-suite shortly:
- static assert that the memory math works in favour of the load factor constants
- remove XXXshaver above ReallocSlots or make FIXME
- ReallocSlots' sizeof math can overflow
- Rename ReallocSlots to GrowSlots?
- invert denseness test in array_length_setter

Comment 39

[Robert Sayre]

Got a patch that applies to the current trunk?

Comment 40

[Mike Shaver (:shaver emeritus)]

Attachment: WIP 18, merged to trunk and crowder's fixes for some stuff from comment 36

Passes the suite vs older trunk, runs sunspider.

Comment 41

[Mike Shaver (:shaver emeritus)]

Comment on attachment 302408 [details] [diff] [review]
WIP 18, merged to trunk and crowder's fixes for some stuff from comment 36

This left duplicate #defines of ARRAY_IS_DENSE and OBJ_IS_ARRAY in jsarray.c, I'll get 'em on the next update.

Comment 42

[Mike Shaver (:shaver emeritus)]

Attachment: WIP 19: rationalize length management, optimize SetArrayElement/GetArrayElement, fix JS_IsArrayObject and BigIndexToId

This passes the suite, has everything fixed but the threadsafety protocol, which needs 416615 and then some follow-on adjustments here.  If the review chronology worked that way, it would be _tempting_ to land without the threadsafety protocol, since we are unlikely to be sharing arrays across threads in the browser, and it would give a few extra days of bake time.

Comment 43

[Mike Shaver (:shaver emeritus)]

Attachment: WIP 20: fixed array_push

The big two-oh!  It turns out that array_push is important to the browser; you may remember it from such films as "Restoring Sessions", "How To Use Session History" and "Oh My!  Where's My Awesomebar?".

-+    if (len + 1 >= ARRAY_LENGTH(obj))
-+        ARRAY_SET_LENGTH(obj, len + 2);
++    ARRAY_SET_LENGTH(obj, len + 1);

Comment 44

[Brendan Eich [:brendan]]

Comment on attachment 302538 [details] [diff] [review]
WIP 20: fixed array_push

>@@ -129,7 +129,7 @@ else
> ifdef USE_MSVC
> OPTIMIZER  = -Zi
> else
>-OPTIMIZER  = -g
>+OPTIMIZER  = -g3

For everyone? Haven't tried it myself yet.

>+ *  - the load factor (COUNT / DENSELEN) is less than 0.25, and there are
>+ *    more than MIN_SPARSE_INDEX slots total

[snip...]

>+#define ARRAY_SET_LENGTH(obj, len)                                             \
>+    STOBJ_SET_SLOT((obj), JSSLOT_ARRAY_LENGTH, (uint32)len)
>+#define ARRAY_LENGTH(obj) (uint32)STOBJ_GET_SLOT((obj), JSSLOT_ARRAY_LENGTH)
>+#define ARRAY_SET_COUNT(obj, count)                                            \
>+    STOBJ_SET_SLOT((obj), JSSLOT_ARRAY_COUNT, (jsval)(count))
>+#define ARRAY_COUNT(obj)   (uint32)(STOBJ_GET_SLOT((obj), JSSLOT_ARRAY_COUNT))

Nit: align non-overflowing macro definitions to start in same column.

>+/* Small arrays are dense, no matter what. */
>+#define MIN_SPARSE_INDEX 32
>+#define INDEX_TOO_SPARSE(array, index)                                         \
>+    ((index) > ARRAY_DENSELEN(array) && (index) > MIN_SPARSE_INDEX &&          \
>+     (index) > (ARRAY_COUNT(array) + 1) * 4)

Seems like comparing index to *LEN or MIN_*INDEX should use >= not > -- else you can't have index = 32 (MIN_SPARSE_INDEX) result in a true result for INDEX_TOO_SPARSE.

>+static
>+JSBool MakeArraySlow(JSContext *cx, JSObject *obj);

Nit: wrap after return type, not before.

>@@ -254,6 +363,23 @@ GetArrayElement(JSContext *cx, JSObject 
>     JSObject *obj2;
>     JSProperty *prop;
> 
>+    if (ARRAY_IS_DENSE(cx, obj)) {
>+        if (index >= ARRAY_DENSELEN(obj)) {
>+            *vp = JSVAL_VOID;
>+            *hole = JS_TRUE;
>+            return JS_TRUE;
>+        }
>+
>+        *vp = obj->dslots[index];
>+        if (*vp == JSVAL_HOLE) {
>+            *hole = JS_TRUE;
>+            *vp = JSVAL_VOID;

Nit: set *vp before *hole to match earlier order and put *vp store next to test.

>@@ -288,6 +414,23 @@ SetArrayElement(JSContext *cx, JSObject 
> {
>     jsid id;
> 
>+    if (ARRAY_IS_DENSE(cx, obj)) {
>+        if (INDEX_TOO_SPARSE(obj, index)) {
>+            if (!MakeArraySlow(cx, obj))
>+                return JS_FALSE;
>+        } else {
>+
>+            if (!EnsureLength(cx, obj, index + 1))
>+                return JS_FALSE;
>+            if (index >= ARRAY_LENGTH(obj))
>+                ARRAY_SET_LENGTH(obj, index + 1);
>+            if (obj->dslots[index] == JSVAL_HOLE)
>+                ARRAY_SET_COUNT(obj, ARRAY_COUNT(obj) - 1);

Last line should add 1, not subtract 1.

>@@ -418,86 +568,535 @@ array_length_setter(JSContext *cx, JSObj
> 
>     if (!ValueIsLength(cx, *vp, &newlen))
>         return JS_FALSE;
>+    oldlen = ARRAY_LENGTH(obj);
>+
>+    if (oldlen == newlen)
>+        return JS_TRUE;
>+
>     if (oldlen > newlen) {
>+        if (ARRAY_IS_DENSE(cx, obj)) {
>+            if (ARRAY_DENSELEN(obj) && !ResizeSlots(cx, obj, oldlen, newlen))
>                 return JS_FALSE;
>+        } else {
>+            if (oldlen - newlen < (1 << 24)) {

Could use else if here, minimize the patch by avoiding indenting the if-else?

>     if (!IndexToValue(cx, newlen, vp))
>         return JS_FALSE;
>-    STOBJ_SET_SLOT(obj, JSSLOT_ARRAY_LENGTH, *vp);
>+
>+    ARRAY_SET_LENGTH(obj, newlen);
>+

Nit: lose the blank line after.

>     return JS_TRUE;
> }
> 
> static JSBool
>-array_addProperty(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
>+array_lookupProperty(JSContext *cx, JSObject *obj, jsid id, JSObject **objp,
>+                     JSProperty **propp)
> {
>-    jsuint index, length;
>+    uint32 i;
>+
>+    if (!ARRAY_IS_DENSE(cx, obj))
>+        return js_LookupProperty(cx, obj, id, objp, propp);
> 
>+    /* 
>+     * We only have indexed properties up to DENSELEN (excepting holes), plus

"have only"

>+    /* FIXME threadsafety: could race with a lookup on another thread.
>+     * If we can only have a single lookup active per context, we could
>+     * pigeonhole this on the context instead. */

File that bug and cite its number here. Could cite bug 408416 too.

>+static JSBool
>+slowarray_addProperty(JSContext *cx, JSObject *obj, jsid id, jsval *vp)

slow_array_ to match slow_array_push? Or the other way around: slowarray_push.

jsval id, beware other JSClass hooks defined with jsid id.

>+static void
>+slowarray_trace(JSTracer *trc, JSObject *obj)
>+{
>+    uint32 length = ARRAY_LENGTH(obj);
>+
>+    JS_ASSERT(STOBJ_GET_CLASS(obj) == &js_SlowArrayClass);
>+    STOBJ_SET_SLOT(obj, JSSLOT_ARRAY_LENGTH, JSVAL_VOID);
>+    js_TraceObject(trc, obj);
>+    STOBJ_SET_SLOT(obj, JSSLOT_ARRAY_LENGTH, length);
>+}

Comment this fine code-sharing hack?

>+static JSBool
>+array_defineProperty(JSContext *cx, JSObject *obj, jsid id, jsval value,
>+                     JSPropertyOp getter, JSPropertyOp setter, uintN attrs,
>+                     JSProperty **propp)
>+{
>+    uint32 i;
>+
>+    if (id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom))
>+        return JS_TRUE;
>+
>+    if (!js_IdIsIndex(ID_TO_VALUE(id), &i) ||
>+        (attrs & (JSPROP_GETTER | JSPROP_SETTER))) {

How about other attrs, e.g. JSPROP_READONLY or JSPROP_PERMANENT? Or lack of JSPROP_ENUMERATE.

>+array_getAttributes(JSContext *cx, JSObject *obj, jsid id, JSProperty *prop,
>+                    uintN *attrsp)
>+{
>+    if (id == ATOM_TO_JSID(cx->runtime->atomState.lengthAtom))
>+        *attrsp = JSPROP_PERMANENT;
>+    else
>+        *attrsp = JSPROP_ENUMERATE;

Nit: *attrsp = ... ? ... : ...; seems better.

Here in array_deleteProperty:

>+    if (!js_IdIsIndex(id, &i) || i >= ARRAY_DENSELEN(obj) ||
>+        obj->dslots[i] == JSVAL_HOLE) {
>+        *rval = JSVAL_TRUE;
>+        return JS_TRUE;
>+    }
>+    
>+    ARRAY_SET_COUNT(obj, ARRAY_COUNT(obj) - 1);
>+    obj->dslots[i] = JSVAL_HOLE;
>+
>+    *rval = JSVAL_TRUE;
>+    return JS_TRUE;

Common *rval = true; return by inverting if condition to guard ARRAY_SET_COUNT and obj->dslots[i] hole setting.

>+}
>+
>+static JSBool
>+slowarray_enumerate(JSContext *cx, JSObject *obj, JSIterateOp enum_op,
>+                    jsval *statep, jsid *idp)
>+{
>+    /* Are we continuing an enumeration that started when we were dense? */
>+    if (JSVAL_IS_BOOLEAN(*statep)) {
>+        jsval lastIndex = INT_TO_JSVAL(JSVAL_TO_BOOLEAN(*statep));
>+
>+        /* Replace our enumeration state with a native one. */
>+        if (!js_Enumerate(cx, obj, JSENUMERATE_INIT, statep, idp))
>+            return JS_FALSE;
>+
>+        /* Advance the native enumeration state to the previous index. */
>+        do {
>+            if (!js_Enumerate(cx, obj, JSENUMERATE_NEXT, statep, idp))
>+                return JS_FALSE;
>+        } while (*idp != lastIndex && *statep != JSVAL_NULL);
>+
>+        if (*statep == JSVAL_NULL)
>+            return JS_TRUE;

Put this in the loop to avoid testing twice.

>+
>+        /* Now fall through to our usual js_Enumerate pass-through. */
>+    }
>+    return js_Enumerate(cx, obj, enum_op, statep, idp);
>+}
>+
>+/*
>+ * array_enumerate stores its index state as a crypto-boolean,

Avoid my bogus term: should be pseudo-boolean, a crypto-boolean would be a hidden boolean value, but these are false boolean values.

>+ * array_enumerate's.  This encoding limits dense arrays to 2^29-1 enumerable

Enforce this in code.

>+MakeArraySlow(JSContext *cx, JSObject *obj)
>+{
>+    JSObjectMap *map, *oldmap;
>+    uint32 i, length;
>+
>+    JS_ASSERT(OBJ_GET_CLASS(cx, obj) == &js_ArrayClass);
>+
>+    /* Create a native scope. */
>+    map = js_NewObjectMap(cx, obj->map->nrefs, &js_SlowArrayObjectOps,
>+                          &js_SlowArrayClass, obj);
>+    if (!map)
>+        return JS_FALSE;
>+
>+    length = ARRAY_DENSELEN(obj);
>+    if (length) {
>+        map->freeslot = STOBJ_NSLOTS(obj) + JS_INITIAL_NSLOTS;
>+        obj->dslots[-1] = length + JS_INITIAL_NSLOTS;

This can't be right -- obj->dslots[-1] is net length in jsvals starting at obj->dslots, so length, not length + JS_INITIAL_NSLOTS -- right?

>+        /*
>+         * We use SPROP_IS_ALIAS temporarily so that the native scope code
>+         * doesn't freak out about us adding a property which points to a slot
>+         * that's already in use.
>+         */
>+        sprop = js_AddScopeProperty(cx, (JSScope *)map, id, NULL, NULL,
>+                                    i + JS_INITIAL_NSLOTS, JSPROP_ENUMERATE,
>+                                    SPROP_IS_ALIAS, 0);
>+        if (!sprop)
>+            goto out_bad;
>+        sprop->flags &= ~SPROP_IS_ALIAS;

Can't do this -- sprop is hashed based on identity including most flag bits, definitely including SPROP_IS_ALIAS. We need to extend js_AddScopeProperty so it takes a given valid slot and uses it.

>@@ -606,10 +1205,16 @@ array_join_sub(JSContext *cx, JSObject *
> 
>     /* Use rval to locally root each element value as we loop and convert. */
>     for (index = 0; index < length; index++) {
>+        if (ARRAY_IS_DENSE(cx, obj) && index < ARRAY_DENSELEN(obj)) {

(I deleted - lines.) Could adjust loop to make if condition loop invariant, invert it to be outside the loop, for faster iteration up to ARRAY_DENSELEN(obj) -- which could be < length?

>@@ -725,8 +1330,10 @@ array_toSource(JSContext *cx, uintN argc
>     JSObject *obj;
> 
>     obj = JSVAL_TO_OBJECT(vp[1]);
>-    if (!JS_InstanceOf(cx, obj, &js_ArrayClass, vp + 2))
>+    if (!OBJ_IS_ARRAY(cx, obj) &&
>+        !JS_InstanceOf(cx, obj, &js_ArrayClass, vp + 2)) {

Here and below, could avoid testing for both classes in OBJ_IS_ARRAY using just OBJ_GET_CLASS(cx, obj) != &js_SlowArrayClass test.

> InitArrayElements(JSContext *cx, JSObject *obj, jsuint start, jsuint end,
>                   jsval *vector)
> {
>+    if (ARRAY_IS_DENSE(cx, obj)) {
>+        if (!EnsureLength(cx, obj, end))
>+            return JS_FALSE;
>+
>+        if (end >= ARRAY_LENGTH(obj))
>+            ARRAY_SET_LENGTH(obj, end);

The if test should use > not >=.

>@@ -1625,10 +2269,18 @@ array_concat(JSContext *cx, uintN argc, 
>     JS_ASSERT(JS_THIS_OBJECT(cx, vp) == JSVAL_TO_OBJECT(argv[0]));
> 
>     /* Create a new Array object and root it using *vp. */
>-    nobj = js_NewArrayObject(cx, 0, NULL);
>-    if (!nobj)
>-        return JS_FALSE;
>-    *vp = OBJECT_TO_JSVAL(nobj);
>+    if (ARRAY_IS_DENSE(cx, (aobj = JS_THIS_OBJECT(cx, vp)))) {

Pull the aobj setting out of the macro call, put it before the if.

>+        nobj = js_NewArrayObject(cx, ARRAY_DENSELEN(aobj), aobj->dslots);
>+        if (!nobj)
>+            return JS_FALSE;
>+        ARRAY_SET_LENGTH(nobj, ARRAY_LENGTH(aobj));
>+        *vp = OBJECT_TO_JSVAL(nobj);

Adjust argv and argc here to avoid copying aobj's elements again.

>@@ -1743,6 +2389,20 @@ array_slice(JSContext *cx, uintN argc, j
>     if (begin > end)
>         begin = end;
> 
>+    if (ARRAY_IS_DENSE(cx, obj)) {
>+        nobj = js_NewArrayObject(cx, end - begin, obj->dslots + begin);
>+        *vp = OBJECT_TO_JSVAL(nobj);
>+        if (!nobj)
>+            return JS_FALSE;
>+        return JS_TRUE;

Don't set *vp if !nobj.

>@@ -53,7 +53,11 @@ JS_BEGIN_EXTERN_C
> extern JSBool
> js_IdIsIndex(jsval id, jsuint *indexp);
> 
>-extern JSClass js_ArrayClass;
>+extern JSClass js_ArrayClass, js_SlowArrayClass;
>+
>+#define ARRAY_IS_DENSE(cx, obj)  (OBJ_GET_CLASS(cx, obj) == &js_ArrayClass)
>+#define OBJ_IS_ARRAY(cx, obj) (ARRAY_IS_DENSE(cx, obj) ||                      \
>+                               OBJ_GET_CLASS(cx, obj) == &js_SlowArrayClass)
..12345678901234567890123456789012345678901234567890123456789012345678901234567890

Looks like \ is in column 80 instead of standard 79 (Emacs still wraps wrongly if there's a non-newline in 80, if memory serves). Also, could make the two macro bodies start on the same column (33) for more readable layout.

>+#if 0
>+struct JSArray {
>+    uint32   length;        /* length as reflected by .length */
>+    uint32   maxIndex;      /* highest index with actual property */
>+    uint32   elementCount;  /* number of set indexed properties */
>+    jsbitmap *indexMap;     /* */
>+    jsval    *fastslots;
>+};
>+
>+typedef struct JSArray JSArray;
>+#endif

Lose this.

>@@ -3981,14 +3981,21 @@ interrupt:
>                 str = JSVAL_TO_STRING(lval);
>                 rval = INT_TO_JSVAL(JSSTRING_LENGTH(str));
>             } else if (!JSVAL_IS_PRIMITIVE(lval) &&
>-                       (obj = JSVAL_TO_OBJECT(lval),
>-                        OBJ_GET_CLASS(cx, obj) == &js_ArrayClass)) {
>+                       (obj = JSVAL_TO_OBJECT(lval), OBJ_IS_ARRAY(cx, obj))) {
>+
>                 /*
>                  * We know that the array is created with only its 'length'
>                  * private data in a fixed slot at JSSLOT_ARRAY_LENGTH. See
>                  * also JSOP_ARRAYPUSH, far below.
>                  */
>-                rval = obj->fslots[JSSLOT_ARRAY_LENGTH];
>+                i = obj->fslots[JSSLOT_ARRAY_LENGTH];
>+                if (i <= JSVAL_INT_MAX) {

Fails if length is > 2^31 - 1 -- i will be negative but won't fit in an int jsval. Need a jsuint length block-local here.

>@@ -6384,9 +6391,8 @@ interrupt:
>              * of the comprehension have added the only properties directly in
>              * the array object.
>              */
>-            lval = obj->fslots[JSSLOT_ARRAY_LENGTH];
>-            JS_ASSERT(JSVAL_IS_INT(lval));
>-            i = JSVAL_TO_INT(lval);
>+            i = obj->fslots[JSSLOT_ARRAY_LENGTH];
>+            lval = INT_TO_JSVAL(i);

Don't need to set lval here. Don't need jsuint length either, i is safe.

>             if (i == ARRAY_INIT_LIMIT) {
>                 JS_ReportErrorNumberUC(cx, js_GetErrorMessage, NULL,
>                                        JSMSG_ARRAY_INIT_TOO_BIG);
>diff -Npru js-arrays.58afda732578/jsiter.c js-arrays/jsiter.c
>--- js-arrays.58afda732578/jsiter.c	2008-02-11 02:22:44.000000000 -0500
>+++ js-arrays/jsiter.c	2008-02-11 02:22:44.000000000 -0500
>@@ -324,7 +324,7 @@ js_GetNativeIteratorFlags(JSContext *cx,
> 
> /*
>  * Call ToObject(v).__iterator__(keyonly) if ToObject(v).__iterator__ exists.
>- * Otherwise construct the defualt iterator.
>+ * Otherwise construct the default iterator.
>  */
> JS_FRIEND_API(JSBool)
> js_ValueToIterator(JSContext *cx, uintN flags, jsval *vp)
>diff -Npru js-arrays.58afda732578/jsobj.c js-arrays/jsobj.c
>--- js-arrays.58afda732578/jsobj.c	2008-02-11 02:22:44.000000000 -0500
>+++ js-arrays/jsobj.c	2008-02-11 02:22:44.000000000 -0500
>@@ -4109,8 +4109,10 @@ js_Enumerate(JSContext *cx, JSObject *ob
>     rt = cx->runtime;
>     clasp = OBJ_GET_CLASS(cx, obj);
>     enumerate = clasp->enumerate;
>-    if (clasp->flags & JSCLASS_NEW_ENUMERATE)
>+    if (clasp->flags & JSCLASS_NEW_ENUMERATE) {
>+        JS_ASSERT(enumerate != JS_EnumerateStub);
>         return ((JSNewEnumerateOp) enumerate)(cx, obj, enum_op, statep, idp);
>+    }
> 
>     switch (enum_op) {
>       case JSENUMERATE_INIT:
>@@ -4822,8 +4824,8 @@ js_DumpScopeMeters(JSRuntime *rt)
> #endif
> 
> #ifdef DEBUG
>-static void
>-PrintObjectSlotName(JSTracer *trc, char *buf, size_t bufsize)
>+void
>+js_PrintObjectSlotName(JSTracer *trc, char *buf, size_t bufsize)
> {
>     JSObject *obj;
>     uint32 slot;
>@@ -4834,7 +4836,7 @@ PrintObjectSlotName(JSTracer *trc, char 
>     uint32 key;
>     const char *slotname;
> 
>-    JS_ASSERT(trc->debugPrinter == PrintObjectSlotName);
>+    JS_ASSERT(trc->debugPrinter == js_PrintObjectSlotName);
>     obj = (JSObject *)trc->debugPrintArg;
>     slot = (uint32)trc->debugPrintIndex;
> 
>@@ -4983,7 +4985,7 @@ js_TraceObject(JSTracer *trc, JSObject *
>     for (i = 0; i != nslots; ++i) {
>         v = STOBJ_GET_SLOT(obj, i);
>         if (JSVAL_IS_TRACEABLE(v)) {
>-            JS_SET_TRACING_DETAILS(trc, PrintObjectSlotName, obj, i);
>+            JS_SET_TRACING_DETAILS(trc, js_PrintObjectSlotName, obj, i);
>             JS_CallTracer(trc, JSVAL_TO_TRACEABLE(v), JSVAL_TRACE_KIND(v));
>         }
>     }
>diff -Npru js-arrays.58afda732578/jsobj.h js-arrays/jsobj.h
>--- js-arrays.58afda732578/jsobj.h	2008-02-11 02:22:44.000000000 -0500
>+++ js-arrays/jsobj.h	2008-02-11 02:22:44.000000000 -0500
>@@ -637,6 +637,9 @@ extern void
> js_TraceObject(JSTracer *trc, JSObject *obj);
> 
> extern void
>+js_PrintObjectSlotName(JSTracer *trc, char *buf, size_t bufsize);
>+
>+extern void
> js_Clear(JSContext *cx, JSObject *obj);
> 
> extern jsval
>diff -Npru js-arrays.58afda732578/jsregexp.c js-arrays/jsregexp.c
>--- js-arrays.58afda732578/jsregexp.c	2008-02-11 02:22:44.000000000 -0500
>+++ js-arrays/jsregexp.c	2008-02-11 02:22:44.000000000 -0500
>@@ -3434,7 +3434,7 @@ js_ExecuteRegExp(JSContext *cx, JSRegExp
>          * matches, an index property telling the length of the left context,
>          * and an input property referring to the input string.
>          */
>-        obj = js_NewArrayObject(cx, 0, NULL);
>+        obj = js_NewSlowArrayObject(cx);
>         if (!obj) {
>             ok = JS_FALSE;
>             goto out;
>diff -Npru js-arrays.58afda732578/jsstr.c js-arrays/jsstr.c
>--- js-arrays.58afda732578/jsstr.c	2008-02-11 02:22:44.000000000 -0500
>+++ js-arrays/jsstr.c	2008-02-11 02:22:45.000000000 -0500
>@@ -804,7 +804,7 @@ str_toLocaleUpperCase(JSContext *cx, uin
> 
>     /*
>      * Forcefully ignore the first (or any) argument and return toUpperCase(),
>-     * ECMA has reserved that argument, presumbaly for defining the locale.
>+     * ECMA has reserved that argument, presumably for defining the locale.
>      */
>     if (cx->localeCallbacks && cx->localeCallbacks->localeToUpperCase) {
>         str = js_ValueToString(cx, vp[1]);
>@@ -1277,7 +1277,7 @@ match_glob(JSContext *cx, jsint count, G
>     if (!matchstr)
>         return JS_FALSE;
>     v = STRING_TO_JSVAL(matchstr);
>-    return js_SetProperty(cx, arrayobj, INT_TO_JSID(count), &v);
>+    return JS_SetElement(cx, arrayobj, count, &v);

I would just bypass the thin JS API layer and call OBJ_SET_PROPERTY(cx, arrayobj, INT_TO_JSID(count), &v) here. Old code, might need an assertion that count fits in an int jsval.

/be

Comment 45

[Brendan Eich [:brendan]]

> hidden boolean value, but these are false boolean values.

"fake boolean values", better -- or "lying boolean values" (pseudo- etymology: Greek, from pseudēs, false, from pseudein, to lie.)

/be

Comment 46

[Brendan Eich [:brendan]]

(Apologies for the failure to trim the patch there at the end of comment 44!)

Comment 47

[Brendan Eich [:brendan]]

Comment on attachment 302538 [details] [diff] [review]
WIP 20: fixed array_push

>+/* FIXME: use same logic as in jsobj.c:ReallocSlots? */

Cite followup bug or remove this now.

>+static JSBool
>+ResizeSlots(JSContext *cx, JSObject *obj, uint32 oldlen, uint32 len)
>+{
>+    jsval *slots, *newslots;
>+    
>+    if (len == 0) {
>+        if (obj->dslots) {
>+            JS_free(cx, obj->dslots - 1);
>+            obj->dslots = NULL;
>+        }
>+        return JS_TRUE;
>+    } 
>+
>+    if (len > ~(uint32)0 / sizeof(jsval)) /* realloc overflow? */
>+        return JS_FALSE;

Bug: need JS_ReportOutOfMemory(cx); before false return

Nit: the "realloc overflow?" comment doesn't do much for me.

/be

Comment 48

[Brendan Eich [:brendan]]

Forgot to say how nice the patch reads -- the object op entry points that deal with dense arrays, casting out length and proto-property cases early, then doing the fast thing, truly rock.

/be

Comment 49

[Mike Shaver (:shaver emeritus)]

Attachment: 21: it can drink in california, can it pass review?

Brendan's review comments (mostly) addressed, plus chunking ResizeSlots calls to grow by 8 (the realloc was showing up in some places, sayrer threatened to cane me again).

Comment 50

[Mike Shaver (:shaver emeritus)]

Attachment: 22: missed one of brendan's review comments

> >-OPTIMIZER  = -g
> >+OPTIMIZER  = -g3
> 
> For everyone? Haven't tried it myself yet.

Could do -- it's much better for debugging the monkey, though it does bloat
object size a fair bit.

> >+static JSBool
> >+slowarray_addProperty(JSContext *cx, JSObject *obj, jsid id, jsval *vp)
> 
> slow_array_ to match slow_array_push? Or the other way around: slowarray_push.

slow_array_push means "array_push, but slow"; slowarray_* means "op for slow
arrays".  I renamed slow_array_push to array_push_slowly.

> >+        nobj = js_NewArrayObject(cx, ARRAY_DENSELEN(aobj), aobj->dslots);
> >+        if (!nobj)
> >+            return JS_FALSE;
> >+        ARRAY_SET_LENGTH(nobj, ARRAY_LENGTH(aobj));
> >+        *vp = OBJECT_TO_JSVAL(nobj);
> 
> Adjust argv and argc here to avoid copying aobj's elements again.

Yep, and early-out if there were no args.

> (I deleted - lines.) Could adjust loop to make if condition loop invariant,
> invert it to be outside the loop, for faster iteration up to
> ARRAY_DENSELEN(obj) -- which could be < length?

I looked at that, but I ended up duplicating a bunch of the conversion logic in the dense loop case.  We should go over the natives after this lands and see what sort of damage we can do to sort and join and friends.

Comment 51

[Mike Shaver (:shaver emeritus)]

Attachment: 23: trivial conflict resolution

I can't wait to see the back of this patch.

Comment 52

[Brendan Eich [:brendan]]

Comment on attachment 303360 [details] [diff] [review]
23: trivial conflict resolution

EnsureLength: if (len > oldlen) consequent is multiline -- brace it.

But on a more substantive note, doesn't ARRAY_GROWBY break dense length
reckoning? ResizeSlots does

+    ARRAY_SET_DENSELEN(obj, len);

Argh, your JSObjectOps got switched to jsval id from jsid id! Should be jsid id.
Similarly, lastIndex in slowarray_enumerate should be a jsid, not a jsval, set
by INT_TO_JSID(...).

Nit: if (argc-- == 0) in array_concat makes my skin crawl, must be my anti-unsigned-wrap-under-0 spider sense. Put the -- with the argv++, after the if?

This is a style foul:

+                jsuint length;
                 /*

Blank line before comment taking one or more lines, unless preceding char is a
left brace.

Wha? It's a single-bit flag, no need for == itself to make a boolean, just !!.

+    reuseSlot = (flags & SPROP_REUSE_SLOT) == SPROP_REUSE_SLOT;

But you should avoid adding a new unstored SPROP_* flag and just take any slot not equal to SPROP_INVALID_SLOT as the slot to use. That loses the overwriting
assertion, but it simplifies the internal js_AddScopeProperty API.  Do not want 
 SPROP_FLAG_MASK.

Comment 53

[Mike Shaver (:shaver emeritus)]

(In reply to comment #52)
> But on a more substantive note, doesn't ARRAY_GROWBY break dense length
> reckoning? ResizeSlots does
> 
> +    ARRAY_SET_DENSELEN(obj, len);

That's true, per your IRC illumination, but harmless other than needing an update to the header's definiton of DENSELEN.  The overallocation here is identical to the case in which we were genuinely setting the index of the new len, and then subsequently deleted the excess properties.

Proving that to myself did uncover a bug in getProperty, though: we need to look through holes to the prototype's properties!

New patch in a jiffy.

Comment 54

[Mike Shaver (:shaver emeritus)]

Attachment: 24: good to go?

Comment 55

[Mike Shaver (:shaver emeritus)]

Attachment: 23-24 interdiff, 23 on left for gramps

Comment 56

[Brendan Eich [:brendan]]

Comment on attachment 303413 [details] [diff] [review]
24: good to go?

>+ *  - the number of slots allocated to dslots (DENSELEN), in dslots[-1] if
>+ *    dslots is non-NULL.

"the net number of slots starting at dslots" or something like that seems better. "the number of slots allocated to dslots" suggests gross length of the dslots vector, not net.

Argh, you still have jsval id for array_[gs]etProperty!

/be

Comment 57

[Brendan Eich [:brendan]]

Shaver has standing r+a rights for the fixed patch. Go strong, beware jsval not jsid dependencies inside array_[gs]etProperty!

/be

Comment 58

[Mike Shaver (:shaver emeritus)]

Curse you, JSPropertyIdOp and JSPropertyOp!

diff -r 7764cf546433 -r 9e6d488f4f15 jsarray.c
--- a/jsarray.c Thu Feb 14 19:36:27 2008 -0500
+++ b/jsarray.c Thu Feb 14 20:03:10 2008 -0500
@@ -49,7 +49,7 @@
  * We track these pieces of metadata for arrays in dense mode:
  *  - the array's length property as a uint32, in JSSLOT_ARRAY_LENGTH,
  *  - the number of indices that are filled (non-holes), in JSSLOT_ARRAY_COUNT,
- *  - the number of slots allocated to dslots (DENSELEN), in dslots[-1] if
+ *  - the net number of slots starting at dslots (DENSELEN), in dslots[-1] if
  *    dslots is non-NULL.
  * 
  * In dense mode, holes in the array are represented by JSVAL_HOLE.  The final
@@ -687,7 +687,7 @@ array_dropProperty(JSContext *cx, JSObje
 }
 
 static JSBool
-array_getProperty(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
+array_getProperty(JSContext *cx, JSObject *obj, jsid id, jsval *vp)
 {
     uint32 i;
 
@@ -755,7 +755,7 @@ slowarray_getObjectOps(JSContext *cx, JS
 }
 
 static JSBool
-array_setProperty(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
+array_setProperty(JSContext *cx, JSObject *obj, jsid id, jsval *vp)
 {
     uint32 i;

Comment 59

[Mike Shaver (:shaver emeritus)]

Attachment: posterity

Checking in config.mk;
/cvsroot/mozilla/js/src/config.mk,v  <--  config.mk
new revision: 3.21; previous revision: 3.20
done
Checking in js.c;
/cvsroot/mozilla/js/src/js.c,v  <--  js.c
new revision: 3.193; previous revision: 3.192
done
Checking in js.msg;
/cvsroot/mozilla/js/src/js.msg,v  <--  js.msg
new revision: 3.85; previous revision: 3.84
done
Checking in jsapi.c;
/cvsroot/mozilla/js/src/jsapi.c,v  <--  jsapi.c
new revision: 3.410; previous revision: 3.409
done
Checking in jsarray.c;
/cvsroot/mozilla/js/src/jsarray.c,v  <--  jsarray.c
new revision: 3.152; previous revision: 3.151
done
Checking in jsarray.h;
/cvsroot/mozilla/js/src/jsarray.h,v  <--  jsarray.h
new revision: 3.19; previous revision: 3.18
done
Checking in jsinterp.c;
/cvsroot/mozilla/js/src/jsinterp.c,v  <--  jsinterp.c
new revision: 3.424; previous revision: 3.423
done
Checking in jsiter.c;
/cvsroot/mozilla/js/src/jsiter.c,v  <--  jsiter.c
new revision: 3.87; previous revision: 3.86
done
Checking in jsobj.c;
/cvsroot/mozilla/js/src/jsobj.c,v  <--  jsobj.c
new revision: 3.430; previous revision: 3.429
done
Checking in jsobj.h;
/cvsroot/mozilla/js/src/jsobj.h,v  <--  jsobj.h
new revision: 3.87; previous revision: 3.86
done
Checking in jsregexp.c;
/cvsroot/mozilla/js/src/jsregexp.c,v  <--  jsregexp.c
new revision: 3.184; previous revision: 3.183
done
Checking in jsscope.c;
/cvsroot/mozilla/js/src/jsscope.c,v  <--  jsscope.c
new revision: 3.80; previous revision: 3.79
done
Checking in jsstr.c;
/cvsroot/mozilla/js/src/jsstr.c,v  <--  jsstr.c
new revision: 3.190; previous revision: 3.189
done

Comment 60

[Mike Shaver (:shaver emeritus)]

FIXED, baby.

Comment 61

[:Gavin Sharp [email: [e-mail]]]

I had to back this out due to several unit test failures: http://tinderbox.mozilla.org/showlog.cgi?log=Firefox/1203038849.1203040309.32336.gz&fulltext=1 (jQuery, Scriptaculous).

Comment 62

[Bob Clary [:bc] (inactive)]

Also <http://tinderbox.mozilla.org/showlog.cgi?log=MozillaTest/1203038947.1203041848.3572.gz&fulltext=1>

shell failed to build on mac w/
cc -dynamiclib  -framework System -o Darwin_DBG.OBJ/libjs.dylib Darwin_DBG.OBJ/jsapi.o Darwin_DBG.OBJ/jsarena.o Darwin_DBG.OBJ/jsarray.o Darwin_DBG.OBJ/jsatom.o Darwin_DBG.OBJ/jsbool.o Darwin_DBG.OBJ/jscntxt.o Darwin_DBG.OBJ/jsdate.o Darwin_DBG.OBJ/jsdbgapi.o Darwin_DBG.OBJ/jsdhash.o Darwin_DBG.OBJ/jsdtoa.o Darwin_DBG.OBJ/jsemit.o Darwin_DBG.OBJ/jsexn.o Darwin_DBG.OBJ/jsfun.o Darwin_DBG.OBJ/jsgc.o Darwin_DBG.OBJ/jshash.o Darwin_DBG.OBJ/jsinterp.o Darwin_DBG.OBJ/jsiter.o Darwin_DBG.OBJ/jslock.o Darwin_DBG.OBJ/jslog2.o Darwin_DBG.OBJ/jslong.o Darwin_DBG.OBJ/jsmath.o Darwin_DBG.OBJ/jsnum.o Darwin_DBG.OBJ/jsobj.o Darwin_DBG.OBJ/jsopcode.o Darwin_DBG.OBJ/jsparse.o Darwin_DBG.OBJ/jsprf.o Darwin_DBG.OBJ/jsregexp.o Darwin_DBG.OBJ/jsscan.o Darwin_DBG.OBJ/jsscope.o Darwin_DBG.OBJ/jsscript.o Darwin_DBG.OBJ/jsstr.o Darwin_DBG.OBJ/jsutil.o Darwin_DBG.OBJ/jsxdrapi.o Darwin_DBG.OBJ/jsxml.o Darwin_DBG.OBJ/prmjtime.o   
ld: common symbols not allowed with MH_DYLIB output format with the -multi_module option
Darwin_DBG.OBJ/jsarray.o definition of common _js_SlowArrayObjectOps (size 96)
/usr/bin/libtool: internal link edit command failed

Comment 63

[Robert Sayre]

Also failed an xpcshell test:

../../../../_tests/xpcshell-simple/test_toolkit_contentprefs/unit/test_contentPrefs.js: FAIL

Comment 64

[Mike Shaver (:shaver emeritus)]

Thanks, Gavin.  Looking now.

bc: I have no idea what that means, but I build this on Mac in several configs all the time, so I sure am surprised!

Comment 65

[Bob Clary [:bc] (inactive)]

shaver: me neither, but it went back to building as soon as this was backed out. Its an older 10.4 ppc box though, if that helps.

Comment 66

[Mike Shaver (:shaver emeritus)]

contentPrefs at least was a bug in array_concat I addressed during the review cycle, and after which I didn't re-run sufficient suites.  Chastened am I; testing the updated patch via mochi and make check and then I'll attach!

Comment 67

[Mike Shaver (:shaver emeritus)]

Attachment: postering _plus_ passing the test suites

Interdiff:

@@ -2270,23 +2270,25 @@ array_concat(JSContext *cx, uintN argc, 
         nobj = js_NewArrayObject(cx, ARRAY_DENSELEN(aobj), aobj->dslots);
         if (!nobj)
             return JS_FALSE;
-        ARRAY_SET_LENGTH(nobj, ARRAY_LENGTH(aobj));
+        length = ARRAY_LENGTH(aobj);
+        ARRAY_SET_LENGTH(nobj, length);
         *vp = OBJECT_TO_JSVAL(nobj);
-        if (argc-- == 0)
+        if (argc == 0)
             return JS_TRUE;
+        argc--;
         argv++;
     } else {
         nobj = js_NewArrayObject(cx, 0, NULL);
         if (!nobj)
             return JS_FALSE;
         *vp = OBJECT_TO_JSVAL(nobj);
+        length = 0;
     }
 
     /* After this, control must flow through label out: to exit. */
     JS_PUSH_SINGLE_TEMP_ROOT(cx, JSVAL_NULL, &tvr);
 
     /* Loop over [0, argc] to concat args into nobj, expanding all Arrays. */
-    length = 0;
     for (i = 0; i <= argc; i++) {
         ok = JS_CHECK_OPERATION_LIMIT(cx, JSOW_JUMP);
         if (!ok)

Comment 68

[Mike Shaver (:shaver emeritus)]

Comment on attachment 303486 [details] [diff] [review]
postering _plus_ passing the test suites

There's another bug I'm tripping in the suite, working it.

Comment 69

[Mike Shaver (:shaver emeritus)]

Attachment: 27: restore JS_INITIAL_NSLOTS bias in MakeArraySlow

Additive interdiff:

@@ -1049,7 +1049,7 @@ MakeArraySlow(JSContext *cx, JSObject *o
     length = ARRAY_DENSELEN(obj);
     if (length) {
         map->freeslot = STOBJ_NSLOTS(obj) + JS_INITIAL_NSLOTS;
-        obj->dslots[-1] = length;
+        obj->dslots[-1] = length + JS_INITIAL_NSLOTS;
     } else {
         map->freeslot = STOBJ_NSLOTS(obj);
     }

Comment 70

[Brendan Eich [:brendan]]

Comment on attachment 303493 [details] [diff] [review]
27: restore JS_INITIAL_NSLOTS bias in MakeArraySlow

Nit/suggestion: reorder + terms in

+        obj->dslots[-1] = length + JS_INITIAL_NSLOTS;

so JS_INITIAL_NSLOTS is on the left -- mimic storage order.

Hope this is "it"!

/be

Comment 71

[Mike Shaver (:shaver emeritus)]

Checking in config.mk;
/cvsroot/mozilla/js/src/config.mk,v  <--  config.mk
new revision: 3.23; previous revision: 3.22
done
Checking in js.c;
/cvsroot/mozilla/js/src/js.c,v  <--  js.c
new revision: 3.195; previous revision: 3.194
done
Checking in js.msg;
/cvsroot/mozilla/js/src/js.msg,v  <--  js.msg
new revision: 3.87; previous revision: 3.86
done
Checking in jsapi.c;
/cvsroot/mozilla/js/src/jsapi.c,v  <--  jsapi.c
new revision: 3.412; previous revision: 3.411
done
Checking in jsarray.c;
/cvsroot/mozilla/js/src/jsarray.c,v  <--  jsarray.c
new revision: 3.154; previous revision: 3.153
done
Checking in jsarray.h;
/cvsroot/mozilla/js/src/jsarray.h,v  <--  jsarray.h
new revision: 3.21; previous revision: 3.20
done
Checking in jsinterp.c;
/cvsroot/mozilla/js/src/jsinterp.c,v  <--  jsinterp.c
new revision: 3.426; previous revision: 3.425
done
Checking in jsiter.c;
/cvsroot/mozilla/js/src/jsiter.c,v  <--  jsiter.c
new revision: 3.89; previous revision: 3.88
done
Checking in jsobj.c;
/cvsroot/mozilla/js/src/jsobj.c,v  <--  jsobj.c
new revision: 3.432; previous revision: 3.431
done
Checking in jsobj.h;
/cvsroot/mozilla/js/src/jsobj.h,v  <--  jsobj.h
new revision: 3.89; previous revision: 3.88
done
Checking in jsregexp.c;
/cvsroot/mozilla/js/src/jsregexp.c,v  <--  jsregexp.c
new revision: 3.186; previous revision: 3.185
done
Checking in jsscope.c;
/cvsroot/mozilla/js/src/jsscope.c,v  <--  jsscope.c
new revision: 3.82; previous revision: 3.81
done
Checking in jsstr.c;
/cvsroot/mozilla/js/src/jsstr.c,v  <--  jsstr.c
new revision: 3.192; previous revision: 3.191
done

Comment 72

[Mike Shaver (:shaver emeritus)]

Attachment: posterity, best yet

Comment 73

[Igor Bukanov]

(In reply to comment #71)
> Checking in config.mk;

A side remark: this was checked in when mochi tests where consistently failing on the tinderbox. Why is the rush?

Comment 74

[Mike Shaver (:shaver emeritus)]

The mochitest orange boxes were stalled, and consensus seemed to be that they would respin and go green on next commit.  So I provided the next commit, as it were, and I'll watch them to see if consensus bears out.

Comment 75

[Mike Shaver (:shaver emeritus)]

Get 6 mochifails on Prototype, backed out again.  On the morrow, as it were.

Comment 76

[Bob Clary [:bc] (inactive)]

fyi for js tests:

mac shell opt/debug: typeof Array.prototype expect object, but got function

ecma/Array/15.4.4.js
ecma/Expressions/11.2.1-1.js
ecma/Expressions/11.2.1-1.js

win shell debug crashes

e4x/GC/regress-339785.js
js1_2/Array/slice.js
js1_2/Array/splice2.js
js1_8/genexps/regress-380237-01.js

Comment 77

[Mike Shaver (:shaver emeritus)]

(In reply to comment #76)
> fyi for js tests:
> 
> mac shell opt/debug: typeof Array.prototype expect object, but got function
> 
> ecma/Array/15.4.4.js
> ecma/Expressions/11.2.1-1.js
> ecma/Expressions/11.2.1-1.js

Yep, that's the bug for which I will attach a patch presently.

> win shell debug crashes
> 
> e4x/GC/regress-339785.js
> js1_2/Array/slice.js
> js1_2/Array/splice2.js
> js1_8/genexps/regress-380237-01.js

I can't reproduce any of these crashes on Mac.  Does the shell get clobbered before rebuilding?  Is there a way to get stacks with the patch I'm about to attach?

Comment 78

[Mike Shaver (:shaver emeritus)]

Attachment: 29: with fix for typeof(slowArray) == "function" badness

This mochis well, though I got bit by the screen saver coming on in the middle, which I think made the form-autocomplete tests bail.  They retested clean, though.

Comment 79

[Bob Clary [:bc] (inactive)]

(In reply to comment #77)

Yes. clobbered each time. I can try to do it on one of the buildbot slaves.

Comment 80

[Bob Clary [:bc] (inactive)]

shaver, how do i apply this hg patch to a cvs tree?

Comment 81

[Mike Shaver (:shaver emeritus)]

patch -p1 in js/src should work.

Comment 82

[Bob Clary [:bc] (inactive)]

Attachment: stack for e4x/GC/regress-339785.js win debug shell

Comment 83

[Mike Shaver (:shaver emeritus)]

Those crashes are 417981, which valgrind found instantly.

Comment 84

[Mike Shaver (:shaver emeritus)]

Attachment: 31: track trunk

Updated and resolved a few conflicts, mostly due to bug 417893's commit.  Testing now on top of brendan's fix for bug 417981.

Comment 85

[Mike Shaver (:shaver emeritus)]

Comment on attachment 304029 [details] [diff] [review]
31: track trunk

Interdiff since last-reviewed patch:
* make js_SlowArrayObjectObs static to avoid Mac PPC BSS pain
* reorder math in MakeArraySlow to match allocation order
* make sure slow arrays aren't callable!

diff -r 088b510c791c -r 42941b6e78df jsarray.c
--- a/jsarray.c	Fri Feb 15 04:30:10 2008 -0500
+++ b/jsarray.c	Fri Feb 15 09:35:52 2008 -0500
@@ -746,7 +746,7 @@ slowarray_trace(JSTracer *trc, JSObject 
     STOBJ_SET_SLOT(obj, JSSLOT_ARRAY_LENGTH, length);
 }
 
-JSObjectOps js_SlowArrayObjectOps;
+static JSObjectOps js_SlowArrayObjectOps;
 
 static JSObjectOps *
 slowarray_getObjectOps(JSContext *cx, JSClass *clasp)
@@ -1049,7 +1049,7 @@ MakeArraySlow(JSContext *cx, JSObject *o
     length = ARRAY_DENSELEN(obj);
     if (length) {
         map->freeslot = STOBJ_NSLOTS(obj) + JS_INITIAL_NSLOTS;
-        obj->dslots[-1] = length + JS_INITIAL_NSLOTS;
+        obj->dslots[-1] = JS_INITIAL_NSLOTS + length;
     } else {
         map->freeslot = STOBJ_NSLOTS(obj);
     }
@@ -2823,6 +2823,7 @@ js_InitArrayClass(JSContext *cx, JSObjec
     memcpy(&js_SlowArrayObjectOps, &js_ObjectOps, sizeof(JSObjectOps));
     js_SlowArrayObjectOps.trace = slowarray_trace;
     js_SlowArrayObjectOps.enumerate = slowarray_enumerate;
+    js_SlowArrayObjectOps.call = NULL;
 
     proto = JS_InitClass(cx, obj, NULL, &js_ArrayClass, Array, 1,
                          array_props, array_methods, NULL, NULL);

Comment 86

[Brendan Eich [:brendan]]

Comment on attachment 304029 [details] [diff] [review]
31: track trunk

>@@ -1380,7 +1998,31 @@ array_pop(JSContext *cx, uintN argc, jsv
>     JSBool hole;
> 
>     obj = JS_THIS_OBJECT(cx, vp);
>-    if (!obj || !js_GetLengthProperty(cx, obj, &index))
>+	if (!obj)
>+        return JS_FALSE;

Indentation's off there.

r/a=me with that fixed.

/be

Comment 87

[Mike Shaver (:shaver emeritus)]

That's what I get for using the tab-happy FileMerge to resolve my conflicts, thanks.

Checking in config.mk;
/cvsroot/mozilla/js/src/config.mk,v  <--  config.mk
new revision: 3.25; previous revision: 3.24
done
Checking in js.c;
/cvsroot/mozilla/js/src/js.c,v  <--  js.c
new revision: 3.198; previous revision: 3.197
done
Checking in js.msg;
/cvsroot/mozilla/js/src/js.msg,v  <--  js.msg
new revision: 3.89; previous revision: 3.88
done
Checking in jsapi.c;
/cvsroot/mozilla/js/src/jsapi.c,v  <--  jsapi.c
new revision: 3.417; previous revision: 3.416
done
Checking in jsarray.c;
/cvsroot/mozilla/js/src/jsarray.c,v  <--  jsarray.c
new revision: 3.157; previous revision: 3.156
done
Checking in jsarray.h;
/cvsroot/mozilla/js/src/jsarray.h,v  <--  jsarray.h
new revision: 3.23; previous revision: 3.22
done
Checking in jsinterp.c;
/cvsroot/mozilla/js/src/jsinterp.c,v  <--  jsinterp.c
new revision: 3.432; previous revision: 3.431
done
Checking in jsiter.c;
/cvsroot/mozilla/js/src/jsiter.c,v  <--  jsiter.c
new revision: 3.92; previous revision: 3.91
done
Checking in jsobj.c;
/cvsroot/mozilla/js/src/jsobj.c,v  <--  jsobj.c
new revision: 3.437; previous revision: 3.436
done
Checking in jsobj.h;
/cvsroot/mozilla/js/src/jsobj.h,v  <--  jsobj.h
new revision: 3.92; previous revision: 3.91
done
Checking in jsregexp.c;
/cvsroot/mozilla/js/src/jsregexp.c,v  <--  jsregexp.c
new revision: 3.189; previous revision: 3.188
done
Checking in jsscope.c;
/cvsroot/mozilla/js/src/jsscope.c,v  <--  jsscope.c
new revision: 3.84; previous revision: 3.83
done
Checking in jsstr.c;
/cvsroot/mozilla/js/src/jsstr.c,v  <--  jsstr.c
new revision: 3.195; previous revision: 3.194
done

Comment 88

[Igor Bukanov]

The check in broke the following tests when run on Linux with a debug build of js shell:

js1_5/extensions/regress-311792-02.js
js1_5/extensions/regress-355497.js   
js1_5/extensions/regress-311792-01.js
js1_5/extensions/regress-365692.js   
js1_5/extensions/regress-315509-02.js
js1_6/extensions/regress-414098.js

Comment 89

[Mike Shaver (:shaver emeritus)]

Failures are filed as bug 418314.