2
\$\begingroup\$

I was recently talking to someone about a function I wrote to mimic (very basically) the string interpolation function String.Format() found in the C# language. They mentioned that I would have performance concerns using RegExp, and that I should try to parse the string template rune by rune. So I wrote a loop the best I could to accomplish that very task. It looks alarmingly ugly (to me) and I wanted some input on the performance considerations with the loop version. As well, maybe some better suggestions on how to accomplish this function in a more sensible/clean fashion.

Here's the two different versions of the implementation:

void main() {
  String thestring = '{0} {1} {2} {3}!';
  assert(formatStringListRegExp([thestring, 'This', 'was', 'a', 'triumph']) == 'This was a triumph!');

  assert(formatStringListloop([thestring, 'This', 'was', 'a', 'triumph']) == 'This was a triumph!');
}

String formatStringListRegExp(List<String> args)
{
  if (args == null || args.length < 2) {
    throw new ArgumentError('expected at least two paramters.');
  }
  if (args[0] is !String) {
    throw new ArgumentError('expected a string for the first paramter.');
  }
  var str = args[0];
  var inserts = args.sublist(1);
  for (var i = 0; i < inserts.length; i++) {
    str = str.replaceAll('{$i}', inserts[i].toString());
  }
  return str;
}

String formatStringListLoop(List<String> args)
{
  if (args == null || args.length < 2) {
    throw new ArgumentError('expected at least two paramters.');
  }

  if (args[0] is !String) {
    throw new ArgumentError('expected a string for the first paramter.');
  }

  var str = args[0];
  var inserts = args.sublist(1);
  StringBuffer buffer = new StringBuffer();

  for (var i = 0; i < str.length; i++) {
    if (str[i] == '{' && i < str.length + 1) {
      var value = '';
      var count = 1;
      var number;

      while(true) {
        if (i + count < str.length - 1) {
          try {
            number = int.parse(str[i + count]);
          } catch (e) {
            break;
          }
        } else {
          break;
        }

        if (number is int) {
          value += number.toString();
          count++;
        } else {
          break;
        }
      }

      if (str[i + count] == '}') {
        if (value.isNotEmpty) {
          int index = int.parse(value);
          if (index < inserts.length) {
            buffer.write(inserts[index]);
            i += count;
          } else {
            buffer.write('{');
          }
        }
      }
    } else {
      buffer.write(str[i]);
    }
  }

  return buffer.toString();
}
\$\endgroup\$
  • \$\begingroup\$ Did you actually benchmark the two implementations? Is the regular expression version actually as slow as whoever you talked to thought it would be? \$\endgroup\$ – rici Aug 24 '14 at 6:12
  • \$\begingroup\$ After loosely benchmarking both versions, the original regexp version is about 2000% faster on a rough average. \$\endgroup\$ – Hydra Aug 25 '14 at 5:11
  • \$\begingroup\$ I guess that means that it's fine to use regexps :) \$\endgroup\$ – rici Aug 25 '14 at 5:17
2
\$\begingroup\$

I don't know Dart, but I haven't had any problems with Javascript regular expression speed, so I don't see why it would be a problem with Dart.

If you format strings are long -- which is probably unlikely -- then scanning the whole string once for each substitution string is not ideal. It's also buggy. Consider the calls:

formatStringListRegExp(['{0} {1}', '{1}', 'foo']) 
formatStringListRegExp(['{0} {1}', 'foo', '{0}'])

So what I'd do is this (all error checking removed for brevity):

String formatStringListRegExp(List<String> args)
{
  return args[0].replaceAllMapped(new RegExp(r'{(\d+)}'),
                                  (Match m) => args[int.parse(m[1])+1])
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ When Dart is transpiled to JavaScript it uses just the JavaScript implementation. The pure Dart implementation wasn't yet optimized and is notable slower. If you want to know for sure if it's worth using custom code you have to benchmark. \$\endgroup\$ – Günter Zöchbauer Aug 24 '14 at 8:09
2
\$\begingroup\$

I would try a pure RegExp version first and see if it really is a performance issue. If you can live with the speed of the RegExp implementation in the Dart VM, I would just stick with it. We (the Dart team) will eventually improve the speed and then your program will silently go faster.

Also: you are not running through the runes, but the code units. In this case it probably doesn't matter. (I just wanted to point that out).

For your current implementation, a few suggestions:

  • don't use try { int.parse(...) } catch. int.parse has an optional argument that is invoked when the input is not a number.
  • when parsing "{" don't try int.parse for each digit one by one. Continue running through the string until you see a "}", and then parse the whole thing.
  • you should think about dealing with escapes: "\{{1}"

If you want a simpler version, maybe this one could help as a starting point. For performance you would avoid the call to int.parse and sum up the digits yourself (after all, you are already running through them). But then you would need to deal with 0x yourself.

    var buffer = new StringBuffer();
    int last = -1;
    for (int i = 0; i < str.length; i++) {
      if (str[i] == '{') {
        buffer.write(str.substring(last + 1, i);
        int start = i++;
        while (i < str.length && str[i] != '}') i++;
        if (i >= str.length) throw "error: no closing }";
        if (i == start + 1) throw "error: empty {}";
        int index = int.parse(str.substring(start + 1, i);  // throws if not valid.
        buffer.write(inserts[index]);
        last = i;
      }
    }
    buffer.write(str.substring(last + 1, str.length);
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ It should be mentioned that int.parse still throws even when an onError handler was passed when the value to parse is null. Always ensure the value passed to int.parse is not null but then try/catch is redundant. See also stackoverflow.com/questions/24085385 for a few examples. \$\endgroup\$ – Günter Zöchbauer Aug 24 '14 at 11:17
  • \$\begingroup\$ I didn't think to keep running until I saw a }, good idea. I'll try that and the replaceAllMapped() version and compare the tree. \$\endgroup\$ – Hydra Aug 25 '14 at 5:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.