Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!spool.mu.edu!uunet!overload!dillon
From: dillon@overload.Berkeley.CA.US (Matthew Dillon)
Newsgroups: comp.sys.amiga.programmer
Subject: Re: How fast/slow is memory DEallocation?
Message-ID: <dillon.8233@overload.Berkeley.CA.US>
Date: 1 Jun 91 01:33:02 GMT
Article-I.D.: overload.dillon.8233
References: <8504@jhunix.HCF.JHU.EDU>
Organization: Not an Organization
Lines: 115

In article <8504@jhunix.HCF.JHU.EDU> barrett@jhunix.HCF.JHU.EDU (Dan Barrett) writes:
>
>	I wrote a program that uses a LARGE data structure with thousands of
>pointers, and I'm now porting it to my Amiga 1000 (stock 68000).  I have
>noticed that my data structure is being deallocated extremely slowly ---
>almost excruciatingly so.
>..
>	I have a feeling that this is a system-dependent issue and not an
>error in my code.  The program already runs on 3 other CPU's, and
>deallocation is lightning fast.  I am using Manx 5.0d.
>
>	Any suggestions?
>
>							 Dan

    If the system must allocate & deallocate similar-sized objects then
    I generally cache deallocated objects in a list instead of calling
    free() or FreeMem().  When you want to allocate an object simply check
    the appropriate list first.  If the list is not empty simply pop the
    object off of it, zero its memory (if necessary), and return it.

    Using singly linked lists for your freelist is generally the easiest
    way to implement this.  Example:

    #define CACHE_MAX	256		/*  cache 0-255 byte allocations */
    #define CACHE_SIZE	(CACHE_MAX/4)   /*  number of entries in cache   */
    void *CacheAry[CACHE_MAX/4];

    void *
    MyAlloc(bytes)
    long bytes;
    {
	void **ptr;
	long lws = (bytes + 3) >> 2;    /*  # of longwords  */

	if (lws < CACHE_MAX/4) {
	    void *res;

	    ptr = CacheAry + lws;
	    if (res = *ptr) {           /*  if list not empty   */
		*ptr = *(void **)res;   /*  unlink from list    */

		/*
		 *  zero object here (??)
		 */

		return(res);
	    }
	    /*
	     *	list empty, fall through to normal allocation
	     */
	}

	Do Normal Allocation of (lws * 4) bytes here

	/*
	 *  zero object here (??) then return object pointer.
	 */

    }

    void
    MyFree(res, bytes)
    void *res;
    long bytes;
    {
	long lws = (bytes + 3) >> 2;    /*  # of longwords      */

	if (lws < CACHE_MAX/4) {        /*  add to linked list  */
	    void **ptr = CacheAry + lws;

	    *(void **)res = *ptr;       /*  link into list      */
	    *ptr = res;
	} else {

	    Do Normal deallocation here

	}
    }


    Now, obviously that is kind of rough.  For one, if you are doing a
    *lot* of allocations you can cut down by changing 'normal allocation'
    to allocate out of a large block which is allocated in, say, 4K chunks.

    In some cases, when allocating and deallocating huge numbers of objects
    you might want to add code to return memory all the way back to the
    system when the free-list(s) get too large (too many deallocated
    objects in the freelist that could be free'd back to the system)

    But, essentially, the above is pretty much what you want.  Note
    especially the fact that allocations are rounded up to the nearest four
    byte boundry.  Do NOT make the mistake of allocating only enough to
    satisfy 'bytes' in the 'Do normal allocation' part above, this is a
    quick way to crash because the deallocator will then cache the object
    which may later be allocated from the same list with a request 3 bytes
    larger.  That's about the only sneakiness in the code.

    P.S. I haven't tested the above.

					    -Matt

>
> //////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
>| Dan Barrett, Department of Computer Science	    Johns Hopkins University |
>| INTERNET:   barrett@cs.jhu.edu	    |				     |
>| COMPUSERVE: >internet:barrett@cs.jhu.edu | UUCP:   barrett@jhunix.UUCP    |
> \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\/////////////////////////////////////

--

    Matthew Dillon	    dillon@Overload.Berkeley.CA.US
    891 Regal Rd.	    uunet.uu.net!overload!dillon
    Berkeley, Ca. 94708
    USA