Which memory allocation strategy?

Hi all,


I'm thinking about writing a new allocator for C/C++, and I need to
decide on an allocation strategy. My two candidates are "Best Fit",
in which an allocation request is satisfied by the smallest big enough
free block and "Address order first fit", in which a request is
satisfied by the big enough free block with the lowest address (lowest
address in the oldest memory region if you allocate from the OS that
way).


Now, I can implement best fit in nearly constant time per allocation,
whereas address order first fit necessarily takes O(log N) in the
number of free blocks. I have an excellent survey of allocation
strategies which suggests that these strategies have similar
fragmentation characteristics, but I intuitively prefer address order
first fit and believe that it will allow me to return memory to the OS
more often.


I seek, then, some subjective advice.




</Matt>




Matt Timmermans | Phone: +1 613 596-2233
Microstar Software Ltd. | Fax: +1 613 596-5934
3775 Richmond Road | E-mail: mtimmerm@microstar.com
Nepean Ontario CANADA K2H 5B7 | Web: http://www.microstar.com
--

Return to the comp.compilers page.
Search the comp.compilers archives again.