Closed Bug 322889 (native-arrays) Opened 14 years ago Closed 12 years ago

Array implementation should specialize its own nearly-native JSObjectOps

Categories

(Core :: JavaScript Engine, defect, P2)

defect

Tracking

()

RESOLVED FIXED
mozilla1.9beta4

People

(Reporter: brendan, Assigned: shaver)

References

(Depends on 1 open bug)

Details

(Keywords: perf)

Attachments

(4 files, 31 obsolete files)

119.82 KB, image/png
Details
129.01 KB, image/png
Details
1.04 KB, text/plain
Details
51.45 KB, patch
brendan
: review+
brendan
: approval1.9+
Details | Diff | Splinter Review
See bug 322135 comment 5, bug 101964, bug 171262, bug 253138, and probably others.

/be
Status: NEW → ASSIGNED
Priority: -- → P2
Blocks: 101964
Blocks: 171262
Flags: testcase-
I think mrbkap is on this already.

/be
Assignee: brendan → mrbkap
Status: ASSIGNED → NEW
Blocks: 334935
No longer blocks: 334935
Hey BKap - are you workin on this one?
Flags: blocking1.9?
Duplicate of this bug: 394448
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?
(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!   
Moving to blocker list since we are doing a perf push.   If you disagree let me know ...
Flags: blocking1.9? → blocking1.9+
Assignee: mrbkap → crowder
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.
Attached patch WIP (obsolete) — Splinter Review
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.
Attached patch WIP 2: now with better GC (obsolete) — Splinter Review
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.)
Attachment #295074 - Attachment is obsolete: true
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.
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.
Attachment #295077 - Attachment is obsolete: true
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.
Attachment #295338 - Attachment is obsolete: true
Blocks: 200505
Blocks: 410994
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.
Attachment #295347 - Attachment is obsolete: true
** TOTAL **:           1.129x as fast    4861.9ms +/- 0.4%   4306.1ms +/- 0.2%     significant

Crypto especially liked this work.
(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.
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.
Attachment #296808 - Attachment is obsolete: true
Attachment #296809 - Attachment is obsolete: true
Attachment #297029 - Attachment is patch: false
Attachment #297029 - Attachment mime type: text/plain → image/png
Blocks: 374740
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.
Alias: native-arrays
unshift and sort (in the presence of holes in some positions; likewise for reverse, I should have added) also cause orders to diverge.
Attached patch WIP 7: implement the new model (obsolete) — Splinter Review
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.
Assignee: crowder → shaver
Attachment #296906 - Attachment is obsolete: true
Status: NEW → ASSIGNED
Comment on attachment 297989 [details] [diff] [review]
WIP 8: as before, merged to trunk

Nurr, still learning to drive hg, sorry.
Attachment #297989 - Attachment is obsolete: true
Now vs. current trunk, not my baseline trunk.
Attached patch WIP 9: now with compiling (obsolete) — Splinter Review
A post-test change to add JSOP_HOLE accidentally crept into my rebased diff, tee hee.  This should have 100% fewer compilation errors.
Attachment #297991 - Attachment is obsolete: true
No longer blocks: 260106
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.
Attachment #297995 - Attachment is obsolete: true
- 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.
Attachment #298065 - Attachment is obsolete: true
Attached patch WIP 13: passes all array tests (obsolete) — Splinter Review
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...
Attachment #298247 - Attachment is obsolete: true
Looks like I broke regexps pretty good!  Working on it.
Attached patch WIP 14: fix regexp tests. (obsolete) — Splinter Review
js_SetElement takes a jsid, which is an integer.  JS_SetElement takes an untagged index, which is an integer.  Discuss.
Attachment #298251 - Attachment is obsolete: true
Attached patch WIP 15: pass js/test suite (obsolete) — Splinter Review
We now pass everything in js/test which is passed by the trunk source, as of this moment.
Attachment #298280 - Attachment is obsolete: true
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.
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"
}
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!
Attachment #299317 - Attachment is obsolete: true
Attachment #299796 - Flags: review?
While reviewing with Brendan, I noticed that I had rolled back some constant tuning in the previous patch.
Attachment #299796 - Attachment is obsolete: true
Attachment #299796 - Flags: review?
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
Shaver are we going to try for this for b3 today?
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
Depends on: 408416
Got a patch that applies to the current trunk?
Passes the suite vs older trunk, runs sunspider.
Attachment #299901 - Attachment is obsolete: true
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.
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.
Attachment #302408 - Attachment is obsolete: true
Attachment #302514 - Flags: review?(brendan)
Attached patch WIP 20: fixed array_push (obsolete) — Splinter Review
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);
Attachment #302514 - Attachment is obsolete: true
Attachment #302538 - Flags: review?(brendan)
Attachment #302514 - Flags: review?(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
> 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
(Apologies for the failure to trim the patch there at the end of comment 44!)
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
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
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).
Attachment #302538 - Attachment is obsolete: true
Attachment #303324 - Flags: review?(brendan)
Attachment #302538 - Flags: review?(brendan)
> >-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.
Attachment #303324 - Attachment is obsolete: true
Attachment #303340 - Flags: review?(brendan)
Attachment #303324 - Flags: review?(brendan)
Attached patch 23: trivial conflict resolution (obsolete) — Splinter Review
I can't wait to see the back of this patch.
Attachment #303340 - Attachment is obsolete: true
Attachment #303360 - Flags: review?(brendan)
Attachment #303340 - Flags: review?(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.
(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.
Attached patch 24: good to go? (obsolete) — Splinter Review
Attachment #303360 - Attachment is obsolete: true
Attachment #303413 - Flags: review?(brendan)
Attachment #303360 - Flags: review?(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
Shaver has standing r+a rights for the fixed patch. Go strong, beware jsval not jsid dependencies inside array_[gs]etProperty!

/be
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;
Attached file posterity (obsolete) —
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
Attachment #303413 - Attachment is obsolete: true
Attachment #303414 - Attachment is obsolete: true
Attachment #303422 - Flags: review+
Attachment #303413 - Flags: review?(brendan)
FIXED, baby.
Status: ASSIGNED → RESOLVED
Closed: 12 years ago
Resolution: --- → FIXED
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).
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
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
Target Milestone: mozilla1.9alpha1 → mozilla1.9beta4
Also failed an xpcshell test:

../../../../_tests/xpcshell-simple/test_toolkit_contentprefs/unit/test_contentPrefs.js: FAIL
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!
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.
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!
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)
Attachment #303422 - Attachment is obsolete: true
Attachment #303486 - Flags: review?(brendan)
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.
Attachment #303486 - Attachment is obsolete: true
Attachment #303486 - Flags: review?(brendan)
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);
     }
Attachment #303493 - Flags: review?(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
Attachment #303493 - Flags: review?(brendan)
Attachment #303493 - Flags: review+
Attachment #303493 - Flags: approval1.9+
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
Status: REOPENED → RESOLVED
Closed: 12 years ago12 years ago
Resolution: --- → FIXED
(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?
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.
Get 6 mochifails on Prototype, backed out again.  On the morrow, as it were.
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
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
(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?
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.
Attachment #303493 - Attachment is obsolete: true
Attachment #303496 - Attachment is obsolete: true
Attachment #303533 - Flags: review?(brendan)
(In reply to comment #77)

Yes. clobbered each time. I can try to do it on one of the buildbot slaves.
shaver, how do i apply this hg patch to a cvs tree?
patch -p1 in js/src should work.
Those crashes are 417981, which valgrind found instantly.
Keywords: perf
Attached patch 31: track trunkSplinter Review
Updated and resolved a few conflicts, mostly due to bug 417893's commit.  Testing now on top of brendan's fix for bug 417981.
Attachment #303533 - Attachment is obsolete: true
Attachment #303533 - Flags: review?(brendan)
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);
Attachment #304029 - Flags: review?(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
Attachment #304029 - Flags: review?(brendan)
Attachment #304029 - Flags: review+
Attachment #304029 - Flags: approval1.9+
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
Status: REOPENED → RESOLVED
Closed: 12 years ago12 years ago
Resolution: --- → FIXED
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




Status: RESOLVED → REOPENED
Resolution: FIXED → ---
Depends on: 418314
Failures are filed as bug 418314.
Status: REOPENED → RESOLVED
Closed: 12 years ago12 years ago
No longer depends on: 418314
Resolution: --- → FIXED
Blocks: 419537
No longer blocks: 419537
Depends on: 419537
Depends on: 418737
Depends on: 423342
Depends on: 472619
Depends on: 476447
Depends on: 417501
No longer depends on: 419537
Depends on: 474402
You need to log in before you can comment on or make changes to this bug.