Re: CVS update: subversion/subversion/client main.c

On Mon, Feb 05, 2001 at 01:35:25AM -0500, Greg Hudson wrote:
> Greg Stein committed:
> > + /* ### this function must be fixed to do an apr_stat() for SIZE,
> > + ### alloc the buffer, then read the file into the buffer. Using
> > + ### an svn_string_t means quadratic memory usage: start with
> > + ### BUFSIZE, allocate 2*BUFSIZE, then alloc 4*BUFSIZE, etc. */
>
> This doesn't yield quadratic memory usage; in the limit, this yields
> memory usage of double the size of the file. (Try counting from the
> last allocation back to the first.)
>
> We can still do better, of course; a factor of two is a big deal for a
> potentially unbounded file. (Not that I've checked what this file is
> or how likely it is to get large.)

My comment wasn't clear, which I noticed after a second read. I added a new
sentence to the end: "The pools keep each of those allocs around."

Let's say that BUFSIZE is 10 bytes, and you read a 1000 byte file:

*) alloc BUFSIZE (10) bytes. copy the read data in (10 bytes).
*) double to 20 bytes. copy the read data in.
*) double to 40 bytes. copy in two chunks of data.
*) double to 80 bytes. copy in four chunks.
*) double to 160. copy 8 chunks
*) double to 320. copy 16 chunks
*) double to 640. copy 64 chunks
*) double to 1280. copy 36 chunks.

Total memory allocated: 1280+640+320+160+80+40+20+10 = 2250 bytes.

If there is a better name for that behavior than "quadratic", then I'd be
happy to be educated. I think that is the appropriate term here.

[ N + N/2 + N/4 + N/8 ... any mathematicians around? ]

Ah... rereading your comment now that I've written the formula. You're
saying that formula converges on 2N, right? Ah. So yes... O(N) memory. The
copying is something like O(N log N) though. Those first ten bytes get
copied a bunch of times.

Well, whatever. It can clearly be improved :-)

In this instance, the file won't be large. It is used for reading options
from a file :-)

Back to your original point: can you think of a goo term for describing the
behavior? [that I can slap into that comment?]

Cheers,
-g

-- 
Greg Stein, http://www.lyra.org/