Compilation times of record operations could be improved about shapeless HOT 13 CLOSED

See also #102.

from shapeless.

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.

from shapeless.

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.

from shapeless.

Thanks for the immediate feedback, Miles

from shapeless.

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

from shapeless.

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

from shapeless.

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

from shapeless.

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

from shapeless.

@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.

from shapeless.

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.

from shapeless.

Fixed along the lines suggested by @retronym.

from shapeless.

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

from shapeless.

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?

from shapeless.