556165 - dead code in array_shift()

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Nicholas Nethercote [inactive]]

array_shift() has this code:

    if (length == 0) {
        *vp = JSVAL_VOID;
    } else {
        length--;

        if (obj->isDenseArray() && !js_PrototypeHasIndexedProperties(cx, obj) &&
            length < js_DenseArrayCapacity(obj)) {
            if (JS_LIKELY(obj->dslots != NULL)) {
                *vp = obj->getDenseArrayElem(0);
                if (*vp == JSVAL_HOLE)
                    *vp = JSVAL_VOID;
                else
                    obj->fslots[JSSLOT_ARRAY_COUNT]--;
                memmove(obj->dslots, obj->dslots + 1, length * sizeof(jsval));
                obj->setDenseArrayElem(length, JSVAL_HOLE);
            } else {
                // !! never reached !!
                /*
                 * We don't need to modify the indexed properties of an empty array
                 * with an explicitly set non-zero length when shift() is called on
                 * it, but note fallthrough to reduce the length by one.
                 */
                JS_ASSERT(obj->fslots[JSSLOT_ARRAY_COUNT] == 0);
                *vp = JSVAL_VOID;
            }

The line marked "!! never reached !!" is never reached.  Why not?  For it to be
reached, obj->dslots must be NULL.  But 'length' is unsigned, as is
'js_DenseArrayCapacity(obj)', so for the JS_LIKELY test to be hit
js_DenseArrayCapacity() must be at least 1.  And if it's at least 1, then
dslots cannot be NULL.

Just to check, I tried putting a JS_ASSERT(0) in the "never reached" part
just to check, and couldn't trigger it with the js regtests.

One option is to just remove the dead code, but I suspect that the "if
(obj->isDenseArray()...)" condition might not quite be right.  However, the
comment in the never reached part also seems not quite right, particularly
the "fallthrough" bit.

Comment 1

[Jeff Walden [:Waldo]]

Removing the dead code looks correct to me.  (I'm not quite sure, at a glance, what I was originally thinking when I wrote the code, but I believe the comment responds to a reader's question of why no memmove is necessary.)  Our steps are:

* get the value to return
* update the values in the array
* update array count
* decrement array length

The value to return is the zeroth value unless it's a hole, where we censor to JSVAL_VOID.  Since we always have dslots, and we have at least length many by the < test, the memmove performs that step correctly.  The array count update is correct as long as we shifted off a non-hole -- and the condition guards that.  It can't underflow because, to underflow, the zeroth element must be a hole -- but then we don't hit that decrement.  Finally, the array length decrement is handled by decrementing length (can't underflow, length == 0 is handled separately) and then setting that as the new length.

Beyond removing the dead code, since we know we have a dense array here, we could (I think *should*) inline and specialize js_SetLengthProperty for dense arrays:

  obj->fslots[JSSLOT_ARRAY_LENGTH] = length;

This also has the slight benefit of reducing indentation within the method.  Feel like coding up these changes?

Comment 2

[Nicholas Nethercote [inactive]]

(In reply to comment #1)
> 
> Beyond removing the dead code, since we know we have a dense array here, we
> could (I think *should*) inline and specialize js_SetLengthProperty for dense
> arrays:
> 
>   obj->fslots[JSSLOT_ARRAY_LENGTH] = length;

You sure?  The js_SetLengthProperty() call is at a point where we aren't guaranteed to have a dense array, AFAICT.

> This also has the slight benefit of reducing indentation within the method. 
> Feel like coding up these changes?

Not really -- I don't agree/understand them, and I don't have a good feel for the function and all the different cases.  I'd be happy to review a patch, though :)

Comment 3

[Nicholas Nethercote [inactive]]

Attachment: patch

But here's a patch that just removes the dead code, in case you're happy with just that.

Comment 4

[Jeff Walden [:Waldo]]

(In reply to comment #2)
> You sure?  The js_SetLengthProperty() call is at a point where we aren't
> guaranteed to have a dense array, AFAICT.

Oh, sorry, lack of precision: insert that assignment in the is-dense-and-speedy case and return immediately after, so that the call at the end is used only in the slow case.


> Not really -- I don't agree/understand them, and I don't have a good feel for
> the function and all the different cases.  I'd be happy to review a patch,
> though :)

Okay, we can tag-team it here.

Comment 5

[Jeff Walden [:Waldo]]

Comment on attachment 437523 [details] [diff] [review]
patch

Looks good, except:

>diff --git a/js/src/jsarray.cpp b/js/src/jsarray.cpp

>+            NanoAssert(obj->dslots != NULL);

Should be JS_ASSERT, we're not in nanojit anymore, Toto.


>+            *vp = obj->dslots[0];
>+            if (*vp == JSVAL_HOLE)
>                 *vp = JSVAL_VOID;
>-            }
>+            else
>+                obj->decArrayCountBy(1);

"decArrayCountBy"?  Yuck!  I should have been paying attention to names in the bug that made this change; "reduce" would have been the better verb.

Comment 6

[Brendan Eich [:brendan]]

"reduce" is abstract, and used for functional folds. Confusion!

I let dec and inc go by because decrease and increase are too long (plus, we are hackers; bonus: DEC homage), but at least these are not overloaded.

/be

Comment 7

[Nicholas Nethercote [inactive]]

Attachment: patch v2

This inlines the length setting in the fast case.  Maybe we should do something similar in the length==0 case, but I couldn't work out what it would look like.

Comment 8

[Jeff Walden [:Waldo]]

Comment on attachment 438020 [details] [diff] [review]
patch v2

(In reply to comment #7)
> Maybe we should do something similar in the length==0 case, but I couldn't
> work out what it would look like.

It'd be easy enough to do with a split on whether obj->isArray() or not -- but on the other hand, shifting off an empty array is a big edge case in my book, and I don't think it pays in terms of code size cost (source or compiled), so I think what's here is also what's most desirable.

Comment 9

[Nicholas Nethercote [inactive]]

http://hg.mozilla.org/tracemonkey/rev/96463282ddd6

Comment 10

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/96463282ddd6