TclX loop slow in the default case

I seem to have missed this thread ...

In 8.5 the variable access code has been optimised for access via Tcl_Obj names,
with some cost for access via the string interfaces. If TclX is using the string
interfaces, this could explain things.

On Aug 28, 3: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
> }
> }

What about [uplevel {for ...}] instead of [for ... uplevel] ?
(Miguel, what versions received your patch bringing compilation of
[uplevel] ?)

proc loop {var from to body} {
uplevel 1[list for[list set $var $from] "\$$var<$to"[list incr
$var] $body]
}

-Alex

Alexandre Ferrieux wrote:
> On Aug 28, 3: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
>> }
>> }
>
> (Miguel, what versions received your patch bringing compilation of
> [uplevel] ?)

I think this patch is in 8.5.3, but it doesn't show up in Evilson's examples because he uses an empty loop body. Using just a minimal loop body (for example {expr {$i+5}}) gives largely different results:

tclsh: 8.4.12
time (us) taken for 10000 iterations
1157 <-- tcl 'for'
33650 <-- loop_eval

tclsh: 8.5.4
time (us) taken for 10000 iterations
1151 <-- tcl 'for'
5271 <-- loop_eval

--Koen

On Aug 28, 7:32*pm, Koen Danckaert <k...@usenet.cnntp.org> wrote:
> I think this patch is in 8.5.3, but it doesn't show up in Evilson's examples because he uses an empty loop body. Using just a minimal loop body (forexample {expr {$i+5}}) gives largely different results:
>
> tclsh: 8.4.12
> time (us) taken for 10000 iterations
> 1157 * * <-- tcl 'for'
> 33650 * *<-- loop_eval
>
> tclsh: 8.5.4
> time (us) taken for 10000 iterations
> 1151 * * <-- tcl 'for'
> 5271 * * <-- loop_eval
>
> --Koen

Indeed, I was wondering about the iteration speed. So then I put an
[expr] in the body and got:

tclsh 8.4.18
2944 naked_for
14215 tclx_loop
81158 naive_loop
23162 clever_loop <-- from Alex earlier in thread

tclsh 8.5.3
3949 naked_for
23765 tclx_loop <-- as dkf/msf expected
105259 naive_loop <-- what the!
25769 clever_loop

tclsh 8.5.4
4040 naked_for
24557 tclx_loop
17135 naive_loop <-- optimisation work kicks in as Koen/msf said.
35612 clever_loop <-- not in the 8.5.4 possible world

And just to make a fool of myself, I'll include my bug-ridden procs
#-------------------------------------------------------------
# ignore $body, we want a baseline
proc naked_for { var from to {body {}} } {
for {set var $from} {$var<$to} {incr var} {expr {$var*$var}}
}

# e.g. from dkf which responds to all the optimisation work
proc naive_loop { var from to {body {}} } {
upvar $var i
for {set i $from} {$i<$to} {incr i} {
uplevel 1 $body
}
}

#ignore body, 'loop' already has some evaluating to do
proc tclx_loop { var from to {body {}} } {
upvar $var i
loop i $from $to 1 { expr {$i*$i}}
}

# from Alex
proc clever_loop { var from to {body {}} } {
uplevel 1[list for[list set $var $from] \
"\$$var<$to"[list incr $var] $body]
}

The procs above are called from:
#-------------------------------------------------------------
proc main {n} {
global aProcs

foreach {i} [lsort -integer [array names aProcs]] {
set proc $aProcs($i)
if {[info procs $proc] eq $proc } {
puts -nonewline [timeus[list \
$proc var 0 $n {expr {$var*$var}}]]
puts \t$proc
} else {
puts -nonewline "proc $proc currently undefined"
}
}
}

# timeus is a helper proc that does the obvious thing

Cheers
Evilson.

On Aug 28, 9:14*pm, Evil Son <ewilsonm...@gmail.com> wrote:
> tclsh 8.5.4
> 17135 * naive_loop <-- optimisation work kicks in as Koen/msf said.
> 35612 * clever_loop <-- not in the 8.5.4 possible world

Argh. Donal, can you explain why, despite [uplevel] compiling its
argument, uplevelling a computed [for] doesn't approach the speed of
the naked for (nor even that of for..uplevel) ?

-Alex

Alexandre Ferrieux wrote:
> Evil Son wrote:
>> tclsh 8.5.4
>> 17135 naive_loop <-- optimisation work kicks in as Koen/msf said.
>> 35612 clever_loop <-- not in the 8.5.4 possible world
>
> Argh. Donal, can you explain why, despite [uplevel] compiling its
> argument, uplevelling a computed [for] doesn't approach the speed of
> the naked for (nor even that of for..uplevel) ?

Yes.

Variable accesses are only efficient when they can be tied to an index
into a local variable table. This process is (probably) the #1 source of
speed in Tcl's bytecode engine (either that or the dealing with the fact
that no parsing needs to be done, but that's out of scope here). When a
script is processed with [uplevel] in 8.5 and before[*] then it cannot
be bound to local variables, resulting in each variable access for
reading or writing being done through a hash table lookup. For a [for]
loop, this is quite a significant cost!

OK, perhaps the "cannot" was a bit strong. "Has not yet been possible
to" is perhaps closer to the truth.

In the "naïve" version, the [upvar] binds the variable in the parent
scope to a local variable in the [naive_loop]'s own scope, and makes the
actual [for] loop part of it efficient (though accesses from inside the
body still suck). BTW, if you want performance out of [uplevel], always
remember to include the level argument in 8.5.

Donal.
[* This might change in 8.6. ]

On Aug 29, 10:31 am, "Donal K. Fellows"
<donal.k.fell...@manchester.ac.uk> wrote:
>
> Variable accesses are only efficient when they can be tied to an index
> into a local variable table. This process is (probably) the #1 source of
> speed in Tcl's bytecode engine (either that or the dealing with the fact
> that no parsing needs to be done, but that's out of scope here).

OK, so the compiling of uplevel's body bridged "only" half the canyon,
right ?
(That's not quite out of scope. It is interesting for performance-
concerned people to know such properties !)

> When a script is processed with [uplevel] in 8.5 and before[*] then it
> cannot be bound to local variables ...
> OK, perhaps the "cannot" was a bit strong. "Has not yet been possible
> to" is perhaps closer to the truth.
> [* This might change in 8.6. ]

Very interesting !

Random idea: what about extending the bytecode compiler API so that it
can be passed a non-empty "context" (compiledLocals, possibly
literals, etc) instead of starting afresh ? This way, in the dominant
case where the upper context is also a compiled proc, the body-
bytecode would "land" among the upper locals and access them at full
speed (not even a linkvar). Or is such sharing of lists of compiled
locals impossible in the current setup ?

-Alex

Alexandre Ferrieux wrote:
> Random idea: what about extending the bytecode compiler API so that it
> can be passed a non-empty "context" (compiledLocals, possibly
> literals, etc) instead of starting afresh ? This way, in the dominant
> case where the upper context is also a compiled proc, the body-
> bytecode would "land" among the upper locals and access them at full
> speed (not even a linkvar). Or is such sharing of lists of compiled
> locals impossible in the current setup ?

Done in 8.6 HEAD since 2008-06-08 [Patch 1973096]

miguel wrote:
> Done in 8.6 HEAD since 2008-06-08 [Patch 1973096]

I wasn't sure if that had been done or not. I knew you'd been talking
about it, but I'd been forced to focus on work at that time... :-(

Donal.

At 2008-08-29 06:24AM, "Alexandre Ferrieux" wrote:
> Random idea: what about extending the bytecode compiler API so that it
[...]

Your random idea generator sucks

A truly random idea would involve whales or petunias.


--
Glenn Jackman
Write a wise saying and your name will live forever. -- Anonymous