Consider removing `while` from the language

[propensive]

It seems that while does not need to be a part of the core language. A simple definition such as,

@tailrec
def while(pred: => Boolean)(fn: => Unit): Unit = if(pred) { fn; while(pred)(fn) }

in Predef would suffice to provide the same functionality, and would enable a slight reduction in the size of the core language. I don't know what difference (if any) it would make to performance characteristics. There would be a potential disadvantage that it would become possible to shadow the while method, but not by existing code, of course.

Something similar would probably be possible with do/while syntax.

[nairbv]

It looks like it was added as a primitive for performance reasons. In "Scala By Example," Odersky includes essentially the same as your above code with this description:

For efficiency and better error diagnostics the while loop is a primitive construct in
Scala. But in principle, it could have just as well been a predefined function. Here is
a possible implementation of it:

def While (p: => Boolean) (s: => Unit) {
  if (p) { s ; While(p)(s) }
}

[propensive]

It would be interesting to revisit the performance argument in case more recent optimisations render the difference irrelevant, in particular now that we have inline.

[adamgfraser]

I tried playing with this a bit. It looks like the tail recursive implementation is about three times slower in my admittedly simplistic test. I imagine that given how common iteration is in lower level code this wouldn't make sense. Note that I wasn't able to use inline here, receiving the following error message: Maximal number of successive inlines (32) exceeded, Maybe this is caused by a recursive inline method?.

import scala.annotation.tailrec

object Comparison extends App {

  val N = 100000
  val as = (1 to N).toIndexedSeq

  println("Native while loop:")
  timeit(10000)(nativeSum(as))
  println("Tail recursive implementation:")
  timeit(10000)(tailRecSum(as))

  @tailrec
  def While(condition: => Boolean)(action: => Unit): Unit =
    if (condition) { action; While(condition)(action) }

  def nativeSum(as: IndexedSeq[Int]): Int = {
    var i = 0
    var sum = 0
    while (i < as.length) {
      sum += as(i)
      i += 1
    }
    sum
  }

  def tailRecSum(as: IndexedSeq[Int]): Int = {
    var i = 0
    var sum = 0
    While (i < as.length) {
      sum += as(i)
      i += 1
    }
    sum
  }

  def timeit(n: Int)(task: => Unit): Unit = {
    val start = System.currentTimeMillis
    (0 to n).foreach { _ => task }
    val stop = System.currentTimeMillis
    println((stop - start) / 1000.0 + " seconds")
  }
}

Native while loop:
4.089 seconds
Tail recursive implementation:
11.669 seconds

[nairbv]

The "Scala by example" book also mentioned "better error diagnostics." Maybe the extra lines in each stack trace is what he means?

scala> While(true) { throw new Exception("thrown from function while block") }
java.lang.Exception: thrown from function while block
  at .$anonfun$res4$2(<console>:14)
  at scala.Function0.apply$mcV$sp(Function0.scala:34)
  at .While(<console>:14)
  ... 28 elided

scala> While(throw new Exception("thrown from functional condition check")) { println("in block") }
java.lang.Exception: thrown from functional condition check
  at .$anonfun$res5$1(<console>:14)
  at scala.Function0.apply$mcZ$sp(Function0.scala:34)
  at .While(<console>:14)
  ... 28 elided

scala> while(true) { throw new Exception("thrown from regular while block") }
java.lang.Exception: thrown from regular while block
  ... 28 elided

scala> while(throw new Exception("thrown from regular condition check")) { println("in block") }
java.lang.Exception: thrown from regular condition check
  ... 28 elided

[pnf]

@adamgfraser Re timing: what I would worry about most is short loops where the JIT doesn't get enough reps to deem it worth inlining. jmh would be useful here. It would also be interesting to compare the timings and the generated assembler using graal, which can be shockingly better on higher-order functions.

[pnf]

Also: I mentioned on a twitter thread already, but it's interesting that the Dotty documentation contains an example with both inline and while keywords:

inline def foreach(op: => Int => Unit): Unit = {
  var i = from
  while (i < end) {
    op(i)
    i += 1
  }
}

The following might be my personal quirks, but I tend to think

1. Having constructs like while available to extract maximum performance in core infrastructure is totally consistent with Scala philosophy.
2. Higher-order functions taking impure closures are weird; if I were looking for controversial deprecations, I'd axe foreach.

[He-Pin]

Remove it and let the compiler do optimization ？

[joroKr21]

Adding inline essentially unrolls the loop which is not what you want.

[joroKr21]

What you need to do instead of inline is a macro (I'm not sure what the syntax is these days so consider this pseudo code):

macro def while(p: Expr[Boolean])(b: Expr[Unit]): Unit = '{
  def w(): Unit = if (~p) { ~b; w() }
  w()
} 

But it' s probably not worth doing. It's more interesting to automatically transform a mutating while loop into a pure tailrec method which takes all variables as arguments, but that's a lot more involved.

[LPTK]

@joroKr21 why would you need a macro ?

I think you could do it as:

inline def doWhile(p: => Bool): Unit = {
  @tailrec def rec: Unit = if (p) rec
  rec
}

AFAIK the by-name parameter to the inline function will be copied to its use sites (here, the condition of the if) in the inlined body.

[adamgfraser]

I was able to use inline with the method like this:

  inline def While(condition: => Boolean)(action: => Unit): Unit = {
    @tailrec
    def go: Unit = if (condition) { action; go }
    go
  }

With that implementation and testing with JMH, the inline version is slightly faster than a native while loop. The inline version is dramatically faster than the tail recursive version without inlining. So it looks like we could potentially replace while with a library method without compromising performance.

[info] Benchmark              Mode  Cnt  Score   Error   Units
[info] TestWhile.inlineSum   thrpt   20  2.150 ± 0.044  ops/ms
[info] TestWhile.nativeSum   thrpt   20  1.967 ± 0.040  ops/ms
[info] TestWhile.tailRecSum  thrpt   20  0.885 ± 0.050  ops/ms

I also checked the error reporting and we still get nice error messages. I'm not sure how much this all buys us because we're still using highly impure actions that have the type => Unit and with @tailrec we're still compiling down to a while loop on the JVM. But it is definitely interesting that we can implement this without any performance penalty, and potentially with a slight speedup, by using inline. Does it make sense to pursue this further?

package bench

import java.util.concurrent.TimeUnit

import scala.annotation.tailrec

import org.openjdk.jmh.annotations._

@OutputTimeUnit(TimeUnit.MILLISECONDS)
@BenchmarkMode(Array(Mode.Throughput))
@State(Scope.Benchmark)
class TestWhile {

  val as = (1 to 100000).toIndexedSeq

  inline def While(condition: => Boolean)(action: => Unit): Unit = {
    @tailrec
    def go: Unit = if (condition) { action; go }
    go
  }

  @tailrec
  final def While0(condition: => Boolean)(action: => Unit): Unit =
    if (condition) { action; While0(condition)(action) }

  @Benchmark
  def nativeSum: Int = {
    var i = 0
    var sum = 0
    while (i < as.length) {
      sum += as(i)
      i += 1
    }
    sum
  }

  @Benchmark
  def inlineSum: Int = {
    var i = 0
    var sum = 0
    While (i < as.length) {
      sum += as(i)
      i += 1
    }
    sum
  }

  @Benchmark
  def tailRecSum: Int = {
    var i = 0
    var sum = 0
    While0 (i < as.length) {
      sum += as(i)
      i += 1
    }
    sum
  }
}

import scala.annotation.tailrec

object Test {

  def main(args: Array[String]): Unit =
    failingSum(as)

  def as = (1 to 100000).toIndexedSeq

  def failingSum(as: IndexedSeq[Int]): Int = {
    var i = 0
    var sum = 0
    While (i < as.length) {
      if (as(i) > 50000) throw new Exception("Boom!")
      sum += as(i)
      i += 1
    }
    sum
  }

  inline def While(condition: => Boolean)(action: => Unit): Unit = {
    @tailrec
    def go: Unit = if (condition) { action; go }
    go
  }
}

[error] (run-main-3) java.lang.Exception: Boom!
[error] java.lang.Exception: Boom!
[error]         at Test$.go$1(Test.scala:14)
[error]         at Test$.failingSum(Test.scala:24)
[error]         at Test$.main(Test.scala:6)
[error]         at Test.main(Test.scala)
[error]         at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
[error]         at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
[error]         at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
[error]         at java.lang.reflect.Method.invoke(Method.java:498)

[propensive]

Thanks for investing the time into benchmarking this, @adamgfraser - the results are certainly interesting!

I also mentioned this to @odersky recently, and he suggested that the do/while variant could be removed completely. It looks like we might be able to avoid it, but as a general rule, any reduction in performance of while would be a blocker, though.

[adamgfraser]

@propensive That totally makes sense. Is there anything else I can do to help? The results are encouraging but it is just one benchmark. Is there a broader set of benchmarks that we could use to determine whether there would be any reduction in performance?

[LPTK]

It seems nobody mentioned performance of the compiler. Compiling a while statement is probably much faster than inlining a def and optimizing it away.

If this change made while-heavy projects slower to compile (if there are any?), then it'd be a bad idea.

[pnf]

Maybe, especially since both closures have to involve outer references, but we can test that too. Dotty has a suite of jmh tests for compilation.

On Sun, Nov 18, 2018, at 12:58 PM, Lionel Parreaux wrote: It seems nobody mentioned performance of *the compiler*. Compiling a while statement is probably much faster than inlining a def and optimizing it away.> If this change made while-heavy projects slower to compile (if there are any?), then it'd be a bad idea.> — You are receiving this because you commented. Reply to this email directly, view it on GitHub[1], or mute the thread[2].

Links: 1. #5440 (comment) 2. https://github.com/notifications/unsubscribe-auth/ABNP7fNmfVl7SL1rKrn-1tZ_keNaDOqCks5uwZ-sgaJpZM4Ycn60