New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Slow, exponential compile times for HLists > 200 elements #8478
Comments
Imported From: https://issues.scala-lang.org/browse/SI-8478?orig=1 |
@retronym said: |
@retronym said: Applying this patch to master:
Takes compilation down for me from 1:18 to 0:16. This suggests one workaround: you could make the hlist implicit a macro, which disables divergence checking. Another possibility, which I'll try out soon, is to add an "fast track" implicit for HLists of, say, size 8, and arrange for this to be prioritized over the hlist of size 1 implicit. |
@cvogt said: |
@cvogt said: |
@retronym said: |
@cvogt said: |
@retronym said: |
@retronym said: trait Tables {
type Column[T]
type HList
type HNil <: HList
type HCons[+Value, +Tail <: HList] <: HList
type :: [+Value, +Tail <: HList] = HCons[Value, Tail]
trait ShapeLevel
object ShapeLevel{
trait Nested extends ShapeLevel
trait Flat extends Nested
trait Columns extends Flat
}
abstract class Shape[Level <: ShapeLevel, -Mixed_, Unpacked_, Packed_]
abstract class HListShape[Level <: ShapeLevel, M <: HList, U <: HList, P <: HList] extends Shape[Level, M, U, P]
trait LowPriorityImplicits2 {
implicit def hnilShape[Level <: ShapeLevel]: HListShape[Level, HNil, HNil, HNil] = ???
implicit def hconsShape[Level <: ShapeLevel, L1 <: Level, L2 <: Level, M1, M2 <: HList, U1, U2 <: HList, P1, P2 <: HList](implicit s1: Shape[L1, M1, U1, P1], s2: HListShape[L2, M2, U2, P2]) : HListShape[Level, M1 :: M2, U1 :: U2, P1 :: P2] = ???
}
trait LowPriorityImplicits1 extends LowPriorityImplicits2 {
// This implicit is redundant (hconsShape would be sufficient) but it serves to
// limit the depth of implicit search through `hconsShape`, which has
// exponential performance (albeit at a low constant factor) shows up with hlists
// in the order of 100 elements. See SI-8478.
implicit def hconsShape8[Level <: ShapeLevel,
L1 <: Level, L2 <: Level, L3 <: Level, L4 <: Level, L5 <: Level, L6 <: Level, L7 <: Level, L8 <: Level,
M1, M2, M3, M4, M5, M6, M7, M8 <: HList,
U1, U2, U3, U4, U5, U6, U7, U8 <: HList,
P1, P2, P3, P4, P5, P6, P7, P8 <: HList](
implicit
s1: Shape[L1, M1, U1, P1],
s2: Shape[L2, M2, U2, P2],
s3: Shape[L3, M3, U3, P3],
s4: Shape[L4, M4, U4, P4],
s5: Shape[L5, M5, U5, P5],
s6: Shape[L6, M6, U6, P6],
s7: Shape[L7, M7, U7, P7],
s8: HListShape[L8, M8, U8, P8]
) : HListShape[Level, M1 :: M2 :: M3 :: M4 :: M5 :: M6 :: M7 :: M8,
U1 :: U2 :: U3 :: U4 :: U5 :: U6 :: U7 :: U8,
P1 :: P2 :: P3 :: P4 :: P5 :: P6 :: P7 :: P8] = ???
}
object Implicits extends LowPriorityImplicits1 {
implicit def primitiveShape[Level <: ShapeLevel]: Shape[Level, String, String, Column[String]] = ???
}
import Implicits._
type HList10[T <: HList] = HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,T]]]]]]]]]]
type HList100[T <: HList] = HList10[HList10[HList10[HList10[HList10[HList10[HList10[HList10[HList10[HList10[T]]]]]]]]]]
type JobRow = HList10[HList10[HList10[HList10[HList10[HList10[HList100[HList100[HNil]]]]]]]] // size 260
implicitly[Shape[_ <: ShapeLevel.Flat, JobRow, JobRow, _]]
} |
@cvogt said: |
@szeiger said: |
@retronym said: |
@cvogt said (edited on Apr 7, 2014 11:08:37 PM UTC): import scala.reflect.ClassTag
import scala.slick.ast.{TypedType}
import scala.slick.lifted.FlatShapeLevel
import scala.slick.lifted.Shape
import scala.slick.collection.heterogenous._
trait Tables {
implicit def stringColumnType: TypedType[String] = ???
type BranchRow = HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HNil.type]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]
implicitly[Shape[_ <: FlatShapeLevel, BranchRow, BranchRow, _]]
def x = implicitly[Shape[_ <: FlatShapeLevel, HCons[String,HNil.type], _, _]]
val i = x
} This takes like 20 seconds on my machine (add 6 elements to the list for 60 seconds). The odd thing is, if you remove the line with the val, it compiles in 1 second. |
@retronym said:
|
@cvogt said: https://github.com/cvogt/slick-presentation/tree/tmp/hlistSpeed |
@retronym said (edited on Apr 22, 2014 11:16:39 AM UTC):
|
@retronym said: |
@retronym said: |
@retronym said: More directly, this takes 23 seconds to typecheck: import scala.reflect.ClassTag
import scala.slick.ast.{TypedType}
import scala.slick.lifted.FlatShapeLevel
import scala.slick.lifted.Shape
import scala.slick.collection.heterogenous._
trait Tables {
implicit def stringColumnType: TypedType[String] = ???
type BranchRow = HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HCons[String,HNil.type]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]
implicitly[Shape[_ <: FlatShapeLevel, HCons[String,HNil.type], _, _]]
implicitly[Shape[_ <: FlatShapeLevel, BranchRow, BranchRow, _]]
} As opposed to 3 seconds with: implicitly[Shape[_ <: FlatShapeLevel, BranchRow, BranchRow, _]]
implicitly[Shape[_ <: FlatShapeLevel, HCons[String,HNil.type], _, _]] If, using the patch below, we remove the "use count" based pre-sorting of implicits (which implments the strategy to try popular implicits before less popular ones of the same specificity), we return to deterministic speed. This happens to be fast, but I suspect that this is by chance, and depends on the declaration order of some implicits. git diff -U1
diff --git a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
index d87090f..fcc7d75 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
@@ -881,4 +881,3 @@ trait Implicits {
- // most frequent one first
- matches sortBy (x => if (isView) -x.useCountView else -x.useCountArg)
+ matches
} |
@retronym said: |
@milessabin care to update the status on this? |
The inductive implicits PR interacts with byname implicits, so it's stuck in a queue behind that. |
Is this fixed by scala/scala#6580? |
@adriaanm I see a very marginal speedup (a couple of %, consistently better, but small enough to be counted as noise) with scala/scala#6580 on the original case. I think the conclusion above was that the original case was somewhat pathological. I'd give the revised example a spin, but it isn't standalone and we don't have a 2.13.x Slick build. |
This is a blocker for longer HLists of sizes of a few hundred elements, which is not uncommon for database table column numbers, e.g. http://stackoverflow.com/questions/22842486/eclipse-scala-ide-slow-and-crashes-caused-by-slick-generated-hcon-hlist
Hopefully there is room for speedup in Scalac for this.
I measured the following compile times on my machine:
Clearly the compile times are exponential in the length of the HList.
Reproduce code:
The text was updated successfully, but these errors were encountered: