08-10-2010, 10:25 AM
[attachment=5376]
DYNAMIC MEMORY MANAGEMENT
INTRODUCTION
String processing requires memory to be allocated for string storage. New strings may be input or created, old strings discarded, and strings in general may expand or contract during this processing. This requires some means of allocating storage in segments of variable size, and "recycling" unused space for new data.
The Forth language has only two structures for allocation and de-allocation: the dictionary, and the stack. Both of these are Last-In First-Out allocators, releasing memory only in the reverse order of its original allocation.
Since this is an unacceptable restriction, patternForth requires a dynamic memory manager.
Design
There are four design criteria for a memory allocator.
a) Efficiency of representation. Data should be stored in a form which can be efficiently processed by the end application.
b) Speed of allocation. The time involved to obtain a new segment of memory would preferably be finite and deterministic; ideally, short and invariant.
c) Speed of "recycling". Likewise, the time make a segment of memory available for re-use, would preferably be finite and deterministic; ideally, short and invariant.
d) Utilization of memory. The amount of memory which is made available for data should be maximized. This implies:
* memory should be "parceled out" in such a manner as to minimize "wasted space";
* the allocator should use as little storage as possible for its own internal data;
* the amount of memory which is made available through recycling should be maximized. Ideally, storage which is recycled should be completely re-usable. This is particularly significant since the allocate-recycle- allocate cycle will repeat endlessly.
A memory allocator should solve, or at least address, the problem of "fragmentation." This is the division of memory so as to leave small, unusable segments.
All memory managers represent a tradeoff among these four criteria. The Patternforth memory manager design weighted them as follows:
a) Efficiency of representation. We decided that each string would be stored in a contiguous block of memory. The machine-level string operations which are available (on the 8086) are much more suited to incrementing pointers than traversing linked lists.
b) Speed of allocation. The time required to allocate a segment of memory could be variable, but bounded. We desired an "upper limit" on the search time for a suitable segment.
c) Speed of "recycling". The time involved to recycle a segment of memory could be variable, but bounded. In particular, we wished to avoid the often-seen problem of halting for several seconds while memory is consolidated.
We valued recycling over allocation. We strongly desired a recycling scheme whose time is short and fixed.
d) Utilization of memory. This was the least emphasized of the four criteria. Since we anticipated the use of long strings, we favored schemes having a "fixed" overhead (X bytes per string), as opposed to a "variable" overhead (X bytes per character).
