Merge pull request #130 from davidmorgan/improve-performance-use-queue
Fix performance issues due to list.removeAt(0), which makes parsing O(n^2).
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 98d13e3..7eac77d 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,3 +1,7 @@
+## 1.5.3
+
+* Improve performance for large numbers of args.
+
## 1.5.2
* Added support for `usageLineLength` in `CommandRunner`
diff --git a/lib/src/allow_anything_parser.dart b/lib/src/allow_anything_parser.dart
index 46f7e12..e6f13d0 100644
--- a/lib/src/allow_anything_parser.dart
+++ b/lib/src/allow_anything_parser.dart
@@ -2,6 +2,8 @@
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
+import 'dart:collection';
+
import 'arg_parser.dart';
import 'arg_results.dart';
import 'option.dart';
@@ -77,7 +79,7 @@
@override
ArgResults parse(Iterable<String> args) =>
- Parser(null, this, args.toList()).parse();
+ Parser(null, this, Queue.of(args)).parse();
@override
String getUsage() => usage;
diff --git a/lib/src/arg_parser.dart b/lib/src/arg_parser.dart
index eda76ed..72211ba 100644
--- a/lib/src/arg_parser.dart
+++ b/lib/src/arg_parser.dart
@@ -320,7 +320,7 @@
/// Parses [args], a list of command-line arguments, matches them against the
/// flags and options defined by this parser, and returns the result.
ArgResults parse(Iterable<String> args) =>
- Parser(null, this, args.toList()).parse();
+ Parser(null, this, Queue.of(args)).parse();
/// Generates a string displaying usage information for the defined options.
///
diff --git a/lib/src/parser.dart b/lib/src/parser.dart
index 8df2535..2a41f17 100644
--- a/lib/src/parser.dart
+++ b/lib/src/parser.dart
@@ -2,6 +2,8 @@
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
+import 'dart:collection';
+
import 'arg_parser.dart';
import 'arg_parser_exception.dart';
import 'arg_results.dart';
@@ -28,7 +30,7 @@
final ArgParser grammar;
/// The arguments being parsed.
- final List<String> args;
+ final Queue<String> args;
/// The remaining non-option, non-command arguments.
final rest = <String>[];
@@ -42,7 +44,7 @@
}
/// The current argument being parsed.
- String get current => args[0];
+ String get current => args.first;
/// Parses the arguments. This can only be called once.
ArgResults parse() {
@@ -58,7 +60,7 @@
while (args.isNotEmpty) {
if (current == '--') {
// Reached the argument terminator, so stop here.
- args.removeAt(0);
+ args.removeFirst();
break;
}
@@ -67,7 +69,7 @@
var command = grammar.commands[current];
if (command != null) {
validate(rest.isEmpty, 'Cannot specify arguments before a command.');
- var commandName = args.removeAt(0);
+ var commandName = args.removeFirst();
var commandParser = Parser(commandName, command, args, this, rest);
try {
@@ -92,7 +94,7 @@
// This argument is neither option nor command, so stop parsing unless
// the [allowTrailingOptions] option is set.
if (!grammar.allowTrailingOptions) break;
- rest.add(args.removeAt(0));
+ rest.add(args.removeFirst());
}
// Invoke the callbacks.
@@ -116,7 +118,7 @@
validate(args.isNotEmpty, 'Missing argument for "${option.name}".');
setOption(results, option, current);
- args.removeAt(0);
+ args.removeFirst();
}
/// Tries to parse the current argument as a "solo" option, which is a single
@@ -136,7 +138,7 @@
return parent.parseSoloOption();
}
- args.removeAt(0);
+ args.removeFirst();
if (option.isFlag) {
setFlag(results, option, true);
@@ -186,7 +188,7 @@
}
}
- args.removeAt(0);
+ args.removeFirst();
return true;
}
@@ -217,7 +219,7 @@
var name = longOpt[1];
var option = grammar.options[name];
if (option != null) {
- args.removeAt(0);
+ args.removeFirst();
if (option.isFlag) {
validate(longOpt[3] == null,
'Flag option "$name" should not be given a value.');
@@ -240,7 +242,7 @@
return parent.parseLongOption();
}
- args.removeAt(0);
+ args.removeFirst();
validate(option.isFlag, 'Cannot negate non-flag option "$name".');
validate(option.negatable, 'Cannot negate option "$name".');
diff --git a/test/parse_performance_test.dart b/test/parse_performance_test.dart
new file mode 100644
index 0000000..16e412f
--- /dev/null
+++ b/test/parse_performance_test.dart
@@ -0,0 +1,47 @@
+// Copyright (c) 2020, the Dart project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+import 'package:args/args.dart';
+import 'package:test/test.dart';
+
+void main() {
+ group('ArgParser.parse()', () {
+ test('is fast', () {
+ var parser = ArgParser()..addFlag('flag');
+
+ var baseSize = 200000;
+ var baseList = List<String>.generate(baseSize, (_) => '--flag');
+
+ var multiplier = 10;
+ var largeList =
+ List<String>.generate(baseSize * multiplier, (_) => '--flag');
+
+ var baseAction = () => parser.parse(baseList);
+ var largeAction = () => parser.parse(largeList);
+
+ // Warm up JIT.
+ baseAction();
+ largeAction();
+
+ var baseTime = _time(baseAction);
+ var largeTime = _time(largeAction);
+
+ print('Parsed $baseSize elements in ${baseTime}ms, '
+ '${baseSize * multiplier} elements in ${largeTime}ms.');
+
+ expect(largeTime, lessThan(baseTime * multiplier * 3),
+ reason:
+ 'Comparing large data set time ${largeTime}ms to small data set time '
+ '${baseTime}ms. Data set increased ${multiplier}x, time is allowed to '
+ 'increase up to ${multiplier * 3}x, but it increased '
+ '${largeTime ~/ baseTime}x.');
+ });
+ });
+}
+
+int _time(void Function() function) {
+ var stopwatch = Stopwatch()..start();
+ function();
+ return stopwatch.elapsedMilliseconds;
+}
