7 ms·

"Best Fit" memory management. Malloc three buffers, in order: 64K, 1K, 64K. Now free all three. Next allocate 1K. Guess where it resides in the heap? Yep: the m

by musesum 11y ago

"Best Fit" memory management. Malloc three buffers, in order: 64K, 1K, 64K. Now free all three. Next allocate 1K. Guess where it resides in the heap? Yep: the middle! After a while, memory was fragmented with 1K detritus. Even though you were supposed to have 500K available, there wasn't room for a 64K buffer anymore. This was the default for Microsoft's C compiler, in 1990. How did I find out? There was a project that was crashing into a blue screen of death after a few hours. The crashing library had #defines that went 15 levels deep. The stack dump wasn't very instructive. Even though the library ISV was based in Boston, I had to fly out to Santa Cruz to talk to the developer directly. He was somewhat belligerent: "you should have figured it out yourself!". 15 levels of #defines. He was the perfect example of the other side of Dunning-Kruger thinking his arcane shit was obvious. But, that didn't solve the problem. His fix didn't. So, I flew back to Boston. I started to trace everything with -ahem- #defines of the main APIs. It was turning into a Zen Koan: the sound of one app crashing. Everything worked with the Borland compiler. It was just the MSC compiler that failed. The company was one of the top 3 ISVs back then. Meetings about what to do would last for hours. There were technical politics: "Can we use Borland?" No; the company had standardized on MS. I could talk to their engineers directly, though. But, they didn't have a clue. So, I read though the docs to see what compiler switches were available. And there it was: best-fit. Fixed! So, I wrote an analysis about why best-fit was absolutely the worst possible memory management and sent it to Microsoft. It took 8 years for MS to change the default. So, the reason why software would blow up? Best fit. Why early versions of Windows with go into blue-screen-of-death? Best fit. How many developers had to deal with this? Worst nightmare in aggregate.

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 ago
  Man, oh man, BC was the bomb! In a good way; maybe I should exclaim that it was the anti-bomb!
- dalke 11y ago
  I 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.
Fiahil 11y ago
Wait, the three buffers should be merged together upon free(), if they're consecutive in memory, isn't it? What did I miss?
- coldcode 11y ago
  Typical memory managers put blocks onto a free list during free() calls in order to reuse them later. I wrote a commercial memory allocator library in the 90's and I always coalesced consecutive blocks in free(), which limits fragmentation and speeds up allocation by avoiding long list searches. But even then many libraries did the easy choice of the free lists.
  - Fiahil 11y ago
    That would be, indeed, a poor memory allocator implementation. But unlike what parent said, it's definitively not a failure of the best fit algorithm.
  - musesum 11y ago
    @coldcode, was that SmartHeap? The 90's was the era of 3rd party tools for memory pooling and GuardMalloc for debugging.
    - coldcode 11y ago
      No I competed with them and basically pushed them out of the Mac OS market. But OS X came along and mine was no longer necessary.
purpled_haze 11y ago
> the company had standardized on MS This is a whole topic in itself. There has to be some good medium between consistency and best tool for the job. For example, IBM determined that, despite Windows dominating Desktop/laptop market share ( https://en.wikipedia.org/wiki/Usage_share_of_operating_systems https://en.wikipedia.org/wiki/Usage_share_of_operating_syste... ), Macs were cheaper to use ( http://www.businessinsider.com/apple-says-ibm-saves-270-for-every-mac-it-uses-instead-of-a-pc-2015-10 http://www.businessinsider.com/apple-says-ibm-saves-270-for-... ). Now you could go further into that and ask whether OS X is the right tool for everyone's job, as I'd argue in some cases it isn't. However, I think that it shouldn't be that difficult for a company to be open to letting their employees choose the hardware, software, and other tools to get the job done. If the budget is there, then why not have the discussion, and if it isn't, allow the employee to make the case for an exception. The same could be said for priorities and tasks. Allow your employees to make the case for what they should be working on, and allow group discussion if appropriate. You may be surprised at what good could come of it.

by musesum 11y ago

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 ago
Man, oh man, BC was the bomb! In a good way; maybe I should exclaim that it was the anti-bomb!
dalke 11y ago
I 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.

Fiahil 11y ago

Wait, the three buffers should be merged together upon free(), if they're consecutive in memory, isn't it? What did I miss?

coldcode 11y ago
Typical memory managers put blocks onto a free list during free() calls in order to reuse them later. I wrote a commercial memory allocator library in the 90's and I always coalesced consecutive blocks in free(), which limits fragmentation and speeds up allocation by avoiding long list searches. But even then many libraries did the easy choice of the free lists.
- Fiahil 11y ago
  That would be, indeed, a poor memory allocator implementation. But unlike what parent said, it's definitively not a failure of the best fit algorithm.
- musesum 11y ago
  @coldcode, was that SmartHeap? The 90's was the era of 3rd party tools for memory pooling and GuardMalloc for debugging.
  - coldcode 11y ago
    No I competed with them and basically pushed them out of the Mac OS market. But OS X came along and mine was no longer necessary.

purpled_haze 11y ago

> the company had standardized on MS This is a whole topic in itself. There has to be some good medium between consistency and best tool for the job. For example, IBM determined that, despite Windows dominating Desktop/laptop market share ( https://en.wikipedia.org/wiki/Usage_share_of_operating_systems https://en.wikipedia.org/wiki/Usage_share_of_operating_syste... ), Macs were cheaper to use ( http://www.businessinsider.com/apple-says-ibm-saves-270-for-every-mac-it-uses-instead-of-a-pc-2015-10 http://www.businessinsider.com/apple-says-ibm-saves-270-for-... ). Now you could go further into that and ask whether OS X is the right tool for everyone's job, as I'd argue in some cases it isn't. However, I think that it shouldn't be that difficult for a company to be open to letting their employees choose the hardware, software, and other tools to get the job done. If the budget is there, then why not have the discussion, and if it isn't, allow the employee to make the case for an exception. The same could be said for priorities and tasks. Allow your employees to make the case for what they should be working on, and allow group discussion if appropriate. You may be surprised at what good could come of it.