Message
> ----- Original Message -----
> From: Paul Heinz
> Sent: Thursday, August 08, 2002 6:15 PM
> Subject: RE: [DUG]: File Export Speed
> Corey wrote:
> > > ----- Original Message -----
> > > From: Myles Penlington
> > > Sent: Wednesday, August 07, 2002 10:20 AM
> > > Subject: RE: [DUG]: File Export Speed
> > >
> > > This string concatenation will be very slow - it is a
> > > N squared algorithm for the number of bytes copied ie
> > > bad news.
> >
> > Not quite that bad. AFAIK Strings allocate memory a
> > block at a time... but it's still pretty bad. I wrote a
> > program that passed Strings down a recursive tree
> > search, then rewrote it using PChars and got a major
> > speed increase... run time went from an average of 2
> > minutes to a little over 18 seconds. Definitely worth
> > the extra coding effort.
>
> Yes, it is an O(N squared) algorithm since each string
> concatenation will require an extension which means
> allocating a new bigger string and copying the result
> over. Copying the string will take an amount of time
> proportional to the current length (a function of N) and
> this will be done a number of times that is a function of
> N. Hence, overall O(N squared) where N is Rows * Fields.
Seems I was wrong. I stepped through the asm code in System.pas, and it
does indeed reallocate the string's memory every time you add to it. If the
string happens to be in a space it can grow into the memory management
simply extends the allocated buffer, otherwise it will allocate a new buffer
and copy the contents of the string to it then append the new string. So it
has a non-predictive order approaching O(N^2), or possibly O(N^2log(N)) for
extreme memory fragmentation.
I think perhaps I was getting confused with TMemoryStream, which does
allocate (in BCB4 at least) in blocks of 8k.
> Change the code to write each string field independently
> (i.e. avoid concatenations) and the algorithm will run
> much faster and still offer text output. Some buffering on
> the TFileStream may help as well to avoid many small
> writes but the OS should do a fair job of that for you.
I agree. String concatenation is not required in this case, and just wastes
time. Writing directly to the stream, with or without a buffer of some
sort, should be significantly faster.
--
Corey Murtagh
The Electric Monk
"Quidquid latine dictum sit, altum viditur!"
---------------------------------------------------------------------------
New Zealand Delphi Users group - Delphi List - [EMAIL PROTECTED]
Website: http://www.delphi.org.nz
To UnSub, send email to: [EMAIL PROTECTED]
with body of "unsubscribe delphi"
Web Archive at: http://www.mail-archive.com/delphi%40delphi.org.nz/
