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
$102.50
Apple Inc.
+0.25
MSFT
$45.43
Microsoft Corpora
+0.55
GOOG
$571.60
Google Inc.
+2.40

MacTech Search:
Community Search:

Software Updates via MacUpdate

VueScan 9.4.41 - Scanner software with a...
VueScan is a scanning program that works with most high-quality flatbed and film scanners to produce scans that have excellent color fidelity and color balance. VueScan is easy to use, and has... Read more
Cloud 3.0.0 - File sharing from your men...
Cloud is simple file sharing for the Mac. Drag a file from your Mac to the CloudApp icon in the menubar and we take care of the rest. A link to the file will automatically be copied to your clipboard... Read more
LibreOffice 4.3.1.2 - Free Open Source o...
LibreOffice is an office suite (word processor, spreadsheet, presentations, drawing tool) compatible with other major office suites. The Document Foundation is coordinating development and... Read more
SlingPlayer Plugin 3.3.20.505 - Browser...
SlingPlayer is the screen interface software that works hand-in-hand with the hardware inside the Slingbox to make your TV viewing experience just like that at home. It features an array of... Read more
Get Lyrical 3.8 - Auto-magically adds ly...
Get Lyrical auto-magically add lyrics to songs in iTunes. You can choose either a selection of tracks, or the current track. Or turn on "Active Tagging" to get lyrics for songs as you play them.... Read more
Viber 4.2.2 - Send messages and make cal...
Viber lets you send free messages and make free calls to other Viber users, on any device and network, in any country! Viber syncs your contacts, messages and call history with your mobile device,... Read more
Cocktail 7.6 - General maintenance and o...
Cocktail is a general purpose utility for OS X that lets you clean, repair and optimize your Mac. It is a powerful digital toolset that helps hundreds of thousands of Mac users around the world get... Read more
LaunchBar 6.1 - Powerful file/URL/email...
LaunchBar is an award-winning productivity utility that offers an amazingly intuitive and efficient way to search and access any kind of information stored on your computer or on the Web. It provides... Read more
Maya 2015 - Professional 3D modeling and...
Maya is an award-winning software and powerful, integrated 3D modeling, animation, visual effects, and rendering solution. Because Maya is based on an open architecture, all your work can be scripted... Read more
BBEdit 10.5.12 - Powerful text and HTML...
BBEdit is the leading professional HTML and text editor for the Mac. Specifically crafted in response to the needs of Web authors and software developers, this award-winning product provides a... Read more

Latest Forum Discussions

See All

Qube Kingdom – Tips, Tricks, Strategies,...
Qube Kingdom is a tower defense game from DeNA. You rally your troops – magicians, archers, knights, barbarians, and others – and fight against an evil menace looking to dominate your kingdom of tiny squares. Planning a war isn’t easy, so here are a... | Read more »
Qube Kingdom Review
Qube Kingdom Review By Nadia Oxford on August 29th, 2014 Our Rating: :: KIND OF A SQUARE KINGDOMUniversal App - Designed for iPhone and iPad Qube Kingdom has cute visuals, but it’s a pretty basic tower defense game at heart.   | Read more »
Fire in the Hole Review
Fire in the Hole Review By Rob Thomas on August 29th, 2014 Our Rating: :: WALK THE PLANKUniversal App - Designed for iPhone and iPad Seafoam’s Fire in the Hole looks like a bright, 8-bit throwback, but there’s not enough booty to... | Read more »
Alien Creeps TD is Now Available Worldwi...
Alien Creeps TD is Now Available Worldwide Posted by Ellis Spice on August 29th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Dodo Master Review
Dodo Master Review By Jordan Minor on August 29th, 2014 Our Rating: :: NEST EGGiPad Only App - Designed for the iPad Dodo Master is tough but fair, and that’s what makes it a joy to play.   | Read more »
Motorsport Manager Review
Motorsport Manager Review By Lee Hamlet on August 29th, 2014 Our Rating: :: MARVELOUS MANAGEMENTUniversal App - Designed for iPhone and iPad Despite its depth and sense of tactical freedom, Motorsport Manager is one of the most... | Read more »
Motorsport Manager – Beginner Tips, Tric...
The world of Motorsport management can be an unforgiving and merciless one, so to help with some of the stress that comes with running a successful race team, here are a few hints and tips to leave your opponents in the dust. | Read more »
CalPal Update Brings the App to 2.0, Add...
CalPal Update Brings the App to 2.0, Adds Lots of New Stuff Posted by Ellis Spice on August 29th, 2014 [ permalink ] | Read more »
Baseball Battle Review
Baseball Battle Review By Jennifer Allen on August 29th, 2014 Our Rating: :: SIMPLE HITTINGUniversal App - Designed for iPhone and iPad Simple and cute, Baseball Battle is a fairly fun baseball game for those looking for something... | Read more »
Checkmark 2.1 Update Released, and it’s...
Checkmark 2.1 Update Released, and it’s on Sale for a Limited Time Posted by Jessica Fisher on August 29th, 2014 [ permalink ] | Read more »

Price Scanner via MacPrices.net

Labor Day Weekend iPad mini sale; $50 to $100...
Best Buy has the iPad mini with Retina Display (WiFi models) on sale for $50 off MSRP on their online store for Labor Day Weekend. Choose free shipping or free local store pick up. Price is for... Read more
13-inch 1.4GHz MacBook Air on sale for $899,...
Adorama has the new 2014 13″ 1.4GHz/128GB MacBook Air on sale for $899.99 including free shipping plus NY & NJ tax only. Their price is $100 off MSRP. Read more
It’s Official: Apple Issues Invitations To Se...
Apple has issued one of its characteristically cryptic press invitations for a special event to be held at the Flint Center for the Performing Arts in hometown Cupertino on Sept. 9, 2014 at 10:00 am... Read more
Tablet Shipments To See First On-year Decline...
TrendForce analyst Caroline Chen notes that when the iPad launched in 2010, it was an instant hit and spurred a tablet PC revolution, with tablets so popular that that notebook PC sales stagnated and... Read more
SOBERLINK Releases Apple iOS Compatible Handh...
Cypress, California based SOBERLINK, Inc., creator of the first handheld Breathalyzer designed to improve recovery outcomes, continues to show prominence in the mobile alcohol monitoring space with... Read more
New 21″ 1.4GHz iMac on sale again for $999, s...
Best Buy has the new 21″ 1.4GHz iMac on sale for $999.99 on their online store. Their price is $100 off MSRP. Choose free shipping or free local store pick up. Price is for online orders only, in-... Read more
Smartphone Outlook Remains Strong for 2014, U...
According to a new mobile phone forecast from the International Data Corporation (IDC) Worldwide Quarterly Mobile Phone Tracker, more than 1.25 billion smartphones will be shipped worldwide in 2014,... Read more
Save up to $60 with Apple refurbished iPod to...
The Apple Store has Apple Certified Refurbished 5th generation iPod touches available starting at $149. Apple’s one-year warranty is included with each model, and shipping is free. Many, but not all... Read more
12-Inch MacBook Air Coming in 4Q14 or 2015 –...
Digitimes’ Aaron Lee and Joseph Tsai report that according to Taiwan-based upstream supply chain insiders, Apple plans to launch a thinner MacBook model either at year end 2014 or in 2015, and that... Read more
Sapphire Screen “Most Wanted” iPhone 6 New Fe...
According to the ‘uSell.com iPhone Most Wanted Survey’ — a representative survey of 1,000 U.S. smartphone users conducted by used iPhone marketplace uSell.com — close to half of all smartphone users... Read more

Jobs Board

*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.