📄 heapinfo.txt
字号:
The MSC heap manager is far more sensitive to the pattern
of access. Two extreme cases serve to illustrate this fact.
Given a performance test based on malloc(constant) where
the total heap memory pool is much smaller than the size
of available memory the MSC heap manager is quite fast.
The replacement heap manager is only half as fast as the
original under these conditions.
Equally extreme is a test based on random allocations,
deallocations, and reallocations of random size, where the
total demand matches the size of available memory. In this
case the MSC heap manager chokes on heap fragmentation and
garbage collection. It is up to 200 times slower than the
first test. The replacement is slightly slower than it was
in the first test.
The extreme tests are indicative of trends, but not definitive.
The file bench.c implements a mixture of 3 parts malloc(),
2 parts free(), and 1 part realloc() as representative of
heap processing. The sizes of the heap entries are skewed
toward the smaller chunks as an example of reasonable heap
usage. The exact distribution is triangular, with a block
of size {N:0..32767} appearing with a probability of
(32768-N) / (32768 * 32769 / 2).
Running the above test with various iteration limits confirms
that the replacement heap manager performs linearly. It takes
twice as long to do twice as much. The MSC performance is not
so predictable. It appears to be a power curve of some sort.
The raw data (in seconds) is as follows:
Iterations MSC New
---------- --- ---
1000 1 0
2000 4 1
4000 8 2
8000 34 4
16000 98 8
32000 231 17
64000 499 33
128000 1034 66
256000 132
512000 265
Incredibly, the above data indicates that the MSC heap
manager is SLOWER than the replacement heap manager. Further,
as the constraints get tighter, the MSC heap manager falls
further and further behind.
Out of curiosity, I ran the same test using a constant
quantum of allocation and obtained the following data:
8 bytes 80 bytes
Iterations MSC New MSC New
---------- --- --- --- ---
1000 0 0 0 0
2000 0 0 0 0
4000 0 0 0 0
8000 0 1 0 1
16000 0 1 1 1
32000 1 3 3 2
64000 4 5 125 11
128000 9 16 395 27
256000 27 48 919 59
512000 5128 112 1999 125
It appears that the MSC heap manager is doing fine until
it has to start garbage collection. At that point it
suffers horribly. Note the sudden transition from about
1/2 minute to about 3 hours!
All of the above tests were run three times, once for
each optimization mode. The size/space optimization modes
were about 75% as fast as the time-optimized mode. The
figures in the tables above reflect the time-optimized
modes as time optimization is the closest match to the
functionality of the MSC heap manager.
2. Memory
The memory usage figures can be obtained from the output
of _fheapdump(). Depending on the usage pattern and the
optimization mode the memory efficiency varies from 75%
to 98%. The space-optimized mode (best fit) turns out to
be quite efficient. The size-optimized mode (first fit) is
almost as efficient, but it does a reasonable job of limiting
the growth of the heap. The time-optimized mode (LIFO) is
roughly 85% as efficient as the space-optimized mode.
Detailed figures were not compiled for the MSC version, but
inspection of the failure counts in the output of the test
program showed that even the time-optimized replacement
heap manager is considerably better than the MSC heap manager.
I attribute this efect to the fact that the MSC heap manager
wastes more space on fragmentation than it saves in overhead
per block.
3. Real software
As a rough (subjective) test I linked the replacement heap
manager with a medium sized application (40K LOC, 150Kb
heap requirement, 450Kb (overlaid) executable) and found
it noticeably improved. Previously, it had suffered about
15% overhead in the form of fragmented, unusable free space.
With the replacement heap manager the wasted space went to zero.
Literally, there were no free blocks left amoung the allocated
blocks. There was just one at the end of the heap.
Try it on one or two of your programs and see what you get.
You dont have to recompile anything, just link with heap.lib.
III. Flexibility and user control
The features described here allow the application programmer to
control the behavior of the heap. The capability for tuning the
heap performance simplifies the design of application software
because it is not necessary to design around the limitations of
the heap manager.
A. Heap entries can be relocated and the heap shrunk as needed.
The _relocate() and _fheappack() functions provide an efficient
method of dealing with multi-phase processing. _Relocate()
serves to reposition entries as low as possible in memory.
Note that your mileage may vary, but _relocate() is guaranteed
to do no harm. I.e., it will only act when improvement is
certain. Thus it is feasible to make multiple passes through
allocated memory (typically until nothing moves) in order to
obtain as much compression as possible. The compression
maximizes the effect of _fheappack().
In addition to compressing the heap in order to maximize the
free DOS memory, the relocation process is the basis for a
heap garbage collector. An allocation that fails due to
heap fragmentation may succeed if the heap is compacted.
Applications that cannot afford to crash "out of heap" can
overcome heap fragmentation by relocating the active heap
entries.
_Fheappack() releases excess heap memory back to DOS.
The file packdemo.c illustrates the basic techniques.
B. Functional extensions to the MSC design.
These capabilities exceed those of the MSC heap manager, so
they contain the seeds of incompatibility. However, their
use is in no way mandated. The replacement heap manager
may be treated exactly as the MSC heap manager.
1. Manifest constants
These describe the constants specific to the replacement
heap manager.
a. SIZE_MAX
This constant describes the maximum size of a heap
entry. SIZE_MAX is to size_t as INT_MAX is to int.
The value is 65535.
b. Heap optimization modes
_HEAPTIME, _HEAPSIZE, and _HEAPSPACE define the
legitimate values for _heapmode. _HEAPTIME produces
LIFO free list handling, and maximizes throughput
at the expense of memory eficiency. _HEAPSIZE produces
first-fit free list handling, and minimizes the overall
size of the heap memory pool. _HEAPSPACE produces
best-fit free list handling, and minimizes the wasted
heap space.
The interpretations are described in detail in section II.A.
2. Global variables:
These variables are declared in heap.h and defined in
heaputil.c. They provide application programs with control
over the behavior of the heap manager.
a. int _Heapmode;
_Heapmode controls the optimization mode of the heap
manager via free list handling algorithms. Section II.A
describes its use in detail.
b. size_t _Heappad;
_Heappad controls the safety margin allocated as part of
every heap entry. The default value is zero, but an
application program may set a non-zero value prior to
using the heap.
Section IV.B gives details about debugging with _heappad.
3. Entry points
These functions extend the power of the heap manager to
cover previously unaddressed issues.
a. void _fheapdump( FILE *fp, int verbose );
_Fheapdump() is a utility function that writes a complete
description of the state of the heap to the indicated
stream file. The report inclues the following information:
- Key to notation
- Global variables
- _heapmode
- _heappad
- Arena headers -- DOS interface
- Address [pointer]
- Size
- Forward and backward links [pointers] on arena list
- Chunk headers -- C RTL interface
- Address {<pointer>}
- Size
- Forward and backward links <pointers> on chunk list
- Forward and backward links {pointers} on free list
- Status: ok, read-only, or bad.
- In debug mode additional info is reported:
- Function that last changed the entry
- Desired size of the entry
- Transaction (sequence) number
- Name of source file
- Line number in source file
- Controls for free and join lists
- Address {pointer}
- Number of entries on the list (not including master)
- Forward and backward links {pointers}
- Summary statistics on heap usage
- Pagination: formfeed
Verbose is a boolean argument that controls the level of
detail in the heap status report. In non-verbose mode
the report excludes the chunk info.
b. void _fheappack( void );
_Fheappack() releases unused heap memory back to DOS. It
searches the entire heap, shrinking arenas that contain
active entries to the minimum, and totally freeing arenas
that contain no active entries.
Section II.B.1 also describes heap compaction.
c. int _fheapwatch( void far *ptr, int enable );
_Fheapwatch() establishes a heap entry as read-only. The
enable argument controls the status of the heap entry.
_Heapchk() tests all the read-only entries in the heap
and reports _HEAPBADPTR if one has changed. Similarly,
the debugging routines will trigger a diagnostic report
is a read-only entry changes.
Section IV.F provides details on the use of _fheapwatch().
d. void far *_relocate( void far *ptr );
_Relocate() repositions a heap entry as low as possible
in memory. It is the basis for heap compaction and
garbage collection as described in section II.B.1.
e. char *_heapstat( int status );
_Heapstat() translates heap status codes obtained from
_fheapchk(), _fheapset(), and _fheapwalk() into descriptive
strings.
f. void far *_hexpand( void far *ptr, long nbytes );
_Hexpand is a "huge" version of _expand(). It is one
of the superset functions described in section II.E.2.
g. void far *hrealloc( void far *ptr, long nbytes );
Hrealloc() is a "huge" version of realloc(). It is
one of the superset functions described in section II.E.2.
h. long _hmsize( void far *ptr );
_Hmsize() is a "huge" version of _msize(). It is one of
the superset functions described in section II.E.2.
4. Compiler options
These options affect applications that #include "heap.h".
Enable the special options via the compiler command line
with -D<symbol>=<value>.
a. STDMSC -- enforcing strict source code compatibility
This symbol controls the declaration of the symbols,
variables, and functions unique to the replacement heap
manager. If STDMSC is defined heap.h behaves just like
malloc.h. If STDMSC is not defined, the extra capabilites
of the replacement heap manager are available to
application programs.
b. _HEAPCHECK -- pointer checking and reporting
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -