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.

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Bookends 12.5.8 - Reference management a...
Bookends is a full-featured bibliography/reference and information-management system for students and professionals. Access the power of Bookends directly from Mellel, Nisus Writer Pro, or MS Word (... Read more
Chromium 44.0.2403.125 - Fast and stable...
Chromium is an open-source browser project that aims to build a safer, faster, and more stable way for all Internet users to experience the web. Version 44.0.2403.125: This release contains a number... Read more
iMazing 1.2.2 - Complete iOS device mana...
iMazing (was DiskAid) is the ultimate iOS device manager with capabilities far beyond what iTunes offers. With iMazing and your iOS device (iPhone, iPad, or iPod), you can: Copy music to and from... Read more
Audio Hijack 3.2.0 - Record and enhance...
Audio Hijack (was Audio Hijack Pro) drastically changes the way you use audio on your computer, giving you the freedom to listen to audio when you want and how you want. Record and enhance any audio... Read more
FontExplorer X Pro 5.0.1 - Font manageme...
FontExplorer X Pro is optimized for professional use; it's the solution that gives you the power you need to manage all your fonts. Now you can more easily manage, activate and organize your... Read more
Calcbot 1.0.2 - Intelligent calculator a...
Calcbot is an intelligent calculator and unit converter for the rest of us. Featuring an easy-to-read history tape, expression view, intuitive conversion, and much more! Features History Tape -... Read more
MTR 5.0.0.1 - The Mac's oldest and...
MTR (was MacTheRipper)--the Mac's oldest and smartest DVD-backup app--is now updated to version 5.001 MTR -- the complete toolbox, not a one-trick, point-and-click extractor. MTR is intended for... Read more
LibreOffice 4.4.5.2 - Free, open-source...
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
Adobe Lightroom 6.1.1 - Import, develop,...
Adobe Lightroom is available as part of Adobe Creative Cloud for as little as $9.99/month bundled with Photoshop CC as part of the photography package. Lightroom 6 is also available for purchase as a... Read more
File Juicer 4.41 - Extract images, video...
File Juicer is a drag-and-drop can opener and data archaeologist. Its specialty is to find and extract images, video, audio, or text from files which are hard to open in other ways. It finds and... Read more

Pac-Man Championship Edition DX has brou...
Bandai Namco has released Pac-Man Championship Edition DX on iOS and Android, which features the classic arcade gameplay that we've all grown to love. Pac-Man Championship Edition DX can be enjoyed in much shorter bursts than the arcade versions... | Read more »
Cosmonautica (Games)
Cosmonautica 1.1 Device: iOS Universal Category: Games Price: $6.99, Version: 1.1 (iTunes) Description: Cast off! Are you ready for some hilarious adventures in outer space? | Read more »
Rescue humanity from a Demon horde in An...
Angel Stone is Fincon's follow up to the massively successful Hello Hero and is out now on iOS and Android. You play as a member of The Resistance, a group of mighty human warriors who have risen up in defiance of the Demon horde threatening to... | Read more »
Gallery Doctor (Photography)
Gallery Doctor 1.0 Device: iOS iPhone Category: Photography Price: $2.99, Version: 1.0 (iTunes) Description: Free up valuable iCloud and iPhone storage with Gallery Doctor, the only iPhone cleaner that automatically identifies the... | Read more »
You Against Me (Games)
You Against Me 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: A simple game… You. Me. Claim, steal, lock, score, win! | Read more »
Yep, it's True - Angry Birds 2 is O...
The not exactly rumors were true and the birds are back. Angry Birds 2 has come to the App Store and the world will... well I suppose it'll still be the same, but now we have more bird-flinging options! [Read more] | Read more »
You Could Design Your Own Card for Chain...
If you've ever wanted to create your own item, weapon, trap, or even monster for Chainsaw Warrior: Lords of the Night, this is your chance. Auroch Digital is currently holding a contest so that fans can fight to the death (not really) to see which... | Read more »
Bitcoin Billionaire is Going Back in Tim...
If you thought you managed to buy everything there is to buy in Bitcoin Billionaire and make all the money, well you though wrong. Those of you who made it far enough might remember investing in time travel - and it looks like that investment is... | Read more »
Domino Drop (Games)
Domino Drop 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Domino Drop is a delightful new puzzle game with dominos and gravity!Learn how to play it in a minute, master it day by day.Your... | Read more »
OPERATION DRACULA (Games)
OPERATION DRACULA 1.0.1 Device: iOS Universal Category: Games Price: $5.99, Version: 1.0.1 (iTunes) Description: 25% off launch sale!!! 'Could prove to be one of the most accurate representations of the Japanese bullet hell shmup... | Read more »

Price Scanner via MacPrices.net

Sale! 13-inch MacBook Pros on sale for $100 o...
B&H Photo has 13″ MacBook Pros on sale for $100 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 2.5GHz/500GB MacBook Pro: $999.99 save $100 - 13″ 2.7GHz/128GB Retina... Read more
Sale! Save $100 on 13-inch MacBook Airs this...
B&H Photo has the 13″ 1.6GHz/128GB MacBook Air on sale for $899.99 including free shipping plus NY tax only. Their price is $100 off MSRP, and it’s the lowest price available for this model.... Read more
Worldwide Tablet Market Decline Continues, Ap...
The worldwide tablet market declined -7.0% year-over-year in the second quarter of 2015 (2Q15) with shipments totaling 44.7 million units according to preliminary data from the International Data... Read more
TP-LINK TL-PA8030P KIT Powerline Featuring Ho...
Consumer and business networking products provider TP-LINK is now shipping its TL-PA8030P KIT AV1200 3-Port Gigabit Passthrough Powerline Starter Kit that expands your home’s network over its... Read more
Apple refurbished iPad Air 2s available for u...
The Apple Store has Apple Certified Refurbished iPad Air 2s available for up to $140 off the price of new models. Apple’s one-year warranty is included with each model, and shipping is free: - 128GB... Read more
Updated Apple iPad Price Trackers
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. Read more
Apple refurbished 2014 13-inch 128GB MacBook...
The Apple Store has Apple Certified Refurbished 2014 13″ MacBook Airs available starting at $759. An Apple one-year warranty is included with each MacBook, and shipping is free: - 13″ 1.4GHz/128GB... Read more
Apple’s Education discount saves up to $300 o...
Purchase a new Mac or iPad at The Apple Store for Education and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free,... Read more
Save up to $600 with Apple refurbished Mac Pr...
The Apple Store has Apple Certified Refurbished Mac Pros available for up to $600 off the cost of new models. An Apple one-year warranty is included with each Mac Pro, and shipping is free. The... Read more
Mac Pros on sale for up to $260 off MSRP
B&H Photo has Mac Pros on sale for up to $260 off MSRP. Shipping is free, and B&H charges sales tax in NY only: - 3.7GHz 4-core Mac Pro: $2799, $200 off MSRP - 3.5GHz 6-core Mac Pro: $3719.99... Read more

Jobs Board

Executive Administrative Assistant, *Apple*...
…supporting presentation development for senior leadership. * User experience with Apple hardware and software is preferred. Additional Requirements The following list Read more
*Apple* Bus Company is now hirin - Apple Bus...
Apple Bus Company is now hiring school bus drivers in the Pettis County area. Class B CDL preferred. Free training provided. No nights or weekends required. Flexible Read more
*Apple* Certified Mac Technician - Updated 6...
…and friendly, hands-on technical support to customers troubleshooting and repairing Apple /Mac products with courtesy, speed and skill. Use your problem-solving skills Read more
Infrastructure Engineer - *Apple* /Mac Envir...
…a part of a team Requires proven problem solving skills Preferred Additional Apple Certified System Administrator (ACSA) Apple Certified Technical Coordinator (ACTC) Read more
*Apple* Retail - Multiple Positions (US) - A...
Job Description: Sales. Specialist - Retail Customer Service and Sales. Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.