Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site utcsri.UUCP
Path: utzoo!utcsri!greg
From: greg@utcsri.UUCP (Gregory Smith)
Newsgroups: net.unix,net.unix-wizards,net.lang.c
Subject: Re: faster malloc anyone?
Message-ID: <2699@utcsri.UUCP>
Date: Sun, 4-May-86 14:19:43 EDT
Article-I.D.: utcsri.2699
Posted: Sun May  4 14:19:43 1986
Date-Received: Sun, 4-May-86 19:14:33 EDT
References: <433@geowhiz.UUCP>
Reply-To: greg@utcsri.UUCP (Gregory Smith)
Distribution: net
Organization: CSRI, University of Toronto
Lines: 123
Summary: Yup

In article <433@geowhiz.UUCP> larry@geowhiz.UUCP (Larry McVoy) writes:
>each call to strsav().  So, I wrote the following little chunks of code and
>am requesting comments.  Can anyone point out why these are a *bad* idea 
>(aside from the obvious upper bound problem)?  Another problem is that
>free() won't work on these blocks...
	stay tuned...
>
>new.h:
># define	BLKSIZ		8096
>char* new();
>
>utils.c:
>/* utils.c -- strsav(), new() */
># include	"new.h"
>
>    char*
>strsav(s)
>    register char* s;
>{
>    char* strcpy();
>    register char* t;
>
>    t = new(strlen(s) + 1);	/* strings smaller than BLKSIZ */
>    return strcpy(t, s);
>}
>
>
>/*------------------------------------------------------------------02/May/86-*
> * new(size) - fast(??) memory allocator
> *
> * Inputs    -> (int)
> *
> * Returns   -> (char*)
> *
> * Results  ->The memory is allocated in big contiguous blocks via calloc(3).
> *		If the requst can fit in what's left of a block, then a block
> *		of the size requested is returned.  Otherwise, the rest of the
> *		block is discarded & a new block is allocated. 
> * 
> * Warning   -> This would seem to work great for little stuff.  Don't use it
> *		for big blocks.  Absolute largest allocatable block is BLKSIZ.
> *		For speed NO CHECK IS PERFORMED TO SEE IF THE REQUEST IS LESS
> *		THAN BLKSIZ.  BLKSIZ is guaranteed to be 1k or bigger (usually
> *		much bigger).
> * Revisions:
> *-----------------------------------------------------------------larry-*/
>    char*
>new(size)
>    register unsigned size;
>{
>    register char* blk;
>    static char* block = NULL;
>    static unsigned bytes_left = 0;
>
>    if (bytes_left < size)
			/* bytes_left should be set to BLKSIZ here */
>	if (!(block = calloc(1, BLKSIZ)))
>	    syserr("calloc in new");
>
>    blk = block;
>    block += size;
>    bytes -= size;
     return blk;		:-)
>}
>-- 

If the storage occupied by these strings can be released all at once,
the following 'new' can be used:


struct str_block{
	struct str_block *sb_link;
	char sb_chars[ BLKSIZ ];
} *allocated = NULL;
unsigned bytes_left = 0;
char* block;

char *new(size)
register unsigned size;
{   register char* blk;
    register struct str_block *new_blk;

    if (bytes_left < size){
	if ((new_blk =(struct str_block*) malloc(sizeof( struct str_block)))
		== NULL)
	    syserr("malloc in new");
	bytes_left = BLKSIZ;
	new_blk->sb_link = allocated;
	allocated = new_blk;
	block = new_blk->sb_chars;
    }
    blk = block;
    block += size;
    bytes_left -= size;
    return blk;
}

/*
 * this subroutine frees up all allocated memory
 */
forget(){
	register struct str_block *p;
	while( (p = allocated) != NULL ){
		allocated = p->sb_link;
		free(p);
	}
	bytes_left = 0;
}

I used a similar approach on a program I wrote recently - many small structs
needed to be allocated and reused during a certain phase of execution, and
then they were all released at once. So I got them from malloc in blocks of
about 200, and handled them on linked lists. When I was done, I released all
the blocks, which were kept on another linked list.

An enhancement: maintain separate 'allocated, bytes_left, block'
triplets for independent storage categories - then each category can be
'forgotten' independently of the others.

-- 
"For every action there is an equal and opposite malfunction"
----------------------------------------------------------------------
Greg Smith     University of Toronto      UUCP: ..utzoo!utcsri!greg