diff options
author | Adriaan Moors <adriaan.moors@epfl.ch> | 2012-07-19 04:30:05 -0700 |
---|---|---|
committer | Adriaan Moors <adriaan.moors@epfl.ch> | 2012-07-19 04:30:05 -0700 |
commit | 9377625260699cd0d9f0aa2de2dce66edd0fca5a (patch) | |
tree | 813e7802cf90522545beca2ff95bb4f33e93e660 | |
parent | d9b65592df28e8c9655b52c0265f499d757617ba (diff) | |
parent | d905558749cceff50e9872efb490450c54b6bd81 (diff) | |
download | scala-9377625260699cd0d9f0aa2de2dce66edd0fca5a.tar.gz scala-9377625260699cd0d9f0aa2de2dce66edd0fca5a.tar.bz2 scala-9377625260699cd0d9f0aa2de2dce66edd0fca5a.zip |
Merge pull request #906 from adriaanm/optimize-findmember
Optimize findmember
-rw-r--r-- | src/compiler/scala/tools/nsc/Driver.scala | 4 | ||||
-rw-r--r-- | src/compiler/scala/tools/nsc/Main.scala | 6 | ||||
-rw-r--r-- | src/compiler/scala/tools/nsc/MainBench.scala | 48 | ||||
-rw-r--r-- | src/compiler/scala/tools/nsc/typechecker/RefChecks.scala | 2 | ||||
-rw-r--r-- | src/compiler/scala/tools/nsc/typechecker/Typers.scala | 7 | ||||
-rw-r--r-- | src/reflect/scala/reflect/api/StandardNames.scala | 1 | ||||
-rw-r--r-- | src/reflect/scala/reflect/internal/Names.scala | 3 | ||||
-rw-r--r-- | src/reflect/scala/reflect/internal/Scopes.scala | 20 | ||||
-rw-r--r-- | src/reflect/scala/reflect/internal/StdNames.scala | 2 | ||||
-rw-r--r-- | src/reflect/scala/reflect/internal/Types.scala | 202 | ||||
-rw-r--r-- | src/reflect/scala/reflect/runtime/SymbolLoaders.scala | 4 |
11 files changed, 226 insertions, 73 deletions
diff --git a/src/compiler/scala/tools/nsc/Driver.scala b/src/compiler/scala/tools/nsc/Driver.scala index 0051c3bdec..15e2929ff1 100644 --- a/src/compiler/scala/tools/nsc/Driver.scala +++ b/src/compiler/scala/tools/nsc/Driver.scala @@ -1,10 +1,12 @@ package scala.tools.nsc import scala.tools.nsc.reporters.{Reporter, ConsoleReporter} -import Properties.{ versionString, copyrightString } +import Properties.{ versionString, copyrightString, residentPromptString } import scala.reflect.internal.util.{ BatchSourceFile, FakePos } abstract class Driver { + + val prompt = residentPromptString val versionMsg = "Scala compiler " + versionString + " -- " + diff --git a/src/compiler/scala/tools/nsc/Main.scala b/src/compiler/scala/tools/nsc/Main.scala index 19c872b6d3..8b7e76e994 100644 --- a/src/compiler/scala/tools/nsc/Main.scala +++ b/src/compiler/scala/tools/nsc/Main.scala @@ -12,15 +12,13 @@ import scala.tools.nsc.interactive.{ RefinedBuildManager, SimpleBuildManager } import scala.tools.nsc.io.AbstractFile import scala.tools.nsc.reporters.{Reporter, ConsoleReporter} import scala.reflect.internal.util.{ BatchSourceFile, FakePos } //{Position} -import Properties.{ versionString, copyrightString, residentPromptString, msilLibPath } +import Properties.msilLibPath /** The main class for NSC, a compiler for the programming - * language Scala. + * language Scala. */ object Main extends Driver with EvalLoop { - val prompt = residentPromptString - def resident(compiler: Global) { loop { line => val args = line.split(' ').toList diff --git a/src/compiler/scala/tools/nsc/MainBench.scala b/src/compiler/scala/tools/nsc/MainBench.scala new file mode 100644 index 0000000000..0037de7b94 --- /dev/null +++ b/src/compiler/scala/tools/nsc/MainBench.scala @@ -0,0 +1,48 @@ +/* NSC -- new Scala compiler + * Copyright 2005-2011 LAMP/EPFL + * @author Martin Odersky + */ + +package scala.tools.nsc + +import java.io.File +import File.pathSeparator + +import scala.tools.nsc.interactive.{ RefinedBuildManager, SimpleBuildManager } +import scala.tools.nsc.io.AbstractFile +import scala.tools.nsc.reporters.{Reporter, ConsoleReporter} +import scala.reflect.internal.util.{ BatchSourceFile, FakePos } //{Position} +import Properties.{ versionString, copyrightString, residentPromptString, msilLibPath } +import scala.reflect.internal.util.Statistics + +/** The main class for NSC, a compiler for the programming + * language Scala. + */ +object MainBench extends Driver with EvalLoop { + + lazy val theCompiler = Global(settings, reporter) + + override def newCompiler() = theCompiler + + val NIter = 50 + val NBest = 10 + + override def main(args: Array[String]) = { + val times = new Array[Long](NIter) + var start = System.nanoTime() + for (i <- 0 until NIter) { + if (i == NIter-1) { + theCompiler.settings.Ystatistics.value = true + Statistics.enabled = true + } + process(args) + val end = System.nanoTime() + val duration = (end-start)/1000000 + println(s"${duration}ms") + times(i) = duration + start = end + } + val avg = times.sorted.take(NBest).sum / NBest + println(s"avg shortest $NBest times ${avg}ms") + } +} diff --git a/src/compiler/scala/tools/nsc/typechecker/RefChecks.scala b/src/compiler/scala/tools/nsc/typechecker/RefChecks.scala index 7318538de7..3518316fbb 100644 --- a/src/compiler/scala/tools/nsc/typechecker/RefChecks.scala +++ b/src/compiler/scala/tools/nsc/typechecker/RefChecks.scala @@ -119,7 +119,7 @@ abstract class RefChecks extends InfoTransform with reflect.internal.transform.R // those with the DEFAULTPARAM flag, and infer the methods. Looking for the methods // directly requires inspecting the parameter list of every one. That modification // shaved 95% off the time spent in this method. - val defaultGetters = clazz.info.findMember(nme.ANYNAME, 0L, DEFAULTPARAM, false).alternatives + val defaultGetters = clazz.info.findMembers(0L, DEFAULTPARAM) val defaultMethodNames = defaultGetters map (sym => nme.defaultGetterToMethod(sym.name)) defaultMethodNames.distinct foreach { name => diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala index a570cd74d6..9371af4848 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala @@ -4509,6 +4509,8 @@ trait Typers extends Modes with Adaptations with Tags { assert(errorContainer == null, "Cannot set ambiguous error twice for identifier") errorContainer = tree } + + val fingerPrint: Long = name.fingerPrint var defSym: Symbol = tree.symbol // the directly found symbol var pre: Type = NoPrefix // the prefix type of defSym, if a class member @@ -4547,7 +4549,10 @@ trait Typers extends Modes with Adaptations with Tags { var cx = startingIdentContext while (defSym == NoSymbol && cx != NoContext && (cx.scope ne null)) { // cx.scope eq null arises during FixInvalidSyms in Duplicators pre = cx.enclClass.prefix - defEntry = cx.scope.lookupEntry(name) + defEntry = { + val scope = cx.scope + if ((fingerPrint & scope.fingerPrints) != 0) scope.lookupEntry(name) else null + } if ((defEntry ne null) && qualifies(defEntry.sym)) { // Right here is where SI-1987, overloading in package objects, can be // seen to go wrong. There is an overloaded symbol, but when referring diff --git a/src/reflect/scala/reflect/api/StandardNames.scala b/src/reflect/scala/reflect/api/StandardNames.scala index 9ec66b8531..eb1ecda900 100644 --- a/src/reflect/scala/reflect/api/StandardNames.scala +++ b/src/reflect/scala/reflect/api/StandardNames.scala @@ -43,7 +43,6 @@ trait StandardNames extends base.StandardNames { val SUPER_PREFIX_STRING: String val TRAIT_SETTER_SEPARATOR_STRING: String - val ANYNAME: TermName val FAKE_LOCAL_THIS: TermName val INITIALIZER: TermName val LAZY_LOCAL: TermName diff --git a/src/reflect/scala/reflect/internal/Names.scala b/src/reflect/scala/reflect/internal/Names.scala index 20da38fd63..72e6707f57 100644 --- a/src/reflect/scala/reflect/internal/Names.scala +++ b/src/reflect/scala/reflect/internal/Names.scala @@ -415,6 +415,9 @@ trait Names extends api.Names with LowPriorityNames { } else toString } + + @inline + final def fingerPrint: Long = (1L << start) /** TODO - find some efficiency. */ def append(ch: Char) = newName("" + this + ch) diff --git a/src/reflect/scala/reflect/internal/Scopes.scala b/src/reflect/scala/reflect/internal/Scopes.scala index ceacd2afb0..89e3c52de6 100644 --- a/src/reflect/scala/reflect/internal/Scopes.scala +++ b/src/reflect/scala/reflect/internal/Scopes.scala @@ -41,10 +41,15 @@ trait Scopes extends api.Scopes { self: SymbolTable => * This is necessary because when run from reflection every scope needs to have a * SynchronizedScope as mixin. */ - class Scope protected[Scopes] (initElems: ScopeEntry = null) extends Iterable[Symbol] { + class Scope protected[Scopes] (initElems: ScopeEntry = null, initFingerPrints: Long = 0L) extends Iterable[Symbol] { + + /** A bitset containing the last 6 bits of the start value of every name + * stored in this scope. + */ + var fingerPrints: Long = initFingerPrints protected[Scopes] def this(base: Scope) = { - this(base.elems) + this(base.elems, base.fingerPrints) nestinglevel = base.nestinglevel + 1 } @@ -95,7 +100,7 @@ trait Scopes extends api.Scopes { self: SymbolTable => * * @param e ... */ - protected def enter(e: ScopeEntry) { + protected def enterEntry(e: ScopeEntry) { elemsCache = null if (hashtable ne null) enterInHash(e) @@ -113,7 +118,11 @@ trait Scopes extends api.Scopes { self: SymbolTable => * * @param sym ... */ - def enter[T <: Symbol](sym: T): T = { enter(newScopeEntry(sym, this)); sym } + def enter[T <: Symbol](sym: T): T = { + fingerPrints |= sym.name.fingerPrint + enterEntry(newScopeEntry(sym, this)) + sym + } /** enter a symbol, asserting that no symbol with same name exists in scope * @@ -147,6 +156,7 @@ trait Scopes extends api.Scopes { self: SymbolTable => } def rehash(sym: Symbol, newname: Name) { + fingerPrints |= newname.fingerPrint if (hashtable ne null) { val index = sym.name.start & HASHMASK var e1 = hashtable(index) @@ -344,7 +354,7 @@ trait Scopes extends api.Scopes { self: SymbolTable => /** The empty scope (immutable). */ object EmptyScope extends Scope { - override def enter(e: ScopeEntry) { + override def enterEntry(e: ScopeEntry) { abort("EmptyScope.enter") } } diff --git a/src/reflect/scala/reflect/internal/StdNames.scala b/src/reflect/scala/reflect/internal/StdNames.scala index 165e04863c..c8a2424118 100644 --- a/src/reflect/scala/reflect/internal/StdNames.scala +++ b/src/reflect/scala/reflect/internal/StdNames.scala @@ -297,7 +297,7 @@ trait StdNames { val WHILE_PREFIX = "while$" // Compiler internal names - val ANYNAME: NameType = "<anyname>" + val ANYname: NameType = "<anyname>" val CONSTRUCTOR: NameType = "<init>" val EQEQ_LOCAL_VAR: NameType = "eqEqTemp$" val FAKE_LOCAL_THIS: NameType = "this$" diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala index f3dd1f03ad..01679a777d 100644 --- a/src/reflect/scala/reflect/internal/Types.scala +++ b/src/reflect/scala/reflect/internal/Types.scala @@ -14,6 +14,7 @@ import Flags._ import scala.util.control.ControlThrowable import scala.annotation.tailrec import util.Statistics +import scala.runtime.ObjectRef /* A standard type pattern match: case ErrorType => @@ -668,7 +669,8 @@ trait Types extends api.Types { self: SymbolTable => * Note: unfortunately it doesn't work to exclude DEFERRED this way. */ def membersBasedOnFlags(excludedFlags: Long, requiredFlags: Long): List[Symbol] = - findMember(nme.ANYNAME, excludedFlags, requiredFlags, false).alternatives + findMembers(excludedFlags, requiredFlags) +// findMember(nme.ANYNAME, excludedFlags, requiredFlags, false).alternatives def memberBasedOnName(name: Name, excludedFlags: Long): Symbol = findMember(name, excludedFlags, 0, false) @@ -1018,6 +1020,72 @@ trait Types extends api.Types { self: SymbolTable => else (baseClasses.head.newOverloaded(this, alts)) } + def findMembers(excludedFlags: Long, requiredFlags: Long): List[Symbol] = { + // if this type contains type variables, put them to sleep for a while -- don't just wipe them out by + // replacing them by the corresponding type parameter, as that messes up (e.g.) type variables in type refinements + // without this, the matchesType call would lead to type variables on both sides + // of a subtyping/equality judgement, which can lead to recursive types being constructed. + // See (t0851) for a situation where this happens. + val suspension: List[TypeVar] = if (this.isGround) null else suspendTypeVarsInType(this) + + Statistics.incCounter(findMembersCount) + val start = Statistics.pushTimer(typeOpsStack, findMembersNanos) + + //Console.println("find member " + name.decode + " in " + this + ":" + this.baseClasses)//DEBUG + var members: Scope = null + var required = requiredFlags + var excluded = excludedFlags | DEFERRED + var continue = true + var self: Type = null + while (continue) { + continue = false + val bcs0 = baseClasses + var bcs = bcs0 + while (!bcs.isEmpty) { + val decls = bcs.head.info.decls + var entry = decls.elems + while (entry ne null) { + val sym = entry.sym + val flags = sym.flags + if ((flags & required) == required) { + val excl = flags & excluded + if (excl == 0L && + (// omit PRIVATE LOCALS unless selector class is contained in class owning the def. + (bcs eq bcs0) || + (flags & PrivateLocal) != PrivateLocal || + (bcs0.head.hasTransOwner(bcs.head)))) { + if (members eq null) members = newScope + var others: ScopeEntry = members.lookupEntry(sym.name) + var symtpe: Type = null + while ((others ne null) && { + val other = others.sym + (other ne sym) && + ((other.owner eq sym.owner) || + (flags & PRIVATE) != 0 || { + if (self eq null) self = this.narrow + if (symtpe eq null) symtpe = self.memberType(sym) + !(self.memberType(other) matches symtpe) + })}) { + others = members lookupNextEntry others + } + if (others eq null) members enter sym + } else if (excl == DEFERRED) { + continue = true + } + } + entry = entry.next + } // while (entry ne null) + // excluded = excluded | LOCAL + bcs = bcs.tail + } // while (!bcs.isEmpty) + required |= DEFERRED + excluded &= ~(DEFERRED.toLong) + } // while (continue) + Statistics.popTimer(typeOpsStack, start) + if (suspension ne null) suspension foreach (_.suspended = false) + if (members eq null) Nil else members.toList + } + /** * Find member(s) in this type. If several members matching criteria are found, they are * returned in an OverloadedSymbol @@ -1040,75 +1108,83 @@ trait Types extends api.Types { self: SymbolTable => val start = Statistics.pushTimer(typeOpsStack, findMemberNanos) //Console.println("find member " + name.decode + " in " + this + ":" + this.baseClasses)//DEBUG - var members: Scope = null var member: Symbol = NoSymbol + var members: List[Symbol] = null + var lastM: ::[Symbol] = null + var membertpe: Type = null + var required = requiredFlags var excluded = excludedFlags | DEFERRED var continue = true var self: Type = null - var membertpe: Type = null + val fingerPrint: Long = name.fingerPrint + while (continue) { continue = false val bcs0 = baseClasses var bcs = bcs0 while (!bcs.isEmpty) { val decls = bcs.head.info.decls - var entry = - if (name == nme.ANYNAME) decls.elems else decls.lookupEntry(name) - while (entry ne null) { - val sym = entry.sym - if (sym hasAllFlags requiredFlags) { - val excl = sym.getFlag(excluded) - if (excl == 0L && - (// omit PRIVATE LOCALS unless selector class is contained in class owning the def. - (bcs eq bcs0) || - !sym.isPrivateLocal || - (bcs0.head.hasTransOwner(bcs.head)))) { - if (name.isTypeName || stableOnly && sym.isStable) { - Statistics.popTimer(typeOpsStack, start) - if (suspension ne null) suspension foreach (_.suspended = false) - return sym - } else if (member == NoSymbol) { - member = sym - } else if (members eq null) { - if (member.name != sym.name || - !(member == sym || - member.owner != sym.owner && - !sym.isPrivate && { - if (self eq null) self = this.narrow - if (membertpe eq null) membertpe = self.memberType(member) - (membertpe matches self.memberType(sym)) - })) { - members = newScope - members enter member - members enter sym - } - } else { - var prevEntry = members.lookupEntry(sym.name) - var symtpe: Type = null - while ((prevEntry ne null) && - !(prevEntry.sym == sym || - prevEntry.sym.owner != sym.owner && - !sym.hasFlag(PRIVATE) && { - if (self eq null) self = this.narrow - if (symtpe eq null) symtpe = self.memberType(sym) - self.memberType(prevEntry.sym) matches symtpe - })) { - prevEntry = members lookupNextEntry prevEntry - } - if (prevEntry eq null) { - members enter sym + if ((fingerPrint & decls.fingerPrints) != 0) { + var entry = decls.lookupEntry(name) + while (entry ne null) { + val sym = entry.sym + val flags = sym.flags + if ((flags & required) == required) { + val excl = flags & excluded + if (excl == 0L && + (// omit PRIVATE LOCALS unless selector class is contained in class owning the def. + (bcs eq bcs0) || + (flags & PrivateLocal) != PrivateLocal || + (bcs0.head.hasTransOwner(bcs.head)))) { + if (name.isTypeName || stableOnly && sym.isStable) { + Statistics.popTimer(typeOpsStack, start) + if (suspension ne null) suspension foreach (_.suspended = false) + return sym + } else if (member eq NoSymbol) { + member = sym + } else if (members eq null) { + if ((member ne sym) && + ((member.owner eq sym.owner) || + (flags & PRIVATE) != 0 || { + if (self eq null) self = this.narrow + if (membertpe eq null) membertpe = self.memberType(member) + !(membertpe matches self.memberType(sym)) + })) { + lastM = new ::(sym, null) + members = member :: lastM + } + } else { + var others: List[Symbol] = members + var symtpe: Type = null + while ((others ne null) && { + val other = others.head + (other ne sym) && + ((other.owner eq sym.owner) || + (flags & PRIVATE) != 0 || { + if (self eq null) self = this.narrow + if (symtpe eq null) symtpe = self.memberType(sym) + !(self.memberType(other) matches symtpe) + })}) { + others = others.tail + } + if (others eq null) { + val lastM1 = new ::(sym, null) + lastM.tl = lastM1 + lastM = lastM1 + } } + } else if (excl == DEFERRED) { + continue = true } - } else if (excl == DEFERRED.toLong) { - continue = true } - } - entry = if (name == nme.ANYNAME) entry.next else decls lookupNextEntry entry - } // while (entry ne null) + entry = decls lookupNextEntry entry + } // while (entry ne null) + } // if (fingerPrint matches) // excluded = excluded | LOCAL bcs = if (name == nme.CONSTRUCTOR) Nil else bcs.tail } // while (!bcs.isEmpty) - excluded = excludedFlags + required |= DEFERRED + excluded &= ~(DEFERRED.toLong) } // while (continue) Statistics.popTimer(typeOpsStack, start) if (suspension ne null) suspension foreach (_.suspended = false) @@ -1117,9 +1193,11 @@ trait Types extends api.Types { self: SymbolTable => member } else { Statistics.incCounter(multMemberCount) - baseClasses.head.newOverloaded(this, members.toList) + lastM.tl = Nil + baseClasses.head.newOverloaded(this, members) } } + /** The (existential or otherwise) skolems and existentially quantified variables which are free in this type */ def skolemsExceptMethodTypeParams: List[Symbol] = { var boundSyms: List[Symbol] = List() @@ -1610,8 +1688,13 @@ trait Types extends api.Types { self: SymbolTable => if (period != currentPeriod) { tpe.baseClassesPeriod = currentPeriod if (!isValidForBaseClasses(period)) { - tpe.baseClassesCache = null - tpe.baseClassesCache = tpe.memo(computeBaseClasses)(tpe.typeSymbol :: _.baseClasses.tail) + val start = Statistics.pushTimer(typeOpsStack, baseClassesNanos) + try { + tpe.baseClassesCache = null + tpe.baseClassesCache = tpe.memo(computeBaseClasses)(tpe.typeSymbol :: _.baseClasses.tail) + } finally { + Statistics.popTimer(typeOpsStack, start) + } } } if (tpe.baseClassesCache eq null) @@ -5066,7 +5149,7 @@ trait Types extends api.Types { self: SymbolTable => */ def needsOuterTest(patType: Type, selType: Type, currentOwner: Symbol) = { def createDummyClone(pre: Type): Type = { - val dummy = currentOwner.enclClass.newValue(nme.ANYNAME).setInfo(pre.widen) + val dummy = currentOwner.enclClass.newValue(nme.ANYname).setInfo(pre.widen) singleType(ThisType(currentOwner.enclClass), dummy) } def maybeCreateDummyClone(pre: Type, sym: Symbol): Type = pre match { @@ -6909,14 +6992,17 @@ object TypesStats { val lubCount = Statistics.newCounter ("#toplevel lubs/glbs") val nestedLubCount = Statistics.newCounter ("#all lubs/glbs") val findMemberCount = Statistics.newCounter ("#findMember ops") + val findMembersCount = Statistics.newCounter ("#findMembers ops") val noMemberCount = Statistics.newSubCounter(" of which not found", findMemberCount) val multMemberCount = Statistics.newSubCounter(" of which multiple overloaded", findMemberCount) val typerNanos = Statistics.newTimer ("time spent typechecking", "typer") val lubNanos = Statistics.newStackableTimer("time spent in lubs", typerNanos) val subtypeNanos = Statistics.newStackableTimer("time spent in <:<", typerNanos) val findMemberNanos = Statistics.newStackableTimer("time spent in findmember", typerNanos) + val findMembersNanos = Statistics.newStackableTimer("time spent in findmembers", typerNanos) val asSeenFromNanos = Statistics.newStackableTimer("time spent in asSeenFrom", typerNanos) val baseTypeSeqNanos = Statistics.newStackableTimer("time spent in baseTypeSeq", typerNanos) + val baseClassesNanos = Statistics.newStackableTimer("time spent in baseClasses", typerNanos) val compoundBaseTypeSeqCount = Statistics.newSubCounter(" of which for compound types", baseTypeSeqCount) val typerefBaseTypeSeqCount = Statistics.newSubCounter(" of which for typerefs", baseTypeSeqCount) val singletonBaseTypeSeqCount = Statistics.newSubCounter(" of which for singletons", baseTypeSeqCount) diff --git a/src/reflect/scala/reflect/runtime/SymbolLoaders.scala b/src/reflect/scala/reflect/runtime/SymbolLoaders.scala index c1cd5d2911..eb48e9dc79 100644 --- a/src/reflect/scala/reflect/runtime/SymbolLoaders.scala +++ b/src/reflect/scala/reflect/runtime/SymbolLoaders.scala @@ -99,8 +99,10 @@ trait SymbolLoaders { self: SymbolTable => 0 < dp && dp < (name.length - 1) } - class PackageScope(pkgClass: Symbol) extends Scope() with SynchronizedScope { + class PackageScope(pkgClass: Symbol) extends Scope(initFingerPrints = -1L) // disable fingerprinting as we do not know entries beforehand + with SynchronizedScope { assert(pkgClass.isType) + // disable fingerprinting as we do not know entries beforehand private val negatives = mutable.Set[Name]() // Syncnote: Performance only, so need not be protected. override def lookupEntry(name: Name): ScopeEntry = { val e = super.lookupEntry(name) |