Re: Repetitive Appending of Strings
Re: Repetitive Appending of Strings
- Subject: Re: Repetitive Appending of Strings
- From: Andrew Merenbach <email@hidden>
- Date: Tue, 12 Feb 2008 11:48:27 -0800
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@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
_______________________________________________
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