Very slow compilation of a long list of values with different types

[adamw]

Compiler version

3.0.1-RC2

Minimized code

trait E[T]

class X {
  val e1: E[Int] = ???
  val e2: E[String] = ???
  val e3: E[List[Int]] = ???
  val e4: E[List[String]] = ???
  val e5: E[Double] = ???
  val e6: E[(String, String)] = ???
  val e7: E[(String, Int)] = ???
  val e8: E[(Int, List[String])] = ???
  val e9: E[Long] = ???
  val e10: E[(Long, Long)] = ???
  val e11: E[(Long, Long, Int)] = ???
  val e12: E[List[Long]] = ???
  val e13: E[List[Int]] = ???
  val e14: E[(String, String)] = ???
  val e15: E[(String, String, String)] = ???
  val e16: E[(Int, String)] = ???
  val e17: E[(String, Long, String)] = ???
  val e18: E[(Long, String, String)] = ???
  val e19: E[(String, String, Long)] = ???
  val e20: E[(String, Int, String)] = ???
  val e21: E[(Int, String, String)] = ???
  val e22: E[(String, String, Int)] = ???
  val e23: E[(String, String, Boolean)] = ???
  val e24: E[(Boolean, Boolean, String)] = ???
  val e25: E[(String, Int, Boolean)] = ???
  val e26: E[List[(String, String)]] = ???
  val e27: E[List[(Int, String)]] = ???
  val e28: E[List[(String, Int)]] = ???
  val e29: E[List[(Long, String)]] = ???
  val e30: E[List[(String, Long)]] = ???
  val e31: E[List[(Boolean, String)]] = ???
  val e32: E[List[(String, Boolean)]] = ???
  val e33: E[List[((String, String), String)]] = ???
  val e34: E[List[((String, Int), String)]] = ???
  val e35: E[List[((Long, String), String)]] = ???
  val e36: E[List[((Boolean, String), String)]] = ???
  val e37: E[List[((String, String), Int)]] = ???
  val e38: E[List[((String, String), (String, Int))]] = ???
  val e39: E[List[((Boolean, Long), (String, Int))]] = ???
  val e40: E[List[((Int, Long), (Boolean, Int))]] = ???
  val e41: E[List[((String, (Int, String)), (String, Int))]] = ???
  val e42: E[List[((Boolean, (Int, String)), (String, Int))]] = ???
  val e43: E[List[((String, (Int, String)), (Boolean, Int))]] = ???
  val e44: E[(Int, List[String], Long)] = ???
  val e45: E[(Int, List[Int], Long)] = ???
  val e46: E[(Int, List[Long], Long)] = ???
  val e47: E[(String, List[String], Long)] = ???
  val e48: E[(Int, List[String], Boolean)] = ???
  val e49: E[Char] = ???

  val all = List(
    e1,
    e2,
    e3,
    e4,
    e5,
    e6,
    e7,
    e8,
    e9,
    e10,
    e11,
    e12,
    e13,
    e14,
    e15,
    e16,
    e17,
    e18,
    e19,
    e20,
    e21,
    e22,
    e23,
    e24,
    e25,
    e26,
    e27,
    e28,
    e29,
    e30,
    e31,
    e32,
    e33,
    e34,
    e35,
    e36,
    e37,
    e38,
    e39,
    e40,
    e41,
    e42,
    e43,
    e44,
    e45,
    e46,
    e47,
    e48,
    e49
  )
}

Output

Takes 32 seconds to compile locally. A similar list in tapir with 87 elements takes 250 seconds. Shorter lists behave normally, but at some point the compile times explode. The types of the elements on the list must be different - if it's all e.g. E[String] then compilation is fast. I suspect something in the type inferencer grows exponentially.

Expectation

Shorter compile time :)

[bishabosha]

possible duplicate of #7034?

here is the type generated for all, (varargs are inferred as the union of all their elements):

val all: 
      
        List[
          E[?
             >: Int & String & List[Int] & List[String] & Double & (String, 
              String
            ) & (String, Int) & (Int, List[String]) & Long & (Long, Long) & (
              Long
            , Long, Int) & List[Long] & (String, String, String) & (String, 
              String
            , Long) & (String, String, Boolean) & (Boolean, Boolean, String) & 
              List[(String, String)]
             & List[(Int, String)] & List[(String, Int)] & List[(Long, String)] 
              &
             List[(String, Long)] & List[(Boolean, String)] & 
              List[(String, Boolean)]
             & List[((String, String), String)] & List[((String, Int), String)] 
              &
             List[((Long, String), String)] & List[((Boolean, String), String)] 
              &
             List[((String, String), (String, Int))] & 
              List[((Boolean, Long), (String, Int))]
             & List[((Int, Long), (Boolean, Int))] & 
              List[((String, (Int, String)), (String, Int))]
             & (Int, List[Int], Long) & (Int, List[Long], Long) & Char <: Int | 
              String
             | List[Int] | List[String] | Double | (String, String) | (String, 
              Int
            ) | (Int, List[String]) | Long | (Long, Long) | (Long, Long, Int) | 
              List[Long]
             | (String, String, String) | (Int, String) | (String, Long, String)
               
            | (Long, String, String) | (String, String, Long) | (String, Int, 
              String
            ) | (Int, String, String) | (String, String, Int) | (String, String
              , 
            Boolean) | (Boolean, Boolean, String) | (String, Int, Boolean) | 
              List[(String, String)]
             | List[(Int, String)] | List[(String, Int)] | List[(Long, String)] 
              |
             List[(String, Long)] | List[(Boolean, String)] | 
              List[(String, Boolean)]
             | List[((String, String), String)] | List[((String, Int), String)] 
              |
             List[((Long, String), String)] | List[((Boolean, String), String)] 
              |
             List[((String, String), Int)] | 
              List[((String, String), (String, Int))]
             | List[((Boolean, Long), (String, Int))] | 
              List[((Int, Long), (Boolean, Int))]
             | List[((String, (Int, String)), (String, Int))] | 
              List[((Boolean, (Int, String)), (String, Int))]
             | List[((String, (Int, String)), (Boolean, Int))] | (Int, 
              List[String]
            , Long) | (Int, List[Int], Long) | (Int, List[Long], Long) | (String
              , 
            List[String], Long) | (Int, List[String], Boolean) | Char
          ]
        ]
      
     = List.apply[...](...)

[adamw]

@bishabosha could be, though here we've got 50, not 5000 elements :)

Also lists of 50 heterogenous elements probably occur much more frequently than lists of 5000 ;) So maybe this variant will be easier to debug & fix.

[bishabosha]

as a workaround, this compiles much quicker (sorry if you are cross compiling)

...
val all0 = (e1, e2, ..., e49) // aka huge tuple
val all = all0.toList // all0 needs to be in another variable to improve performance

[adamw]

@bishabosha this didn't help - I still got 215 second compile time, but this time failed with an error with some long union type. But I divided the list into sublists of length 10, then I combine all of these, and now it compiles quite quickly (softwaremill/tapir@109908f)

[bishabosha]

another way I think to speed up is to widen each argument to whichever common supertype you want,

val all = List(
  e1: E[?],
  e2: E[?],
  e3: E[?],
  ...
  e47: E[?],
  e48: E[?],
  e49: E[?]
)

[lrytz]

Or val all = List[E[?]]( ... )

[adamw]

Or val all = ListE[?]

Ha! Of course 🤦 Thanks :)

[odersky]

it's a nasty problem for the type inferencer since it ends up with a constraint where the lower bound of a type variable consists of an And with 50 types and the upper bound consists of an Or with 50 types. That's twice the worst case. It's efficient to deal with OrTypes on the left and AndTypes on the right, but the other way round causes backtracking and costly comparisons of constraints. but it should not be that bad, to the degree that a single list requires 32 or 250 seconds.

I managed to fix the problem by balancing AndTypes and OrTypes when we create them in a lub or glb. This brings down the time of the test to 4 seconds on my machine. I have not analyzed yet where the slowdown went before, but it looks generally like a good idea to avoid unbalanced trees.