Menu

#331 avoid quadratic parsing time

closed-accepted
5
2006-07-05
2004-02-24
Don Porter
No

It's been noted on the Wiki...

http://wiki.tcl.tk/9585

that the runtime of

expr 1[string repeat +1 $N]

is quadratic in $N.

This is due to Tcl_ParseExpr().
After each + is parsed in
ParseAddExpr(), a call is made
to PrependSubExprTokens to
shift the already parsed operands
down the token array to make room
for the operand token at the beginning.

This means that $N times, $n tokens
are copied (as $n grows from 1 to $N)
just to get the parsing done -- quadratic
complexity.

Similar issues arise with other expressions
that call PrependSubExprTokens.

For most short expressions, this penalty
hardly matters, but a more scalable parser
would be nice.

Discussion

  • Don Porter

    Don Porter - 2004-03-08

    Logged In: YES
    user_id=80530

    The conceptually obvious fix would
    be for the expr parser to stop trying to
    fill a linear Tcl_Token array on the
    fly, and instead have the parser build
    an actual parse tree. Then when the
    parse tree is complete, a simple
    traversal can create the Tcl_Token
    array in linear time.

    It's a simple transformation in concept,
    but a fairly substantial rewrite of
    generic/tclParseExpr.c. A nice limited
    project for someone who wants to
    get started hacking the core. Who
    needs a project?

     
  • Don Porter

    Don Porter - 2004-03-09

    Logged In: YES
    user_id=80530

    Anyone tackling such a rewrite
    should look into solving
    Tcl Bug 906201 at the same time.

     
  • Don Porter

    Don Porter - 2006-07-05
    • assigned_to: msofer --> dgp
    • status: open --> closed-accepted
     
  • Don Porter

    Don Porter - 2006-07-05

    Logged In: YES
    user_id=80530

    Implemented for 8.5a5