Path: utzoo!utgpu!attcan!uunet!husc6!ukma!tut.cis.ohio-state.edu!osu-cis!att!ihlpb!gregg
From: gregg@ihlpb.ATT.COM (Wonderly)
Newsgroups: comp.lang.c
Subject: Re: Efficient coding considered harmful?
Message-ID: <9027@ihlpb.ATT.COM>
Date: 3 Nov 88 14:55:46 GMT
References: <1709@garth.UUCP>
Organization: AT&T Bell Laboratories - Naperville, Illinois
Lines: 77

From article <1709@garth.UUCP>, by smryan@garth.UUCP (Steven Ryan):
>>>Realloc has to copy data, so this should be less efficient than just
>>>doing another malloc & free.

UMMMM, realloc() only moves things when it has to.

>>
>>Err, umm, "realloc" is often used when you have e.g. an array with N
> 
> ERRR, UMMMM, we seem to have lost the point here.
> 
> It sounds as though someone's guessing what the data structure size should
> be, guesses wrong, and has to increase it. If data structure size keeps
> getting bumped bit by bit until the problem size is finally determined,
> then we've got an O(n) structure which has been copied O(n/increment)=O(n)
> times so that the cost of creating just this structure is O(n**2) so that
> the overall time is quadratic, at best.
>
> .....
>
> Well, gee, how do you allocate an indefinite sized array?
> 
> Glad you asked. I stuff it down a stack, each element individually
> handcrafted with malloc, until I've reached the end and know exactly
> how big it is. Then, IF I need random access, I copy it to an array.
> Linear time.

That is moving all of the data twice, but you are still doing more work than
might be necessary for the simple case.  The cost realloc()ing an array can be
decreased by using incremental resizing where the increment is >>> 1.

/*
 *	addstr()
 *
 *	Add a dynamically allocated string to a dynamically allocated array.
 *	Input is the existing array pointer, the number of entries already
 *	allocated, the entries used (current index) and the string to add.
 */

#define	BIGINC	100

char **addstr (arr, acnt, cnt, str)
	register char **arr, *str;
	register int *acnt, *cnt;
{
	register char *t;

	/*  If space exhausted get some more.  */

	if (*cnt == *acnt) {

		/*  If space allocated, realloc else malloc.  */

		if (!acnt)
			arr = (char **)realloc (arr, (*acnt += BIGINC) * sizeof (char *));
		else
			arr = (char **)malloc ((*acnt += BIGINC) * sizeof (char *));
	}

	/*  Allocate space for the string.  */

	t = (char *) malloc (strlen (str) + 1);
	strcpy (t, str);
	arr[(*cnt)++] = t;
	return (arr);
}

Now, only if there are more than BIGINC entries will I have to realloc the
array, and better yet, I didn't have to move the strings.  And, only
every BIGINC entries will I have to move the pointers...  This method is
extremely STRAIGHT FORWARD, and easy to understand.  It does not involve
lots of tricky programming to try and get around having to move the strings.

-- 
Gregg Wonderly
AT&T Bell Laboratories                   DOMAIN: gregg@ihlpb.att.com
IH2D217 - (312) 979-2794                 UUCP:   att!ihlpb!gregg