Details

    • Type: Improvement
    • Status: Open
    • Priority: Major
    • Resolution: Unresolved
    • Affects Version/s: None
    • Fix Version/s: Backlog
    • Component/s: Compiler (Misc)
    • Labels:
      None
    • Environment:

      compiler, optimize, for loop, while

      Description

      I would like to suggest the compiler optimize the common case of for loops, that is,

      for (var <- Range [by step])
      for (var <- int to int [by step])
      for (var <- int until int [by step])
      

      to use while loops under the covers instead of. Currently, nested for loops using ranges/iterators are sometimes an order of magnitude slower than while loops. However, while loop constructs for iterating over arrays are very cumbersome, and the functional style (foreach) is also cumbersome and introduces a lot of function call overhead as well.

      The following two matrix multipication implementations

        def matMulUsingIterators (
             a : Array[Array[Double]],
             b : Array[Array[Double]],
             c : Array[Array[Double]]) : Unit = {
       
          val b_j = new Array[Double](b.length)
       
          for (j <- 0 until b(0).length) {
              for (k <- 0 until b.length) {
                  b_j(k) = b(k)(j)
              }
              for (i <- 0 until a.length) {
                  val c_i = c(i)
                  val a_i = a(i)
                  var s = 0.0d;
                  for (k <- 0 until b.length) {
                      s += a_i(k) * b_j(k)
                  }
                  c_i(j) = s
              }
          }
        }
       
        def matMulUsingRanges (
             a : Array[Array[Double]],
             b : Array[Array[Double]],
             c : Array[Array[Double]]) : Unit = {
       
          val jRange = 0 until b(0).length;
          val kRange = 0 until b.length;
          val iRange = 0 until a.length;
       
          val b_j = new Array[Double](b.length)
       
          for (j <- jRange) {
              for (k <- kRange) {
                  b_j(k) = b(k)(j)
              }
              for (i <- iRange) {
                  val c_i = c(i);
                  val a_i = a(i);
                  var s = 0.0d;
                  for (k <- kRange) {
                      s += a_i(k) * b_j(k)
                  }
                  c_i(j) = s
              }
          }
        }
      

      are much slower than the same algorithm coded with while loops:

        def matMulUsingWhileLoop (
            a : Array[Array[Double]],
            b : Array[Array[Double]],
            c : Array[Array[Double]]) : Unit = {
       
          val m = a.length;
          val p = b(0).length;
          val n = b.length;
       
          val b_j = new Array[Double](b.length);
       
          var i = 0; var j = 0; var k = 0;
          while (j < p) {
              k = 0
              while (k < n) {
                  b_j(k) = b(k)(j);
                  k += 1
              }
              i = 0
              while (i < m) {
                  val c_i = c(i);
                  val a_i = a(i);
                  var s = 0.0d;
                  k = 0;
                  while (k < n) {
                      s += a_i(k) * b_j(k);
                      k += 1
                  }
                  c_i(j) = s;
                  i += 1
              }
              j += 1;
          }
        }
      

      but the while loop code is more complex and error prone.

      (Sorry, Trac appears to remove some line breaks; I
      added some explicit semis but might have missed some;
      I'll try attaching actual working source code)

      Running this while measuring time in nanoseconds:

      Iterators   2,807,815,301ns
      Ranges      2,789,958,191ns
      While Loop  190,778,574ns
      

      MatMul by Iterators is 14 times as slow as with while loops.

      It does not appear that the Hotspot runtime profiling and optimization dramatically helps this performance problem
      This performance problem can hurt adoption of Scala for many types of uses/applications.

        Attachments

          Activity

          Hide
          olivier.chafik Olivier Chafik added a comment -

          (Sorry for spamming you again, this should be the last time)

          I've just enhanced the plugin with more conversions to while loops :

          • Array.foldLeft / foldRight
          • Array.reduceLeft / reduceRight
          • Array.scanLeft / scanRight
            (in addition to Array.foreach, Array.map and the int range foreach with no filter)

          Also, the conversions should now work on method references and inline lambdas the same way.

          Further progress and plans can be tracked at the bottom of this page :
          http://code.google.com/p/scalacl/wiki/ScalaCLPlugin

          Show
          olivier.chafik Olivier Chafik added a comment - (Sorry for spamming you again, this should be the last time) I've just enhanced the plugin with more conversions to while loops : Array.foldLeft / foldRight Array.reduceLeft / reduceRight Array.scanLeft / scanRight (in addition to Array.foreach, Array.map and the int range foreach with no filter) Also, the conversions should now work on method references and inline lambdas the same way. Further progress and plans can be tracked at the bottom of this page : http://code.google.com/p/scalacl/wiki/ScalaCLPlugin
          Hide
          herrkhosse Herrmann Khosse added a comment -

          +1

          Show
          herrkhosse Herrmann Khosse added a comment - +1
          Hide
          sethtisue Seth Tisue added a comment -

          "Spire also provides a loop macro called cfor whose syntax bears a slight resemblance to a traditional for-loop from C or Java. This macro expands to a tail-recursive function, which will inline literal function arguments." https://github.com/non/spire

          Show
          sethtisue Seth Tisue added a comment - "Spire also provides a loop macro called cfor whose syntax bears a slight resemblance to a traditional for-loop from C or Java. This macro expands to a tail-recursive function, which will inline literal function arguments." https://github.com/non/spire
          Hide
          ochafik Olivier Chafik added a comment -

          Here's another loop macro with an arguably better syntax: Scalaxy/Loops (which reuses code from ScalaCL):

          https://github.com/ochafik/Scalaxy/tree/master/Loops

          Show
          ochafik Olivier Chafik added a comment - Here's another loop macro with an arguably better syntax: Scalaxy/Loops (which reuses code from ScalaCL): https://github.com/ochafik/Scalaxy/tree/master/Loops
          Hide
          darkdimius Dmitry Petrashko added a comment -

          There's a different approach that I've tried in scalaBlitz: dont require users switch from using standard library while they code, but instead give a macro that changes implementation methods, replacing standard library implementation with macro-based one.
          Here's small description of it: http://scala-blitz.github.io/home/documentation//optimize.html

          The Range example in this ticket will be compiled to while loops and get same performance.

          Show
          darkdimius Dmitry Petrashko added a comment - There's a different approach that I've tried in scalaBlitz: dont require users switch from using standard library while they code, but instead give a macro that changes implementation methods, replacing standard library implementation with macro-based one. Here's small description of it: http://scala-blitz.github.io/home/documentation//optimize.html The Range example in this ticket will be compiled to while loops and get same performance.

            People

            • Assignee:
              Unassigned
              Reporter:
              djb David Biesack
              TracCC:
              Adam Kiezun, Alex Cruise, Alexey Romanov, Andrew McCallum, Anton Mellit, Carlos Lopez, Christos KK Loverdos, Daniel Sobral, Erkki Lindpere, federico silva, Ismael Juma, Johannes Rudolph, Jonathan Shore, Lachlan Deck, Miguel Garcia, Mirko Stocker, Olivier Chafik, RĂ¼diger Keller, Sbastien Bocq, Seth Tisue, spiros, turicum
            • Votes:
              36 Vote for this issue
              Watchers:
              31 Start watching this issue

              Dates

              • Created:
                Updated: