Takes 30+% off the startup time for scala/scala...

Takes 30+% off the startup time for scala/scalac with a variety of
optimizations pinpointed by tracing method invocations. Frequent guest
stars in the parade of slowness were: using Lists and ListBuffers when
any amount of random access is needed, using Strings as if one shouldn't
have to supply 80 characters of .substring noise to drop a character
here and there, imagining that code can be reused in any way shape
or form without a savage slowness burn being unleashed upon you and
everything you have ever loved, String.format, methods which return
tuples, and any method written with appealing scala features which turns
out to be called a few orders of magnitude more often than the author
probably supposed.

This may be only the tip of the iceberg. No review.

1 files changed, 122 insertions, 103 deletions

diff --git a/src/compiler/scala/tools/nsc/util/ClassPath.scala b/src/compiler/scala/tools/nsc/util/ClassPath.scala
index 40c3316e09..e1cf6e55d9 100644
--- a/src/compiler/scala/tools/nsc/util/ClassPath.scala
+++ b/src/compiler/scala/tools/nsc/util/ClassPath.scala
@@ -8,7 +8,7 @@ package scala.tools.nsc
 package util
 
 import java.net.URL
-import scala.collection.mutable.ListBuffer
+import scala.collection.mutable
 import io.{ File, Directory, Path, Jar, AbstractFile, ClassAndJarInfo }
 import scala.tools.util.StringOps.splitWhere
 import Jar.isJarOrZip
@@ -55,21 +55,21 @@ object ClassPath {
    *    (name, list of origins)
    *  in the order they occur on the path.
    */
-  def findDuplicates(cp: ClassPath[_]) = {
-    def toFullName(x: (String, _, cp.AnyClassRep)) = x._1 + "." + x._3.name
-    def toOriginString(x: ClassPath[_]) = x.origin getOrElse x.name
-
-    /** Flatten everything into tuples, recombine grouped by name, filter down to 2+ entries. */
-    val flattened = (
-      for ((pkgName, pkg) <- cp.allPackagesWithNames ; clazz <- pkg.classes) yield
-        (pkgName, pkg, clazz)
-    )
-    val multipleAppearingEntries = flattened groupBy toFullName filter (_._2.size > 1)
-
-    /** Extract results. */
-    for (name <- flattened map toFullName distinct ; dups <- multipleAppearingEntries get name) yield
-      (name, dups map { case (_, cp, _) => toOriginString(cp) })
-  }
+  // def findDuplicates(cp: ClassPath[_]) = {
+  //   def toFullName(x: (String, _, cp.AnyClassRep)) = x._1 + "." + x._3.name
+  //   def toOriginString(x: ClassPath[_]) = x.origin getOrElse x.name
+  //
+  //   /** Flatten everything into tuples, recombine grouped by name, filter down to 2+ entries. */
+  //   val flattened = (
+  //     for ((pkgName, pkg) <- cp.allPackagesWithNames ; clazz <- pkg.classes) yield
+  //       (pkgName, pkg, clazz)
+  //   )
+  //   val multipleAppearingEntries = flattened groupBy toFullName filter (_._2.size > 1)
+  //
+  //   /** Extract results. */
+  //   for (name <- flattened map toFullName distinct ; dups <- multipleAppearingEntries get name) yield
+  //     (name, dups map { case (_, cp, _) => toOriginString(cp) })
+  // }
 
   /** Split classpath using platform-dependent path separator */
   def split(path: String): List[String] = (path split pathSeparator).toList filterNot (_ == "") distinct
@@ -149,7 +149,9 @@ object ClassPath {
       for (url <- specToURL(spec).toList ; location <- Option(AbstractFile getURL url)) yield
         newClassPath(location)
 
-    def classesInExpandedPath(path: String) = classesInPathImpl(path, true)
+    def classesInExpandedPath(path: String): IndexedSeq[ClassPath[T]] =
+      classesInPathImpl(path, true).toIndexedSeq
+
     def classesInPath(path: String) = classesInPathImpl(path, false)
 
     // Internal
@@ -160,8 +162,9 @@ object ClassPath {
 
   class JavaContext extends ClassPathContext[AbstractFile] {
     def toBinaryName(rep: AbstractFile) = {
-      assert(rep.name endsWith ".class", rep.name)
-      rep.name dropRight 6
+      val name = rep.name
+      assert(name.length > 6 && name.substring(name.length - 6) == ".class", name)
+      name.substring(0, name.length - 6)
     }
     def newClassPath(dir: AbstractFile) = new DirectoryClassPath(dir, this)
   }
@@ -173,13 +176,13 @@ object ClassPath {
   /** From the source file to its identifier.
    */
   def toSourceName(f: AbstractFile): String = {
-    val nme = f.name
-    if (nme.endsWith(".scala"))
-      nme dropRight 6
-    else if (nme.endsWith(".java"))
-      nme dropRight 5
+    val name = f.name
+    if (name.length > 6 && name.substring(name.length - 6) == ".scala")
+      name.substring(0, name.length - 6)
+    else if (name.length > 5 && name.substring(name.length - 5) == ".java")
+      name.substring(0, name.length - 5)
     else
-      throw new FatalError("Unexpected source file ending: " + nme)
+      throw new FatalError("Unexpected source file ending: " + name)
   }
 }
 import ClassPath._
@@ -215,29 +218,29 @@ abstract class ClassPath[T] {
 
   /** Lists of entities.
    */
-  def classes: List[AnyClassRep]
-  def packages: List[ClassPath[T]]
-  def sourcepaths: List[AbstractFile]
+  def classes: IndexedSeq[AnyClassRep]
+  def packages: IndexedSeq[ClassPath[T]]
+  def sourcepaths: IndexedSeq[AbstractFile]
 
   /** Information which entails walking the tree.  This is probably only
    *  necessary for tracking down problems - it's normally not used.
    */
-  def allPackages: List[ClassPath[T]] = packages ::: (packages flatMap (_.allPackages))
-  def allPackageNames: List[String] = {
-    def subpackages(prefix: String, cp: ClassPath[T]): List[String] = (
-      (cp.packages map (prefix + _.name)) :::
-      (cp.packages flatMap (x => subpackages(prefix + x.name + ".", x)))
-    )
-    subpackages("", this)
-  }
-  def allPackagesWithNames: List[(String, ClassPath[T])] = {
-    val root = packages map (p => p.name -> p)
-    val subs =
-      for ((prefix, p) <- root ; (k, v) <- p.allPackagesWithNames) yield
-        (prefix + "." + k, v)
-
-    root ::: subs
-  }
+  // def allPackages: List[ClassPath[T]] = packages ::: (packages flatMap (_.allPackages))
+  // def allPackageNames: List[String] = {
+  //   def subpackages(prefix: String, cp: ClassPath[T]): List[String] = (
+  //     (cp.packages map (prefix + _.name)) :::
+  //     (cp.packages flatMap (x => subpackages(prefix + x.name + ".", x)))
+  //   )
+  //   subpackages("", this)
+  // }
+  // def allPackagesWithNames: List[(String, ClassPath[T])] = {
+  //   val root = packages map (p => p.name -> p)
+  //   val subs =
+  //     for ((prefix, p) <- root ; (k, v) <- p.allPackagesWithNames) yield
+  //       (prefix + "." + k, v)
+  //
+  //   root ::: subs
+  // }
 
   /**
    * Represents classes which can be loaded with a ClassfileLoader/MSILTypeLoader
@@ -297,17 +300,17 @@ class SourcePath[T](dir: AbstractFile, val context: ClassPathContext[T]) extends
   override def origin = dir.underlyingSource map (_.path)
   def asURLs = dir.sfile.toList map (_.toURL)
   def asClasspathString = dir.path
-  val sourcepaths: List[AbstractFile] = List(dir)
+  val sourcepaths: IndexedSeq[AbstractFile] = IndexedSeq(dir)
 
-  lazy val classes: List[ClassRep] = dir flatMap { f =>
+  lazy val classes: IndexedSeq[ClassRep] = dir flatMap { f =>
     if (f.isDirectory || !validSourceFile(f.name)) Nil
     else List(ClassRep(None, Some(f)))
-  } toList
+  } toIndexedSeq
 
-  lazy val packages: List[SourcePath[T]] = dir flatMap { f =>
+  lazy val packages: IndexedSeq[SourcePath[T]] = dir flatMap { f =>
     if (f.isDirectory && validPackage(f.name)) List(new SourcePath[T](f, context))
     else Nil
-  } toList
+  } toIndexedSeq
 
   override def toString() = "sourcepath: "+ dir.toString()
 }
@@ -320,17 +323,17 @@ class DirectoryClassPath(val dir: AbstractFile, val context: ClassPathContext[Ab
   override def origin = dir.underlyingSource map (_.path)
   def asURLs = dir.sfile.toList map (_.toURL)
   def asClasspathString = dir.path
-  val sourcepaths: List[AbstractFile] = Nil
+  val sourcepaths: IndexedSeq[AbstractFile] = IndexedSeq()
 
-  lazy val classes: List[ClassRep] = dir flatMap { f =>
+  lazy val classes: IndexedSeq[ClassRep] = dir flatMap { f =>
     if (f.isDirectory || !validClassFile(f.name)) Nil
     else List(ClassRep(Some(f), None))
-  } toList
+  } toIndexedSeq
 
-  lazy val packages: List[DirectoryClassPath] = dir flatMap { f =>
+  lazy val packages: IndexedSeq[DirectoryClassPath] = dir flatMap { f =>
     if (f.isDirectory && validPackage(f.name)) List(new DirectoryClassPath(f, context))
     else Nil
-  } toList
+  } toIndexedSeq
 
   override def toString() = "directory classpath: "+ dir
 }
@@ -339,90 +342,106 @@ class DirectoryClassPath(val dir: AbstractFile, val context: ClassPathContext[Ab
  * A classpath unifying multiple class- and sourcepath entries.
  */
 class MergedClassPath[T](
-  val entries: List[ClassPath[T]],
+  val entries: IndexedSeq[ClassPath[T]],
   val context: ClassPathContext[T])
 extends ClassPath[T] {
+  def this(entries: TraversableOnce[ClassPath[T]], context: ClassPathContext[T]) =
+    this(entries.toIndexedSeq, context)
+
   def name = entries.head.name
-  def asURLs = entries flatMap (_.asURLs)
-  lazy val sourcepaths: List[AbstractFile] = entries flatMap (_.sourcepaths)
+  def asURLs = entries flatMap (_.asURLs) toList
+  lazy val sourcepaths: IndexedSeq[AbstractFile] = entries flatMap (_.sourcepaths)
 
   override def origin = Some(entries map (x => x.origin getOrElse x.name) mkString ("Merged(", ", ", ")"))
   override def asClasspathString: String = join(entries map (_.asClasspathString) : _*)
 
-  lazy val classes: List[AnyClassRep] = {
-    val cls = new ListBuffer[AnyClassRep]
+  lazy val classes: IndexedSeq[AnyClassRep] = {
+    var count   = 0
+    val indices = mutable.HashMap[String, Int]()
+    val cls     = new mutable.ArrayBuffer[AnyClassRep](1024)
+
     for (e <- entries; c <- e.classes) {
       val name = c.name
-      val idx = cls.indexWhere(_.name == name)
-      if (idx >= 0) {
+      if (indices contains name) {
+        val idx      = indices(name)
         val existing = cls(idx)
+
         if (existing.binary.isEmpty && c.binary.isDefined)
           cls(idx) = existing.copy(binary = c.binary)
         if (existing.source.isEmpty && c.source.isDefined)
           cls(idx) = existing.copy(source = c.source)
-      } else {
+      }
+      else {
+        indices(name) = count
         cls += c
+        count += 1
       }
     }
-    cls.toList
+    cls.toIndexedSeq
   }
 
-  lazy val packages: List[ClassPath[T]] = {
-    val pkg = new ListBuffer[ClassPath[T]]
+  lazy val packages: IndexedSeq[ClassPath[T]] = {
+    var count   = 0
+    val indices = mutable.HashMap[String, Int]()
+    val pkg     = new mutable.ArrayBuffer[ClassPath[T]](256)
+
     for (e <- entries; p <- e.packages) {
       val name = p.name
-      val idx = pkg.indexWhere(_.name == name)
-      if (idx >= 0) {
+      if (indices contains name) {
+        val idx  = indices(name)
         pkg(idx) = addPackage(pkg(idx), p)
-      } else {
+      }
+      else {
+        indices(name) = count
         pkg += p
+        count += 1
       }
     }
-    pkg.toList
+    pkg.toIndexedSeq
   }
 
   private def addPackage(to: ClassPath[T], pkg: ClassPath[T]) = {
-    val newEntries = to match {
+    val newEntries: IndexedSeq[ClassPath[T]] = to match {
       case cp: MergedClassPath[_] => cp.entries :+ pkg
-      case _                      => List(to, pkg)
+      case _                      => IndexedSeq(to, pkg)
     }
     new MergedClassPath[T](newEntries, context)
   }
-
-  override def allPackages: List[ClassPath[T]] = entries flatMap (_.allPackages)
-  override def allPackageNames = entries flatMap (_.allPackageNames)
-  override def allPackagesWithNames = entries flatMap (_.allPackagesWithNames)
-
-  def duplicatedClasses = {
-    def toFullName(x: (String, _, AnyClassRep)) = x._1 + "." + x._3.name
-
-    /** Flatten everything into tuples, recombine grouped by name, filter down to 2+ entries. */
-    val flattened = (
-      for ((pkgName, pkg) <- allPackagesWithNames ; clazz <- pkg.classes) yield
-        (pkgName, pkg, clazz)
-    )
-    val multipleAppearingEntries = flattened groupBy toFullName filter (_._2.size > 1)
-
-    /** Using original name list as reference point, return duplicated entries as
-     *    (name, list of origins)
-     *  in the order they occur on the path.
-     */
-    for (name <- flattened map toFullName distinct ; dups <- multipleAppearingEntries get name) yield
-      (name, dups map {
-        case (_, cp, _) if cp.origin.isDefined  => cp.origin.get
-        case (_, cp, _)                         => cp.asURLs.mkString
-      })
-  }
-
+  //
+  // override def allPackages: List[ClassPath[T]] = entries flatMap (_.allPackages)
+  // override def allPackageNames = entries flatMap (_.allPackageNames)
+  // override def allPackagesWithNames = entries flatMap (_.allPackagesWithNames)
+  //
+  // def duplicatedClasses = {
+  //   def toFullName(x: (String, _, AnyClassRep)) = x._1 + "." + x._3.name
+  //
+  //   /** Flatten everything into tuples, recombine grouped by name, filter down to 2+ entries. */
+  //   val flattened = (
+  //     for ((pkgName, pkg) <- allPackagesWithNames ; clazz <- pkg.classes) yield
+  //       (pkgName, pkg, clazz)
+  //   )
+  //   val multipleAppearingEntries = flattened groupBy toFullName filter (_._2.size > 1)
+  //
+  //   /** Using original name list as reference point, return duplicated entries as
+  //    *    (name, list of origins)
+  //    *  in the order they occur on the path.
+  //    */
+  //   for (name <- flattened map toFullName distinct ; dups <- multipleAppearingEntries get name) yield
+  //     (name, dups map {
+  //       case (_, cp, _) if cp.origin.isDefined  => cp.origin.get
+  //       case (_, cp, _)                         => cp.asURLs.mkString
+  //     })
+  // }
+  //
   def show() {
     println("ClassPath %s has %d entries and results in:\n".format(name, entries.size))
     asClasspathString split ':' foreach (x => println("  " + x))
   }
-  def showDuplicates() =
-    ClassPath findDuplicates this foreach {
-      case (name, xs) => println(xs.mkString(name + ":\n  ", "\n  ", "\n"))
-    }
-
+  // def showDuplicates() =
+  //   ClassPath findDuplicates this foreach {
+  //     case (name, xs) => println(xs.mkString(name + ":\n  ", "\n  ", "\n"))
+  //   }
+  //
   override def toString() = "merged classpath "+ entries.mkString("(", "\n", ")")
 }
 
@@ -431,7 +450,7 @@ extends ClassPath[T] {
  * as AbstractFile. nsc.io.ZipArchive is used to view zip/jar archives as directories.
  */
 class JavaClassPath(
-  containers: List[ClassPath[AbstractFile]],
+  containers: IndexedSeq[ClassPath[AbstractFile]],
   context: JavaContext)
 extends MergedClassPath[AbstractFile](containers, context) {
 }