TweetFollow Us on Twitter

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
                {create Segment mapping}
                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.

 
AAPL
$99.28
Apple Inc.
+1.61
MSFT
$43.87
Microsoft Corpora
+0.24
GOOG
$516.51
Google Inc.
+5.34

MacTech Search:
Community Search:

Software Updates via MacUpdate

TechTool Pro 7.0.5 - Hard drive and syst...
TechTool Pro is now 7, and this is the most advanced version of the acclaimed Macintosh troubleshooting utility created in its 20-year history. Micromat has redeveloped TechTool Pro 7 to be fully 64... Read more
Yasu 2.9.1 - System maintenance app; per...
Yasu was originally created with System Administrators who service large groups of workstations in mind, Yasu (Yet Another System Utility) was made to do a specific group of maintenance tasks... Read more
Hazel 3.3 - Create rules for organizing...
Hazel is your personal housekeeper, organizing and cleaning folders based on rules you define. Hazel can also manage your trash and uninstall your applications. Organize your files using a... Read more
Autopano Giga 3.7 - Stitch multiple imag...
Autopano Giga allows you to stitch 2, 20, or 2,000 images. Version 3.0 integrates impressive new features that will definitely make you adopt Autopano Pro or Autopano Giga: Choose between 9... Read more
MenuMeters 1.8 - CPU, memory, disk, and...
MenuMeters is a set of CPU, memory, disk, and network monitoring tools for Mac OS X. Although there are numerous other programs which do the same thing, none had quite the feature set I was looking... Read more
Coda 2.5 - One-window Web development su...
Coda is a powerful Web editor that puts everything in one place. An editor. Terminal. CSS. Files. With Coda 2, we went beyond expectations. With loads of new, much-requested features, a few... Read more
Arq 4.6.1 - Online backup to Google Driv...
Arq is super-easy online backup for the Mac. Back up to your own Google Drive storage (15GB free storage), your own Amazon Glacier ($.01/GB per month storage) or S3, or any SFTP server. Arq backs up... Read more
Airfoil 4.8.10 - Send audio from any app...
Airfoil allows you to send any audio to AirPort Express units, Apple TVs, and even other Macs and PCs, all in sync! It's your audio - everywhere. With Airfoil you can take audio from any... Read more
Apple iMovie 10.0.6 - Edit personal vide...
With an all-new design, Apple iMovie lets you enjoy your videos like never before. Browse your clips more easily, instantly share your favorite moments, and create beautiful HD movies and Hollywood-... Read more
Tunnelblick 3.4.1 - GUI for OpenVPN. (Fr...
Tunnelblick is a free, open source graphic user interface for OpenVPN on OS X. It provides easy control of OpenVPN client and/or server connections. It comes as a ready-to-use application with all... Read more

Latest Forum Discussions

See All

GAMEVIL Announces the Upcoming Launch of...
GAMEVIL Announces the Upcoming Launch of Mark of the Dragon Posted by Jessica Fisher on October 20th, 2014 [ permalink ] Mark of the Dragon, by GAMEVIL, put | Read more »
Find Free Food on Campus with Ypay
Find Free Food on Campus with Ypay Posted by Jessica Fisher on October 20th, 2014 [ permalink ] iPhone App - Designed for the iPhone, compatible with the iPad | Read more »
Strung Along Review
Strung Along Review By Jordan Minor on October 20th, 2014 Our Rating: :: GOT NO STRINGSUniversal App - Designed for iPhone and iPad A cool gimmick and a great art style keep Strung Along from completely falling apart.   | Read more »
P2P file transferring app Send Anywhere...
File sharing services like Dropbox have security issues. Email attachments can be problematic when it comes to sharing large files. USB dongles don’t fit into your phone. Send Anywhere, a peer-to-peer file transferring application, solves all of... | Read more »
Zero Age Review
Zero Age Review By Jordan Minor on October 20th, 2014 Our Rating: :: MORE THAN ZEROiPad Only App - Designed for the iPad With its mind-bending puzzles and spellbinding visuals, Zero Age has it all.   | Read more »
Hay Ewe Review
Hay Ewe Review By Campbell Bird on October 20th, 2014 Our Rating: :: SAVE YOUR SHEEPLEUniversal App - Designed for iPhone and iPad Pave the way for your flock in this line drawing puzzle game from the creators of Worms.   | Read more »
My Very Hungry Caterpillar (Education)
My Very Hungry Caterpillar 1.0.0 Device: iOS Universal Category: Education Price: $3.99, Version: 1.0.0 (iTunes) Description: Care for your very own Very Hungry Caterpillar! My Very Hungry Caterpillar will captivate you as he crawls... | Read more »
Dungeon Dick (Games)
Dungeon Dick 1.1 Device: iOS Universal Category: Games Price: $.99, Version: 1.1 (iTunes) Description: Dungeon Dick is a fantasy adventure where you must discover the wicked plot to destroy the lands . 'Fling' at your foes and land... | Read more »
Here’s How the Apple Watch Could Transfo...
With the Apple Watch’s generic release date of, “early 2015” hovering on the horizon, it’s only a matter of time before gamers begin to ask “What’s in it for us?” The obvious choice would be to place entire games directly on the face of the watch,... | Read more »
Republique Episode 3: Ones & Zeroes...
Republique Episode 3: Ones & Zeroes is Available Now Posted by Rob Rich on October 17th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »

Price Scanner via MacPrices.net

2013 15-inch 2.0GHz Retina MacBook Pro availa...
B&H Photo has leftover previous-generation 15″ 2.0GHz Retina MacBook Pros now available for $1599 including free shipping plus NY sales tax only. Their price is $400 off original MSRP. B&H... Read more
Updated iPad Prices
We’ve updated our iPad Air Price Tracker and our iPad mini Price Tracker with the latest information on prices and availability from Apple and other resellers, including the new iPad Air 2 and the... Read more
Apple Pay Available to Millions of Visa Cardh...
Visa Inc. brings secure, convenient payments to iPad Air 2 and iPad mini 3as well as iPhone 6 and 6 Plus. Starting October 20th, eligible Visa cardholders in the U.S. will be able to use Apple Pay,... Read more
Textkraft Pocket – the missing TextEdit for i...
infovole GmbH has announced the release and immediate availability of Textkraft Pocket 1.0, a professional text editor and note taking app for Apple’s iPhone. In March 2014 rumors were all about... Read more
C Spire to offer iPad Air 2 and iPad mini 3,...
C Spire on Friday announced that it will offer iPad Air 2 and iPad mini 3, both with Wi-Fi + Cellular, on its 4G+ LTE network in the coming weeks. C Spire will offer the new iPads with a range of... Read more
Belkin Announces Full Line of Keyboards and C...
Belkin International has unveiled a new lineup of keyboard cases and accessories for Apple’s newest iPads, featuring three QODE keyboards and a collection of thin, lightweight folios for both the... Read more
Verizon offers new iPad Air 2 preorders for $...
Verizon Wireless is accepting preorders for the new iPad Air 2, cellular models, for $100 off MSRP with a 2-year service agreement: - 16GB iPad Air 2 WiFi + Cellular: $529.99 - 64GB iPad Air 2 WiFi... Read more
Price drops on refurbished Mac minis, now ava...
The Apple Store has dropped prices on Apple Certified Refurbished previous-generation Mac minis, with models now available starting at $419. Apple’s one-year warranty is included with each mini, and... Read more
Apple refurbished 2014 MacBook Airs available...
The Apple Store has Apple Certified Refurbished 2014 MacBook Airs available for up to $180 off the cost of new models. An Apple one-year warranty is included with each MacBook, and shipping is free.... Read more
Refurbished 2013 MacBook Pros available for u...
The Apple Store has Apple Certified Refurbished 13″ and 15″ MacBook Pros available starting at $929. Apple’s one-year warranty is standard, and shipping is free: - 13″ 2.5GHz MacBook Pros (4GB RAM/... Read more

Jobs Board

Position Opening at *Apple* - Apple (United...
…customers purchase our products, you're the one who helps them get more out of their new Apple technology. Your day in the Apple Store is filled with a range of Read more
Position Opening at *Apple* - Apple (United...
**Job Summary** At the Apple Store, you connect business professionals and entrepreneurs with the tools they need in order to put Apple solutions to work in their Read more
Position Opening at *Apple* - Apple (United...
**Job Summary** The Apple Store is a retail environment like no other - uniquely focused on delivering amazing customer experiences. As an Expert, you introduce people Read more
Position Opening at *Apple* - Apple (United...
**Job Summary** As businesses discover the power of Apple computers and mobile devices, it's your job - as a Solutions Engineer - to show them how to introduce these Read more
Position Opening at *Apple* - Apple (United...
…Summary** As a Specialist, you help create the energy and excitement around Apple products, providing the right solutions and getting products into customers' hands. You Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.