diff options
author | Jason Zaugg <jzaugg@gmail.com> | 2015-02-18 14:02:08 +1000 |
---|---|---|
committer | Jason Zaugg <jzaugg@gmail.com> | 2015-02-18 14:16:56 +1000 |
commit | b6cbee9d81320524aa2e8a3d80dbf2062dd43fd2 (patch) | |
tree | c20dab2c227285ff184a4a83e6d0e8ee37cf0983 | |
parent | da49d9a00ec373a0e7f2ffe946a897a65c9b0741 (diff) | |
download | scala-b6cbee9d81320524aa2e8a3d80dbf2062dd43fd2.tar.gz scala-b6cbee9d81320524aa2e8a3d80dbf2062dd43fd2.tar.bz2 scala-b6cbee9d81320524aa2e8a3d80dbf2062dd43fd2.zip |
SI-9157 Avoid exponential blowup with chained type projections
Calling `findMember` in the enclosed test was calling into
`NonClassTypeRef#relativeInfo` an exponentially-increasing number
of times, with respect to the length of the chained type projections.
The numbers of calls increased as: 26, 326, 3336, 33446, 334556.
Can any pattern spotters in the crowd that can identify the sequence?
(I can't.)
Tracing the calls saw we were computing the same `memberType`
repeatedly. This part of the method was not guarded by the cache.
I have changed the method to use the standard idiom of using the
current period for cache invalidation. The enclosed test now compiles
promptly, rather than in geological time.
-rw-r--r-- | src/compiler/scala/tools/nsc/typechecker/TreeCheckers.scala | 1 | ||||
-rw-r--r-- | src/reflect/scala/reflect/internal/Types.scala | 10 | ||||
-rw-r--r-- | test/files/pos/t9157.scala | 13 |
3 files changed, 18 insertions, 6 deletions
diff --git a/src/compiler/scala/tools/nsc/typechecker/TreeCheckers.scala b/src/compiler/scala/tools/nsc/typechecker/TreeCheckers.scala index 743bbe53bd..02356580cc 100644 --- a/src/compiler/scala/tools/nsc/typechecker/TreeCheckers.scala +++ b/src/compiler/scala/tools/nsc/typechecker/TreeCheckers.scala @@ -266,7 +266,6 @@ abstract class TreeCheckers extends Analyzer { if (tree ne typed) treesDiffer(tree, typed) - tree } diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala index ce36f7efa3..8f114caac0 100644 --- a/src/reflect/scala/reflect/internal/Types.scala +++ b/src/reflect/scala/reflect/internal/Types.scala @@ -1976,13 +1976,13 @@ trait Types * usage scenario. */ private var relativeInfoCache: Type = _ - private var memberInfoCache: Type = _ + private var relativeInfoPeriod: Period = NoPeriod - private[Types] def relativeInfo = { - val memberInfo = pre.memberInfo(sym) - if (relativeInfoCache == null || (memberInfo ne memberInfoCache)) { - memberInfoCache = memberInfo + private[Types] def relativeInfo = /*trace(s"relativeInfo(${safeToString}})")*/{ + if (relativeInfoPeriod != currentPeriod) { + val memberInfo = pre.memberInfo(sym) relativeInfoCache = transformInfo(memberInfo) + relativeInfoPeriod = currentPeriod } relativeInfoCache } diff --git a/test/files/pos/t9157.scala b/test/files/pos/t9157.scala new file mode 100644 index 0000000000..e178b5d84d --- /dev/null +++ b/test/files/pos/t9157.scala @@ -0,0 +1,13 @@ +trait Flow[-In, +Out] { + type Repr[+O] <: Flow[In, O] + def map: Repr[String] +} + +class Test { + // typechecking was exponentially slow wrt the number of projections here. + def slowFlow( + f: Flow[String,String]#Repr[String]#Repr[String]#Repr[String]#Repr[String]#Repr[String]#Repr[String]#Repr[String]#Repr[String]#Repr[String]#Repr[String]#Repr[String] + ) = { + f.map + } +} |