January 92 - Blueprint for Automatic Segmentation
Blueprint for Automatic Segmentation
Alan Bommer
Segmenting an application can be tedious and frustrating. Since MacApp eliminates
many tedious and frustrating tasks for programmers, segmentation seems even more
odious to users of MacApp. This article outlines two ways segmentation could be
automated in MacApp.
The Goals of Segmentation
There are generally four (sometimes conflicting) objectives in segmenting a MacApp
application:
• Minimize the "temporary memory reserve." This reduces the amount of
memory that is necessary to run the application. To achieve this goal, make
sure the segments loaded at the time of peak temporary memory usage do not
contain routines that are unnecessary at the peak time.
• Minimize the time used for loading and unloading segments from disk. This
improves program performance. Smaller segments load faster than larger
segments, but loading two 5k segments takes longer than loading one 10k
segment. To minimize the loading and unloading time, segments should be
large, but should not contain routines that are unnecessary.
• Minimize heap fragmentation. This speeds the performance of the Memory
Manager and ensures that no memory is wasted in memory fragments too small
to be useful. Larger segments minimize the number of handles in memory and
hence minimize potential fragmentation.
• Minimize the number of jump table entries. This improves program
performance as intra-segment code-to-code references (no jump table
involved) are faster than inter-segment code-to-code references that use the
jump table. Keeping the jump table size less than 32k (4096 entries) can
also improve the program's performance by eliminating the need for (the
slower) "32-bit everything." Larger segments minimize the number of jump
table entries, because they appear as intra-segment references instead.
The Statistical Analysis Approach
The statistical analysis scheme for automatic segmentation consists of three steps:
1. Modify the source code so that every routine not in a user-specified (or
MacApp-specified) segment is put in its own segment;
2. Run the program a representative number of times and collect statistical
information on the usage of segments;
3. Analyze the statistical information and generate segment mappings (this
step is by far the hardest).
Modifying the source code (step 1)
You must segment all routines in your source code in either the standard way-{$S
segname}-or as {$S autoseg}. An MPW tool will then (by referencing
Appname.MABuild) change all the {$S autoseg} directives to {$S autosegN}, where N is
a unique number for each routine. For repeatability, the tool also renumbers any {$S
autosegX} that it encounters.
Collecting the statistics (step 2)
The modified source code must be built with the options "-NoDebug -AutoSeg
-ModelFar." MacApp will collect the necessary statistics by adding a new procedure
and a few lines to UnloadAllSegments. Every time UnloadAllSegments is called, the new
procedure will update a data file of a format similar to these quasi-Pascal records:
UsageRecord = RECORD
flags: LONGINT; {is segment resident? etc}
segmentSize: LONGINT; {code size}
usedWith: ARRAY[1..numSegs] OF LONGINT;
END;
DataFile = RECORD
numSegs: LONGINT;
usage: ARRAY[1..numSegs] OF UsageRecord;
END;
The "usage" and "usedWith" fields are defined so that "dataFile.usage[i].usedWith[j]
is the number of times that segment "i" and segment "j" are both loaded between calls
to UnloadAllSegments.
This data file is very large. For 1000 segments (routines), the size is about 4M; for
4000 segments (routines) the size is about 60M. These sizes can be cut in half by
taking advantage of the symmetry of the data file (dataFile.usage[i].usedWith[j] =
dataFile.usage[j].used With[i]).
Analyzing the statistics (step 3)
The hardest part of the automatic segmentation scheme is analyzing the data. Empirical
rules determine which segments were mapped together. Below are some rules in order
of preference:
• Limit segment sizes to 32k unless the "-modelFar" option will be used.
• Segments that are always loaded together should be in the same segment.
• Non-resident segments should not be mapped with resident segments.
• Segments with the highest percentage of being loaded together should be
mapped together before segments with a lower percentage.
• Segments loaded more often should be mapped before those segments loaded
less often.
The Total History Approach
The total history approach consists of three steps similar to the statistical analysis
approach outlined above: (1) the first step is exactly the same, (2) step two is the
same, except that the information stored on disk is the (almost) total time history of
all segment loads, and (3) the third step is to analyze the history and create segment
mappings to meet the goals explained above.
Collecting the data (step 2)
After the source code segmentation is modified with the MPW tool as explained in
"Modifying the Source Code" above, the application must be built with the options
"-NoDebug -AutoSeg -ModelFar." MacApp collects the necessary statistics by adding a
new procedure (different than the one in the statistical analysis approach) and a few
lines to UnloadAllSegments. Every time UnloadAllSegments is called, the new
procedure updates a data file of a format similar to these quasi-Pascal Records:
SegmentNumber = INTEGER;
SampleRecord = RECORD
numNonResSegsInSample: INTEGER;
{system use of reserve (in bytes)}
nonCodeRsrcUsage: LONGINT;
{total use of reserve (in bytes)}
totalCodeReserveUsage: LONGINT;
segmentsLoaded:
ARRAY[1..numNonResSegsInSample] OF SegmentNumber;
END;
DataFile = RECORD
numSegs: INTEGER;
numSamples: LONGINT;
sizeResidentCode: LONGINT;
peakCodeReserveUsage: LONGINT;
segmentSizes: ARRAY[1..numSegs] OF LONGINT;
sample: ARRAY[1..numSamples] OF SampleRecord;
END;
To minimize the disk space required, SampleRecords only keeps track of non-resident
segments and won't be written if no non-resident segment had been loaded between the
calls to UnloadAllSegments. The new procedure increments DataFile.numSamples and
adds an additional SampleRecord to DataFile. The SampleRecord.segmentsLoaded lists
all the non-resident segments loaded between calls to UnloadAllSegments.
This data file is very large. The longer a program is tested, the larger the data file
becomes. The file can get big enough to make this approach impossible.
Analyzing the data (step 3)
You can use this data to produce a good set of segment mappings. I chose the method
outlined here because it is relatively simple and it produces results that are optimal
in one category and reasonable in others.
This analysis algorithm gives the absolute minimum necessary code reserve (given
that it only creates segment mappings) and reasonable segmentation for minimizing
the number of segment loads.
The algorithm works by analyzing samples in order of totalCodeReserveUsage
(maximum to minimum). Within each sample segment, combinations are tried (in
order of most commonly loaded segments to least commonly loaded segments). If a
potential segment mapping does not cause any sample to exceed the
peakCodeReserveUsage, it is accepted and the next possible mapping is tried. As a by
product, the algorithm can also create the seg! and mem! resources needed to define the
temporary memory reserve.
The following pseudo-code shows the algorithm:
FOR sampleNum := 1 TO numSamples DO
BEGIN
{sort samples from largest code reserve size to smallest}
SortSamplesByMaxCodeReserveUsageStartingWith(sampleNum);
sampleToAnalyze := dataFile.sample[sampleNum];
{Sort segment list in sample by order of }
{ maximum to minimum use}
SortSegsByMaxUseInSample(sampleToAnalyze);
FOR mapToSegNum := 1 TO numSegs DO
BEGIN
toSegment := sampleToAnalyze.segmentsLoaded[mapToSegNum];
FOR mapFromSegNum := mapToSegNum + 1 TO numSegs DO
BEGIN
fromSegment :=
sampleToAnalyze.segmentsLoaded[mapFromSegNum];
{if combining segments doesn't cause any sample to}
{exceed maxCodeReserve then do it}
{also could check 32k per segment limit}
IF CombinedSegmentsWithinMax(toSegment,fromSegment) THEN
BEGIN
SegmentTogether(toSegment,fromSegment);
{fix samples as totalCodeReserveUsage etc. may }
{ now be wrong}
FixDataFileToReflectMapping(toSegment,fromSegment);
END; {IF}
END; {FOR mapFromSegNum}
END; {FOR mapToSegNum}
END; {FOR sampleNum}
Conclusions
These two schemes are first attempts (by a structural engineer, not a software
engineer) to design an automatic segmentation mechanism for MacApp. The statistical
analysis approach is limited because it relies on the quality of its empirical rules, but
will probably produce reasonable results. The time history approach will produce
optimal results (judged by code reserve size) if the history is representative and still
small enough that it can be practically stored on disk.
The MacApp team at Apple can surely improve upon these methods, or more likely find
a better alternative. MacAppers everywhere hope it's soon.