[uplevel] speedup

[miguel]

I have committed Patch #1973096, "bytecompiling uplevel, with access to the
LVT". If you are using or maintaining code that is a heavy user of [uplevel],
maybe even in a heavily used inner loop ...

... please be sure to test 8.6 during the alpha phase! If you have some way of
timing your app, please do so too. It should be a bit faster.

Thank you, as you were.

Miguel

[Neil Madden]

Sounds good! Thanks, Miguel. I am a heavy user of uplevel, so I'll be
sure to test/time these changes.

-- Neil

[Koen Danckaert]

Sometimes I need a counter in the body of a "foreach" loop. I once wrote a tiny wrapper around foreach, to provide such a counter:

proc foreachcount {var list countvar command} {
upvar $var v
upvar $countvar i
set i 0
foreach v $list {
uplevel 1 $command
incr i
}
}

However this turned out to be very slow: compare the following timings...

proc loop1 {} {
global a
set i 0
foreach x $a {
set y [expr {$i + $x}]
incr i
}
}

proc loop2 {} {
global a
foreachcount x $a i {
set y [expr {$i + $x}]
}
}

for {set i 0} {$i < 1000} {incr i} {lappend a [expr {$i * $i}]}
puts [time loop1 100]
puts [time loop2 100]

Results:
185.76 microseconds per iteration
6171.26 microseconds per iteration

With the 8.6 CVS, I obtain:
189.45 microseconds per iteration
757.31 microseconds per iteration

So it's not "a bit" faster, it's an order of magnitude faster :-)
Thanks!

--Koen

[miguel]

Try this to make it even faster (and do tell me how much faster!):

proc loop3 {} {
global a
set i {}; # make sure that i is in the LVT

foreachcount x $a i {
set y [expr {$i + $x}]
}
}

(this is working around a shortcoming that I don't yet know how to solve
automatically: let the uplevel script define new LVT variables)

[miguel]

Oops --- need all vars in the LVT (your smallish test script does not do that,
and I missed it). So ...

proc loop3 {} {
global a
set i {}; # make sure that i is in the LVT

set x {};
set y {};

[Koen Danckaert]

miguel wrote:
>>> I have committed Patch #1973096, "bytecompiling uplevel, with access
>>> to the LVT". If you are using or maintaining code that is a heavy
>>> user of [uplevel], maybe even in a heavily used inner loop ...
>>>

>> Results:
>> 185.76 microseconds per iteration
>> 6171.26 microseconds per iteration
>>
>> With the 8.6 CVS, I obtain:
>> 189.45 microseconds per iteration
>> 757.31 microseconds per iteration
>>
>> So it's not "a bit" faster, it's an order of magnitude faster :-)
>> Thanks!
>
> Try this to make it even faster (and do tell me how much faster!):
>
> proc loop3 {} {
> global a
> set i {}; # make sure that i is in the LVT
> foreachcount x $a i {
> set y [expr {$i + $x}]
> }
> }

Indeed a bit faster again:

loop1: 185.94 microseconds per iteration
loop2: 757.15 microseconds per iteration
loop3: 686.05 microseconds per iteration

--Koen

[Glenn Jackman]

At 2008-06-09 10:39AM, "miguel" wrote:
> Oops --- need all vars in the LVT

To satisfy my curiosity: What's an LVT?

--
Glenn Jackman
"If there is anything the nonconformist hates worse than a conformist,
it's another nonconformist who doesn't conform to the prevailing
standard of nonconformity." -- Bill Vaughan

[Koen Danckaert]

Indeed, now it's even better:

loop1: 187.63 microseconds per iteration
loop2: 755.36 microseconds per iteration
loop3: 513.87 microseconds per iteration

--Koen

[miguel]

Glenn Jackman wrote:
> At 2008-06-09 10:39AM, "miguel" wrote:
>> Oops --- need all vars in the LVT
>
> To satisfy my curiosity: What's an LVT?
>

"Local Variable Table"

Variables that are known at compile time are looked up by indexing into the LVT,
which is much faster than a lookup by name (either by linear search in the LVT,
or else in a hash table).