Re: Repetitive Appending of Strings
Re: Repetitive Appending of Strings
- Subject: Re: Repetitive Appending of Strings
- From: Adam P Jenkins <email@hidden>
- Date: Tue, 12 Feb 2008 13:53:28 -0500
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@hidden)
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:
This email sent to email@hidden