Cocoa mail archive
Re: Repetitive Appending of Strings
FROM : Andrew Merenbach
DATE : Tue Feb 12 20:48:27 2008
Hi, Adam,
I understand what you (and others) are saying about premature
optimization. My feelings were only hunches, really, which is why
Shark might be a good idea. A test of the buffer idea, however --
with an NSZoneCalloc'ed buffer of unichars -- and calculating a
quotient out to a million digits, yielded what was something like a
three-second time for the actual calculation -- compared with ten
seconds when using the -appendFormat: method.
I can't imagine a case where a person would actually want more than a
thousand -- or even more than a hundred, really -- digits for their
equations, but I would like to make the program capable of this, if
only for completeness (now, there's also a practical limit, I suppose,
on how many bytes of data an NSTextView can hold, but I don't know
what that is). Using a buffer seems to speed things up immensely --
in fact, the slowest part seems now to be the actual updating of the
text view.
Cheers,
Andrew
On Feb 12, 2008, at 10:53 AM, Adam P Jenkins wrote:
> I agree that the method invocation itself is probably not a big
> problem. However appending to a string repeatedly could be very
> inefficient depending on how it's implemented. In the worst case,
> append always makes a new internal copy of its character buffer with
> just the right amount of extra space at the end to hold the appended
> content, so building up a string by appending one character at a
> time becomes a O(n^2) operation. I assume this is what the
> original poster was worried about.
>
> You can easily avoid this worst case behavior by using the
> +stringWithCapacity: method of NSMutableString, passing in the max
> length of your digit string, so that your string already has an
> internal buffer preallocated to the max number of characters the
> string will grow to. Then you can append one char at a time up to
> the internal capacity without causing any reallocate/copies to
> occur. This seems more straightforward to me than using an explicit
> char array which you have to manage and null-terminate yourself.
>
> Also, I don't know about NSMutableString specifically, but other
> string classes whose internals I've examined actually use a
> heuristic allocation strategy to avoid this worst case append
> behavior, at the expense of possibly using more memory than
> necessary. When an append is performed that causes the internal
> char buffer to need to be extended, rather than just extending it
> only as much as necessary to hold the new characters, they double
> the size of the internal buffer. This optimizes for the common
> usage of strings, where strings are built up from many small
> appends. The amortized cost of building up a string from n 1
> character appends then becomes O(n) rather than O(n^2).
>
> The upshot of all this is, don't prematurely optimize. It may be
> just fine to use -appendFormat: repeatedly if NSMutableString uses a
> heuristic like I described above. And in any case you can use
> +stringWithCapacity: to preallocate the internal buffer if you know
> how big your string can grow to. So that leaves you with only
> method call cost to worry about.
>
> Adam
>
>
> On Feb 12, 2008, at 1:22 PM, Michael Ash wrote:
>> An Objective-C message send takes on the order of a dozen cycles to
>> execute. Put it another way, on any Mac you can buy today, an
>> Objective-C message will take less than ten *nanoseconds* to
>> complete.
>>
>> Unless you're outputting a ridiculously large number of digits, and
>> you've actually measured the code and determined that this is where
>> the problem is, it's simply not worth worrying about.
>>
>> It's tempting to fret about Objective-C messages because they appear
>> to do so much, but they're ridiculously fast and it almost never pays
>> to try to avoid them.
>>
>> Mike
> _______________________________________________
>
> Cocoa-dev mailing list (<email_removed>)
>
> Please do not post admin requests or moderator comments to the list.
> Contact the moderators at cocoa-dev-admins(at)lists.apple.com
>
> Help/Unsubscribe/Update your Subscription:
> http://lists.apple.com/mailman/options/cocoa-dev/andrew.<email_removed>
>
> This email sent to andrew.<email_removed>
DATE : Tue Feb 12 20:48:27 2008
Hi, Adam,
I understand what you (and others) are saying about premature
optimization. My feelings were only hunches, really, which is why
Shark might be a good idea. A test of the buffer idea, however --
with an NSZoneCalloc'ed buffer of unichars -- and calculating a
quotient out to a million digits, yielded what was something like a
three-second time for the actual calculation -- compared with ten
seconds when using the -appendFormat: method.
I can't imagine a case where a person would actually want more than a
thousand -- or even more than a hundred, really -- digits for their
equations, but I would like to make the program capable of this, if
only for completeness (now, there's also a practical limit, I suppose,
on how many bytes of data an NSTextView can hold, but I don't know
what that is). Using a buffer seems to speed things up immensely --
in fact, the slowest part seems now to be the actual updating of the
text view.
Cheers,
Andrew
On Feb 12, 2008, at 10:53 AM, Adam P Jenkins wrote:
> I agree that the method invocation itself is probably not a big
> problem. However appending to a string repeatedly could be very
> inefficient depending on how it's implemented. In the worst case,
> append always makes a new internal copy of its character buffer with
> just the right amount of extra space at the end to hold the appended
> content, so building up a string by appending one character at a
> time becomes a O(n^2) operation. I assume this is what the
> original poster was worried about.
>
> You can easily avoid this worst case behavior by using the
> +stringWithCapacity: method of NSMutableString, passing in the max
> length of your digit string, so that your string already has an
> internal buffer preallocated to the max number of characters the
> string will grow to. Then you can append one char at a time up to
> the internal capacity without causing any reallocate/copies to
> occur. This seems more straightforward to me than using an explicit
> char array which you have to manage and null-terminate yourself.
>
> Also, I don't know about NSMutableString specifically, but other
> string classes whose internals I've examined actually use a
> heuristic allocation strategy to avoid this worst case append
> behavior, at the expense of possibly using more memory than
> necessary. When an append is performed that causes the internal
> char buffer to need to be extended, rather than just extending it
> only as much as necessary to hold the new characters, they double
> the size of the internal buffer. This optimizes for the common
> usage of strings, where strings are built up from many small
> appends. The amortized cost of building up a string from n 1
> character appends then becomes O(n) rather than O(n^2).
>
> The upshot of all this is, don't prematurely optimize. It may be
> just fine to use -appendFormat: repeatedly if NSMutableString uses a
> heuristic like I described above. And in any case you can use
> +stringWithCapacity: to preallocate the internal buffer if you know
> how big your string can grow to. So that leaves you with only
> method call cost to worry about.
>
> Adam
>
>
> On Feb 12, 2008, at 1:22 PM, Michael Ash wrote:
>> An Objective-C message send takes on the order of a dozen cycles to
>> execute. Put it another way, on any Mac you can buy today, an
>> Objective-C message will take less than ten *nanoseconds* to
>> complete.
>>
>> Unless you're outputting a ridiculously large number of digits, and
>> you've actually measured the code and determined that this is where
>> the problem is, it's simply not worth worrying about.
>>
>> It's tempting to fret about Objective-C messages because they appear
>> to do so much, but they're ridiculously fast and it almost never pays
>> to try to avoid them.
>>
>> Mike
> _______________________________________________
>
> Cocoa-dev mailing list (<email_removed>)
>
> Please do not post admin requests or moderator comments to the list.
> Contact the moderators at cocoa-dev-admins(at)lists.apple.com
>
> Help/Unsubscribe/Update your Subscription:
> http://lists.apple.com/mailman/options/cocoa-dev/andrew.<email_removed>
>
> This email sent to andrew.<email_removed>
