Re: String concatenation
I think you just documented this: http://www.yafla.com/dforbes/String_Concatenation_and_Immutable_Strings_Speeding_Spidermonkey/ On Fri, Oct 7, 2011 at 2:01 AM, Wes Garland wrote: > On 6 October 2011 14:09, Tom Schuster 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: > http://en.wikipedia.org/wiki/Rope_%28computer_science%29 > > Wes > > -- > Wesley W. Garland > Director, Product Development > PageMail, Inc. > +1 613 542 2787 x 102 > ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: String concatenation
On 6 October 2011 14:09, Tom Schuster 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: http://en.wikipedia.org/wiki/Rope_%28computer_science%29 Wes -- Wesley W. Garland Director, Product Development PageMail, Inc. +1 613 542 2787 x 102 ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: String concatenation
(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 Thu, Oct 6, 2011 at 7:34 PM, Brendan Eich wrote: > (1) is faster on modern engines. > I don't think we need to overdo it here. SunSpider already did :-/. > /be > > ___ > es-discuss mailing list > es-discuss@mozilla.org > https://mail.mozilla.org/listinfo/es-discuss > > ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: String concatenation
On Oct 5, 2011, at 9:10 AM, Axel Rauschmayer wrote: >> The two concatenation approaches I know of are: >> 1. via += >> 2. 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 :-/. /be ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: String concatenation
On Wed, Oct 5, 2011 at 12:10 PM, Axel Rauschmayer wrote: > The two concatenation approaches I know of are: >> 1. via += >> 2. 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). -- John A. Tamplin Software Engineer (GWT), Google ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: String concatenation
> The two concatenation approaches I know of are: > 1. via += > 2. 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. -- Dr. Axel Rauschmayer a...@rauschma.de twitter.com/rauschma home: rauschma.de blog: 2ality.com ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: String concatenation
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: 1. via += 2. 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. ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: String concatenation
On Wed, Oct 5, 2011 at 11:45 AM, 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: > 1. via += > 2. 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? ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss