3 ms·
You just brought back old memories for me. I wrote the heap manager for Borland C. I chose the next-fit algorithm for its balance of speed and reasonable fragme
by davidst 11y ago
You just brought back old memories for me. I wrote the heap manager for Borland C. I chose the next-fit algorithm for its balance of speed and reasonable fragmentation under common use cases. Best-fit performs exactly as you described.
- musesum 11y agoMan, oh man, BC was the bomb! In a good way; maybe I should exclaim that it was the anti-bomb!
- dalke 11y agoI pulled out my old Minix (1987) book, which I keep for nostalgia. Tanenbaum on p. 202 writes: > The simplest algorithm is first fit... A minor variation of first fit is next fit. ... Simulations by Bays (1977) show that next first gives slightly worse performance than first fit. ... Another well-known algorithm is best fit. ... Best fit is slower than first fit.... Somewhat surprisingly, it also results in more wasted memory than first fit or next fit because it tends to fill up memory with tiny, useless holes. First fit generates larger holes on the average. ... one could think about worst fit... Simulation has shown that worst first is not a very good idea. ... > quick fit ... has the same disadvantage as all schemes that sort by hole size, namely, when a process terminates or is swapped out, finding its neighbors to see if a merge is possible is expensive. If merging is not done, memory will quickly fragment into a large number of small, useless holes.