Which memory allocation strategy?

mtimmerm@microstar.com (Matt Timmermans)
25 Jan 1997 22:10:50 -0500

          From comp.compilers

Related articles
Which memory allocation strategy? mtimmerm@microstar.com (1997-01-25)
| List of all articles for this month |

From: mtimmerm@microstar.com (Matt Timmermans)
Newsgroups: comp.compilers
Date: 25 Jan 1997 22:10:50 -0500
Organization: IGS - Information Gateway Services
Keywords: storage, question

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

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 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

Post a followup to this message

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