Efficient string concatenation - proposed new
Code Critic rule Optimization > String concatenation instead of streams says: "Check for string concatenation inside some iteration message. Since string concatenation is O(n^2), it is better to use streaming since it is O(n) - assuming that n is large enough. As a general principal avoid , since the receiver is copied. Therefore chaining , messages will lead to multiple useless copies of the receiver." That is, String streamContents: [:s | #('abc' 'def' 'ghi') do: [:each | s nextPutAll: each asString]] should be used instead of... 'abc' , 'def' , 'ghi'. However the first clutters the code. What about something like... { 'abc' . 'def' . 'ghi' } asStreamString where Collection>>asStreamString ^ String streamContents: [:s | self do: [:each | s nextPutAll: each asString]] cheers -ben
You already have it: '' join: #('abc' 'def' 'ghi') Doru On Sat, Nov 16, 2013 at 7:09 PM, <btc@openinworld.com> wrote:
Code Critic rule Optimization > String concatenation instead of streams says:
"Check for string concatenation inside some iteration message. Since string concatenation is O(n^2), it is better to use streaming since it is O(n) - assuming that n is large enough. As a general principal avoid , since the receiver is copied. Therefore chaining , messages will lead to multiple useless copies of the receiver."
That is, String streamContents: [:s | #('abc' 'def' 'ghi') do: [:each | s nextPutAll: each asString]]
should be used instead of... 'abc' , 'def' , 'ghi'.
However the first clutters the code. What about something like... { 'abc' . 'def' . 'ghi' } asStreamString where Collection>>asStreamString ^ String streamContents: [:s | self do: [:each | s nextPutAll: each asString]]
cheers -ben
-- www.tudorgirba.com "Every thing has its own flow"
Well, maybe, although it's interesting to consider how many strings streams need to beat string concatenation. Moreover, streams aren't hyper efficient either... On 11/16/13 10:09 , btc@openinworld.com wrote:
Code Critic rule Optimization > String concatenation instead of streams says:
"Check for string concatenation inside some iteration message. Since string concatenation is O(n^2), it is better to use streaming since it is O(n) - assuming that n is large enough. As a general principal avoid , since the receiver is copied. Therefore chaining , messages will lead to multiple useless copies of the receiver."
That is, String streamContents: [:s | #('abc' 'def' 'ghi') do: [:each | s nextPutAll: each asString]]
should be used instead of... 'abc' , 'def' , 'ghi'.
However the first clutters the code. What about something like... { 'abc' . 'def' . 'ghi' } asStreamString where Collection>>asStreamString ^ String streamContents: [:s | self do: [:each | s nextPutAll: each asString]]
cheers -ben
On 17 Nov 2013, at 12:49, Andres Valloud <avalloud@smalltalk.comcastbiz.net> wrote:
Well, maybe, although it's interesting to consider how many strings streams need to beat string concatenation. Moreover, streams aren't hyper efficient eitherâ¦
Yes, indeed. It also depends on what is being concatenated (constants vs objects). Quick and dirty (totally unscientific): [ 'foo', 'bar' ] bench. '4,650,000 per second.' [ '' join: #( 'foo' 'bar' ) ] bench. '814,000 per second.' [ String streamContents: [ :out | out nextPutAll: 'foo'; nextPutAll: 'bar' ] ] bench. '1,900,000 per second.' [ 'foo', 'bar', 'baz' ] bench. '2,470,000 per second.' [ '' join: #( 'foo' 'bar' 'baz' ) ] bench. '719,000 per second.' [ String streamContents: [ :out | out nextPutAll: 'foo'; nextPutAll: 'bar'; nextPutAll: 'baz' ] ] bench. '1,710,000 per second.' [ 'foo', 'bar', 'baz', 'foobar' ] bench. '2,030,000 per second.' [ '' join: #( 'foo' 'bar' 'baz' 'foobar' ) ] bench. '665,000 per second.' [ String streamContents: [ :out | out nextPutAll: 'foo'; nextPutAll: 'bar'; nextPutAll: 'baz'; nextPutAll: 'foobar' ] ] bench. '1,580,000 per second.' [ Date today asString, $- asString, Time now asString ] bench. '61,800 per second.' [ String streamContents: [ :out | out print: Date today; nextPut: $-; print: Time now ] ] bench. '71,700 per second.' Weâre only measuring execution speed, not memory allocation, which is important too. The length of the strings is a variable as well, of course. Furthermore, many #printOn: implementations are not very efficient while they should be. Conclusion, letâs be careful with a too simple advice. Sven
On 11/16/13 10:09 , btc@openinworld.com wrote:
Code Critic rule Optimization > String concatenation instead of streams says:
"Check for string concatenation inside some iteration message. Since string concatenation is O(n^2), it is better to use streaming since it is O(n) - assuming that n is large enough. As a general principal avoid , since the receiver is copied. Therefore chaining , messages will lead to multiple useless copies of the receiver."
That is, String streamContents: [:s | #('abc' 'def' 'ghi') do: [:each | s nextPutAll: each asString]]
should be used instead of... 'abc' , 'def' , 'ghi'.
However the first clutters the code. What about something like... { 'abc' . 'def' . 'ghi' } asStreamString where Collection>>asStreamString ^ String streamContents: [:s | self do: [:each | s nextPutAll: each asString]]
cheers -ben
this one is surprising to me
[ 'foo', 'bar', 'baz', 'foobar' ] bench. '2,030,000 per second.' [ '' join: #( 'foo' 'bar' 'baz' 'foobar' ) ] bench. '665,000 per second.' [ String streamContents: [ :out | out nextPutAll: 'foo'; nextPutAll: 'bar'; nextPutAll: 'baz'; nextPutAll: 'foobar' ] ] bench. '1,580,000 per second.'
The details really don't fit in an email, however the 2nd volume of my Fundamentals book already has an analysis of this issue and hence my previous comment. On 11/17/13 8:45 , Stéphane Ducasse wrote:
this one is surprising to me
[ 'foo', 'bar', 'baz', 'foobar' ] bench. '2,030,000 per second.' [ '' join: #( 'foo' 'bar' 'baz' 'foobar' ) ] bench. '665,000 per second.' [ String streamContents: [ :out | out nextPutAll: 'foo'; nextPutAll: 'bar'; nextPutAll: 'baz'; nextPutAll: 'foobar' ] ] bench. '1,580,000 per second.'
.
Weâre only measuring execution speed, not memory allocation, which is important too.
Yes. And besides having to collect the garbage at some point, allocation can be costly because the VM has to zero out the string bytes (or nil them if the string is not encoded) and then write on those zeroed (nilled) places with something else. It takes time.
The length of the strings is a variable as well, of course.
The order also matters, e.g. (String new: 7812681237643287423), 'a', 'b', 'c' and the way you aggregate the result matters as well.
Conclusion, letâs be careful with a too simple advice.
Yes, it's much more complex than it seems when the inefficiency of naive concatenation methods is not flagrant. Andres.
Hi, Hmm, I knew it would be slower, but I did not expect this slowdown. Thank you both for the explanations. Something to learn every single day :). Cheers, Doru On Sun, Nov 17, 2013 at 9:54 PM, Andres Valloud < avalloud@smalltalk.comcastbiz.net> wrote:
Weâre only measuring execution speed, not memory allocation, which is
important too.
Yes. And besides having to collect the garbage at some point, allocation can be costly because the VM has to zero out the string bytes (or nil them if the string is not encoded) and then write on those zeroed (nilled) places with something else. It takes time.
The length of the strings is a variable as well, of course.
The order also matters, e.g.
(String new: 7812681237643287423), 'a', 'b', 'c'
and the way you aggregate the result matters as well.
Conclusion, letâs be careful with a too simple advice.
Yes, it's much more complex than it seems when the inefficiency of naive concatenation methods is not flagrant.
Andres.
-- www.tudorgirba.com "Every thing has its own flow"
participants (5)
-
Andres Valloud -
btc＠openinworld.com -
Stéphane Ducasse -
Sven Van Caekenberghe -
Tudor Girba