Complexity of reallocating storage (was users command crap)

[John F Haugh II]

In article <15325:Jan2903:19:4991 at kramden.acf.nyu.edu> brnstnd at kramden.acf.nyu.edu (Dan Bernstein) writes:
>Any single-pass ``users'' has to either use quadratic time or be a rude
>abuser of resources. Why not use two passes and be done with it?

No, it doesn't.  It can get it exactly right the first time and be done
with it.

	fd = open ("/etc/utmp", O_RDONLY);
	fstat (fd, &statb);
	users = (struct utmp *) malloc (statb.st_size);
	read (fd, (char *) users, statb.st_size);

This has certain problems, all of which Dan will point out, but any
non-atomic operation has other "problems".  I would argue that this
has "less" problems because it is "more" atomic and far less complex.
Besides, this is my posting, and quite clearly I am right about
everything I post [ ;-)'s for the humor impaired only ]

As for doubling realloc, given the large number of demand paged
systems these days, doubling realloc often is a big win because the
wasted pages are never touched, so they neither take physical memory
nor backing store.  Doubling realloc avoids the silly practice of
gradually incrementing your memory up to the appropriate size.  That
is a sure performance sucker if ever there was one.
-- 
John F. Haugh II                             UUCP: ...!cs.utexas.edu!rpp386!jfh
Ma Bell: (512) 832-8832                           Domain: jfh at rpp386.cactus.org
"13 of 17 valedictorians in Boston High Schools last spring were immigrants
 or children of immigrants"   -- US News and World Report, May 15, 1990