Iterating over an interval: the new across loop

Introduction

Version 6.6 of EiffelStudio introduced a new construct to iterate through homogenous structures: the across loop.

Bertrand Meyer, in his post describing the syntax in details, mentions a form of the across loop that iterates through an interval:

  across m  |..| n  as c from  sum := 0  loop sum := sum +  a [c.item] end
               — Computes Σ a [i], for i ranging from m to n, for an array (or other structure) a. 

Taking two INTEGER m and n, the |..| free operator produces an INTEGER_INTERVAL object. This interval can then be enumerated like any array. This elegantly replicates the short syntax seen in other languages, while exposing the similarity between intervals of integers, lists and arrays, captured in a single syntax.

Performance

I experimented with the new construct in an environment where execution time matters. I started with a simple loop, that computes the sum of the first n integers.

sum := 0 from i := 1 until i > n loop sum := sum + i i := i + 1 end

To measure how fast the code performs, I chose a high value for n and multiplied executions of the loop significantly. Time is measured with TIME objects from the time library. I didn't check what the accuracy of this class is, but as you will see below it doesn't matter much.

First version with loop

The first version of the code looks like this: sigma_loop (n, repeat_count: INTEGER): INTEGER local sum, i: INTEGER repeat: INTEGER do from repeat := 1 until repeat > repeat_count loop sum := 0 from i := 1 until i > n loop sum := sum + i i := i + 1 end repeat := repeat + 1 end result := sum end test_run: TIME_DURATION local n: INTEGER repeat_count: INTEGER sum: INTEGER start, stop: TIME do n := 65535 repeat_count := 5000 create start.make_now sum := sigma_loop(n, repeat_count) create stop.make_now result := stop.relative_duration(start) print_result(n, repeat_count, result) end

The call to print_result (source code not provided) is there to stop the compiler from optimizing the loops by removing them altogether, since it uses the value of sum.

Execution of this code on my computer takes approximately 0 seconds, or a value so low that it's below the accuracy of the time measurement class.

Second version with across

I then replaced the inner loop with the equivalent across construct over the same interval:

from repeat := 1 until repeat > repeat_count loop sum := 0 across 1 |..| n as i loop sum := sum + i.item end repeat := repeat + 1 end

This code takes 1 mn and 39 seconds to execute, a dramatic difference coming from a lack of optimization of the new loop.

Third version with a precalculated interval

An obvious candidate for the part of the code slowing down the loop is the creation of the interval object. It can be created only once and reused:

sigma_across (n, repeat_count: INTEGER): INTEGER local sum, i: INTEGER repeat: INTEGER interval: INTEGER_INTERVAL do interval := 1 |..| n from repeat := 1 until repeat > repeat_count loop sum := 0 across interval as i loop sum := sum + i.item end repeat := repeat + 1 end result := sum end

The result isn't much better: 1 mn and 33 seconds. The slow code must then lie either in the calculation of the sum, or in the hidden support code created by the across construct.

Last version, ignoring the cursor

To verify it, I simply changed the sum := sum + i.item instruction to sum := sum + 1. The execution time is moderately improved, becoming 33 seconds.

Conclusion

The new across construct allows us to elegantly write loops iterating over an interval, however in its current implementation it shouldn't be used in code that has any consideration for speed.