-
Notifications
You must be signed in to change notification settings - Fork 3.1k
Compiler performance improvements around Symbols and Types #5823
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
Conversation
@@ -696,21 +696,23 @@ trait Types | |||
* }}} | |||
*/ | |||
def memberInfo(sym: Symbol): Type = { | |||
// assert(sym ne NoSymbol, this) | |||
require(sym ne NoSymbol, this) |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
this seems to be more than an optimization
@adriaanm: l0rinc@1f6f7f8#diff-ecaa4198a04261cd0e00a708b695eafbL689
*/ | ||
override def boundSyms: Set[Symbol] = emptySymbolSet | ||
|
||
/* |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
minor: you may want to delete commented code instead of formatting it
(thiss eq that) || { | ||
var these = thiss | ||
var those = that | ||
while (!these.isEmpty && !those.isEmpty && these.head.equals(those.head)) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
minor: could probably be while (these.nonEmpty && those.nonEmpty
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I've got a bit of an aversion to nonEmpty
(a mixed in trait method) in hot code because in some cases it is harder for JIT to devirtualize and inline. Not sure whether that's the case here.
@@ -61,6 +61,19 @@ trait Collections { | |||
head | |||
} | |||
|
|||
final def sameElementsEquals(thiss: List[AnyRef], that: List[AnyRef]): Boolean = { | |||
// Probably immutable, so check reference identity first (it's quick anyway) | |||
(thiss eq that) || { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
question: this inlining of thiss.sameElements(that)
seems like a micro-optimization to my untrained eye :)
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
The key difference is using .equals
rather than .==
. The latter is routed through BoxesRuntime.equals
which needs to perform a few type tests on the operands before delegating to equals
in order to paper over the differences between primitive and boxed numeric equality.
finalizeHash(mix(h, args.hashCode()), 3) | ||
else | ||
finalizeHash(h, 2) | ||
var i = 0 |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
could be inited with 2
to avoid 2 + i
later
@@ -184,8 +184,8 @@ private[internal] trait GlbLubs { | |||
/** Eliminate from list of types all elements which are a supertype | |||
* of some other element of the list. */ | |||
private def elimSuper(ts: List[Type]): List[Type] = ts match { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I don't claim to understand it, but I have a question:
This seems to be an O(n^2)
operation (i.e. for every element search all remaining). Would it be faster to cache the parents in a Set
and check the set for inconsistencies for the previously encountered parents instead?
That could make it linear, I think.
(would probably be slower if the number of elements is small)
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Type
-s aren't amenable to use in a HashSet
because =:=
isn't compatible with hashCode
. This code here is actually using subtyping, which makes it harder again to find ways to beat O(N^2)
.
@@ -195,8 +195,8 @@ private[internal] trait GlbLubs { | |||
* of some other element of the list. */ | |||
private def elimSub(ts: List[Type], depth: Depth): List[Type] = { | |||
def elimSub0(ts: List[Type]): List[Type] = ts match { | |||
case List() => List() | |||
case List(t) => List(t) | |||
case List() => ts |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
could probably be:
case List() | List(_) => ts
instead
mapOverArgs(args, sym.typeParams) | ||
else | ||
if (trackVariance && args.nonEmpty && !variance.isInvariant) { | ||
val tparams = sym.typeParams |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
minor: to make it more obvious what happened to the sym.typeParams.nonEmpty
part of the if
, this could probably be simplified to
if (sym.typeParams.nonEmpty) mapOverArgs(args, sym.typeParams)
else args mapConserve this
@@ -722,9 +722,20 @@ private[internal] trait TypeMaps { | |||
else subst(tp, sym, from.tail, to.tail) | |||
) | |||
|
|||
private def fromContains(syms: Set[Symbol]): Boolean = { | |||
if (!syms.isEmpty) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
minor: can probably be syms.nonEmpty && {
case Nil => Nil | ||
@tailrec | ||
def loop(xs: List[Symbol], result: List[Symbol]): List[Symbol] = xs match { | ||
case Nil => result | ||
case x :: xs => |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
minor: could also be y :: ys
to avoid name collision with parent match
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Looking good!
@@ -3604,7 +3604,10 @@ trait Types | |||
if (sym.isAliasType && sameLength(sym.info.typeParams, args) && !sym.lockOK) | |||
throw new RecoverableCyclicReference(sym) | |||
|
|||
TypeRef(pre, sym, args) | |||
if ((args eq Nil) && (pre eq NoPrefix)) | |||
sym.tpeHK // opt lean on TypeSymbol#tyconCache, rather than interning a type ref. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Could this be pushed further down into TypeRef.apply
?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
IIRC, we can't (easily) do that because tpeHK
calls that TypeRef.apply
, so we'd loop.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
OK, I see.. We could clean up TypeRef construction one day.
@@ -1085,7 +1085,8 @@ trait Types | |||
override def baseTypeSeq: BaseTypeSeq = supertype.baseTypeSeq | |||
override def baseTypeSeqDepth: Depth = supertype.baseTypeSeqDepth | |||
override def baseClasses: List[Symbol] = supertype.baseClasses | |||
} | |||
override def boundSyms: Set[Symbol] = emptySymbolSet |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
since mapOver
recurses into components, it seems there are some unnecessary calls to resultType.boundSyms
:
MethodType
override def boundSyms = resultType.boundSyms ++ params
PolyType
override def boundSyms = immutable.Set[Symbol](typeParams ++ resultType.boundSyms: _*)
and an unnecessary override in NullaryMethodType
override def boundSyms = resultType.boundSyms
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Yep, I agree. Things seem to work with your proposed changes. I'm pushed a commit that actually avoids calling boundSyms
altogether, which avoids the overhead of creating sets just to check if one of the from
symbols exists in there, I'm pretty sure it will be faster to iterate over, e.g, MethodSymbol#typeParams
directly and compare search for element to from
.
We can actually short-circuit that search in many cases by pre-computing the range of symbol ids in from
and by noting whether it has any term symbols.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Cool! boundSyms
already confused me not long ago (I don't remember the details).
@@ -3788,7 +3788,7 @@ trait Types | |||
private var uniques: util.WeakHashSet[Type] = _ | |||
private var uniqueRunId = NoRunId | |||
|
|||
protected def unique[T <: Type](tp: T): T = { | |||
protected def unique[T <: Type](tp: T): T = { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
@@ -2928,6 +2938,34 @@ trait Symbols extends api.Symbols { self: SymbolTable => | |||
// are a case accessor (you can also be a field.) | < F438 /tr>|||
override def isCaseAccessorMethod = isCaseAccessor | |||
|
|||
def typeAsMemberOf(pre: Type): Type = { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Found 2 binary incompatibilities (22 were filtered out)
=======================================================
* abstract synthetic method
scala$reflect$runtime$SynchronizedSymbols$SynchronizedMethodSymbol$$$outer()scala.reflect.runtime.SynchronizedSymbols
in interface
scala.reflect.runtime.SynchronizedSymbols#SynchronizedMethodSymbol is
present only in current version
* abstract synthetic method
scala$reflect$runtime$SynchronizedSymbols$SynchronizedMethodSymbol$$super$typeAsMemberOf(scala.reflect.internal.Types#Type)scala.reflect.internal.Types#Type
in interface
scala.reflect.runtime.SynchronizedSymbols#SynchronizedMethodSymbol is
present only in current version
@@ -23,9 +23,6 @@ trait Namers extends MethodSynthesis { | |||
import global._ |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
i cannot find the commit referenced in the commit message (8dc4dbf0edde0f83b76c6a31d1f741689fa2e67b), i guess it's 1f6f7f8
if (mtpeRunId == currentRunId) { | ||
if ((mtpePre eq pre) && (mtpeInfo eq info)) return { | ||
mtpeResult | ||
} |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
could merge the two if
s, also the return block is a bit funny
computeMemberType(sym) | ||
} | ||
|
||
def computeMemberType(sym: Symbol): Type = sym.tpeHK match { //@M don't prematurely instantiate higher-kinded types, they will be instantiated by transform, typedTypeApply, etc. when really necessary |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
the comment can probably be dropped, since adriaan removed it in 1f6f7f8
createFromClonedSymbols(bs, restp)((ps1, tp1) => PolyType(ps1, renameBoundSyms(tp1))) | ||
case ExistentialType(bs, restp) => | ||
case MethodType(ps, restp) if fromHasTermSymbol && fromContains(ps) => | ||
createFromClonedSymbols(ps, restp)((ps1, tp1) => copyMethodType(tp, ps1, tp1)) |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I don't understand why we don't need the recursive calls to renameBoundSyms
anymore.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
The result of this method is recursed into with mapOver
, so we'll get back to here with the result type.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Would be good to elaborate on this in a comment
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
The result of this method is recursed into with mapOver, so we'll get back to here with the result type.
Actually, taking another look at this, I think there is a potential problem with existential types, as newExistentialType
collapses nested existential types. If some construction of existentials snuck past that, and an ExistentialType(qs1, ExistentialType(qs2, res))
appeared here, we'd fail to look at qs2
.
/** A creator for existential types which flattens nested existentials.
*/
def newExistentialType(quantified: List[Symbol], underlying: Type): Type =
if (quantified.isEmpty) underlying
else underlying match {
case ExistentialType(qs, restpe) => newExistentialType(quantified ::: qs, restpe)
case _ => ExistentialType(quantified, underlying)
}
As per @adriaanm's offline suggestion, I'm going to split this change into a separate PR and address the review comments there.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Actually, the old code was already assuming existentials has been flattened.
My measurements suggest that the last two commits (removing |
Very nice! |
3af9df6
to
b9c0dad
Compare
// a local class symbol. We can no longer assume that`mtpePre eq pre` is a sufficient condition | ||
// to use the cached result here. | ||
// | ||
// Rather than throwing away the baby with the bathwater, lets at least try to keep the caching |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
👍
case tp => | ||
// Correct caching is nearly impossible because `sym.tpeHK.asSeenFrom(pre, sym.owner)` |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Is this comment worth keeping around?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
The first thing I'm going to type tomorrow is // is this comment worth keeping?
I hope I don't accidentally read it six months from now, because it would blow my brain i.e. mind. The other one I should plant for my future self is // what were you thinking?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
// Ceci n'est pas un commentaire
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
// comment?
val symHiInfo = symHi.info | ||
if (symHiInfo == WildcardType) { | ||
if (symHi.isTerm) (!symHi.isStable || symLo.isStable) // sub-member must remain stable | ||
else true |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Are we guaranteed symHi.isAbstractType
in this case? Can an alias type's info
ever be a wildcard? (If so, the lower symbol's info must also be a wildcard)
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
The common case that I'm trying to optimize is when symHi
is the member of a prototype for HasMember
(e.g { def extensionMethod: ?}
). I'll tweak this to restrict this new fast path to
symHiInfo == WildcardType && symHi.isTerm` and let types flow down the the logic below.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I've pushed this change now.
val r1 = tp1.typeSymbolDirect.isNonBottomSubClass(tp2.typeSymbolDirect) // OPT faster than comparing eta-expanded types | ||
val r2 = isSub(tp1.normalize, tp2.normalize) | ||
if (r1 != r2) | ||
getClass |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
stray debug artifact?
createFromClonedSymbols(bs, restp)((ps1, tp1) => PolyType(ps1, renameBoundSyms(tp1))) | ||
case ExistentialType(bs, restp) => | ||
case MethodType(ps, restp) if fromHasTermSymbol && fromContains(ps) => | ||
createFromClonedSymbols(ps, restp)((ps1, tp1) => copyMethodType(tp, ps1, tp1)) |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Would be good to elaborate on this in a comment
@@ -698,18 +703,30 @@ private[internal] trait TypeMaps { | |||
// OPT this check was 2-3% of some profiles, demoted to -Xdev | |||
if (isDeveloper) assert(sameLength(from, to), "Unsound substitution from "+ from +" to "+ to) | |||
|
|||
private[this] var fromHasTermSymbol = false | |||
private[this] var fromMin = Int.MaxValue |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Kind of like a mini-bloom filter?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Funny, I was re-reading about bloom filters while making this change. I guess this is kindred (we can cheaply determine non-existence in a set without iterating the full set), but OTOH we there isn't any superimposition of information.
I did learn about an Zatocoding in my travels, sort of an analog bloom filter for librarians.
Like using AnyRefMap, we can optimize this datastructure with the knowledge that is only holds AnyRef-s, and we can bypass BoxesRuntime for equality/hashing.
For a no-args, no-prefix type ref, we can bypass the call to TypeRef.apply, and with it, the hash-consing of the type, by asking the Symbol for its type constructor ref, which is cached.
Avoids the megamorphic call to `Type#annotations` in favour of an instanceof check.
We find our way to this method with wildcard types in the search for implicit views. This commit short circuits the computation in this case, avoiding an as-seen-from operation on the low symbol's info
This method is call in symbol substitution, which is a hot path during typechecking. This commit observes that certain types of types don't define any bound symbols, and immediately returns an empty set. These types of types are: ThisType this.type SuperType A.super.B ConstantType 42 SingleType foo.type TypeBounds >: L <: B When a type reports an empty set of bound symbols, symbol substution _does_ recurse into the compoments of the type (with `mapOver`), so we still find bound symbols, for instances, an existential type in one of the type bounds. Before this commit, calling `ThisType#boundSyms` came to the same result via the implementation inherited from `SimpleTypeProxy`, which incurred an needless call to `ThisType#typeOfThis`.
If we arrive at this method with NoSymbol as the candidate symbol, avoid an as-seen-from on the low side of the comparison.
Directly call hashCode on the arguments, rather than indirecting through ##.
Avoid use of BoxesRuntime equals in favour of direct use of Object#equals.
Unfortunately, we've had to add a lot more casts into the code to workaround corner cases in the Fields transform. This commit avoids an inefficiency in synthesizing these trees, by avoid a call to as-seen-from.
babf510
to
6998cf1
Compare
I believe I've addressed the review comments here. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Awesome job, please update the description with the latest stats
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
The subtype change LGTM, but have a question on the sameType one.
def retry(lhs: Type, rhs: Type) = ((lhs ne tp1) || (rhs ne tp2)) && isSameType(lhs, rhs) | ||
def retry(lhs: Type, rhs: Type) = ((lhs ne tp1) || (rhs ne tp2)) && { | ||
def sameSyms(tp1: Type, tp2: Type) = tp1.typeSymbolDirect eq tp2.typeSymbolDirect | ||
val skipRetry = lhs.isInstanceOf[PolyType] && rhs.isInstanceOf[PolyType] && sameSyms(tp1, lhs) && sameSyms(tp2, rhs) |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Could you convince me that we don't need to take into account potential differences in type params / type application due to normalization? I'm not sure how, but I'm also not sure it's impossible that normalizePlus
could take e.g., [T, U](T, U)
to [T, U](U, T)
for one of rhs
/lhs
, so that now [T,U]Swap[U,T] =:= [T,U]Tuple2[T,U]
Also, this feels easier to follow:
val skipRetry =
(lhs eq tp1) && (rhs eq tp2) ||
(lhs.isInstanceOf[PolyType] && rhs.isInstanceOf[PolyType] && sameSyms(tp1, lhs) && sameSyms(tp2, rhs))
!skipRetry && isSameType(lhs, rhs)
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I've reworked that commit a to be more in line with the subtyping change (computing skip
before actually calling normalize
). Given that it is pretty subtle, let's take our time to review it in #5885, rather than in this omnibus.
Restrict the fast path to term symbols (which is the important case for performance) to allow the existing code to handle type symbols.
@paplorinc I've added the benchmark results to the description. |
@retronym the |
The benchmark runs for a fixed duration, so after the speed up then count of executions is higher The results suggest a 3.5% speed up. 1251/1299 |
Thanks, good job! |
Conflicts: src/reflect/scala/reflect/internal/Types.scala Conflict was trivial related to commented out code.
@adriaanm I've resolved the merge conflict here. |
Seems to bring about 4% in aggregate.
Thematically cherry-picked from #5785
UPDATE : benchmark results, with the latest iteration of this PR.
Before:
After: