StringBuffer in JavaScript is much slower than String

[DartBot]

This issue was originally filed by sethladd@gmail.com

---

For the following code:

// use new hotness: StringBuffer
buildWithStringBuffer() {
  var sb = new StringBuffer();

  for (var i = 9999; i > 0; i--) {
    sb.add(i.toString());
    sb.add(" beers on the wall\n");
  }

  var finalString = sb.toString();
}

// use old school + for string concatenation
buildWithConcat() {
  var s = '';

  for (var i = 9999; i > 0; i--) {
    s += i.toString();
    s += " beers on the wall\n";
  }

  var finalString = s;
}

// wrap a function fn with the Stopwatch class to time execution
xmeasure(text,fn) {
  var sw = new Stopwatch.start();
  fn();
  print(text + sw.elapsedInMs());
}

// the following timings are from the Dart VM
// smaller is faster is better
main() {
xmeasure('buildWithConcat: ',buildWithConcat); // 3574 !!
xmeasure('buildWithStringBuffer: ',buildWithStringBuffer); // 20
}

In Dart VM, we see StringBuffer greatly out performing + concat.

When compiled to JavaScript, we see the opposite:

buildWithConcat: 821
buildWithStringBuffer: 3174

The StringBuffer class should work at least as fast as String.

[dgrove]

with frog r3425, here's what I see:

buildWithConcat: 47
buildWithStringBuffer: 157

---

Added Area-Frog label.

[dgrove]

Added Triaged label.

[rakudrama]

"The StringBuffer class should work at least as fast as String." might be impossible.

The emitted JS uses JS string concatenation. In V8 this is optimized by having multiple string representations, including a tree or 'concat' node pointing to the left and right substrings, giving constant time concatenation of large strings (at the cost of more complex access to the string contents). I am not surprised that buildWithConcat beats buildWithStringBuffer when compiled to JS. The StringBuffer is simply incurring overhead by keeping the string fragments in list before using a concat loop!

So "The StringBuffer class should work at least as fast as String." might be impossible on dartc/frog code running on V8. The best you can hope for is that the two are closer, and I think that is a frog corelib implementation issue. If all JS engines have similar concat tricks, direct concatenation might be the best implementation.

DartVM has flat strings, which makes buildWithConcat O(N^2). One might say that the VM has a serious performance bug in that string concatenation is not as fast as StringBuffer, and the exceedingly common 's += ... in a loop' antipattern is not fixed by language runtime technology.

[DartBot]

This comment was originally written by jimhug@google.com

---

John had an idea about this that he suggested to me recently. We could try rewriting the StringBuffer type for the frog corelib to just use string concatenation internally instead of using the default dart implementation. Based on this data, we should try that to see if we can make the two versions of the code closer in performance. Considering all of the optimization work that has gone into string concatentation in the various JS enginges out there, it is highly unlikely that sringbuffer will ever be faster than += for a dart->js compiler. We may be able to make the performance at least close.

---

cc @jmesserly.
Added Accepted label.

[lrhn]

I'd try both string concatenation and collecting the strings in an array and then use String.prototype.join to combine them. Both have their strengths and weaknesses, mostly depending on the further use of the string.

[DartBot]

This comment was originally written by gundla...@gmail.com

---

Re @­5's mention of .join(): why use StringBuffer.toString() at all, instead of using List<String>.join('')? I would hope the implementation would be similar under the hood, and would let Dart eliminate the redundant (verbosely named) class.

FWIW, Python doesn't have a StringBuffer class; you use
  ''.join(['list', 'of', 'strings'])
.

[DartBot]

This comment was originally written by @seaneagan

---

@6: I agree! see issue #324

[anders-sandholm]

Removed Area-Frog label.
Added Area-Dart2JS, FromAreaFrog labels.

[kasperl]

This is likely still the case for dart2js.

---

Removed FromAreaFrog label.

[kasperl]

Added this to the Later milestone.

[kasperl]

Removed this from the Later milestone.

[kasperl]

Added this to the M2 milestone.

[kasperl]

Removed Priority-Medium label.
Added Priority-Low label.

[peter-ahe-google]

Removed this from the M2 milestone.
Added this to the Later milestone.
Removed Priority-Low label.
Added Priority-Medium label.

[peter-ahe-google]

This is the third most starred bug in dart2js.

[peter-ahe-google]

We should be able to do better. I just tried this JavaScript code:

function StringBuffer() {
  this.array = new Array();
  this.add = function (x) { this.array.push(x); }
  this.toString = function() { return this.array.join(""); }
}

function buildWithStringBuffer() {
  var sb = new StringBuffer();

  for (var i = 99999; i > 0; i--) {
    sb.add(i.toString());
    sb.add(" beers on the wall\n");
  }

  return sb.toString();
}

function buildWithConcat() {
  var s = "";

  for (var i = 99999; i > 0; i--) {
    s += i.toString();
    s += " beers on the wall\n";
  }

  return s;
}

function measure(expected, f) {
  var start = Date.now();
  var result = f().length;
  if (result != expected) throw "error: got " + result;
  var elapsed = Date.now() - start;
  console.log(f.name + " took " + elapsed + "ms");
}
measure(2388870, buildWithStringBuffer);
measure(2388870, buildWithConcat);

buildWithStringBuffer took 83ms
buildWithConcat took 34ms

Now concat is "only" 2.4411764705882355 times faster which is an improvement over what was reported (3.8660170523751525) and frog (3.3404255319148937).

[peter-ahe-google]

Using this version of StringBuffer, they are roughly equivalent:

function StringBuffer() {
  this.result = "";
  this.add = function (x) { this.result += x; }
  this.toString = function() { return this.result; }
}

[peter-ahe-google]

Even this version is fine:

function StringBuffer() {
  this.result = "";
  this.add = function (x) {
    if (typeof x != "string") throw "argument error";
    this.result += x;
  }
  this.toString = function() { return this.result; }
}

Best numbers with this version:

buildWithStringBuffer took 38ms
buildWithConcat took 39ms