Do not needlessly create tuples when pattern matching #8790

scabug · 2014-08-10T18:56:04Z

In the current version of Scala, pattern matching on tuples results in extra objects being created at runtime.

Consider the following MWE:

object Test {

  def slow(x: Int, y: Int): String = (x, y) match {
  	case (7, 8) => "You got it!"
  	case _ => "No such luck."
  }

  def faster(x: Int, y: Int): String = x match {
  	case 7 => 
  	  y match {
  	  	case 8 => "You got it!"
  	  	case _ => "No such luck."
  	  }
  	case _ => "No such luck."
  }

}

where the method faster in the above is some attempt to hand-optimise the implementation of the slow method. (I know that I will now have a duplicated case in the generated code, but you get the idea: the pair (x,y) has been eliminated.)

Compiling with scalac -print we see that the pattern matcher generates a Tuple2 when generating the bytecode for slow:

package <empty> {
  object Test extends Object {
    def slow(x: Int, y: Int): String = {
      case <synthetic> val x1: Tuple2 = new Tuple2$mcII$sp(x, y);
      case8(){
        if (x1.ne(null))
          {
            <synthetic> val p2: Int = x1._1$mcI$sp();
            <synthetic> val p3: Int = x1._2$mcI$sp();
            if (7.==(p2))
              if (8.==(p3))
                matchEnd7("You got it!")
              else
                case9()
            else
              case9()
          }
        else
          case9()
      };
      case9(){
        matchEnd7("No such luck.")
      };
      matchEnd7(x: String){
        x
      }
    };
    def faster(x: Int, y: Int): String = {
      case <synthetic> val x1: Int = x;
      (x1: Int) match {
        case 7 => {
          case <synthetic> val x1: Int = y;
          (x1: Int) match {
            case 8 => "You got it!"
            case _ => "No such luck."
          }
        }
        case _ => "No such luck."
      }
    };
    def <init>(): Test.type = {
      Test.super.<init>();
      ()
    }
  }
}

Reading the generated code, we can see that the Tuple generation is unnecessary.

I pattern match on pairs quite often, and the extra strain of short-lived objects such that these Tuples is quite burdensome on the garbage collector, particularly in multi-threaded applications.

The text was updated successfully, but these errors were encountered:

scabug · 2014-08-10T18:56:04Z

Imported From: https://issues.scala-lang.org/browse/SI-8790?orig=1
Reporter: Andrew Bate (andyd89)
Affected Versions: 2.11.2
Attachments:

Test.scala (created on Aug 10, 2014 6:56:04 PM UTC, 331 bytes)

scabug · 2014-08-10T23:35:20Z

@retronym said:
Last swing at this one: scala/scala#2397

scabug · 2014-08-11T12:04:40Z

Andrew Bate (andyd89) said:
I notice that the above pull request is marked as closed. What happened to it? It doesn't seem to have made it into 2.11.2.

scabug · 2014-08-11T16:57:23Z

@paulp said:
KILLED BY PEDANTIC REVIEWER

scabug · 2014-08-11T17:08:51Z

Andrew Bate (andyd89) said:
But I thought you were the assigned reviewer, Paul?
Either way, that's a shame. It forces me to avoid pattern matching on pairs in certain situations because of performance, and these are the places where concise expression would really help. It is these kinds of things that can make Scala feel like a language that isn't quite yet ready for prime time.

scabug · 2014-08-11T17:13:46Z

@paulp said:

But I thought you were the assigned reviewer, Paul?

These statements aren't in opposition.

scabug · 2014-08-11T17:16:31Z

@paulp said:

It forces me to avoid in certain situations because of performance

I can't write three lines of scala where that doesn't happen.

scabug · 2014-08-11T17:22:21Z

Andrew Bate (andyd89) said:
@paul
I'm glad I'm not alone in recognizing that. I wish that Scala had a greater emphasis on practicality. Sadly, I understand that you are no longer involved with Scala's development at Typesafe.

scabug · 2014-08-11T17:26:09Z

@paulp said:
You should say "happily" because you stand a better chance of obtaining something useful from me now than you ever did before.

scabug · 2014-08-11T17:27:53Z

Andrew Bate (andyd89) said:
I've always appreciated your contributions, so in that case, it can only be a good thing!

scabug · 2014-08-13T00:07:49Z

@retronym said:
We definitely want this optimization included in a future point release of 2.11, but we we need to find a better way to implement it.

scabug · 2015-03-04T16:22:47Z

Andrew Bate (andyd89) said:
Has there been any progress on this? This issue is a real performance pain in our code base at the moment (yes, we have profiled). Writing the optimization by hand is really annoying, and not very Scala.

scabug · 2015-03-04T20:47:48Z

@adriaanm said:
I wish I had more time to work on this, but I don't. I started porting my old 2.10 branch (https://github.com/adriaanm/scala/tree/patmat-tuple-opt) to 2.11 (https://github.com/adriaanm/scala/tree/patmat-tuple-opt-211). I already ported the refactoring part. If someone wants to work on this, happy to help.

scabug · 2015-03-05T21:21:15Z

Andrew Bate (andyd89) said:
If I had sufficient knowledge of the Scala compiler's implementation (beyond what I know courtesy of macros), I would help, but alas, I don't. Does the new branch resolve the problems that you and Paul identified in the original patch? It would be great if your hard work was finally contributed.

(As an aside, it is a shame that Scala doesn't some kind of "bug fix rewards system" whereby issues would be upvoted and monetary rewards offered.)

scabug · 2015-03-05T21:35:45Z

@som-snytt said:
(A couple of beers would probably suffice. Depending on the beer. Whisky for blockers.)

scabug · 2015-03-05T22:03:04Z

@adriaanm said:
Thanks! The main challenge is to figure out why my old PR broke the pattern matcher's CSE, which is nontrivial, though very worthwhile.

(Rumors to the contrary, we can't run Typesafe on whiskey and beer.)

scabug · 2015-03-07T01:18:36Z

@adriaanm said:
Well, I couldn't resist and cleaned up the old PR (https://github.com/scala/scala/compare/2.11.x...adriaanm:patmat-tuple-opt-211?expand=1): it works for a simple example. Now the fun begins: make sure it doesn't cause any regressions...

scabug · 2015-03-07T18:28:34Z

Andrew Bate (andyd89) said (edited on Mar 7, 2015 6:28:44 PM UTC):
The branch looks great and will definitely optimize away the cases that I've been optimizing by hand. In fact, your optimizer should produce better bytecode than I am able to by rewriting the source. Let's hope that there are no regressions.... Would we then be good to go? :-)

scabug · 2015-03-12T05:10:36Z

@adriaanm said:
This will land in 2.11.7 under -Xexperimental. scala/scala#4376

scabug · 2015-07-12T19:18:18Z

@som-snytt said:
Maybe it's possible to do the converse and preserve tuple instances across the arrow.

The issue says, If I create a tuple just to deconstruct it, don't bother constructing it.

This would add, if I deconstruct a tuple just to construct it, just reuse the instance, even though it's a different tuple type.

In other words, avoid reboxing the int and the tuple for (x,i):

scala> :pa
// Entering paste mode (ctrl-D to finish)

sealed trait Fruit
case class Apple(weight: Int = 200) extends Fruit
case object Orange extends Fruit
val fruits = Seq[Fruit](Apple(120), Orange, Orange, Apple())

// Exiting paste mode, now interpreting.

defined trait Fruit
defined class Apple
defined object Orange
fruits: Seq[Fruit] = List(Apple(120), Orange, Orange, Apple(200))

scala> fruits.zipWithIndex map { case (x: Apple, i: Int) => (x,i) case _  => (null, -1) }
res0: Seq[(Apple, Int)] = List((Apple(120),0), (null,-1), (null,-1), (Apple(200),3))

Use case from StackOverflow.

scabug · 2016-02-12T01:24:43Z

@retronym said:
@lrytz Is this case handled by the 2.12 optimizer since (scala/scala#4858) ?

scabug · 2016-02-13T16:45:41Z

@lrytz said:
Yes, here's the bytecode for slow with -Yopt:l:method:

  public slow(II)Ljava/lang/String;
    BIPUSH 7
    ILOAD 1
    IF_ICMPNE L1
    BIPUSH 8
    ILOAD 2
    IF_ICMPNE L1
    LDC "You got it!"
    ASTORE 3
    GOTO L2
    LDC "No such luck."
    ASTORE 3
   L2
    ALOAD 3
    ARETURN

scabug · 2016-02-13T18:40:21Z

@lrytz said:
scala/scala#4965

scabug · 2016-02-15T03:20:28Z

@retronym said:
Fixed by the new optimizer in Scala 2.12. We're not planning to address this in the Scala 2.11 series.

scabug closed this as completed Feb 15, 2016

scabug added enhancement patmat labels Apr 7, 2017

scabug added this to the 2.12.0-M4 milestone Apr 7, 2017

scabug assigned lrytz Apr 7, 2017

durban mentioned this issue May 29, 2017

Optimizer doesn't eliminate tuples in if/else branches #10342

Closed

Blaisorblade mentioned this issue Mar 11, 2018

Unnecessary boxing match in destructuring tuple assignment #10767

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Do not needlessly create tuples when pattern matching #8790

Do not needlessly create tuples when pattern matching #8790

scabug commented Aug 10, 2014

scabug commented Aug 10, 2014

scabug commented Aug 10, 2014

scabug commented Aug 11, 2014

scabug commented Aug 11, 2014

scabug commented Aug 11, 2014

scabug commented Aug 11, 2014

scabug commented Aug 11, 2014

scabug commented Aug 11, 2014

scabug commented Aug 11, 2014

scabug commented Aug 11, 2014

scabug commented Aug 13, 2014

scabug commented Mar 4, 2015

scabug commented Mar 4, 2015

scabug commented Mar 5, 2015

scabug commented Mar 5, 2015

scabug commented Mar 5, 2015

scabug commented Mar 7, 2015

scabug commented Mar 7, 2015

scabug commented Mar 12, 2015

scabug commented Jul 12, 2015

scabug commented Feb 12, 2016

scabug commented Feb 13, 2016

scabug commented Feb 13, 2016

scabug commented Feb 15, 2016

Do not needlessly create tuples when pattern matching #8790

Do not needlessly create tuples when pattern matching #8790

Comments

scabug commented Aug 10, 2014

scabug commented Aug 10, 2014

scabug commented Aug 10, 2014

scabug commented Aug 11, 2014

scabug commented Aug 11, 2014

scabug commented Aug 11, 2014

scabug commented Aug 11, 2014

scabug commented Aug 11, 2014

scabug commented Aug 11, 2014

scabug commented Aug 11, 2014

scabug commented Aug 11, 2014

scabug commented Aug 13, 2014

scabug commented Mar 4, 2015

scabug commented Mar 4, 2015

scabug commented Mar 5, 2015

scabug commented Mar 5, 2015

scabug commented Mar 5, 2015

scabug commented Mar 7, 2015

scabug commented Mar 7, 2015

scabug commented Mar 12, 2015

scabug commented Jul 12, 2015

scabug commented Feb 12, 2016

scabug commented Feb 13, 2016

scabug commented Feb 13, 2016

scabug commented Feb 15, 2016