Iterating over an interval: the new across loop

by David Le Bansais (modified: 2010 Apr 14)

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.

Comments
  • Manu (14 years ago 14/4/2010)

    The issue here is that you are not comparing the right things. The idea is to use across instead of a loop when iterating over structures to avoid typical mistakes (such as moving the cursor) and to allow powerful assertions writing when the across some or all variant is used.

    Clearly it was not made to replace efficient counting. In this particular case, the across version performs actual feature calls where the other version has 0 call, just additions. Also make sure to always compare finalized binaries with at the minimum an inlining size of zero and no exception trace enabled.

    Let us know what you find.

    • David Le Bansais (14 years ago 15/4/2010)

      I believe I am comparing the right things. I know it was not made to be efficient, and I'm not criticizing anything or anyone, just posting found facts.

      I compared finalized versions, of course. Traces are disabled, but I couldn't find the inline size option, I'm most likely using the default value for a wizard-generated project.

      Nobody is claiming we should use, or not use, across m |...| n as. However if anyone is considering to port their source code, hopefully this post will help them make an informed decision.

  • Alexander Kogtenkov (8 years ago 3/6/2016)

    Improvements in EiffelStudio 16.05

    Some optimizations for across loops have been shipped with EiffelStudio 16.05. They do not cover the gap between classic loop and across loop versions, but definitely bring them closer.