[net.unix] faster malloc anyone?

larry@geowhiz.UUCP (Larry McVoy) (05/03/86)

[ munch.  Does this bug still exist???? ]

I was looking at the src for [cm]alloc() and came to the (hasty) conclusion
that they take to long for little memory requests.  It seems that they are 
leftover from the days of 256K unix systems where every byte counted.  With
workstations typically having gigabytes of vm and 2-4 megs of phys mem, it
seems that we might sacrifice some memory for speed.  In particular, if you
want to save strings (5-80 bytes), it seems wasteful to do a lot of work for
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...

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)
	if (!(block = calloc(1, BLKSIZ)))
	    syserr("calloc in new");

    blk = block;
    block += size;
    bytes -= size;
}
-- 
Larry McVoy
-----------
Arpa:  mcvoy@rsch.wisc.edu                              
Uucp:  {seismo, ihnp4}!uwvax!geowhiz!geophiz!larry      

"Just remember, wherever you go -- there you are."
 	-Buckaroo Banzai

greg@utcsri.UUCP (Gregory Smith) (05/04/86)

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