It's been noted on the Wiki...
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.
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?
Logged In: YES
user_id=80530
Anyone tackling such a rewrite
should look into solving
Tcl Bug 906201 at the same time.
Logged In: YES
user_id=80530
Implemented for 8.5a5