String concatenation
On Wed, Oct 5, 2011 at 11:45 AM, Axel Rauschmayer <axel at rauschma.de> wrote:
Is this worthy of ES.next support? Or does it belong into a library?
The two concatenation approaches I know of are:
- via +=
- push() into an array, join() it after the last push()
(1) can’t possibly be efficient,
Huh? Engines have optimized the hell out of 1 by essentially doing 2 under the hood. Even rhino's about a land a patch to do just that.
but if (2) is OK on all(!) platforms, then a library would be OK. However, given how frequently this is used, I would like this to become part of the standard library.
What exactly do you want supported?
On 05.10.2011 19:45, Axel Rauschmayer wrote:
Is this worthy of ES.next support? Or does it belong into a library?
The two concatenation approaches I know of are:
- via +=
- push() into an array, join() it after the last push()
(1) can’t possibly be efficient, but if (2) is OK on all(!) platforms, then a library would be OK. However, given how frequently this is used, I would like this to become part of the standard library.
15.5.4.6 String.prototype.concat
Dmitry.
The two concatenation approaches I know of are:
- via +=
- push() into an array, join() it after the last push()
(1) can’t possibly be efficient,
Huh? Engines have optimized the hell out of 1 by essentially doing 2 under the hood. Even rhino's about a land a patch to do just that.
but if (2) is OK on all(!) platforms, then a library would be OK. However, given how frequently this is used, I would like this to become part of the standard library.
What exactly do you want supported?
Something like Java’s StringBuilder. If, however, (2) collects the concatenated substrings and only joins them on demand in current engines, then there is indeed no need for such a thing.
On Wed, Oct 5, 2011 at 12:10 PM, Axel Rauschmayer <axel at rauschma.de> wrote:
The two concatenation approaches I know of are:
- via +=
- push() into an array, join() it after the last push()
(1) can’t possibly be efficient,
Huh? Engines have optimized the hell out of 1 by essentially doing 2 under the hood. Even rhino's about a land a patch to do just that.
but if (2) is OK on all(!) platforms, then a library would be OK. However, given how frequently this is used, I would like this to become part of the standard library.
What exactly do you want supported?
Something like Java’s StringBuilder. If, however, (2) collects the concatenated substrings and only joins them on demand in current engines, then there is indeed no need for such a thing.
GWT's implementation of StringBuilder actually uses both methods #1 and #2 under the hood, because each is faster on different browsers (due to deferred binding, you only get the implementation for the browser you are using and parts of it can be inlined at call sites so you don't pay the penalty for multiple implementations).
On Oct 5, 2011, at 9:10 AM, Axel Rauschmayer wrote:
The two concatenation approaches I know of are:
- via +=
- push() into an array, join() it after the last push()
(1) can’t possibly be efficient,
Huh? Engines have optimized the hell out of 1 by essentially doing 2 under the hood. Even rhino's about a land a patch to do just that.
but if (2) is OK on all(!) platforms, then a library would be OK. However, given how frequently this is used, I would like this to become part of the standard library.
What exactly do you want supported?
Something like Java’s StringBuilder. If, however, (2) collects the concatenated substrings and only joins them on demand in current engines, then there is indeed no need for such a thing.
(1) is faster on modern engines.
I don't think we need to overdo it here. SunSpider already did :-/.
(1) is in fact really good optimized in modern engines. (In case you are interested search for "Ropes: an alternative to strings")
I think today it's not a very good idea to propose methods on probably existing performance problems.
On 6 October 2011 14:09, Tom Schuster <tom at schuster.me> wrote:
(1) is in fact really good optimized in modern engines. (In case you are interested search for "Ropes: an alternative to strings")
You don't even need ropes to make this fast for a lot of common cases. I think even a naive implementer would come up with something like this after a couple of beers:
- Create the initial string
- Mark a bit in the string's private handle (say, a bit in a tagged pointer) when it's referenced
- Upon += if the referenced bit is true, goto naive +=, else
- realloc() the underlying storage
- cat the new string onto the end of the old one
- this works whether or not realloc() moves the underlying storage, which it often won't
There's all kinds of ways to optimize operations like this. Let's not stifle innovation by over specifying.
Incidentally, Tom suggests a great search. The paper is a good read, but the Wikipedia article is a faster skim: en.wikipedia.org/wiki/Rope_(computer_science)
I think you just documented this: www.yafla.com/dforbes/String_Concatenation_and_Immutable_Strings_Speeding_Spidermonkey
Is this worthy of ES.next support? Or does it belong into a library?
The two concatenation approaches I know of are:
(1) can’t possibly be efficient, but if (2) is OK on all(!) platforms, then a library would be OK. However, given how frequently this is used, I would like this to become part of the standard library.