Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!zaphod.mps.ohio-state.edu!wuarchive!uunet!mcsun!cernvax!chx400!bernina!neptune!iiic.ethz.ch!umueller
From: umueller@iiic.ethz.ch (Urban Dominik Mueller)
Newsgroups: comp.sys.amiga.programmer
Subject: Re: How fast/slow is memory DEallocation?
Message-ID: <29283@neptune.inf.ethz.ch>
Date: 7 Jun 91 10:31:37 GMT
References: <8504@jhunix.HCF.JHU.EDU> <dillon.8233@overload.Berkeley.CA.US> <8524@jhunix.HCF.JHU.EDU>
Sender: news@neptune.inf.ethz.ch
Reply-To: umueller@iiic.ethz.ch (Urban Dominik Mueller)
Organization: Departement Informatik, ETH, Zurich
Lines: 29

In article <8524@jhunix.HCF.JHU.EDU> barrett@jhunix.HCF.JHU.EDU (Dan Barrett) writes:
>In article <dillon.8233@overload.Berkeley.CA.US> dillon@overload.Berkeley.CA.US (Matthew Dillon) writes:
>>    [cache small similar-sized allocations]
>
>	Won't work for my application, unfortunately.  I do all the
>allocations first, traverse the data structure, and then deallocate the
>whole thing.  There are no intermediate dealloc/allocs.

The situation you describe is a most typical application for a second
speedup scheme. I assume all your tree nodes have the same size, if
not, you have to change the function to distribute bytes:

int NumberOfFreeItems=0;

void *ItemAlloc()
{
    if (NumberOfFreeItems==0) {
	AllocArrayOf30Items();
	PutArrayInLinkedList();
	NumberOfFreeItems=30;
    }
    return AllocedArray[--NumberOfFreeItems];
}

Note there is no ItemFree(), you can free only all items at once. This
tailored alloc will reduce memory efficiency, but speed up allocations
and deallocations a lot.

    -Dominik