Firefox JavaScript arithmetics performance oddity

Question

Please run this test on firefox.

http://jsperf.com/static-arithmetic

How would you explain the results?

This

b = a + 5*5;
b = a + 6/2;
b = a + 7+1;

executes much faster than

b = a + 25;
b = a + 3;
b = a + 8;

Why?

Answer 1

First of all, your test is slightly flawed.

You should compare the following:

• b = a + 8 - 2; vs b = a + 6

• b = a + 8 + 2; vs b = a + 10

• b = a + 8 / 2; vs b = a + 4

• b = a + 8 * 2; vs b = a + 16

You'll notice something interesting: only problems that have + or - in the second pair of terms are slower (division and multiplication are fine). There must be a clear difference between the implementation of addition/subtraction and multiplication/division. And indeed there is:

So lets look at addition and multiplication (jsparse.cpp):

    JSParseNode *
    Parser::addExpr()
    {
        JSParseNode *pn = mulExpr();
        while (pn &&
               (tokenStream.matchToken(TOK_PLUS) ||
                tokenStream.matchToken(TOK_MINUS))) {
            TokenKind tt = tokenStream.currentToken().type;
            JSOp op = (tt == TOK_PLUS) ? JSOP_ADD : JSOP_SUB;
            pn = JSParseNode::newBinaryOrAppend(tt, op, pn, mulExpr(), tc);
        }
        return pn;
    }

    JSParseNode *
    Parser::mulExpr()
    {
        JSParseNode *pn = unaryExpr();
        while (pn && (tokenStream.matchToken(TOK_STAR) || tokenStream.matchToken(TOK_DIVOP))) {
            TokenKind tt = tokenStream.currentToken().type;
            JSOp op = tokenStream.currentToken().t_op;
            pn = JSParseNode::newBinaryOrAppend(tt, op, pn, unaryExpr(), tc);
        }
        return pn;
    }

But, as we can tell, there isn't a huge difference here. Both are implemented in a similar fashion and both call on newBinaryOrAppend().. so what exactly IS in this function?

(Spoiler: Its namesake may betray why addition/subtraction is more costly. Again, looking at jsparse.cpp)

JSParseNode *
JSParseNode::newBinaryOrAppend(TokenKind tt, JSOp op, JSParseNode *left, JSParseNode *right,
                               JSTreeContext *tc)
{
    JSParseNode *pn, *pn1, *pn2;

    if (!left || !right)
        return NULL;

    /*
     * Flatten a left-associative (left-heavy) tree of a given operator into
     * a list, to reduce js_FoldConstants and js_EmitTree recursion.
     */
    if (PN_TYPE(left) == tt &&
        PN_OP(left) == op &&
        (js_CodeSpec[op].format & JOF_LEFTASSOC)) {
        if (left->pn_arity != PN_LIST) {
            pn1 = left->pn_left, pn2 = left->pn_right;
            left->pn_arity = PN_LIST;
            left->pn_parens = false;
            left->initList(pn1);
            left->append(pn2);
            if (tt == TOK_PLUS) {
                if (pn1->pn_type == TOK_STRING)
                    left->pn_xflags |= PNX_STRCAT;
                else if (pn1->pn_type != TOK_NUMBER)
                    left->pn_xflags |= PNX_CANTFOLD;
                if (pn2->pn_type == TOK_STRING)
                    left->pn_xflags |= PNX_STRCAT;
                else if (pn2->pn_type != TOK_NUMBER)
                    left->pn_xflags |= PNX_CANTFOLD;
            }
        }
        left->append(right);
        left->pn_pos.end = right->pn_pos.end;
        if (tt == TOK_PLUS) {
            if (right->pn_type == TOK_STRING)
                left->pn_xflags |= PNX_STRCAT;
            else if (right->pn_type != TOK_NUMBER)
                left->pn_xflags |= PNX_CANTFOLD;
        }
        return left;
    }

    /*
     * Fold constant addition immediately, to conserve node space and, what's
     * more, so js_FoldConstants never sees mixed addition and concatenation
     * operations with more than one leading non-string operand in a PN_LIST
     * generated for expressions such as 1 + 2 + "pt" (which should evaluate
     * to "3pt", not "12pt").
     */
    if (tt == TOK_PLUS &&
        left->pn_type == TOK_NUMBER &&
        right->pn_type == TOK_NUMBER) {
        left->pn_dval += right->pn_dval;
        left->pn_pos.end = right->pn_pos.end;
        RecycleTree(right, tc);
        return left;
    }

    pn = NewOrRecycledNode(tc);
    if (!pn)
        return NULL;
    pn->init(tt, op, PN_BINARY);
    pn->pn_pos.begin = left->pn_pos.begin;
    pn->pn_pos.end = right->pn_pos.end;
    pn->pn_left = left;
    pn->pn_right = right;
    return (BinaryNode *)pn;
}

Given the above, and in particular the constant folding:

if (tt == TOK_PLUS &&
    left->pn_type == TOK_NUMBER &&
    right->pn_type == TOK_NUMBER) {
    left->pn_dval += right->pn_dval;
    left->pn_pos.end = right->pn_pos.end;
    RecycleTree(right, tc);
    return left;
}

And considering that when formulating the problem like

• b = Number(a) + 7 + 2; vs b = Number(a) + 9;

... the problem disappears altogether (although it's obviously much slower since we're invoking a static method), I'm tempted to believe that either constant folding is broken (which doesn't seem likely since the parenthetical folding appears to work fine), that Spidermonkey isn't categorizing numeric literals (or numeric expressions, i.e. b = a + ( 7 + 2 )) as TOK_NUMBER (at least at the first parsing level), which is also unlikely, or that we're descending somewhere recursively too deep.

I haven't worked with the Spidermonkey codebase, but my Spidey sense is telling me we're getting lost somewhere and I have a feeling it's in RecycleTree().

Answer 2

In Firefox, it looks like it has something to do with floating point math vs. integer math where the floating point is a lot faster. When I add some floating point math, you can see the difference: http://jsperf.com/static-arithmetic/14.

This is a lot faster:

b = a + 26.01;
b = a + 3.1;
b = a + 8.2;

than this:

b = a + 25;
b = a + 3;
b = a + 8;

All I can guess is that Firefox has some floating point optimizations that don't apply to integer math or the code somehow just takes a different path when floating point numbers are involved.

So, extrapolating this info to your original answer, the + 5*5 must be using the faster float path where as the + 25 is not. See the referenced jsPerf for more details.

Once you make everything floats, the + (5.1 * 5.1) option is slower than the + 26.01 option like we would expect.