This page is no longer maintained — Please continue to the home page at www.scala-lang.org

Performance puzzle: for expressions versus while loops

5 replies
Alan Burlison
Joined: 2011-08-26,
User offline. Last seen 42 years 45 weeks ago.

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?

dcsobral
Joined: 2009-04-23,
User offline. Last seen 38 weeks 5 days ago.
Re: 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
> --

Ismael Juma 2
Joined: 2011-01-22,
User offline. Last seen 42 years 45 weeks ago.
Re: Performance puzzle: for expressions versus while loops
On Fri, Feb 17, 2012 at 12:18 PM, Alan Burlison <alan [dot] burlison [at] gmail [dot] 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
Ismael Juma 2
Joined: 2011-01-22,
User offline. Last seen 42 years 45 weeks ago.
Re: Performance puzzle: for expressions versus while loops
On Fri, Feb 17, 2012 at 12:30 PM, Ismael Juma <ismael [at] juma [dot] me [dot] uk> wrote:
On Fri, Feb 17, 2012 at 12:18 PM, Alan Burlison <alan [dot] burlison [at] gmail [dot] 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
dcsobral
Joined: 2009-04-23,
User offline. Last seen 38 weeks 5 days ago.
Re: Performance puzzle: for expressions versus while loops

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
> --

Alan Burlison
Joined: 2011-08-26,
User offline. Last seen 42 years 45 weeks ago.
Re: Performance puzzle: for expressions versus while loops

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

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland