javascript - Firefox JavaScript 算法性能异常

Question

请在 firefox 上运行此测试。

http://jsperf.com/static-arithmetic

您如何解释结果？

这个

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

执行速度比

快得多

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

为什么？

Answer 1

首先，你的测试有点缺陷。

你应该比较以下内容:

• b = a + 8 - 2; 对比 b = a + 6

• b = a + 8 + 2; 对比 b = a + 10

• b = a + 8/2; 对比 b = a + 4

• b = a + 8 * 2; 对比 b = a + 16

您会注意到一些有趣的事情:只有第二对项中有+ 或- 的问题速度较慢(除法和乘法很好)。加/减和乘/除的实现必须有明显的区别。确实有:

那么让我们看看加法和乘法 (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;
    }

但是，正如我们所知，这里并没有太大的区别。两者都以类似的方式实现，并且都调用 newBinaryOrAppend()..那么这个函数到底是什么？

(剧透:它的同名可能会泄露为什么加法/减法的成本更高。再次查看 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;
}

鉴于上述情况，尤其是常量折叠:

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;
}

并在制定问题时考虑到这一点

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

...问题完全消失了(尽管由于我们正在调用静态方法，它显然要慢得多)，我很想相信常量折叠被破坏了(这似乎不太可能，因为括号折叠出现了正常工作)，Spidermonkey 没有将数字文字(或数字表达式，即 b = a + ( 7 + 2 ))分类为 TOK_NUMBER(至少在第一解析级别)，这也不太可能，或者我们递归地下降到某个地方太深了。

我没有使用过 Spidermonkey 代码库，但我的 Spidey 感觉告诉我我们迷路了，我感觉它在 RecycleTree() 中。