Performance puzzle: for expressions versus while loops

This test is misguided. The for loop is only computing length once,
and the while loop is computing it every time. The problem is that
List's length is an O(n) method, so doing it n times gives you O(n
squared) complexity.

On Fri, Feb 17, 2012 at 10:18, Alan Burlison wrote:
> According to https://issues.scala-lang.org/browse/SI-1338, loops over a
> range of integers using 'for' are slower than loops using 'while'. However,
> some simplistic testing seems to disprove that, in fact for lists, loops are
> *faster* than while.
>
> scala> def timed(op: => Unit) = { val start = System.nanoTime; op;
> (System.nanoTime - start) / 1e9 }
> timed: (op: => Unit)Double
>
> scala> val v = Vector.fill(100000)(1)
> scala> val l = List.fill(100000)(1)
>
> scala> timed { var t = 0; for (i <- 0 until l.length - 1) yield t += l(i) +
> l(i + 1) }
> res11: Double = 16.389101803
>
> scala> timed { var t = 0; var i = 0; while (i < l.length - 1) { t += l(i) +
> l(i + 1); i += 1 } }
> res12: Double = 34.668180577
>
> scala> timed { var t = 0; for (i <- 0 until v.length - 1) yield t += v(i) +
> v(i + 1) }
> res13: Double = 0.00958013
>
> scala> timed { var t = 0; var i = 0; while (i < v.length - 1) { t += v(i) +
> v(i + 1); i += 1 } }
> res14: Double = 0.009387144
>
> The difference in performance between the List and Vector isn't surprising
> but I'm puzzled as to why 'for' is approx 2x faster than 'while' in the list
> case.  This test was done with 2.10.0-M1 on Java 1.6.0_26, has the compiler
> been improved to optimize 'for' loops since SI-1338 was logged?
>
> I've been faithfully using 'while' instead of 'for' when I needed to
> index/iterate, have I been wasting my time?
>
> --
> Alan Burlison
> --

On Fri, Feb 17, 2012 at 12:18 PM, Alan Burlison <alan.burlison@gmail.com> wrote:

The difference in performance between the List and Vector isn't surprising but I'm puzzled as to why 'for' is approx 2x faster than 'while' in the list case.

This is expected. Indexed access is slow for linked lists as you need to traverse the nodes to retrieve the appropriate element.
Best,Ismael

On Fri, Feb 17, 2012 at 12:30 PM, Ismael Juma <ismael@juma.me.uk> wrote:

On Fri, Feb 17, 2012 at 12:18 PM, Alan Burlison <alan.burlison@gmail.com> wrote:

The difference in performance between the List and Vector isn't surprising but I'm puzzled as to why 'for' is approx 2x faster than 'while' in the list case.

This is expected. Indexed access is slow for linked lists as you need to traverse the nodes to retrieve the appropriate element.

Seems like I did not read the code carefully enough. The list foreach case is also using indexed access. That in itself makes the benchmark invalid for real-world usage. In any case, Daniel's explanation seems to be the correct one.
Best,Ismael

Oh, and the compiler hasn't improved its optimization (though the
_speed_ at which it does it has been improved), but Range's foreach
(and related methods) have been improved to avoid things that turned
out to be JIT-killers.

On Fri, Feb 17, 2012 at 10:18, Alan Burlison wrote:
> According to https://issues.scala-lang.org/browse/SI-1338, loops over a
> range of integers using 'for' are slower than loops using 'while'. However,
> some simplistic testing seems to disprove that, in fact for lists, loops are
> *faster* than while.
>
> scala> def timed(op: => Unit) = { val start = System.nanoTime; op;
> (System.nanoTime - start) / 1e9 }
> timed: (op: => Unit)Double
>
> scala> val v = Vector.fill(100000)(1)
> scala> val l = List.fill(100000)(1)
>
> scala> timed { var t = 0; for (i <- 0 until l.length - 1) yield t += l(i) +
> l(i + 1) }
> res11: Double = 16.389101803
>
> scala> timed { var t = 0; var i = 0; while (i < l.length - 1) { t += l(i) +
> l(i + 1); i += 1 } }
> res12: Double = 34.668180577
>
> scala> timed { var t = 0; for (i <- 0 until v.length - 1) yield t += v(i) +
> v(i + 1) }
> res13: Double = 0.00958013
>
> scala> timed { var t = 0; var i = 0; while (i < v.length - 1) { t += v(i) +
> v(i + 1); i += 1 } }
> res14: Double = 0.009387144
>
> The difference in performance between the List and Vector isn't surprising
> but I'm puzzled as to why 'for' is approx 2x faster than 'while' in the list
> case.  This test was done with 2.10.0-M1 on Java 1.6.0_26, has the compiler
> been improved to optimize 'for' loops since SI-1338 was logged?
>
> I've been faithfully using 'while' instead of 'for' when I needed to
> index/iterate, have I been wasting my time?
>
> --
> Alan Burlison
> --

On 17/02/2012 12:29, Daniel Sobral wrote:

> This test is misguided. The for loop is only computing length once,
> and the while loop is computing it every time. The problem is that
> List's length is an O(n) method, so doing it n times gives you O(n
> squared) complexity.

Doh! Of course! I was pretty sure I was missing something obvious, and
indeed I was. Thanks Daniel :-)

Here's a version that calculates length just once, outside of the while
condition test, the performance is the same as the for loop version.

scala> timed { var t = 0; for (i <- 0 until l.length - 1) yield t +=
l(i) + l(i + 1) }
res5: Double = 16.33974413

scala> timed { var t = 0; var i = 0; var j = l.length; while (i < j - 1)
{ t += l(i) + l(i + 1); i += 1 } }
res6: Double = 16.352754187