Efficient loops

[Cecil Westerhof]

I had something where I had to use big loops. The number of times it
had to be run increased exponentially. There is wrong way and a right
way to do that. Code at the and of the message.

When calculating the power each time again, the loop takes about a
hundred times the time as when it is calculated in advance.

By converting the float that pow gives there is another 20% that can
be saved.


Is there a better way to do this? For example to signal that the end
value will not change so it has not to be reevaluated each time?


The code (comments and tips are welcome):
#!/usr/bin/env tclsh


proc displayTiming {} {
foreach {function description} {
withPow pow
withFloat float
withInt int
} {
set seconds [expr [lindex [time ${function}] 0] / 1000000.0]
puts [format "%-25s %.2E" "Timing with ${function}: " ${seconds}]
}
}

proc withFloat {} {
set until [expr pow(10, $::exp)]
for {set i 0} {$i < ${until}} {incr i} {
}
}

proc withInt {} {
set until [expr int(pow(10, $::exp))]
for {set i 0} {$i < ${until}} {incr i} {
}
}

proc withPow {} {
for {set i 0} {$i < [expr pow(10, $::exp)]} {incr i} {
}
}


set exp 7

displayTiming


By the way: I love how easy it is to extend the tests in the foreach. :-D

--
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof

[Arjen Markus]

Here are some comments ...

On Monday, April 15, 2019 at 11:59:07 AM UTC+2, Cecil Westerhof wrote:

>
> The code (comments and tips are welcome):
> #!/usr/bin/env tclsh
>
>
> proc displayTiming {} {
> foreach {function description} {
> withPow pow
> withFloat float
> withInt int
> } {
> set seconds [expr [lindex [time ${function}] 0] / 1000000.0]
> puts [format "%-25s %.2E" "Timing with ${function}: " ${seconds}]
> }
> }
>
> proc withFloat {} {
> set until [expr pow(10, $::exp)]
> for {set i 0} {$i < ${until}} {incr i} {
> }
> }

The value of until is calculated once, but in general it is better to brace your expressions:

set until [expr {pow(10, $::exp)}]

>

> proc withInt {} {
> set until [expr int(pow(10, $::exp))]
> for {set i 0} {$i < ${until}} {incr i} {
> }
> }

pow() will evaluate its arguments as floats, AFAIK.

>
> proc withPow {} {
> for {set i 0} {$i < [expr pow(10, $::exp)]} {incr i} {
> }
> }
>

The problems here are:
- You have not braced the expression, meaning that [expr] has to analyse the expression over and over again.
- You do not need an inner [expr] at all
- Defining "exp" as a global variable, rather than getting it from the global namespace might reduce the run time further (by a very small amount that is)

Try

proc withPow {} {
global exp
for {set i 0} {$i < pow(10, $exp)} {incr i} {
}
}

Or:
proc withPow {} {
global exp
for {set i 0} {$i < 10**$exp} {incr i} {

}
}

>
> set exp 7
>
> displayTiming
>
>
> By the way: I love how easy it is to extend the tests in the foreach. :-D
>

Regards,

Arjen

[Rich]

Arjen Markus <arjen.m...@gmail.com> wrote:
> Here are some comments ...
>
> On Monday, April 15, 2019 at 11:59:07 AM UTC+2, Cecil Westerhof wrote:
>
>>
>> The code (comments and tips are welcome):
>> #!/usr/bin/env tclsh
>>
>>
>> proc displayTiming {} {
>> foreach {function description} {
>> withPow pow
>> withFloat float
>> withInt int
>> } {
>> set seconds [expr [lindex [time ${function}] 0] / 1000000.0]

To further add to Arjen's comments, above you run "${function}" once,
which means your timings are also including any bytecode compiler
startup time in your results. This can skew your results because for
the first execution it is possible that the work of the bytecode
compiler might swamp the actual execution time.

Consider using the "count" parameter to 'time' (see the man page) to
request 'time' repeat the function some number of times (50, 100,
etc.). You'll amortize the bytecode work from call one over the other
49 (or 99, or etc.) calls and will end up with a net that is closer to
the true runtime expense.

[Arjen Markus]

On Monday, April 15, 2019 at 1:37:19 PM UTC+2, Rich wrote:

Yes, I missed that bit ;). You might want to call each function once outside the context of [time] - then the compile overhead should not be in the timing at all.

Regards,

Arjen

[Rich]

Cecil Westerhof <Ce...@decebal.nl> wrote:
> I had something where I had to use big loops. The number of times it
> had to be run increased exponentially. There is wrong way and a right
> way to do that. Code at the and of the message.
>
> When calculating the power each time again, the loop takes about a
> hundred times the time as when it is calculated in advance.

It sounds like you have rediscovered loop-invariant code motion
(https://en.wikipedia.org/wiki/Loop-invariant_code_motion) and common
subexpression elimination
(https://en.wikipedia.org/wiki/Common_subexpression_elimination), both
of which are techniques for removing redundant computations from
program code.

Both of the above techniques can be applied by compilers (and some do,
but I do not believe the Tcl bytecode compiler applies either) or by
the code authors before any compiler/interpreter ever sees the code.

Both work from the insight that any computation performed upon the same
inputs and producing the same outputs multiple times can be replaced by
a single computation and reuse of the pre-computed value later.
Obviously the removal of invariants from within loops will produce
greater gains than removing a few single duplicate computations in
non-looping code.

[Cecil Westerhof]

In the case I was talking about it is only called once, so then it is
a good match, but I changed it to:

set seconds [expr {[lindex [time ${function}] 0] / 1000000.0}]

puts [format "%-25s %.2E" "Timing with ${function}: " ${seconds}]

set seconds [expr {[lindex [time ${function}] 0] / 1000000.0}]

puts [format "%-25s %.2E" "Again with ${function}: " ${seconds}]

There is not really a difference in the timings in this case.

[Cecil Westerhof]

Arjen Markus <arjen.m...@gmail.com> writes:

> Here are some comments ...
>
> On Monday, April 15, 2019 at 11:59:07 AM UTC+2, Cecil Westerhof wrote:
>
>>
>> The code (comments and tips are welcome):
>> #!/usr/bin/env tclsh
>>
>>
>> proc displayTiming {} {
>> foreach {function description} {
>> withPow pow
>> withFloat float
>> withInt int
>> } {
>> set seconds [expr [lindex [time ${function}] 0] / 1000000.0]
>> puts [format "%-25s %.2E" "Timing with ${function}: " ${seconds}]
>> }
>> }
>>
>> proc withFloat {} {
>> set until [expr pow(10, $::exp)]
>> for {set i 0} {$i < ${until}} {incr i} {
>> }
>> }
>
> The value of until is calculated once, but in general it is better to brace your expressions:
>
> set until [expr {pow(10, $::exp)}]

Here it does not matter, but when used in the withPow proc it is a
speedup of almost 10.

>> proc withInt {} {
>> set until [expr int(pow(10, $::exp))]
>> for {set i 0} {$i < ${until}} {incr i} {
>> }
>> }
>
> pow() will evaluate its arguments as floats, AFAIK.

Yes, that is why I do an int call on the result. That gives almost 20%
performance boost.

> The problems here are:
> - You have not braced the expression, meaning that [expr] has to
> analyse the expression over and over again.

I knew that, but forgot. I almost never use expr.

> - You do not need an inner [expr] at all
> - Defining "exp" as a global variable, rather than getting it from
> the global namespace might reduce the run time further (by a very
> small amount that is)

For the other two it does not make a big difference, but when used
with withPow it almost halves the time.

>
> Try
>
> proc withPow {} {
> global exp
> for {set i 0} {$i < pow(10, $exp)} {incr i} {
> }
> }

Already done. Almost ten times faster.

> Or:
> proc withPow {} {
> global exp
> for {set i 0} {$i < 10**$exp} {incr i} {

This makes it almost three times as fast again. Takes only two times
the time as withFloat. That are quit significant savings. But still
withInt is significant faster.

[Rich]

I don't see any difference between the first and second time calls
above.

[Rich]

Cecil Westerhof <Ce...@decebal.nl> wrote:
> Arjen Markus <arjen.m...@gmail.com> writes:
>
>> Here are some comments ...
>>
>> On Monday, April 15, 2019 at 11:59:07 AM UTC+2, Cecil Westerhof wrote:
>>
>>>
>>> The code (comments and tips are welcome):
>>> #!/usr/bin/env tclsh
>>>
>>>
>>> proc displayTiming {} {
>>> foreach {function description} {
>>> withPow pow
>>> withFloat float
>>> withInt int
>>> } {
>>> set seconds [expr [lindex [time ${function}] 0] / 1000000.0]
>>> puts [format "%-25s %.2E" "Timing with ${function}: " ${seconds}]
>>> }
>>> }
>>>
>>> proc withFloat {} {
>>> set until [expr pow(10, $::exp)]
>>> for {set i 0} {$i < ${until}} {incr i} {
>>> }
>>> }
>>
>> The value of until is calculated once, but in general it is better to brace your expressions:
>>
>> set until [expr {pow(10, $::exp)}]
>
> Here it does not matter, but when used in the withPow proc it is a
> speedup of almost 10.

Already explained here in depth: https://wiki.tcl-lang.org/page/Brace+your+expr-essions

The tl;dr (in part [1]) is that the unbraced version requires expr to
reparse the expression every time it is executed.

The braced version allows expr to parse the expression once, cache away
the parsed version, and reuse the already parsed version for every
subsequent execution.

Which is why you see such a dramatic speedup in your withPow proc.
Each time through the loop you run expr to compute the power value.
Without braces the loop incurs both parsing and execution time. With
braces, you incur parsing once (on first iteration) and just execution
on subsequent iterations.


[1] The second reason for bracing them is that it avoids possible "code
injection" bugs if the variables used by the expression contain strings
who's content is in one way or another under external user control.

[Cecil Westerhof]

Because U cold it the first time, it does not have to be compiled for
the second time. Or do I miss something?

I also tried:

proc displayTiming {} {
foreach {function description} {
withPow pow
withFloat float
withInt int
} {

foreach {message} {"Timing with ${function}: " "Again with ${function}: "} {

set seconds [expr {[lindex [time ${function}] 0] / 1000000.0}]

puts [format "%-25s %.2E" ${message} ${seconds}]
}
}
}


Still no real difference.

[Rich]

No, you do not. I miss-interpreted your statement to mean you'd
changed the second line relative to the first line.

I tried out your example code, given the time the loops run, a single
cycle with [time] is not any big deal, and the compile time is also
small compared to the total run time. I did not realize, although I
should have, from just reading the code the length of time the loops
were going to take to run.

[Donal K. Fellows]

On 15/04/2019 13:25, Rich wrote:
> Both of the above techniques can be applied by compilers (and some do,
> but I do not believe the Tcl bytecode compiler applies either) or by
> the code authors before any compiler/interpreter ever sees the code.

The most advanced thing the current bytecode compiler does is spot
constant subexpressions and replace them with the constant value that
they would produce. It doesn't major code movement. It doesn't even
reorder variable accesses (as that'd be observable with traces).

Always brace your expressions if possible. With tcl::mathop available,
you don't even need unbraced expressions for things like adding a whole
list together. Bracing expressions is a huge win.

Donal.
--
Donal Fellows — Tcl user, Tcl maintainer, TIP editor.