TclX loop slow in the default case

Hello

I wanted to see how much faster the Tclx loop command was compared to
the ordinary for loop.

When [loop] is used without an explicit increment, it defaults to 1.
I noticed that this default case runs very slowly.

Here is my script:
ed@aleph> cat loop.tcl

# timing "for" and the Tclx "loop"
package require Tclx

proc loop_default {lim} {
loop i 0 $lim {}
}

proc loop_explicit {lim} {
loop i 0 1 $lim {}
}

proc tcl_for {lim} {
for {set i 0} {$i<$lim} {incr i} {}
}

proc run {lim} {
puts "time (us) taken for $lim iterations"
puts "[lindex [time {loop_default $lim}] 0]\t\
<-- TclX 'loop' with default increment"
puts "[lindex [time {loop_explicit $lim}] 0]\t\
<-- TclX 'loop' with explicit increment"
puts "[lindex [time {tcl_for $lim}] 0]\t\ <-- tcl 'for'"
}

if {[info script] eq $argv0 } {
puts "tclsh: [info patchlevel]"
puts "Tclx: [package require Tclx]"
set lim [lindex $argv 0]
run $lim
}
# end ----------------------------------------------------

I tested the script with different values for the iterations/limit 9
times per limit and took the median value. I tested with tcl 8.4 and
8.5.

ed@aleph>
ed@aleph> tclsh8.5 loop.tcl 10 > out.txt
ed@aleph> tclsh8.5 run-tests.tcl 100 >> out.txt
ed@aleph> tclsh8.5 run-tests.tcl 1000 >> out.txt
ed@aleph> tclsh8.5 run-tests.tcl 10000 >> out.txt
ed@aleph> cat out.txt
tclsh: 8.5.3
Tclx: 8.4
time (us) taken for 10 iterations
66 <-- TclX 'loop' with default increment
34 <-- TclX 'loop' with explicit increment
47 <-- tcl 'for'
8.4.18 8.5.3 %chng proc
23 21 -0.02 tcl_for
62 172 1.10 loop_default
7 9 0.02 loop_explicit
8.4.18 8.5.3 %chng proc
200 174 -0.26 tcl_for
561 1605 10.44 loop_default
7 9 0.02 loop_explicit
8.4.18 8.5.3 %chng proc
1961 1700 -2.61 tcl_for
5525 16539 110.14 loop_default
7 10 0.03 loop_explicit
ed@aleph>

Is this a bug for the default increment case?

Regards
Evilson

On Aug 26, 11:02 pm, Evil Son <ewilsonm...@gmail.com> wrote:
>
> proc loop_explicit {lim} {
> loop i 0 1 $lim {}

Afraid you swapped two arguments here:

loop var start end ?increment? command

so you're iterating from 0 to 1 with a $lim increment, explaining the
constant and extremely short time for loop_explicit:

> 7 9 0.02 loop_explicit
> 7 9 0.02 loop_explicit
> 7 10 0.03 loop_explicit

In general, an O(N) algorithm suddenly switching to O(1) in constant
space is suspect ;-) Another, slightly more interesting case would be
a one-page proof that P=NP...

-Alex

On Aug 27, 5:23*pm, Alexandre Ferrieux <alexandre.ferri...@gmail.com>
wrote:
> On Aug 26, 11:02 pm, Evil Son <ewilsonm...@gmail.com> wrote:

> > proc loop_explicit {lim} {
> > * loop i 0 1 $lim {}
>
> Afraid you swapped two arguments here:

Aargh! Thanks! I had fun writing the test harness though, albeit all
screwed up.

> * *loop var start end ?increment? command
> In general, an O(N) algorithm suddenly switching to O(1) in constant
> space is suspect ;-)

Indeed. Here are the new results:

ed@aleph> tclsh8.5 run-tests.tcl 10
8.4.18 8.5.3 ratio proc
6 6 1.00 tcl_for
12 25 2.08 loop_default
12 25 2.08 loop_explicit
ed@aleph> tclsh8.5 run-tests.tcl 100
8.4.18 8.5.3 ratio proc
23 21 0.91 tcl_for
58 176 3.03 loop_default
59 171 2.90 loop_explicit
ed@aleph> tclsh8.5 run-tests.tcl 1000
8.4.18 8.5.3 ratio proc
199 174 0.87 tcl_for
522 1703 3.26 loop_default
531 1718 3.24 loop_explicit
ed@aleph> tclsh8.5 run-tests.tcl 10000
8.4.18 8.5.3 ratio proc
1966 1699 0.86 tcl_for
5466 16827 3.08 loop_default
5481 16433 3.00 loop_explicit

As always, I remain obliged.

On Aug 27, 11:02 am, Evil Son <ewilsonm...@gmail.com> wrote:
> Here are the new results:
>
> ed@aleph> tclsh8.5 run-tests.tcl 10
> 8.4.18 8.5.3 ratio proc
> 6 6 1.00 tcl_for
> 12 25 2.08 loop_default
> 12 25 2.08 loop_explicit
> ed@aleph> tclsh8.5 run-tests.tcl 100
> 8.4.18 8.5.3 ratio proc
> 23 21 0.91 tcl_for
> 58 176 3.03 loop_default
> 59 171 2.90 loop_explicit
> ed@aleph> tclsh8.5 run-tests.tcl 1000
> 8.4.18 8.5.3 ratio proc
> 199 174 0.87 tcl_for
> 522 1703 3.26 loop_default
> 531 1718 3.24 loop_explicit
> ed@aleph> tclsh8.5 run-tests.tcl 10000
> 8.4.18 8.5.3 ratio proc
> 1966 1699 0.86 tcl_for
> 5466 16827 3.08 loop_default
> 5481 16433 3.00 loop_explicit

As you know of course, the near 3x speed gain for [for] is due to
bytecode compilation of its body, while TclX's [loop] command calls
Tcl_EvalObj at each turn.

This experiment IMO fuels the idea that preprocessing could help in
Tcl too from time to time: it would allow to define countless such
variants of Tcl's optimized control primitives without losing the
performance.

Notice that if you're bold enough to ignore fears of string collision,
you can define a variant of proc that does dangerous-yet-useful regexp
parsing. Here you can use [regexp] just to locate the [loop] word, and
then [info complete] to properly find the boundaries of the statement.
Then it's just a matter of substituting the equivalent [for]
incantation...

-Alex

On Aug 27, 7:41*pm, Alexandre Ferrieux <alexandre.ferri...@gmail.com>
wrote:
> ...
> As you know of course, the near 3x speed gain for [for] is due to
> bytecode compilation of its body, while TclX's [loop] command calls
> Tcl_EvalObj at each turn.
>
> This experiment IMO fuels the idea that preprocessing could help in
> Tcl too from time to time: it would allow to define countless such
> variants of Tcl's optimized control primitives without losing the
> performance.

I couldn't agree more.

> Notice that if you're bold enough to ignore fears of string collision,
> you can define a variant of proc that does dangerous-yet-useful regexp
> parsing. Here you can use [regexp] just to locate the [loop] word, and
> then [info complete] to properly find the boundaries of the statement.
> Then it's just a matter of substituting the equivalent [for]
> incantation...

I'm going to be looking at this method as well as some of the 'macro'
techniques available on the wiki. Baby steps just now ... but this
language is addictive.

Cheers.
Evil Son.

Alexandre Ferrieux wrote:
> As you know of course, the near 3x speed gain for [for] is due to
> bytecode compilation of its body, while TclX's [loop] command calls
> Tcl_EvalObj at each turn.

That's not it. Tcl will store the bytecodes for the loop body in that
object and reuse them. (The recompilation hit is actually about 10x when
it strikes, BTW, assuming a trivial script body.) The real hit is
probably due to the fact that TclX still uses the string-based variable
API; if they used Tcl_ObjSetVar2 instead of Tcl_SetVar2Ex, they'd go
quite a bit faster as variable names would not need to be reparsed every
time through the loop. (And the reparsing involves a fair bit of memory
management too...)

I know this because I've just checked the relevant code (tclBasic.c and
tclXgeneral.c FYI).

> This experiment IMO fuels the idea that preprocessing could help in
> Tcl too from time to time: it would allow to define countless such
> variants of Tcl's optimized control primitives without losing the
> performance.

That's the "LISP solution". And it turns out it's a wrong analysis in
this case. :-)

Donal.

On Aug 27, 4:48 pm, "Donal K. Fellows"
<donal.k.fell...@manchester.ac.uk> wrote:
>
> [overhead due to setting var rather than Eval]

I stand corrected !

> > This experiment IMO fuels the idea that preprocessing could help in
> > Tcl too from time to time: it would allow to define countless such
> > variants of Tcl's optimized control primitives without losing the
> > performance.
>
> That's the "LISP solution". And it turns out it's a wrong analysis in
> this case. :-)

Why a wrong analysis ? How would you define [loop] in pure Tcl so that
it has the same performance as a [for] ?

-Alex

Alexandre Ferrieux wrote:
> Why a wrong analysis ? How would you define [loop] in pure Tcl so that
> it has the same performance as a [for] ?

In 8.5 and before, you can't because the body script will not be
compiled to have efficient access to local variables. (This might
change in 8.6 AIUI.) But apart from that you can get close:

proc loop {var from to body} {
upvar 1 $var v
for {set v $from} {$v <= $to} {incr v} {
uplevel 1 $body
}
}

Yes, that's probably the sort of thing you'd write naïvely. That will
use maximally efficient variable accesses (except in the body at the
moment because we don't currently reconnect the compilation of the
body to the local variable table of the calling context) and will
compile the body. By contrast, the TclX loop command is actually less
efficient than that as it currently uses code that isn't very
efficient to assign the loop variables. (The API it uses is optimized
for ease of use with literal variable names, not for execution speed.)

Donal.

On Aug 28, 11:03*am, "Donal K. Fellows" <donal.k.fell...@man.ac.uk>
wrote:
> Alexandre Ferrieux wrote:
> > Why a wrong analysis ? How would you define [loop] in pure Tcl so that
> > it has the same performance as a [for] ?
>
> In 8.5 and before, you can't because the body script will not be
> compiled to have efficient access to local variables. (This might
> change in 8.6 AIUI.) But apart from that you can get close:
>
> * proc loop {var from to body} {
> * * *upvar 1 $var v
> * * *for {set v $from} {$v <= $to} {incr v} {
> * * * * uplevel 1 $body
> * * *}
> * }
>
> Yes, that's probably the sort of thing you'd write naïvely. That will
> use maximally efficient variable accesses (except in the body at the
> moment because we don't currently reconnect the compilation of the
> body to the local variable table of the calling context) and will
> compile the body. By contrast, the TclX loop command is actually less
> efficient than that as it currently uses code that isn't very
> efficient to assign the loop variables. (The API it uses is optimized
> for ease of use with literal variable names, not for execution speed.)
>
> Donal.

Funny you mention it, I had indeed written the naive implementation as
an exercise :-) I had gotten the following results for counting: 0 --
> 10,000-1

ed@aleph> tclsh8.5 run-tests.tcl 10000
8.4.18 8.5.3 ratio proc
1960 1699 0.87 tcl_for
5481 16175 2.95 loop_default
9020 11777 1.31 loop_eval <-- naive implemenation

> ed@aleph> tclsh8.5 run-tests.tcl 10000
> 8.4.18 *8.5.3 * ratio * proc
> 1960 * *1699 * * *0.87 *tcl_for
> 5481 * *16175 * * 2.95 *loop_default
> 9020 * *11777 * * 1.31 *loop_eval *<-- naive implemenation

And here is the result if I use a fixed increment (what is the default
case). i.e.

proc my_loop {index init bound inc script} {
upvar 1 $index i
for {set i $init} {$i < $bound} {incr i} { ;# we dont use incr i
$inc
uplevel 1 $script
}
}

ed@aleph> tclsh8.5 run-tests.tcl 10000
8.4.18 8.5.3 ratio proc
1965 1705 0.87 tcl_for
5400 17278 3.20 loop_default
8620 10818 1.25 loop_eval_fixed_increment

The last line removes the cost of a single variable access
i.e. 8620 vs 9020