6913
Heap Memory Management Is A Mathematically Difficult Problem
Exelis VIS receives many questions about how IDL manages memory use. Since memory is a central issue for any program, these questions are not very surprising.
This Help Article addresses why Heap Memory Management Is A Mathematically Difficult Problem.
Please see additional Help Articles for detailed information on how IDL uses memory:
To allocate dynamic memory, a function (usually malloc()) is used to allocate memory. Once the memory is no longer needed, a corresponding function (free()) is used to free it. To get memory to allocate, malloc grows the processes size by moving the break point. When memory is freed, it is placed on a free list in hope of reusing it again.
Under any circumstances, management of heap memory is complex. The task of optimal memory allocation for general computation is an NP-complete computer science problem, which means that for practical purposes, we cannot prove that any given approach is optimal. Instead, we are limited to algorithms that do a reasonable job in a reasonable amount of time. Some algorithms do a faster job, usually at the cost of less optimal memory layout, while others do a better job of layout, but usually at the cost of taking far longer to allocate and free memory.
Some applications value speed over optimal memory use, while others require the best layout and can afford to sacrifice speed. A given malloc implementation cannot satisfy both of these requirements simultaneously, and most mallocs attempt to deliver something that is reasonably fast and reasonably efficient. Of course, since this is an NP-complete problem, it is difficult or impossible to quantify exactly how well a given implementation of malloc is doing on a given task. A related problem is that for a given malloc, it is always possible to construct a pathological case under which it will perform extremely poorly, even if it is generally excellent.
Once a piece of memory is allocated, it cannot be moved until the user frees it. If memory at lower addresses is freed, this causes a hole in the allocated memory, which is usually put on a free list and becomes available for later reallocation. During this time, it is still part of the processes memory, so the fact that the user has freed it does not make it available for use by other processes.
When memory is freed, a smart malloc will check to see if it is adjacent to other free memory, and if so, will add it to that free block to create a larger (and hence, more reusable) block of memory. This processes, called free list consolidation, can improve memory layout, but causes the free operation to take longer. As with any problem, you quickly hit a point of diminishing returns where each small increment in improvement in layout costs an ever growing runtime cost.
As memory is allocated and freed, it can become cut up into small pieces on the free list that cannot be consolidated. A process can therefore end up with alot of free memory, none of which is large enough to satisfy a given request, and none of which is available for any other process. This problem is called fragmentation. Fragmentation is caused by the fact that memory allocations can have variable sizes, and once memory is allocated, it cannot be moved until the user frees it.
The general problem of memory allocation is difficult. IDL has characteristics that make it especially difficult:
- The lifetime of an IDL session is unbounded, meaning that it can run for an arbitrary amount of time. Hence, we cannot rely on an occasional restart to clean things out. The longer a program runs, the worse the fragmentation problem tends to become. Compare this with typical shell commands, which execute some task for a few milliseconds and then exit, releasing all resources back to the operating system.
- IDL's memory use is unpredictable in that it depends entirely on the instructions given it by the user, and these instructions are rarely, if ever the same between any two IDL sessions. This makes it impossible to optimize memory allocation.
- IDL memory allocations tend to vary widely in size, between very small and very large blocks. This exacerbates the fragmentation problem.
Since some applications value speed over the quality of memory layout, while others value the reverse, which camp does IDL fall into? This question is impossible to answer as posed, because it depends entirely on the user's needs for a given application. In any event, the application rarely has control over this tradeoff, it is entirely controlled by the memory allocation package and is not a variable.
NOTE: It is worth noting that many of IDL's basic advantages stem from these same characteristics listed above.
The X Window server program is a good example of a program that also has these complexities: programmers will often go for months without logging off a machine (they sit down in the morning and go home at night, using the same session everyday). Memory demands from an X server depend on the programs using it and their needs and can fluctuate wildly. Users will often see memory related comments in X Window System newsgroups that are similar to those made by our users.
How does IDL preserve memory and use it efficiently?
- IDL has significant amounts of code dedicated to making sure that it never leaks memory. (A memory leak occurs when memory is allocated and not freed after the program is done with it.)
- IDL is written carefully to use as little memory as possible for a given task. This effort is made more difficult by the generality and flexibility of the IDL language.
- IDL code attempts to allocate and free memory in an order that enhances the odds of a non-sophisticated malloc package being able to consolidate the free list.
Review on 12/31/2013 MM