Don’t try to allocate memory until there is only x% free


I have an ongoing conflict with my in-laws. Their concept of the correct amount of food to have in the refrigerator is "more than will comfortably fit." Whenever they come to visit (which is quite often), they make sure to bring enough food so that my refrigerator bursts at the seams, with vegetables and eggs and other foodstuffs crammed into every available nook and cranny. If I'm lucky, the amount of food manages to get down to "only slightly overfull" before their next visit. And the problem isn't restricted to the refrigerator. I once cleared out some space in the garage, only to find that they decided to use that space to store more food. (Who knows, maybe one day I will return from an errand to find that my parking space has been filled with still more food while I was gone.)

Occasionally, a customer will ask for a way to design their program so it continues consuming RAM until there is only x% free. The idea is that their program should use RAM aggressively, while still leaving enough RAM available (x%) for other use. Unless you are designing a system where you are the only program running on the computer, this is a bad idea.

Consider what happens if two programs try to be "good programs" and leave x% of RAM available for other purposes. Let's call the programs Program 10 (which wants to keep 10% of the RAM free) Program 20 (which wants to keep 20% of the RAM free). For simplicity, let's suppose that they are the only two programs on the system.

Initially, the computer is not under memory pressure, so both programs can allocate all the memory they want without any hassle. But as time passes, the amount of free memory slowly decreases.

Program 10 (20%) Free (60%) Program 20 (20%)
Program 10 (30%) Free (40%) Program 20 (30%)
Program 10 (40%) Free (20%) Program 20 (40%)

And then we hit a critical point: The amount of free memory drops below 20%.

Program 10 (41%) Free (18%) Program 20 (41%)

At this point, Program 20 backs off in order to restore the amount of free memory back to 20%.

Program 10 (41%) Free (20%) Program 20 (39%)

Now, each time Program 10 and Program 20 think about allocating more memory, Program 20 will say "Nope, I can't do that because it would send the amount of free memory below 20%." On the other hand, Program 10 will happily allocate some more memory since it sees that there's a whole 10% it can allocate before it needs to stop. And as soon as Program 10 allocates that memory, Program 20 will free some memory to bring the amount of free memory back up to 20%.

Program 10 (42%) Free (19%) Program 20 (39%)
Program 10 (42%) Free (20%) Program 20 (38%)
Program 10 (43%) Free (19%) Program 20 (38%)
Program 10 (43%) Free (20%) Program 20 (37%)
Program 10 (44%) Free (19%) Program 20 (37%)
Program 10 (44%) Free (20%) Program 20 (36%)

I think you see where this is going. Each time Program 10 allocates a little more memory, Program 20 frees the same amount of memory in order to get the total free memory back up to 20%. Eventually, we reach a situation like this:

Program 10 (75%) Free (20%) P20 (5%)

Program 20 is now curled up in the corner of the computer in a fetal position. Program 10 meanwhile continues allocating memory, and Program 20, having shrunk as much as it can, is forced to just sit there and whimper.

Program 10 (76%) Free (19%) P20 (5%)
Program 10 (77%) Free (18%) P20 (5%)
Program 10 (78%) Free (17%) P20 (5%)
Program 10 (79%) Free (16%) P20 (5%)
Program 10 (80%) Free (15%) P20 (5%)
Program 10 (81%) Free (14%) P20 (5%)
Program 10 (82%) Free (13%) P20 (5%)
Program 10 (83%) Free (12%) P20 (5%)
Program 10 (84%) Free (11%) P20 (5%)
Program 10 (85%) Free (10%) P20 (5%)

Finally, Program 10 stops allocating memory since it has reached its own personal limit of not allocating the last 10% of the computer's RAM. But it's too little too late. Program 20 has already been forced into the corner, thrashing its brains out trying to survive on only 5% of the computer's memory.

It's sort of like when people from two different cultures with different concepts of personal space have a face-to-face conversation. The person from the not-so-close culture will try to back away in order to preserve the necessary distance, while the person from the closer-is-better culture will move forward in order to close the gap. Eventually, the person from the not-so-close culture will end up with his back against the wall anxiously looking for an escape route.

Comments (52)
  1. Zan Lynx says:

    It is a tricky problem. Your illustrations make the point very clear.

    It still needs to be solved somehow though. There are programs (cough. web browsers. cough.) that can usefully use nearly unlimited amounts of RAM. (Predicatively fetch and render all the web pages you might decide to click on next? Sure!)

    I suppose my solution would be to look at the total RAM of the system and pick a cache size based on that. I'd also make it user or administrator configurable. It is probably the best you can do.

  2. Zarat says:

    Is there any solution to the problem which doesn't run into this issue? The problem being that I want a cache fitting into memory but can give some up to other programs if they need to? I guess the operating system should take the role of a negotiator.

    I heared SQL server does something like this, interacting closely with the OS. Also I observed something similar with the .NET GC: after allocating/freeing a lot large objects the used memory (as seen in task manager and resource monitor) was large and only after starting another memory-hungry program the GC was eager to give back unused memory.

  3. David Crowell says:

    Zarat,

    The answer is to ask for whatever memory you need, not base it on how much is free.

    I know any kind of caching needs to be smarter.  SQL Server does some caching that can eat up memory, but I doubt they are using anything as naive as leave x% free.  I doubt Raymond knows what SQL is doing, as he doesn't work on the SQL team.

  4. Billy O'Neal says:

    I've seen tools like "RAMIdle" and "CacheMan" which might want to do something like this — though their function was to force apps that were not being used out to the page file.

  5. Gabe says:

    Rather than having the strategy of "always allow x% free", it's better to have the strategy of "never allocate more than (100-x)%". That way you won't ever consume all the memory in the system, but large programs won't fight over it.

  6. MPage says:

    In contrast, there are programs I've encountered such as XWidget (http://xwidget.com/) that try to "minimize" (quotes intended) memory usage by using 'SetProcessWorkingSetSize(GetCurrentProcess(), (SIZE_T)-1, (SIZE_T)-1)'. Their attempts are, of course, futile as the OS is surely smarter than them in memory management. A post on why one shouldn't use SetProcessWorkingSetSize (normally) would be nice.

  7. Marco Schramp says:

    Most application use a even more naive approach: simply put a fixed cap on memory usage (that's how the Java VM does it: just set a max, SQL server does just the same). This still allows for overcommiting of memory, but at least it's a bit more controled than the example Raymond has given.

  8. Jim Lyon says:

    I prefer to use the combination of what Marco recommends and what Raymond disrecommends: A program that is a major memory consumer should not allocate more than x% of the total memory, nor should it leave less than y% free.

    Still not perfect, but not quite as obnoxious as either strategy alone.

    Of course, the best idea yet is to try to run the memory hogs one at a time. It's hard to do this perfectly too, but depending on the situation is often worth trying.

  9. Joshua says:

    Yes, SQL server does something stupid as x% free. The admin limit doesn't always work.

    It seems the only reliable way of dealing with it is to run a 32 bit machine with >> 4GB ram. SQL server is then forced to stop at 3GB, leaving plenty for everybody else.

  10. Wladimir Palant says:

    @D-Coder: I guess that you are not married. Some things really aren't worth risking your happy marriage over. Yes, offending your in-laws does create tension in the family and maybe you want to skip on it this time.

    [D-Coder seems to prefer the nuclear option. "My brother will sometimes borrow my dremel and not return it for a long time, so I told him to piss of and I never wanted to see him again. Problem solved." -Raymond]
  11. Anonymous says:

    I agree with the gist of what @GWO is saying.  This approach is especially silly with a modern operating system that would page out some of those allocations when memory becomes tight.  I find that when people come up with voodoo like this it's usually because they have a poor understanding of how the overall system works (like the mistaken notion that the system's globally available is meaningful to a user mode application).

  12. James Schend says:

    @Joshua: I guess we have different definitions of "stupid". Since SQL Server, 99.9% of the time, is the only process running on a machine dedicated to running it, I'm ok with it doing whatever the heck it wants with memory.

    If you need to run SQL Server but also leave a lot of free memory– well, then get your workplace to set up a SQL Server for development work, because there's no reason you should need that.

  13. Ken Hagan says:

    Zarat suggested: "I guess the operating system should take the role of a negotiator."

    You could place "discardable" data in the memory that is mapped to a file-mapping object. The OS cache manager can then decide when to keep that data in real RAM or let it fall back to the disc.

  14. Mordachai says:

    I just wish non-OS programmers would stop thinking that they're somehow in charge of such things.  Clue: You're NOT.

    This is an OS/System domain issue, not an application-domain issue.

    Rule: Use exactly what you need, and no more.  Your users will thank you.

  15. Evan says:

    It seems like a decent solution to this is if OSes provided a way to say "take this memory first! and you don't need to page it out, just discard it". Do they?

  16. Mason Wheeler says:

    Isn't this pretty much what .NET's generational garbage collector does?  "Keep allocating memory and never clean anything up until you run into memory pressure."  Only it does it automatically and it's built into the runtime, so you can't tell it not to.

    I've been saying for years that such a system makes your program a bad neighbor on any modern, multitasking computer.  Thanks for writing this!

  17. Joshua says:

    @James Schend: Experiments indicate I can get much better performance by stacking APP and SQL servers on a single big enough box if I can keep SQL Server from hogging all the RAM.

  18. Mason Wheeler says:

    @Joshua: Yeah, that makes sense if your app server needs to talk to the database a lot.  The network overhead, even for just having one computer on a LAN talk to another, can be non-trivial, and eliminating it will definitely speed things up, if done right.

  19. Joshua says:

    @JM: Sorry, but I have documented cases of chewing 1.5GB on 512MB limit when SQL had been idle for an hour (dev workstation). The condition is real.

  20. Evan says:

    @Mason Wheeler

    You confuse running into "internal", self-induced memory pressure with running into system-wide memory pressure. GC typically (OK, I can't speak to .Net's specifically) acts a lot more like some of the other suggestions in the responses, where you set a max heap size and the system will GC when its memory usage approaches that regardless of what the rest of the system is doing.

  21. Ray Trent says:

    It's too bad there's no memory manager function called "HowMuchMemoryCanIReasonablyUse". Obviously, to use this API you'd have to call it periodically because there's no static answer, but it would leave this idiocy to the entity best positioned to perform it.

  22. For large applications, it should be OK to be able to tell them how much memory they can consume. As long as they don't try to be smart and try to figure that behind your back. "Smart" applications doing things behind your back is one of biggest pet peeves of mine. Inevitably, they end up being stupid.

  23. Peter says:

    I agree with Zarat.  It would be really nice if Windows had an API to create in-memory caches.  The basic idea is that Windows would promise not to page out the memory but might change the size on you.  The devil's in the details, of course.

  24. Nawak says:

    What if two Amazon Sellers did this?

    http://www.michaeleisen.org/blog

    [That is awesome. -Raymond]
  25. (Nice diagrams, Raymond, thanks!)

    Wladimir has a point: even a guy with the social skills of a thermonuclear device will probably balk at the idea of chucking away gifts from family and admitting to it.

    Some applications – the Varnish webcache for one – uses essentially the approach Ken Hagan suggests: your cache is an admin-defined size of file on disk, memory-mapped. The operating system itself will then page bits of that in and out as needed, depending on how busy those pages are and how much load there is from other applications. Trying to achieve the same manually – having separate disk and memory caches, plus code and some OS monitoring – amounts to reinventing the wheel.

    @jalf: the 'free' memory will never be 'completely unused' except shortly after boot, since the NT kernel has used all 'unused' memory pages for disk caching all along. (Give or take the handful kept around as pre-zeroed pages for new allocations, anyway.) Just because it isn't used by an application doesn't mean it goes to waste!

    Remember, SQL Server ships as part of the Small Business Server product, intended to share a machine with Exchange, file/print/domain services and the other bits, only the Premium SKU adding the option of putting SQL Server on a second machine.

  26. Æro says:

    @Steve Wolf But how do you define how much memory you "need"? For example, should a web browser cache 20% more elements in RAM if that means it's 15% faster? How about 25% faster?

  27. Maurits says:

    A potential solution to the in-law problem is to put a second refrigerator in the garage for their use.

    [They've already suggested that we get a second refrigerator in the garage because the existing one is too small. All that would happen is that they would fill up the second one, too! -Raymond]
  28. JM says:

    @Joshua: it's possible for an SQL Server to consume 1.5 GB with a buffer pool of only 512 MB. The article I linked to gives some hints on why this might be. Query plans, thread stacks and other internal objects all consume memory that doesn't count towards the buffer pool limit. However, if you're consuming 1 GB of memory not in the buffer pool, I would take a hard look at both your SQL Server version and what your clients are doing, because that's pretty extreme.

    There is in any case no percentage-based allocation involved in SQL Server's strategy. Having said that, there is also no "please don't consume more than X MB of memory absolutely" setting either — "max server memory", despite its name, is not this, and should have been named "max buffer pool size" instead. Also, note that SQL Server follows the First Rule of Acquisition: once you have their memory, you never give it back. If it's using 512 MB of buffer pool and the machine itself is not out of memory, it will never voluntarily shrink it no matter how long it idles. In order to force it to relinquish memory, you have to reduce the "max server memory" setting and then issue a DBCC DROPCLEANBUFFERS command. This will still not shrink memory not allocated to the buffer pool — DBCC FREESYSTEMCACHE will free some of it but not all of it (memory tied up in thread stacks can obviously not be returned, for example).

    If you have a documented case of SQL Server persistently consuming more than X MB of buffer pool, with X the maximum amount of memory you configured, file a bug on Connect. That's not supposed to happen in any case, unless you're doing some really awful things to the machine that prevent SQL Server from even deallocating memory. You can use the sys.dm_os_buffer_descriptors DMV to get the size of the buffer pool.

  29. Joshua says:

    @JM: I listed idle time so you would understand it had no clients connected. The machine would periodically run out of RAM until SQL server was restarted.

    Never saw the behavior after replacing the machine with a new one.

  30. Maurits says:

    All that would happen is that they would fill up the second one, too!

    Right; the suggestion would only work if you could convince them to limit themselves to only one of the refrigerators.  They might complain that there's not enough room in only one refrigerator for all of the food they want to buy.  You would then nod, and say "Exactly."

  31. Zarat says:

    @David: Requesting the memory you want is not a good solution for server (and some desktop) applications. They have a minimum set to run reasonably but can run better the more memory they get for caching *as long as this memory is not swapped to disk*. Overcommitting is plain stupid because once you start swapping too much the cache has no purpose anymore and you want to reduce the size. That is what I've read SQL server does and what I observed with .NET GC.

    I know the naive approach from the post is going nowhere, and I know Raymond doesn't know what SQL server does; I didn't ask about that.

    Ideally I'd want the OS to coordinate the distribution of free memory among applications which can make use of it, because anything else is a custom solution which not everyone can be aware of. But everyone can be aware of the OS they run on ;)

  32. D-Coder says:

    It's *your* refridgerator.

    After they leave, throw out whatever food you least want until you're happy (yep! it's garbage collection!).

    If they ask what happened to the food, politely tell them.  They will be so horrified that they will think before doing it again.  Or, in the worst case, they'll stop coming over, which also solves your problem (yep! refridgerator overflow crash!).

  33. DWalker59 says:

    The program that wanted to allocate memory until x% is free would work *only* if it was the only program doing that.  Some programmers think they are clever, and they don't consider that maybe another program is doing the same thing.  They are also assuming that the rest of the system is stable in its memory requirements.  If that were really true for a given system, then *perhaps* one system could allocate memory until x% was free.

    The flawed assumption, as Raymond's illustrations show very well, is that if two programs do this, the results are terrible.  That's why the question "what if two programs did this" is always a good one to ask.  (Such as with programs wanting to be "topmost".)

    I'm not sure you can solve the problem like Jim suggests, by saying "don't leave less than y% free".  Why not?  If all programs did that, then some of the expensive memory that you paid for would be wasted, since no program would allocate it.

    Maybe, if every program would let you hint how much memory it should take, you could carefully tune your whole system.  But that would be tedious and subject to change.

  34. GWO says:

    My general principle for this is : "Whoever wrote the OS allocator / swap algorithm is *way* more experienced than I am at balancing OS / app working set / and filesystem cache than I am" the core algorithms have been stress tested under more general workloads than I can even imagine. Further, any optimising I do based on "I know best how this app will be used" will be invalidated the first time anyone other than me uses it, and probably before then.

    Jackons'First and Second Rules of Program Optimisation hold

    i) Don’t do it.

    ii) (For experts only!): Don’t do it yet.

  35. jalf says:

    "I prefer to use the combination of what Marco recommends and what Raymond disrecommends: A program that is a major memory consumer should not allocate more than x% of the total memory, nor should it leave less than y% free."

    Huh, so an application which can actually benefit from an infinite amount of memory *is going to leave a significant amount of memory on the system entirely unused*

    Yeah, that's clever. Everyone knows you get the best performance when you don't use the resources at your disposal.

  36. Maurits says:

    Although part of me wants to suggest that you keep buying them refrigerators until either they say "that's enough" or you hit some unavoidable space/electrical limit… just as a sociological experiment.

  37. JM says:

    @Joshua: I call bollocks on that, sorry. The total amount of memory SQL Server consumes *can* go over the limit, but this is because the limit only limits the buffer pool and SQL Server has other memory to manage too. See blogs.technet.com/…/lock-pages-in-memory-do-you-really-need-it.aspx for an in-depth look (this talks about locked pages, but discusses how the memory settings for SQL Server work). It definitely does not work on percentages — even if no limit is specified, SQL Server will try to keep a constant amount of memory free (not a percentage) and, in fact, it will rely on Windows to tell it when the high memory watermark has been reached (so the value used is consistent across other applications that do the same).

    Running 32-bit on a machine with lots of memory is throwing out the baby with the bathwater. It is true that SQL Server is meant to be the only app on the machine. If you want to run multiple SQL servers, you can, but this requires planning ahead. Running SQL Server alongside a different memory-hogging application (like Analysis Services) is best done by fixing the amount of memory each uses and leaving it at that — dynamic configuration will not run into the pathological scenario Raymond describes if all applications agree on the amount of memory should be left available, but that's a big if.

    The alternate solution on really big hardware is to use virtualization (obviously a more complicated solution, which however also brings benefits of maintenance). As far as memory goes, though, this is almost the same solution as fixing the amount of memory each app uses (as the virtual machine has an upper limit too).

  38. Cheong says:

    As long as "program 20" has set a "minimum limit" on memory be freed for relief memory pressure, what's "the bad" be done to "program 20"?

    Btw, this graph make me think that those "make memory by allocating huge space to force other programs to give their share out" type of programs have use afterall. :P

  39. JM says:

    @Joshua: OK — anomaly then. It wasn't clear from your post that it had *never* seen client connections. Once clients *have* connected, even if they're long since disconnected, memory may still be allocated (because, after all, you never know when new clients will drop by who need exactly that data).

  40. Cheong says:

    Regarding the food problem, I think if they bring too much food, it's only logical to share some of them to your best neighbours. From time to time, you might be able to get some food when you "perhep much larger now" fridge feels a little empty. :P

  41. Neil says:

    I suspect the discardable memory features built in to Windows are rarely used. (The obvious case of which I am aware is the discardable bitmap used for windows with the CS_SAVEBITS class style.)

  42. asdbsd says:

    @Ray Trent: What exactly is "reasonable use"? You can reasonably use all of the available memory. It's there for you, if you need it.

  43. Larry Hosken says:

    cheong00's onto something. When your in-laws leave, you might want to hold an Iron Chef contest/potluck party. Early on some Saturday, you divvy up the left-behind food amongst some friends. That evening, they need to bring back dishes they cooked that incorporates that food. Then comes a dinner party/contest judging.

    Heck, maybe don't wait until the in-laws leave. They probably bring food that they like to cook with. They might do well in the contest and thus feel happy.

  44. Skyborne says:

    swapping to a local file

    And by that I actually mean a "private" file, but that brings up another point: what if your cache is accidentally on a network filesystem?

  45. lefty says:

    Clearly the solution to this problem is to set your memory threshold level at something like 5% so you end up shutting out both Program A and Program B. As the author of Program C, I sure don't care about their performance.

    And the solution to Raymond's 'too much food' problem is to send the in-laws to my place.  I love free food (maybe not fish eyes, though).

  46. Skyborne says:

    @Ken Hagan, I was thinking along those same lines, but it seems like Program 20 wants *discard* under pressure to implement a weak cache (and probably some strong->weak cache management in-app so that the entire cache doesn't drop and cause thrashing as it gets re-populated and immediately re-dropped under continuing pressure), but everything I know of (esp. on linux) creates *swap* under pressure behavior.

    mmap is actually worse, because you get swapping to a local file, maybe on volume manager / encryption / software raid / an ssd that the user doesn't actually want you swapping your cache to all the time.

  47. Danny says:

    Ray, isn't this just another variation of walls and ladders game with a twist?

  48. SheepNine says:

    Is it mere coincidence that it is the BLUE process whimpering fetally in the corner while the PINK process proceeds to consume huge swaths of available RAM?

  49. user says:

    I hope IE guys read your blog.

    As I'm writing this there ar three iexplorer processes on my machine consuming 48, 7 and 32 mb of memory for keeping 4 tabs open, 3 from your weblog and one for that amazon thing, let's close that amazon tab … hmm the first process releases 4mb of memory, let's close a tab from your weblog … another 8 mb released. now IE is consuming almost 75 mb of memory just to display two pages of your blog.

  50. 640k says:

    2 refrigerators is enough for everyone.

  51. Hear says:

    It reminds me of a time I couldn't hear what someone was saying, so I came closer and told him to repeat, so he spoke again, but more silently (since I was closer).

    I couldn't hear him again, so I got even closer… (guess what he did)

  52. Kirill says:

    As long as my program is "Program 10", I don't see what the problem is…

    *trollface*

Comments are closed.