From 99dad60d984d3f72338f3bad4c4fe905090edd51 Mon Sep 17 00:00:00 2001 From: Som Snytt Date: Thu, 25 Feb 2016 13:41:20 -0800 Subject: SI-7898 Read user input during REPL warmup The compiler is created on main thread and user input is read on an aux thread (opposite to currently). Fixes completion when `-i` is supplied. Now `-i` means pasted and new option `-I` means line-by-line. The temporary reader uses postInit to swap in the underlying reader. Completion is disabled for the temporary reader, rather than blocking while it waits for a compiler. But manically hitting tab is one way of knowing exactly when completion is live. --- .../scala/tools/nsc/GenericRunnerCommand.scala | 1 + .../scala/tools/nsc/GenericRunnerSettings.scala | 8 +- src/repl/scala/tools/nsc/interpreter/ILoop.scala | 165 ++++++++++++++------- .../tools/nsc/interpreter/InteractiveReader.scala | 95 ++++++++++++ 4 files changed, 212 insertions(+), 57 deletions(-) (limited to 'src') diff --git a/src/compiler/scala/tools/nsc/GenericRunnerCommand.scala b/src/compiler/scala/tools/nsc/GenericRunnerCommand.scala index 24496fa013..bab612bad5 100644 --- a/src/compiler/scala/tools/nsc/GenericRunnerCommand.scala +++ b/src/compiler/scala/tools/nsc/GenericRunnerCommand.scala @@ -79,6 +79,7 @@ Other startup options: -howtorun what to run (default: guess) -i preload before starting the repl + -I preload , enforcing line-by-line interpretation -e execute as if entered in the repl -save save the compiled script in a jar for future use -nc no compilation daemon: do not use the fsc offline compiler diff --git a/src/compiler/scala/tools/nsc/GenericRunnerSettings.scala b/src/compiler/scala/tools/nsc/GenericRunnerSettings.scala index 1289d55c37..d1f8db048b 100644 --- a/src/compiler/scala/tools/nsc/GenericRunnerSettings.scala +++ b/src/compiler/scala/tools/nsc/GenericRunnerSettings.scala @@ -20,10 +20,16 @@ class GenericRunnerSettings(error: String => Unit) extends Settings(error) { "guess") val loadfiles = + MultiStringSetting( + "-I", + "file", + "load a file line-by-line") + + val pastefiles = MultiStringSetting( "-i", "file", - "load a file (assumes the code is given interactively)") + "paste a file") val execute = StringSetting( diff --git a/src/repl/scala/tools/nsc/interpreter/ILoop.scala b/src/repl/scala/tools/nsc/interpreter/ILoop.scala index adac438b37..adaf3a5d25 100644 --- a/src/repl/scala/tools/nsc/interpreter/ILoop.scala +++ b/src/repl/scala/tools/nsc/interpreter/ILoop.scala @@ -175,10 +175,19 @@ class ILoop(in0: Option[BufferedReader], protected val out: JPrintWriter) echo("\n" + msg) in.redrawLine() } - protected def echo(msg: String) = { + protected var mum = false + protected def echo(msg: String) = if (!mum) { out println msg out.flush() } + // turn off intp reporter and our echo + def mumly[A](op: =>A): A = + if (isReplDebug) op + else intp beSilentDuring { + val saved = mum + mum = true + try op finally mum = saved + } /** Search the history */ def searchHistory(_cmdline: String) { @@ -408,12 +417,13 @@ class ILoop(in0: Option[BufferedReader], protected val out: JPrintWriter) * command() for each line of input, and stops when * command() returns false. */ - @tailrec final def loop(): LineResult = { + final def loop(): LineResult = loop(readOneLine()) + + @tailrec final def loop(line: String): LineResult = { import LineResults._ - readOneLine() match { - case null => EOF - case line => if (try processLine(line) catch crashRecovery) loop() else ERR - } + if (line == null) EOF + else if (try processLine(line) catch crashRecovery) loop(readOneLine()) + else ERR } /** interpret all lines from a specified file */ @@ -829,19 +839,7 @@ class ILoop(in0: Option[BufferedReader], protected val out: JPrintWriter) } } - // runs :load `file` on any files passed via -i - def loadFiles(settings: Settings) = settings match { - case settings: GenericRunnerSettings => - for (filename <- settings.loadfiles.value) { - val cmd = ":load " + filename - command(cmd) - addReplay(cmd) - echo("") - } - case _ => - } - - /** Tries to create a JLineReader, falling back to SimpleReader, + /** Tries to create a jline.InteractiveReader, falling back to SimpleReader, * unless settings or properties are such that it should start with SimpleReader. * The constructor of the InteractiveReader must take a Completion strategy, * supplied as a `() => Completion`; the Completion object provides a concrete Completer. @@ -885,49 +883,104 @@ class ILoop(in0: Option[BufferedReader], protected val out: JPrintWriter) } } - private def loopPostInit() { - // Bind intp somewhere out of the regular namespace where - // we can get at it in generated code. - intp.quietBind(NamedParam[IMain]("$intp", intp)(tagOfIMain, classTag[IMain])) - // Auto-run code via some setting. - ( replProps.replAutorunCode.option - flatMap (f => io.File(f).safeSlurp()) - foreach (intp quietRun _) - ) - // classloader and power mode setup - intp.setContextClassLoader() - if (isReplPower) { - replProps.power setValue true - unleashAndSetPhase() - asyncMessage(power.banner) - } - // SI-7418 Now, and only now, can we enable TAB completion. - in.postInit() - } - - // start an interpreter with the given settings + /** Start an interpreter with the given settings. + * @return true if successful + */ def process(settings: Settings): Boolean = savingContextLoader { - this.settings = settings - createInterpreter() - // sets in to some kind of reader depending on environmental cues - in = in0.fold(chooseReader(settings))(r => SimpleReader(r, out, interactive = true)) - globalFuture = future { - intp.initializeSynchronous() - loopPostInit() - !intp.reporter.hasErrors + def newReader = in0.fold(chooseReader(settings))(r => SimpleReader(r, out, interactive = true)) + + /** Reader to use before interpreter is online. */ + def preLoop = { + val sr = SplashReader(newReader) { r => + in = r + in.postInit() + } + in = sr + SplashLoop(sr, prompt) } - loadFiles(settings) - printWelcome() - try loop() match { - case LineResults.EOF => out print Properties.shellInterruptedString - case _ => + /* Actions to cram in parallel while collecting first user input at prompt. + * Run with output muted both from ILoop and from the intp reporter. + */ + def loopPostInit(): Unit = mumly { + // Bind intp somewhere out of the regular namespace where + // we can get at it in generated code. + intp.quietBind(NamedParam[IMain]("$intp", intp)(tagOfIMain, classTag[IMain])) + + // add a help function for anyone who types "help" instead of ":help". Easily shadowed. + //addHelp() + + // Auto-run code via some setting. + ( replProps.replAutorunCode.option + flatMap (f => File(f).safeSlurp()) + foreach (intp quietRun _) + ) + // power mode setup + if (isReplPower) { + replProps.power setValue true + unleashAndSetPhase() + asyncMessage(power.banner) + } + loadInitFiles() + // SI-7418 Now, and only now, can we enable TAB completion. + in.postInit() + } + def loadInitFiles(): Unit = settings match { + case settings: GenericRunnerSettings => + for (f <- settings.loadfiles.value) { + loadCommand(f) + addReplay(s":load $f") + } + for (f <- settings.pastefiles.value) { + pasteCommand(f) + addReplay(s":paste $f") + } + case _ => + } + // TODO: wait until after startup to enable obnoxious settings + def withSuppressedSettings[A](body: =>A): A = { + body } - catch AbstractOrMissingHandler() - finally closeInterpreter() + def startup(): String = withSuppressedSettings { + // starting + printWelcome() - true + // let them start typing + val splash = preLoop + splash.start() + + // while we go fire up the REPL + try { + createInterpreter() + intp.initializeSynchronous() + globalFuture = Future successful true + if (intp.reporter.hasErrors) { + echo("Interpreter encountered errors during initialization!") + null + } else { + loopPostInit() + val line = splash.line // what they typed in while they were waiting + if (line == null) { // they ^D + try out print Properties.shellInterruptedString + finally closeInterpreter() + } + line + } + } finally splash.stop() + } + this.settings = settings + startup() match { + case null => false + case line => + try loop(line) match { + case LineResults.EOF => out print Properties.shellInterruptedString + case _ => + } + catch AbstractOrMissingHandler() + finally closeInterpreter() + true + } } @deprecated("Use `process` instead", "2.9.0") diff --git a/src/repl/scala/tools/nsc/interpreter/InteractiveReader.scala b/src/repl/scala/tools/nsc/interpreter/InteractiveReader.scala index 71753a3e39..1f81d9965c 100644 --- a/src/repl/scala/tools/nsc/interpreter/InteractiveReader.scala +++ b/src/repl/scala/tools/nsc/interpreter/InteractiveReader.scala @@ -50,3 +50,98 @@ object InteractiveReader { def createDefault(): InteractiveReader = apply() // used by sbt } +/** Collect one line of user input from the supplied reader. + * Runs on a new thread while the REPL is initializing on the main thread. + * + * The user can enter text or a `:paste` command. + */ +class SplashLoop(reader: InteractiveReader, prompt: String) extends Runnable { + import java.util.concurrent.SynchronousQueue + import scala.compat.Platform.EOL + + private val result = new SynchronousQueue[Option[String]] + @volatile private var running: Boolean = _ + private var thread: Thread = _ + + /** Read one line of input which can be retrieved with `line`. */ + def run(): Unit = { + var line = "" + try + do { + line = reader.readLine(prompt) + if (line != null) { + line = process(line.trim) + } + } while (line != null && line.isEmpty && running) + finally { + result.put(Option(line)) + } + } + + /** Check for `:paste` command. */ + private def process(line: String): String = { + def isPrefix(s: String, p: String, n: Int) = ( + //s != null && p.inits.takeWhile(_.length >= n).exists(s == _) + s != null && s.length >= n && s.length <= p.length && s == p.take(s.length) + ) + if (isPrefix(line, ":paste", 3)) { + // while collecting lines, check running flag + var help = f"// Entering paste mode (ctrl-D to finish)%n%n" + def readWhile(cond: String => Boolean) = { + Iterator continually reader.readLine(help) takeWhile { x => + help = "" + x != null && cond(x) + } + } + val text = (readWhile(_ => running) mkString EOL).trim + val next = + if (text.isEmpty) "// Nothing pasted, nothing gained." + else "// Exiting paste mode, now interpreting." + Console println f"%n${next}%n" + text + } else { + line + } + } + + def start(): Unit = result.synchronized { + require(thread == null, "Already started") + thread = new Thread(this) + running = true + thread.start() + } + + def stop(): Unit = result.synchronized { + running = false + if (thread != null) thread.interrupt() + thread = null + } + + /** Block for the result line, or null on ctl-D. */ + def line: String = result.take getOrElse null +} +object SplashLoop { + def apply(reader: SplashReader, prompt: String): SplashLoop = new SplashLoop(reader, prompt) +} + +/** Reader during splash. Handles splash-completion with a stub, otherwise delegates. */ +class SplashReader(reader: InteractiveReader, postIniter: InteractiveReader => Unit) extends InteractiveReader { + /** Invoke the postInit action with the underlying reader. */ + override def postInit(): Unit = postIniter(reader) + + override val interactive: Boolean = reader.interactive + + override def reset(): Unit = reader.reset() + override def history: History = reader.history + override val completion: Completion = NoCompletion + override def redrawLine(): Unit = reader.redrawLine() + + override protected[interpreter] def readOneLine(prompt: String): String = ??? // unused + override protected[interpreter] def readOneKey(prompt: String): Int = ??? // unused + + override def readLine(prompt: String): String = reader.readLine(prompt) +} +object SplashReader { + def apply(reader: InteractiveReader)(postIniter: InteractiveReader => Unit) = + new SplashReader(reader, postIniter) +} -- cgit v1.2.3 From 869df338617f2210217827c83d3ef9dc6d810e65 Mon Sep 17 00:00:00 2001 From: Som Snytt Date: Fri, 20 May 2016 18:19:08 -0700 Subject: SI-7898 Quiet REPL at startup Enable noisy modes only when interpreting user input. --- src/repl/scala/tools/nsc/interpreter/ILoop.scala | 24 ++++++++++++++++++------ 1 file changed, 18 insertions(+), 6 deletions(-) (limited to 'src') diff --git a/src/repl/scala/tools/nsc/interpreter/ILoop.scala b/src/repl/scala/tools/nsc/interpreter/ILoop.scala index adaf3a5d25..4e0f60cf2b 100644 --- a/src/repl/scala/tools/nsc/interpreter/ILoop.scala +++ b/src/repl/scala/tools/nsc/interpreter/ILoop.scala @@ -908,9 +908,6 @@ class ILoop(in0: Option[BufferedReader], protected val out: JPrintWriter) // we can get at it in generated code. intp.quietBind(NamedParam[IMain]("$intp", intp)(tagOfIMain, classTag[IMain])) - // add a help function for anyone who types "help" instead of ":help". Easily shadowed. - //addHelp() - // Auto-run code via some setting. ( replProps.replAutorunCode.option flatMap (f => File(f).safeSlurp()) @@ -938,9 +935,24 @@ class ILoop(in0: Option[BufferedReader], protected val out: JPrintWriter) } case _ => } - // TODO: wait until after startup to enable obnoxious settings - def withSuppressedSettings[A](body: =>A): A = { - body + // wait until after startup to enable noisy settings + def withSuppressedSettings[A](body: => A): A = { + val ss = this.settings + import ss._ + val noisy = List(Xprint, Ytyperdebug) + val noisesome = noisy.exists(!_.isDefault) + val current = (Xprint.value, Ytyperdebug.value) + if (isReplDebug || !noisesome) body + else { + this.settings.Xprint.value = List.empty + this.settings.Ytyperdebug.value = false + try body + finally { + Xprint.value = current._1 + Ytyperdebug.value = current._2 + intp.global.printTypings = current._2 + } + } } def startup(): String = withSuppressedSettings { // starting -- cgit v1.2.3 From 5450ae6102eaeb8ec0f9b524bf43ac5f604b5074 Mon Sep 17 00:00:00 2001 From: Som Snytt Date: Mon, 23 May 2016 10:12:41 -0700 Subject: SI-7898 Report paste errors improvedly Use a "label" for errors, so that script names are shown. Position is still wrong for scripts in REPL. Initial scripts are run with `ILoop.echo` and results printing turned off, but reporter still enabled. --- src/repl/scala/tools/nsc/interpreter/ILoop.scala | 20 ++++++++++--------- src/repl/scala/tools/nsc/interpreter/IMain.scala | 25 +++++++++++++++--------- test/files/run/t9170.scala | 2 +- 3 files changed, 28 insertions(+), 19 deletions(-) (limited to 'src') diff --git a/src/repl/scala/tools/nsc/interpreter/ILoop.scala b/src/repl/scala/tools/nsc/interpreter/ILoop.scala index 4e0f60cf2b..7dab371caf 100644 --- a/src/repl/scala/tools/nsc/interpreter/ILoop.scala +++ b/src/repl/scala/tools/nsc/interpreter/ILoop.scala @@ -1,5 +1,5 @@ /* NSC -- new Scala compiler - * Copyright 2005-2015 LAMP/EPFL + * Copyright 2005-2016 LAMP/EPFL * @author Alexander Spoon */ package scala @@ -15,7 +15,7 @@ import scala.tools.asm.ClassReader import scala.util.Properties.{ jdkHome, javaVersion, versionString, javaVmName } import scala.tools.nsc.util.{ ClassPath, Exceptional, stringFromWriter, stringFromStream } import scala.reflect.classTag -import scala.reflect.internal.util.{ BatchSourceFile, ScalaClassLoader } +import scala.reflect.internal.util.{ BatchSourceFile, ScalaClassLoader, NoPosition } import ScalaClassLoader._ import scala.reflect.io.{ File, Directory } import scala.tools.util._ @@ -181,9 +181,9 @@ class ILoop(in0: Option[BufferedReader], protected val out: JPrintWriter) out.flush() } // turn off intp reporter and our echo - def mumly[A](op: =>A): A = + def mumly[A](op: => A): A = if (isReplDebug) op - else intp beSilentDuring { + else intp beQuietDuring { val saved = mum mum = true try op finally mum = saved @@ -576,9 +576,9 @@ class ILoop(in0: Option[BufferedReader], protected val out: JPrintWriter) } } - def withFile[A](filename: String)(action: File => A): Option[A] = { + def withFile[A](filename: String)(action: File => A): Option[A] = intp.withLabel(filename) { val res = Some(File(filename)) filter (_.exists) map action - if (res.isEmpty) echo("That file does not exist") // courtesy side-effect + if (res.isEmpty) intp.reporter.warning(NoPosition, s"File `$filename' does not exist.") // courtesy side-effect res } @@ -715,6 +715,7 @@ class ILoop(in0: Option[BufferedReader], protected val out: JPrintWriter) */ def pasteCommand(arg: String): Result = { var shouldReplay: Option[String] = None + var label = "" def result = Result(keepRunning = true, shouldReplay) val (raw, file, margin) = if (arg.isEmpty) (false, None, None) @@ -735,6 +736,7 @@ class ILoop(in0: Option[BufferedReader], protected val out: JPrintWriter) } val code = (file, margin) match { case (Some(name), None) => + label = name withFile(name) { f => shouldReplay = Some(s":paste $arg") val s = f.slurp.trim @@ -757,17 +759,17 @@ class ILoop(in0: Option[BufferedReader], protected val out: JPrintWriter) text } def interpretCode() = { - val res = intp interpret code + val res = intp.withLabel(label)(intp interpret code) // if input is incomplete, let the compiler try to say why if (res == IR.Incomplete) { echo("The pasted code is incomplete!\n") // Remembrance of Things Pasted in an object - val errless = intp compileSources new BatchSourceFile("", s"object pastel {\n$code\n}") + val errless = intp compileSources new BatchSourceFile(label, s"object pastel {\n$code\n}") if (errless) echo("...but compilation found no error? Good luck with that.") } } def compileCode() = { - val errless = intp compileSources new BatchSourceFile("", code) + val errless = intp compileSources new BatchSourceFile(label, code) if (!errless) echo("There were compilation errors!") } if (code.nonEmpty) { diff --git a/src/repl/scala/tools/nsc/interpreter/IMain.scala b/src/repl/scala/tools/nsc/interpreter/IMain.scala index ef6ab4063a..1e7a9cefed 100644 --- a/src/repl/scala/tools/nsc/interpreter/IMain.scala +++ b/src/repl/scala/tools/nsc/interpreter/IMain.scala @@ -1,5 +1,5 @@ /* NSC -- new Scala compiler - * Copyright 2005-2013 LAMP/EPFL + * Copyright 2005-2016 LAMP/EPFL * @author Martin Odersky */ @@ -74,13 +74,14 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set lazy val isClassBased: Boolean = settings.Yreplclassbased.value - private[nsc] var printResults = true // whether to print result lines - private[nsc] var totalSilence = false // whether to print anything - private var _initializeComplete = false // compiler is initialized - private var _isInitialized: Future[Boolean] = null // set up initialization future - private var bindExceptions = true // whether to bind the lastException variable - private var _executionWrapper = "" // code to be wrapped around all lines - var partialInput: String = "" // code accumulated in multi-line REPL input + private[nsc] var printResults = true // whether to print result lines + private[nsc] var totalSilence = false // whether to print anything + private var _initializeComplete = false // compiler is initialized + private var _isInitialized: Future[Boolean] = null // set up initialization future + private var bindExceptions = true // whether to bind the lastException variable + private var _executionWrapper = "" // code to be wrapped around all lines + var partialInput: String = "" // code accumulated in multi-line REPL input + private var label = "" // compilation unit name for reporting /** We're going to go to some trouble to initialize the compiler asynchronously. * It's critical that nothing call into it until it's been initialized or we will @@ -108,6 +109,12 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set try body finally if (!saved) settings.nowarn.value = false } + // Apply a temporary label for compilation (for example, script name) + def withLabel[A](temp: String)(body: => A): A = { + val saved = label + label = temp + try body finally label = saved + } /** construct an interpreter that reports to Console */ def this(settings: Settings, out: JPrintWriter) = this(null, settings, out) @@ -810,7 +817,7 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set case Right(result) => Right(result) } - def compile(source: String): Boolean = compileAndSaveRun("", source) + def compile(source: String): Boolean = compileAndSaveRun(label, source) /** The innermost object inside the wrapper, found by * following accessPath into the outer one. diff --git a/test/files/run/t9170.scala b/test/files/run/t9170.scala index f39467bc25..87471fb129 100644 --- a/test/files/run/t9170.scala +++ b/test/files/run/t9170.scala @@ -44,7 +44,7 @@ object Y { // Exiting paste mode, now interpreting. -:13: error: double definition: +:13: error: double definition: def f[A](a: => A): Int at line 12 and def f[A](a: => Either[Exception,A]): Int at line 13 have same type after erasure: (a: Function0)Int -- cgit v1.2.3 From b462e5a97b499bc91222014e45ec2439f56b46b7 Mon Sep 17 00:00:00 2001 From: Lukas Rytz Date: Tue, 24 May 2016 08:21:56 +0200 Subject: SI-7898 Label for parsing -i sources Text-based REPL pre-parses, so use the current label for errors. --- src/repl/scala/tools/nsc/interpreter/IMain.scala | 2 +- test/files/run/repl-paste-parse.check | 6 ++++++ test/files/run/repl-paste-parse.scala | 27 ++++++++++++++++++++++++ test/files/run/repl-paste-parse.script | 1 + 4 files changed, 35 insertions(+), 1 deletion(-) create mode 100755 test/files/run/repl-paste-parse.check create mode 100644 test/files/run/repl-paste-parse.scala create mode 100644 test/files/run/repl-paste-parse.script (limited to 'src') diff --git a/src/repl/scala/tools/nsc/interpreter/IMain.scala b/src/repl/scala/tools/nsc/interpreter/IMain.scala index 1e7a9cefed..dc8b6204c0 100644 --- a/src/repl/scala/tools/nsc/interpreter/IMain.scala +++ b/src/repl/scala/tools/nsc/interpreter/IMain.scala @@ -1191,7 +1191,7 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set var isIncomplete = false def parse = { reporter.reset() - val trees = newUnitParser(line).parseStats() + val trees = newUnitParser(line, label).parseStats() if (reporter.hasErrors) Error(trees) else if (isIncomplete) Incomplete(trees) else Success(trees) diff --git a/test/files/run/repl-paste-parse.check b/test/files/run/repl-paste-parse.check new file mode 100755 index 0000000000..7b2148dc74 --- /dev/null +++ b/test/files/run/repl-paste-parse.check @@ -0,0 +1,6 @@ +Type in expressions for evaluation. Or try :help. + +scala> repl-paste-parse.script:1: error: illegal start of simple pattern +val case = 9 + ^ +:quit diff --git a/test/files/run/repl-paste-parse.scala b/test/files/run/repl-paste-parse.scala new file mode 100644 index 0000000000..e93ad4d02b --- /dev/null +++ b/test/files/run/repl-paste-parse.scala @@ -0,0 +1,27 @@ + +import java.io.{ BufferedReader, StringReader, StringWriter, PrintWriter } + +import scala.tools.partest.DirectTest +import scala.tools.nsc.interpreter.ILoop +import scala.tools.nsc.GenericRunnerSettings + +object Test extends DirectTest { + override def extraSettings = s"-usejavacp -i $scriptPath" + def scriptPath = testPath.changeExtension("script") + override def newSettings(args: List[String]) = { + val ss = new GenericRunnerSettings(Console.println) + ss.processArguments(args, true) + ss + } + def code = "" + def show() = { + val r = new BufferedReader(new StringReader("")) + val w = new StringWriter + val p = new PrintWriter(w, true) + new ILoop(r, p).process(settings) + w.toString.lines foreach { s => + if (!s.startsWith("Welcome to Scala")) println(s) + } + } +} + diff --git a/test/files/run/repl-paste-parse.script b/test/files/run/repl-paste-parse.script new file mode 100644 index 0000000000..903f6e7b0c --- /dev/null +++ b/test/files/run/repl-paste-parse.script @@ -0,0 +1 @@ +val case = 9 -- cgit v1.2.3 From 100d6374c282d94497ee9f0d4a206d427951c74c Mon Sep 17 00:00:00 2001 From: Performant Data LLC Date: Sun, 22 May 2016 09:40:54 -0700 Subject: SI-9789 use quadratic probing in OpenHashMap The original probe sequence, taken from Python's hash table code, is exponential, jumping around in the hash table with poor memory locality. This replaces the probe algorithm with the more conventional quadratic probing. This also adds tests to the benchmarking code using AnyRef keys, which have pseudorandom hash codes (unlike Ints, whose hash code is simply the Int itself). The intensity of the benchmarking is reduced to make the tests complete within 9 hours, by removing unnecessary sampling. --- .../scala/collection/mutable/OpenHashMap.scala | 18 +- .../src/main/scala/benchmark/KeySeq.scala | 24 +++ .../src/main/scala/benchmark/KeySeqBuilder.scala | 33 ++++ .../collection/mutable/OpenHashMapBenchmark.scala | 216 +++++++++++++++------ .../collection/mutable/OpenHashMapRunner.scala | 60 +++--- 5 files changed, 257 insertions(+), 94 deletions(-) create mode 100644 test/benchmarks/src/main/scala/benchmark/KeySeq.scala create mode 100644 test/benchmarks/src/main/scala/benchmark/KeySeqBuilder.scala (limited to 'src') diff --git a/src/library/scala/collection/mutable/OpenHashMap.scala b/src/library/scala/collection/mutable/OpenHashMap.scala index 5f8f5b9a0a..c86357efad 100644 --- a/src/library/scala/collection/mutable/OpenHashMap.scala +++ b/src/library/scala/collection/mutable/OpenHashMap.scala @@ -108,16 +108,13 @@ extends AbstractMap[Key, Value] * @param hash hash value for `key` */ private[this] def findIndex(key: Key, hash: Int): Int = { - var j = hash - var index = hash & mask - var perturb = index + var j = 0 while(table(index) != null && !(table(index).hash == hash && table(index).key == key)){ - j = 5 * j + 1 + perturb - perturb >>= 5 - index = j & mask + j += 1 + index = (index + j) & mask } index } @@ -172,20 +169,17 @@ extends AbstractMap[Key, Value] def get(key : Key) : Option[Value] = { val hash = hashOf(key) - - var j = hash var index = hash & mask - var perturb = index var entry = table(index) + var j = 0 while(entry != null){ if (entry.hash == hash && entry.key == key){ return entry.value } - j = 5 * j + 1 + perturb - perturb >>= 5 - index = j & mask + j += 1 + index = (index + j) & mask entry = table(index) } None diff --git a/test/benchmarks/src/main/scala/benchmark/KeySeq.scala b/test/benchmarks/src/main/scala/benchmark/KeySeq.scala new file mode 100644 index 0000000000..126b92b3b6 --- /dev/null +++ b/test/benchmarks/src/main/scala/benchmark/KeySeq.scala @@ -0,0 +1,24 @@ +package benchmark + +/** A sequence of keys. + * + * Tests of maps and sets require a sequence of keys that can be used + * to add entries and possibly to find them again. + * This type provides such a sequence. + * + * Note that this needn't be a "sequence" in the full sense of [[collection.Seq]], + * particularly in that it needn't extend [[PartialFunction]]. + * + * @tparam K the type of the keys + */ +trait KeySeq[K] { + /** Selects a key by its index in the sequence. + * Repeated calls with the same index return the same key (by reference equality). + * + * @param idx The index to select. Should be non-negative and less than `size`. + */ + def apply(idx: Int): K + + /** The size of this sequence. */ + def size: Int +} diff --git a/test/benchmarks/src/main/scala/benchmark/KeySeqBuilder.scala b/test/benchmarks/src/main/scala/benchmark/KeySeqBuilder.scala new file mode 100644 index 0000000000..95f6c7afd7 --- /dev/null +++ b/test/benchmarks/src/main/scala/benchmark/KeySeqBuilder.scala @@ -0,0 +1,33 @@ +package benchmark + +/** Builder of a [[KeySeq]] + * + * @tparam K the type of the keys + */ +trait KeySeqBuilder[K] { + /** Return a [[KeySeq]] having at least the given size. */ + def build(size: Int): KeySeq[K] +} + +object KeySeqBuilder { + /** Builder of a sequence of `Int` keys. + * Simply maps the sequence index to itself. + */ + implicit object IntKeySeqBuilder extends KeySeqBuilder[Int] { + def build(_size: Int) = new KeySeq[Int] { + def apply(idx: Int) = idx + def size = _size + } + } + + /** Builder of a sequence of `AnyRef` keys. */ + implicit object AnyRefKeySeqBuilder extends KeySeqBuilder[AnyRef] { + def build(_size: Int) = new KeySeq[AnyRef] { + private[this] val arr = new Array[AnyRef](size) + for (i <- 0 until size) arr(i) = new AnyRef() + + def apply(idx: Int) = arr(idx) + def size = _size + } + } +} diff --git a/test/benchmarks/src/main/scala/scala/collection/mutable/OpenHashMapBenchmark.scala b/test/benchmarks/src/main/scala/scala/collection/mutable/OpenHashMapBenchmark.scala index 26e26b3065..64e2244499 100644 --- a/test/benchmarks/src/main/scala/scala/collection/mutable/OpenHashMapBenchmark.scala +++ b/test/benchmarks/src/main/scala/scala/collection/mutable/OpenHashMapBenchmark.scala @@ -1,14 +1,12 @@ package scala.collection.mutable; -import java.util.concurrent.TimeUnit import org.openjdk.jmh.annotations._ -import org.openjdk.jmh.infra.Blackhole -import org.openjdk.jmh.infra.BenchmarkParams -import org.openjdk.jol.info.GraphLayout -import org.openjdk.jol.info.GraphWalker -import org.openjdk.jol.info.GraphVisitor -import org.openjdk.jmh.infra.IterationParams +import org.openjdk.jmh.infra._ import org.openjdk.jmh.runner.IterationType +import org.openjdk.jol.info.GraphLayout + +import benchmark._ +import java.util.concurrent.TimeUnit /** Utilities for the [[OpenHashMapBenchmark]]. * @@ -16,7 +14,8 @@ import org.openjdk.jmh.runner.IterationType * instead of using the JMH harness, which iterates for a fixed length of time. */ private object OpenHashMapBenchmark { - /** State container for the `put()` bulk calling tests. + + /** Abstract state container for the `put()` bulk calling tests. * * Provides an array of adequately-sized, empty maps to each invocation, * so that hash table allocation won't be done during measurement. @@ -25,10 +24,11 @@ private object OpenHashMapBenchmark { * so that only the GCs caused by the invocation contribute to the measurement. * * Records the memory used by all the maps in the last invocation of each iteration. + * + * @tparam K type of the map keys to be used in the test */ @State(Scope.Thread) - @AuxCounters - class BulkPutState { + private[this] abstract class BulkPutState[K](implicit keyBuilder: KeySeqBuilder[K]) { /** A lower-bound estimate of the number of nanoseconds per `put()` call */ private[this] val nanosPerPut: Double = 5 @@ -39,35 +39,43 @@ private object OpenHashMapBenchmark { private[this] var size: Int = _ /** Total number of entries in all of the `maps` combined. */ - var mapEntries: Int = _ + private[this] var _mapEntries: Int = _ + protected def mapEntries = _mapEntries /** Number of operations performed in the current invocation. */ - var operations: Int = _ + private[this] var _operations: Int = _ + protected def operations = _operations /** Bytes of memory used in the object graphs of all the maps. */ - var memory: Long = _ + private[this] var _memory: Long = _ + protected def memory = _memory + + /** The sequence of keys to store into a map. */ + private[this] var _keys: KeySeq[K] = _ + def keys() = _keys - var maps: Array[OpenHashMap[Int,Int]] = null + var maps: Array[OpenHashMap[K,Int]] = null @Setup def threadSetup(params: BenchmarkParams) { size = params.getParam("size").toInt val n = math.ceil(minNanosPerInvocation / (nanosPerPut * size)).toInt - mapEntries = size * n + _mapEntries = size * n + _keys = keyBuilder.build(size) maps = new Array(n) } @Setup(Level.Iteration) def iterationSetup { - operations = 0 + _operations = 0 } @Setup(Level.Invocation) def setup(params: IterationParams) { - for (i <- 0 until maps.length) maps(i) = new OpenHashMap[Int,Int](size) + for (i <- 0 until maps.length) maps(i) = new OpenHashMap[K,Int](size) if (params.getType == IterationType.MEASUREMENT) { - operations += mapEntries + _operations += _mapEntries System.gc() // clean up after last invocation } } @@ -76,72 +84,124 @@ private object OpenHashMapBenchmark { def iterationTeardown(params: IterationParams) { if (params.getType == IterationType.MEASUREMENT) { // limit to smaller cases to avoid OOM - memory = if (mapEntries <= 1000000) GraphLayout.parseInstance(maps(0), maps.tail).totalSize else 0 + _memory = + if (_mapEntries <= 1000000) GraphLayout.parseInstance(maps(0), maps.tail).totalSize + else 0 } } } - /** State container for the `get()` bulk calling tests. + /** Abstract state container for the `get()` bulk calling tests. * * Provides a thread-scoped map of the expected size. * Performs a GC after loading the map. + * + * @tparam K type of the map keys to be used in the test */ @State(Scope.Thread) - class BulkGetState { - val map = new OpenHashMap[Int,Int].empty + private[this] abstract class BulkGetState[K](implicit keyBuilder: KeySeqBuilder[K]) { + /** The sequence of keys to store into a map. */ + private[this] var _keys: KeySeq[K] = _ + def keys() = _keys + + val map = new OpenHashMap[K,Int].empty /** Load the map with keys from `1` to `size`. */ @Setup def setup(params: BenchmarkParams) { val size = params.getParam("size").toInt - put_Int(map, 1, size) + _keys = keyBuilder.build(size) + put(map, keys, 0, size) System.gc() } } - /** State container for the `get()` bulk calling tests with deleted entries. + /** Abstract state container for the `get()` bulk calling tests with deleted entries. * * Provides a thread-scoped map of the expected size, from which entries have been removed. * Performs a GC after loading the map. + * + * @tparam K type of the map keys to be used in the test */ @State(Scope.Thread) - class BulkRemovedGetState { - val map = new OpenHashMap[Int,Int].empty + private[this] abstract class BulkRemovedGetState[K](implicit keyBuilder: KeySeqBuilder[K]) { + /** The sequence of keys to store into a map. */ + private[this] var _keys: KeySeq[K] = _ + def keys() = _keys + + val map = new OpenHashMap[K,Int].empty /** Load the map with keys from `1` to `size`, removing half of them. */ @Setup def setup(params: BenchmarkParams) { val size = params.getParam("size").toInt - put_remove_Int(map, size) + _keys = keyBuilder.build(size) + put_remove(map, keys) System.gc() } } - /** Put elements into the given map. */ - private def put_Int(map: OpenHashMap[Int,Int], from: Int, to: Int) { + /* In order to use `@AuxCounters` on a class hierarchy (as of JMH 1.11.3), + * it's necessary to place it on the injected (sub)class, and to make the + * counters visible as explicit public members of the that class. JMH doesn't + * scan the ancestor classes for counters. + */ + + @AuxCounters + private class IntBulkPutState extends BulkPutState[Int] { + override def mapEntries = super.mapEntries + override def operations = super.operations + override def memory = super.memory + } + private class IntBulkGetState extends BulkGetState[Int] + private class IntBulkRemovedGetState extends BulkRemovedGetState[Int] + + @AuxCounters + private class AnyRefBulkPutState extends BulkPutState[AnyRef] { + override def mapEntries = super.mapEntries + override def operations = super.operations + override def memory = super.memory + } + private class AnyRefBulkGetState extends BulkGetState[AnyRef] + private class AnyRefBulkRemovedGetState extends BulkRemovedGetState[AnyRef] + + + /** Put entries into the given map. + * Adds entries using a range of keys from the given list. + * + * @param from lowest index in the range of keys to add + * @param to highest index in the range of keys to add, plus one + */ + private[this] def put[K](map: OpenHashMap[K,Int], keys: KeySeq[K], from: Int, to: Int) { var i = from - while (i <= to) { // using a `for` expression instead adds significant overhead - map.put(i, i) + while (i < to) { // using a `for` expression instead adds significant overhead + map.put(keys(i), i) i += 1 } } - /** Put elements into the given map, removing half of them as they're added. + /** Put entries into the given map. + * Adds entries using all of the keys from the given list. + */ + private def put[K](map: OpenHashMap[K,Int], keys: KeySeq[K]): Unit = + put(map, keys, 0, keys.size) + + /** Put entries into the given map, removing half of them as they're added. * - * @param size number of entries to leave in the map on return + * @param keys list of keys to use */ - def put_remove_Int(map: OpenHashMap[Int,Int], size: Int) { - val blocks = 50 // should be a factor of `size` - val totalPuts = 2 * size // add twice as many, because we remove half of them - val blockSize: Int = totalPuts / blocks + private def put_remove[K](map: OpenHashMap[K,Int], keys: KeySeq[K]) { + val blocks = 25 // should be a non-trivial factor of `size` + val size = keys.size + val blockSize: Int = size / blocks var base = 0 - while (base < totalPuts) { - put_Int(map, base + 1, base + blockSize) + while (base < size) { + put(map, keys, base, base + blockSize) // remove every other entry - var i = base + 1 - while (i <= base + blockSize) { - map.remove(i) + var i = base + while (i < base + blockSize) { + map.remove(keys(i)) i += 2 } @@ -150,55 +210,99 @@ private object OpenHashMapBenchmark { } /** Get elements from the given map. */ - def get_Int(map: OpenHashMap[Int,Int], size: Int, bh: Blackhole) { - var i = 1 - while (i <= size) { - bh.consume(map.get(i).getOrElse(0)) + private def get[K](map: OpenHashMap[K,Int], keys: KeySeq[K]) = { + val size = keys.size + var i = 0 + var sum = 0 + while (i < size) { + sum += map.get(keys(i)).getOrElse(0) i += 1 } + sum } } /** Benchmark for the library's [[OpenHashMap]]. */ @BenchmarkMode(Array(Mode.AverageTime)) -@Fork(6) +@Fork(5) @Threads(1) @Warmup(iterations = 20) -@Measurement(iterations = 6) +@Measurement(iterations = 5) @OutputTimeUnit(TimeUnit.NANOSECONDS) @State(Scope.Benchmark) class OpenHashMapBenchmark { import OpenHashMapBenchmark._ - @Param(Array("25", "50", "100", "250", "1000", "2500", "10000", "25000", "100000", "250000", "1000000", "2500000", + @Param(Array("50", "100", "1000", "10000", "100000", "1000000", "2500000", "5000000", "7500000", "10000000", "25000000")) var size: Int = _ + // Tests with Int keys + /** Test putting elements to a map of `Int` to `Int`. */ @Benchmark - def put_Int(state: BulkPutState) { + def put_Int(state: IntBulkPutState) { var i = 0 while (i < state.maps.length) { - OpenHashMapBenchmark.put_Int(state.maps(i), 1, size) + put(state.maps(i), state.keys) i += 1 } } /** Test putting and removing elements to a growing map of `Int` to `Int`. */ @Benchmark - def put_remove_Int(state: BulkPutState) { + def put_remove_Int(state: IntBulkPutState) { var i = 0 while (i < state.maps.length) { - OpenHashMapBenchmark.put_remove_Int(state.maps(i), size) + put_remove(state.maps(i), state.keys) i += 1 } } /** Test getting elements from a map of `Int` to `Int`. */ @Benchmark - def put_get_Int(state: BulkGetState, bh: Blackhole) = OpenHashMapBenchmark.get_Int(state.map, size, bh) + def get_Int_after_put(state: IntBulkGetState) = + get(state.map, state.keys) + + /** Test getting elements from a map of `Int` to `Int` from which elements have been removed. + * Note that half of these queries will fail to find their keys, which have been removed. + */ + @Benchmark + def get_Int_after_put_remove(state: IntBulkRemovedGetState) = + get(state.map, state.keys) + + + // Tests with AnyRef keys + + /** Test putting elements to a map of `AnyRef` to `Int`. */ + @Benchmark + def put_AnyRef(state: AnyRefBulkPutState) { + var i = 0 + while (i < state.maps.length) { + put(state.maps(i), state.keys) + i += 1 + } + } + + /** Test putting and removing elements to a growing map of `AnyRef` to `Int`. */ + @Benchmark + def put_remove_AnyRef(state: AnyRefBulkPutState) { + var i = 0 + while (i < state.maps.length) { + put_remove(state.maps(i), state.keys) + i += 1 + } + } + + /** Test getting elements from a map of `AnyRef` to `Int`. */ + @Benchmark + def get_AnyRef_after_put(state: AnyRefBulkGetState) = + get(state.map, state.keys) - /** Test getting elements from a map of `Int` to `Int` from which elements have been removed. */ + /** Test getting elements from a map of `AnyRef` to `Int` from which elements have been removed. + * Note that half of these queries will fail to find their keys, which have been removed. + */ @Benchmark - def put_remove_get_Int(state: BulkRemovedGetState, bh: Blackhole) = OpenHashMapBenchmark.get_Int(state.map, size, bh) + def get_AnyRef_after_put_remove(state: AnyRefBulkRemovedGetState) = + get(state.map, state.keys) } diff --git a/test/benchmarks/src/main/scala/scala/collection/mutable/OpenHashMapRunner.scala b/test/benchmarks/src/main/scala/scala/collection/mutable/OpenHashMapRunner.scala index 1a58b18ee9..b14b733a81 100644 --- a/test/benchmarks/src/main/scala/scala/collection/mutable/OpenHashMapRunner.scala +++ b/test/benchmarks/src/main/scala/scala/collection/mutable/OpenHashMapRunner.scala @@ -1,20 +1,18 @@ package scala.collection.mutable -import java.io.BufferedWriter import java.io.File -import java.io.FileOutputStream -import java.io.OutputStreamWriter import java.io.PrintWriter -import scala.collection.JavaConversions + import scala.language.existentials + +import org.openjdk.jmh.results.Result import org.openjdk.jmh.results.RunResult import org.openjdk.jmh.runner.Runner import org.openjdk.jmh.runner.options.CommandLineOptions -import org.openjdk.jmh.runner.options.Options -import benchmark.JmhRunner import org.openjdk.jmh.runner.options.OptionsBuilder import org.openjdk.jmh.runner.options.VerboseMode -import org.openjdk.jmh.results.Result + +import benchmark.JmhRunner /** Replacement JMH application that runs the [[OpenHashMap]] benchmark. * @@ -27,6 +25,7 @@ object OpenHashMapRunner extends JmhRunner { /** Qualifier to add to the name of a memory usage data set. */ private[this] val memoryDatasetQualifier = "-memory" + /** Adapter to the JMH result class that simplifies our method calls. */ private[this] implicit class MyRunResult(r: RunResult) { /** Return the dataset label. */ def label = r.getPrimaryResult.getLabel @@ -34,13 +33,13 @@ object OpenHashMapRunner extends JmhRunner { /** Return the value of the JMH parameter for the number of map entries per invocation. */ def size: String = r.getParams.getParam("size") - /** Return the operation counts. */ + /** Return the operation counts. Not every test tracks this. */ def operations = Option(r.getSecondaryResults.get("operations")) /** Return the number of map entries. */ def entries = r.getSecondaryResults.get("mapEntries") - /** Return the memory usage. */ + /** Return the memory usage. Only defined if memory usage was measured. */ def memory = Option(r.getSecondaryResults.get("memory")) } @@ -50,7 +49,6 @@ object OpenHashMapRunner extends JmhRunner { def main(args: Array[String]) { import scala.collection.JavaConversions._ - import scala.language.existentials val opts = new CommandLineOptions(args: _*) var builder = new OptionsBuilder().parent(opts).jvmArgsPrepend("-Xmx6000m") @@ -58,7 +56,12 @@ object OpenHashMapRunner extends JmhRunner { val results = new Runner(builder.build).run() - // Sort the results + /* Sort the JMH results into "data sets", each representing a complete test of one feature. + * Some results only measure CPU performance; while others also measure memory usage, and + * thus are split into two data sets. A data set is distinguished by its label, which is + * the label of the JMH result, for CPU performance, or that with an added suffix, for memory + * usage. + */ /** Map from data set name to data set. */ val datasetByName = Map.empty[String, Set[RunResult]] @@ -83,23 +86,28 @@ object OpenHashMapRunner extends JmhRunner { val f = new PrintWriter(outputFile, "UTF-8") try { - datasetByName.foreach(_ match { case (label: String, dataset: Iterable[RunResult]) => { - f.println(s"# [$label]") - - val isMemoryUsageDataset = label.endsWith(memoryDatasetQualifier) - dataset.foreach { r => - f.println(r.size + " " + ( - if (isMemoryUsageDataset) - stats(r.entries) + " " + stats(r.memory.get) - else - stats(r.operations getOrElse r.getPrimaryResult) - )) - } - - f.println(); f.println() // data set separator - }}) + datasetByName.foreach(_ match { + case (label: String, dataset: Iterable[RunResult]) => + outputDataset(f, label, dataset) + }) } finally { f.close() } } + + private[this] def outputDataset(f: PrintWriter, label: String, dataset: Iterable[RunResult]) { + f.println(s"# [$label]") + + val isMemoryUsageDataset = label.endsWith(memoryDatasetQualifier) + dataset.foreach { r => + f.println(r.size + " " + ( + if (isMemoryUsageDataset && !r.memory.get.getScore.isInfinite) + stats(r.entries) + " " + stats(r.memory.get) + else + stats(r.operations getOrElse r.getPrimaryResult) + )) + } + + f.println(); f.println() // data set separator + } } -- cgit v1.2.3