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.

5 files changed, 172 insertions, 125 deletions

diff --git a/src/compiler/scala/tools/nsc/io/Path.scala b/src/compiler/scala/tools/nsc/io/Path.scala
index 3cfab55aaa..beae4b8647 100644
--- a/src/compiler/scala/tools/nsc/io/Path.scala
+++ b/src/compiler/scala/tools/nsc/io/Path.scala
@@ -159,10 +159,18 @@ class Path private[io] (val jfile: JFile) {
     if (p isSame this) Nil else p :: p.parents
   }
   // if name ends with an extension (e.g. "foo.jpg") returns the extension ("jpg"), otherwise ""
-  def extension: String = (name lastIndexOf '.') match {
-    case -1   => ""
-    case idx  => name drop (idx + 1)
+  def extension: String = {
+    var i = name.length - 1
+    while (i >= 0 && name.charAt(i) != '.')
+      i -= 1
+
+    if (i < 0) ""
+    else name.substring(i + 1)
   }
+  // def extension: String = (name lastIndexOf '.') match {
+  //   case -1   => ""
+  //   case idx  => name drop (idx + 1)
+  // }
   // compares against extensions in a CASE INSENSITIVE way.
   def hasExtension(ext: String, exts: String*) = {
     val xs = (ext +: exts) map (_.toLowerCase)
diff --git a/src/compiler/scala/tools/nsc/io/ZipArchive.scala b/src/compiler/scala/tools/nsc/io/ZipArchive.scala
index 22121cc714..52d6c41354 100644
--- a/src/compiler/scala/tools/nsc/io/ZipArchive.scala
+++ b/src/compiler/scala/tools/nsc/io/ZipArchive.scala
@@ -138,8 +138,8 @@ private[io] trait ZipContainer extends AbstractFile {
         if (dir.entry == null) dir.entry = entry
       }
       else {
-        val (home, name) = splitPath(path)
-        _parent = getDir(dirs, home)
+        _parent = getDir(dirs, pathFront(path))
+        val name = pathRear(path)
         _parent.entries(name) = FileEntryConstructor(f(this), name, path, entry)
       }
     }
@@ -149,13 +149,28 @@ private[io] trait ZipContainer extends AbstractFile {
       root
     }
   }
-
-  protected def splitPath(path: String): (String, String) = {
-    (path lastIndexOf '/') match {
-      case -1   => ("/", path)
-      case idx  => path splitAt (idx + 1)
-    }
+  // Uglified for performance.
+  // protected def splitPath(path: String): (String, String) = {
+  //   (path lastIndexOf '/') match {
+  //     case -1   => ("/", path)
+  //     case idx  => path splitAt (idx + 1)
+  //   }
+  // }
+  protected def splitPath(path: String, front: Boolean): String = {
+    var i = path.length - 1
+    while (i >= 0 && path.charAt(i) != '/')
+      i -= 1
+
+    if (i < 0)
+      if (front) "/"
+      else path
+    else
+      if (front) path.substring(0, i + 1)
+      else path.substring(i + 1)
   }
+  private def pathFront(path: String) = splitPath(path, true)
+  private def pathRear(path: String) = splitPath(path, false)
+  // End uglify.
 
   /**
    * Returns the abstract file in this abstract directory with the
@@ -181,9 +196,12 @@ private[io] trait ZipContainer extends AbstractFile {
    */
   protected def getDir(dirs: Map[String, DirEntryInterface], path: String): DirEntryInterface =
     dirs.getOrElseUpdate(path, {
-      val (home, name) = splitPath(path init)
-      val parent = getDir(dirs, home)
-      val dir = DirEntryConstructor(parent, name, path)
+      val pathTail = path.substring(0, path.length - 1)
+      val home     = pathFront(pathTail)
+      val name     = pathRear(pathTail)
+      val parent   = getDir(dirs, home)
+      val dir      = DirEntryConstructor(parent, name, path)
+
       parent.entries(name + path.last) = dir
       dir
     })
@@ -218,7 +236,7 @@ final class ZipArchive(file: File, val archive: ZipFile) extends PlainFile(file)
   ) extends VirtualFile(name, path)
   {
     override def underlyingSource = Some(self)
-    final override def path = "%s(%s)".format(self, super.path)
+    final override def path = self + "(" + super.path + ")"
     final def archive = self.archive
 
     override def hashCode = super.hashCode + container.hashCode
@@ -291,7 +309,7 @@ final class URLZipArchive(url: URL) extends AbstractFile with ZipContainer {
   def container = unsupported
 
   abstract class Entry(name: String, path: String) extends VirtualFile(name, path) {
-    final override def path = "%s(%s)".format(URLZipArchive.this, super.path)
+    final override def path = URLZipArchive.this + "(" + super.path + ")"
     override def container = URLZipArchive.this
   }
   final class DirEntry(name: String, path: String) extends Entry(name, path) with DirEntryInterface {
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) {
 }
diff --git a/src/compiler/scala/tools/nsc/util/MsilClassPath.scala b/src/compiler/scala/tools/nsc/util/MsilClassPath.scala
index 7a6f42c420..13fb3185ab 100644
--- a/src/compiler/scala/tools/nsc/util/MsilClassPath.scala
+++ b/src/compiler/scala/tools/nsc/util/MsilClassPath.scala
@@ -135,7 +135,7 @@ class AssemblyClassPath(types: Array[MSILType], namespace: String, val context:
         cls += ClassRep(Some(types(i)), None)
       i += 1
     }
-    cls.toList
+    cls.toIndexedSeq
   }
 
   lazy val packages = {
@@ -152,11 +152,13 @@ class AssemblyClassPath(types: Array[MSILType], namespace: String, val context:
       }
       i += 1
     }
-    for (ns <- nsSet.toList)
+    val xs = for (ns <- nsSet.toList)
       yield new AssemblyClassPath(types, ns, context)
+
+    xs.toIndexedSeq
   }
 
-  val sourcepaths: List[AbstractFile] = Nil
+  val sourcepaths: IndexedSeq[AbstractFile] = IndexedSeq()
 
   override def toString() = "assembly classpath "+ namespace
 }
diff --git a/src/compiler/scala/tools/util/PathResolver.scala b/src/compiler/scala/tools/util/PathResolver.scala
index b1a5ba6d46..1420499e91 100644
--- a/src/compiler/scala/tools/util/PathResolver.scala
+++ b/src/compiler/scala/tools/util/PathResolver.scala
@@ -10,7 +10,7 @@ import java.net.{ URL, MalformedURLException }
 import scala.util.Properties._
 import nsc.{ Settings, GenericRunnerSettings }
 import nsc.util.{ ClassPath, JavaClassPath, ScalaClassLoader }
-import nsc.io.{ File, Directory, Path }
+import nsc.io.{ File, Directory, Path, AbstractFile }
 import ClassPath.{ JavaContext, DefaultJavaContext, join, split }
 import PartialFunction.condOpt
 
@@ -193,7 +193,7 @@ class PathResolver(settings: Settings, context: JavaContext) {
     import context._
 
     // Assemble the elements!
-    def basis = List(
+    def basis = List[Traversable[ClassPath[AbstractFile]]](
       classesInPath(javaBootClassPath),             // 1. The Java bootstrap class path.
       contentsOfDirsInPath(javaExtDirs),            // 2. The Java extension class path.
       classesInExpandedPath(javaUserClassPath),     // 3. The Java application class path.
@@ -228,7 +228,7 @@ class PathResolver(settings: Settings, context: JavaContext) {
   def containers = Calculated.containers
 
   lazy val result = {
-    val cp = new JavaClassPath(containers, context)
+    val cp = new JavaClassPath(containers.toIndexedSeq, context)
     if (settings.Ylogcp.value) {
       Console.println("Classpath built from " + settings.toConciseString)
       Console.println("Defaults: " + PathResolver.Defaults)