s.t.cmd.CommandLineParser has exponential performance

[retronym]

⚡ for N in 10000 20000 40000 80000; do (yes /path/to/fileeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee.scal
10000
error: source file '/path/to/fileeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee.scala' could not be found
one error found

real	0m2.662s
user	0m6.006s
sys	0m0.323s
20000
error: source file '/path/to/fileeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee.scala' could not be found
one error found

real	0m6.835s
user	0m13.575s
sys	0m0.627s
40000
error: source file '/path/to/fileeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee.scala' could not be found
one error found

real	0m24.827s
user	0m50.809s
sys	0m1.815s
80000
error: source file '/path/to/fileeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee.scala' could not be found
one error found

real	2m4.690s
user	4m5.447s
sys	0m6.882s

I thought I fixed this in scala/scala@0c520b5, but it was only fixed on JDK versions in which String.substring was cheap (sharing the backing char[]).

The code in question is in https://github.com/scala/scala/blob/0022db978beadb8759cc2ede6d8ef5e4a8a1c58c/src/compiler/scala/tools/cmd/CommandLineParser.scala#L75

• Write a unit test to show the current behaviour of this code
• Write a JMH benchmark that ranges across different input sizes (like the bash command above) to show the performance problem
• Rewrite the recursive method commandLine to avoid taking ever-smaller substrings of the input, perhaps by using String.subsequence (which is cheap), or some analagous method keeping track of how much input remains to be parsed.

I believe that most build tools aren't affected by this performance bug, as they tend to programattically provide the list of sources to the compiler, rather than providing them as part of the list of compiler options.

[retronym]

Looks like a similar problem exists in:

  /** Iterates over the arguments applying them to settings where applicable.
   *  Then verifies setting dependencies are met.
   *
   *  This temporarily takes a boolean indicating whether to keep
   *  processing if an argument is seen which is not a command line option.
   *  This is an expedience for the moment so that you can say
   *
   *    scalac -d /tmp foo.scala -optimise
   *
   *  while also allowing
   *
   *    scala Program opt opt
   *
   *  to get their arguments.
   *
   *  Returns (success, List of unprocessed arguments)
   */
  def processArguments(arguments: List[String], processAll: Boolean): (Boolean, List[String]) = {
    def loop(args: List[String], residualArgs: List[String]): (Boolean, List[String]) = args match {
      case Nil        =>
        (checkDependencies, residualArgs)
      case "--" :: xs =>
        (checkDependencies, xs)
      // discard empties, sometimes they appear because of ant or etc.
      // but discard carefully, because an empty string is valid as an argument
      // to an option, e.g. -cp "" .  So we discard them only when they appear
      // where an option should be, not where an argument to an option should be.
      case "" :: xs =>
        loop(xs, residualArgs)
      case x :: xs  =>
        if (x startsWith "-") {
          parseParams(args) match {
            case newArgs if newArgs eq args => errorFn(s"bad option: '$x'") ; (false, args)
            case newArgs                    => loop(newArgs, residualArgs)
          }
        }
        else if (processAll)
          loop(xs, residualArgs :+ x)
        else
          (checkDependencies, args)
    }
    loop(arguments, Nil)
  }

[som-snytt]

/** A simple (overly so) command line parser.
 *  !!! This needs a thorough test suite to make sure quoting is
 *  done correctly and portably.
 */

[som-snytt]

An imperative take.

[Ichoran]

For reference, the problem was "quadratic" not "exponential" performance.

[SethTisue]

it’s more sophisticated to call it “polynomial”. only muggles care what the exponent is

[martijnhoekstra]

Constant performance is polynomial too, I suppose.

…

On Wed, May 16, 2018, 22:18 Seth Tisue ***@***.***> wrote: it’s more sophisticated to call it “polynomial”. only muggles care what the exponent is — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#485 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AA13EX4lD6JZ2sxTWqPW_unrTMmpdkbAks5tzImqgaJpZM4TjCeI> .

[hrhino]

It's also exponential: O(1^n)