Compilation times of record operations could be improved

[jonifreeman]

As a simple performance test consider a class below. Uncomment line by line and measure the build time.

object Test {
  val r =
    ("k01" ->> 1) :: ("k02" ->> 1) :: ("k03" ->> 1) :: ("k04" ->> 1) :: ("k05" ->> 1) ::
    ("k06" ->> 1) :: ("k07" ->> 1) :: ("k08" ->> 1) :: ("k09" ->> 1) :: ("k10" ->> 1) ::
    ("k11" ->> 1) :: ("k12" ->> 1) :: ("k13" ->> 1) :: ("k14" ->> 1) :: ("k15" ->> 1) ::
    ("k16" ->> 1) :: ("k17" ->> 1) :: ("k18" ->> 1) :: ("k19" ->> 1) :: ("k20" ->> 1) ::
    ("k21" ->> 1) :: ("k22" ->> 1) :: ("k23" ->> 1) :: ("k24" ->> 1) :: ("k25" ->> 1) ::
    ("k26" ->> 1) :: ("k27" ->> 1) :: ("k28" ->> 1) :: ("k29" ->> 1) :: ("k30" ->> 1) ::
    ("k31" ->> 1) :: ("k32" ->> 1) :: ("k33" ->> 1) :: ("k34" ->> 1) :: ("k35" ->> 1) :: HNil

  // r get "k01"
  // r get "k02"
  // r get "k03"
  // r get "k04"
  // r get "k05"
  // r get "k10"
  // r get "k20"
}

Times on my machine with current Shapeless.

// r get "k01"  // 1s
// r get "k02"  // 4s
// r get "k03"  // 7s
// r get "k04"  // 10s
// r get "k05"  // 12s
// r get "k10"  // 21s
// r get "k20"  // 30s

Using Witnesses is more expensive than objects as keys.

object k01; object k02; object k03; object k04; object k05; object k06; object k07; object k08;
object k09; object k10; object k11; object k12; object k13; object k14; object k15; object k16;
object k17; object k18; object k19; object k20; object k21; object k22; object k23; object k24;
object k25; object k26; object k27; object k28; object k29; object k30; object k31; object k32;
object k33; object k34; object k35

object Test2 {
  val r =
    (k01 -> 1) :: (k02 -> 1) :: (k03 -> 1) :: (k04 -> 1) :: (k05 -> 1) ::
    (k06 -> 1) :: (k07 -> 1) :: (k08 -> 1) :: (k09 -> 1) :: (k10 -> 1) ::
    (k11 -> 1) :: (k12 -> 1) :: (k13 -> 1) :: (k14 -> 1) :: (k15 -> 1) ::
    (k16 -> 1) :: (k17 -> 1) :: (k18 -> 1) :: (k19 -> 1) :: (k20 -> 1) ::
    (k21 -> 1) :: (k22 -> 1) :: (k23 -> 1) :: (k24 -> 1) :: (k25 -> 1) ::
    (k26 -> 1) :: (k27 -> 1) :: (k28 -> 1) :: (k29 -> 1) :: (k30 -> 1) ::
    (k31 -> 1) :: (k32 -> 1) :: (k33 -> 1) :: (k34 -> 1) :: (k35 -> 1) :: HNil

  // r get k01
  // r get k02
  // r get k03
  // r get k04
  // r get k05
  // r get k10
  // r get k20
}

Times on my machine with current Shapeless.

// r get k01  // 1s
// r get k02  // 2s
// r get k03  // 4s
// r get k04  // 5s
// r get k05  // 6s
// r get k10  // 9s
// r get k20  // 12s

Switching to

type FieldType[K, V] = (K, V)

improves compilation times.

// Witnesses as keys
// r get "k01"  // 1s
// r get "k02"  // 3s
// r get "k03"  // 5s
// r get "k04"  // 6s
// r get "k05"  // 7s
// r get "k10"  // 12s
// r get "k20"  // 16s

// Objects as keys
// r get k01  // 1s
// r get k02  // 2s
// r get k03  // 2s
// r get k04  // 3s
// r get k05  // 3s
// r get k10  // 5s
// r get k20  // 7s

Getting beyond that is perhaps not possible in Shapeless and further optimizations should be done in scalac?

[milessabin]

See also #102.

[gabro]

Is there any other update on this issue?
I've implemented a little record-based module in my project and since I've started using it extensively, compilation time went up from ~30 seconds to several minutes.

My code uses Witnesses of Symbols as keys.
This, combined with this other issue, is really getting in the way, and my productivity drops whenever I need to touch any part of the code that uses records.

[milessabin]

At the moment I'm afraid not ... this is going to need a Scala compiler fix to eliminate the pathological behaviour for String singleton types. My current plan is to investigate this in typelevel/scala#41 and if successful feed a patch back to scala/scala.

[gabro]

Thanks for the immediate feedback, Miles

[retronym]

I'm afraid that constant type stringification isn't the true pathology here. It's easy enough to speed it up (scala/scala@2.11.x...retronym:ticket/perf-constant-type-string), but it doesn't make an appreciable different to this benchmark.

Similarly, avoiding more needless anonymous subsclass of SingletonOps (master...retronym:topic/record-perf) is a worthwhile change, but again only adjusts a constant factor.

I believe that the quadratic factor comes from the implicit search for a record.Selector peeling the hlist apart one element at a time. Compiling the example with -Xlog-implicits is helpful to see how much work is going on during the implicit search.

One solution here would be to "intrinsify" this operation into a single implicit macro that internalized the recursion over the hlist type.

As a starting point, here is a method that determines the index of a tag within the hlist type. It is just a POC, a real implementation should be more robust against unexpected types.

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

    def indexOf(s: String, hlistType: Type, i: Int = 0): Int = {
      val hnilTpe = typeOf[HNil]
      val hconsClass = typeOf[::[_, _]].typeSymbol
      val keyTagClass = typeOf[labelled.KeyTag[_, _]].typeSymbol
      def loop(tp: Type, i: Int): Int = {
        if (tp <:< hnilTpe) -1
        else {
          val TypeRef(_, _, List(head, tail)) = tp.baseType(hconsClass)
          val TypeRef(_, _, List(tag, _)) = head.baseType(keyTagClass)
          tag match {
            case ConstantType(Constant(`s`)) => i
            case _ => loop(tail, i + 1)
          }
        }
      }
      loop(hlistType, 0)
    }


  import shapeless._
  import record._
  import ops.hlist.ToList
  import ops.record.{ Keys, Values }
  import syntax.singleton._

  val r =
    ("k01" ->> 1) :: ("k02" ->> 1) :: ("k03" ->> 1) :: ("k04" ->> 1) :: ("k05" ->> 1) ::
    ("k06" ->> 1) :: ("k07" ->> 1) :: ("k08" ->> 1) :: ("k09" ->> 1) :: ("k10" ->> 1) ::
    ("k11" ->> 1) :: ("k12" ->> 1) :: ("k13" ->> 1) :: ("k14" ->> 1) :: ("k15" ->> 1) ::
    ("k16" ->> 1) :: ("k17" ->> 1) :: ("k18" ->> 1) :: ("k19" ->> 1) :: ("k20" ->> 1) ::
    ("k21" ->> 1) :: ("k22" ->> 1) :: ("k23" ->> 1) :: ("k24" ->> 1) :: ("k25" ->> 1) ::
    ("k26" ->> 1) :: ("k27" ->> 1) :: ("k28" ->> 1) :: ("k29" ->> 1) :: ("k30" ->> 1) ::
    ("k31" ->> 1) :: ("k32" ->> 1) :: ("k33" ->> 1) :: ("k34" ->> 1) :: ("k35" ->> 1) :: HNil

// Exiting paste mode, now interpreting.

indexOf: (s: String, hlistType: $r.intp.global.Type, i: Int)Int
import shapeless._
import record._
import ops.hlist.ToList
import ops.record.{Keys, Values}
import syntax.singleton._
r: shapeless.::[Int with shapeless.labelled.KeyTag[String("k01"),Int],shapeless.::[Int with shapeless.labelled.KeyTag[String("k02"),Int],shapeless.::[Int with shapeless.labelled.KeyTag[String("k03"),Int],shapeless.::[Int with shapeless.labelled.KeyTag[String("k04"),Int],shapeless.::[Int with shapeless.labelled.KeyTag[String("k05"),Int],shapeless.::[Int with shapeless.labelled.KeyTag[String("k06"),Int],shapeless.::[Int with shapeless.labelled.KeyTag[String("k07"),Int],shapeless.::[Int with shapeless.labelled.KeyTag[String("k08"),Int],shapeless.::[Int with shapeless.labelled.KeyTag[String("k09"),Int],shapeless...

scala> indexOf("k01", typeOf[r.type])
res26: Int = 0

scala> indexOf("k10",  typeOf[r.type])
res27: Int = 9

scala> indexOf("xxx",  typeOf[r.type])
res28: Int = -1

[milessabin]

Thanks for the analysis @retronym. I'll pursue something along these lines in shapeless 3.0.

[pchlupacek]

@milessabin any chance this can get addresses for 2.2.x? Any more complex patterns are making compile times to explode :-(

[milessabin]

@pchlupacek are you able to test @retronym's suggested indexOf in your specific context?

[pchlupacek]

@milessabin will do (need to understand it first). In fact I think there is something really weird going on. I have feelings that compilation times gets longer and longer for the same code within sbt. At least I can prove that fresh sbt build takes much less (~1/3) of compilation time after using the sbt for the while.

[milessabin]

If you're able to pull out something representative which shows non-linear scaling of compile times along the lines of the example here or in #381 or #420 that would be incredibly helpful.

[milessabin]

Fixed along the lines suggested by @retronym.

[pchlupacek]

@milessabin excellent thanks. Will test it agains this fix and let you know.

[jamborta]

We have a deep nested structure to parse from case classes to shapeless records which is very slow, takes almost 20 minutes to compile. Any suggestion how that can be improved?