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

GraphicConverter 10.5.4 - $39.95
GraphicConverter is an all-purpose image-editing program that can import 200 different graphic-based formats, edit the image, and export it to any of 80 available file formats. The high-end editing... Read more
Dash 4.1.3 - Instant search and offline...
Dash is an API documentation browser and code snippet manager. Dash helps you store snippets of code, as well as instantly search and browse documentation for almost any API you might use (for a full... Read more
Microsoft OneNote 16.9 - Free digital no...
OneNote is your very own digital notebook. With OneNote, you can capture that flash of genius, that moment of inspiration, or that list of errands that's too important to forget. Whether you're at... Read more
DEVONthink Pro 2.9.17 - Knowledge base,...
Save 10% with our exclusive coupon code: MACUPDATE10 DEVONthink Pro is your essential assistant for today's world, where almost everything is digital. From shopping receipts to important research... Read more
OmniGraffle 7.6 - Create diagrams, flow...
OmniGraffle helps you draw beautiful diagrams, family trees, flow charts, org charts, layouts, and (mathematically speaking) any other directed or non-directed graphs. We've had people use Graffle to... Read more
iFinance 4.3.7 - Comprehensively manage...
iFinance allows you to keep track of your income and spending -- from your lunchbreak coffee to your new car -- in the most convenient and fastest way. Clearly arranged transaction lists of all your... Read more
Opera 50.0.2762.58 - High-performance We...
Opera is a fast and secure browser trusted by millions of users. With the intuitive interface, Speed Dial and visual bookmarks for organizing favorite sites, news feature with fresh, relevant content... Read more
Microsoft Office 2016 16.9 - Popular pro...
Microsoft Office 2016 - Unmistakably Office, designed for Mac. The new versions of Word, Excel, PowerPoint, Outlook and OneNote provide the best of both worlds for Mac users - the familiar Office... Read more
SoftRAID 5.6.4 - High-quality RAID manag...
SoftRAID allows you to create and manage disk arrays to increase performance and reliability. SoftRAID allows the user to create and manage RAID 4 and 5 volumes, RAID 1+0, and RAID 1 (Mirror) and... Read more
OmniGraffle Pro 7.6 - Create diagrams, f...
OmniGraffle Pro helps you draw beautiful diagrams, family trees, flow charts, org charts, layouts, and (mathematically speaking) any other directed or non-directed graphs. We've had people use... Read more

Latest Forum Discussions

See All

The 7 best games that came out for iPhon...
Well, it's that time of the week. You know what I mean. You know exactly what I mean. It's the time of the week when we take a look at the best games that have landed on the App Store over the past seven days. And there are some real doozies here... | Read more »
Popular MMO Strategy game Lords Mobile i...
Delve into the crowded halls of the Play Store and you’ll find mobile fantasy strategy MMOs-a-plenty. One that’s kicking off the new year in style however is IGG’s Lords Mobile, which has beaten out the fierce competition to receive Google Play’s... | Read more »
Blocky Racing is a funky and fresh new k...
Blocky Racing has zoomed onto the App Store and Google Play this week, bringing with it plenty of classic kart racing shenanigans that will take you straight back to your childhood. If you’ve found yourself hooked on games like Mario Kart or Crash... | Read more »
Cytus II (Games)
Cytus II 1.0.1 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0.1 (iTunes) Description: "Cytus II" is a music rhythm game created by Rayark Games. It's our fourth rhythm game title, following the footsteps of three... | Read more »
JYDGE (Games)
JYDGE 1.0.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.0 (iTunes) Description: Build your JYDGE. Enter Edenbyrg. Get out alive. JYDGE is a lawful but awful roguehate top-down shooter where you get to build your... | Read more »
Tako Bubble guide - Tips and Tricks to S...
Tako Bubble is a pretty simple and fun puzzler, but the game can get downright devious with its puzzle design. If you insist on not paying for the game and want to manage your lives appropriately, check out these tips so you can avoid getting... | Read more »
Everything about Hero Academy 2 - The co...
It's fair to say we've spent a good deal of time on Hero Academy 2. So much so, that we think we're probably in a really good place to give you some advice about how to get the most out of the game. And in this guide, that's exactly what you're... | Read more »
Everything about Hero Academy 2: Part 3...
In the third part of our Hero Academy 2 guide we're going to take a look at the different modes you can play in the game. We'll explain what you need to do in each of them, and tell you why it's important that you do. [Read more] | Read more »
Everything about Hero Academy 2: Part 2...
In this second part of our guide to Hero Academy 2, we're going to have a look at the different card types that you're going to be using in the game. We'll split them up into different sections too, to make sure you're getting the most information... | Read more »
Everything about Hero Academy 2: Part 1...
So you've started playing Hero Academy 2, and you're feeling a little bit lost. Don't worry, we've got your back. So we've come up with a series of guides that are going to help you get to grips with everything that's going on in the game. [Read... | Read more »

Price Scanner via MacPrices.net

How to find the lowest prices on 2017 Apple M...
Apple has Certified Refurbished 13″ and 15″ 2017 MacBook Pros available for $200 to $420 off the cost of new models. Apple’s refurbished prices are the lowest available for each model from any... Read more
The lowest prices anywhere on Apple 12″ MacBo...
Apple has Certified Refurbished 2017 12″ Retina MacBooks available for $200-$240 off the cost of new models. Apple will include a standard one-year warranty with each MacBook, and shipping is free.... Read more
Apple now offering a full line of Certified R...
Apple is now offering Certified Refurbished 2017 10″ and 12″ iPad Pros for $100-$190 off MSRP, depending on the model. An Apple one-year warranty is included with each model, and shipping is free: –... Read more
27″ iMacs on sale for $100-$130 off MSRP, pay...
B&H Photo has 27″ iMacs on sale for $100-$130 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 27″ 3.8GHz iMac (MNED2LL/A): $2199 $100 off MSRP – 27″ 3.... Read more
2.8GHz Mac mini on sale for $899, $100 off MS...
B&H Photo has the 2.8GHz Mac mini (model number MGEQ2LL/A) on sale for $899 including free shipping plus NY & NJ sales tax only. Their price is $100 off MSRP. Read more
Apple offers Certified Refurbished iPad minis...
Apple has Certified Refurbished 128GB iPad minis available today for $339 including free shipping. Apple’s standard one-year warranty is included. Their price is $60 off MSRP. Read more
Amazon offers 13″ 256GB MacBook Air for $1049...
Amazon has the 13″ 1.8GHz/256B #Apple #MacBook Air on sale today for $150 off MSRP including free shipping: – 13″ 1.8GHz/256GB MacBook Air (MQD42LL/A): $1049.99, $150 off MSRP Read more
9.7-inch 2017 WiFi iPads on sale starting at...
B&H Photo has 9.7″ 2017 WiFi #Apple #iPads on sale for $30 off MSRP for a limited time. Shipping is free, and pay sales tax in NY & NJ only: – 32GB iPad WiFi: $299, $30 off – 128GB iPad WiFi... Read more
Wednesday deal: 13″ MacBook Pros for $100-$15...
B&H Photo has 13″ #Apple #MacBook Pros on sale for up to $100-$150 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 13-inch 2.3GHz/128GB Space Gray... Read more
Apple now offering Certified Refurbished 2017...
Apple has Certified Refurbished 9.7″ WiFi iPads available for $50-$80 off the cost of new models. An Apple one-year warranty is included with each iPad, and shipping is free: – 9″ 32GB WiFi iPad: $... Read more

Jobs Board

*Apple* Store Leader - Retail District Manag...
Job Description: Job Summary As more and more people discover Apple , they visit our retail stores seeking ways to incorporate our products into their lives. It's Read more
Sr. Experience Designer, Today at *Apple* -...
# Sr. Experience Designer, Today at Apple Job Number: 56495251 Santa Clara Valley, California, United States Posted: 18-Jan-2018 Weekly Hours: 40.00 **Job Summary** Read more
Security Applications Engineer, *Apple* Ret...
# Security Applications Engineer, Apple Retail Job Number: 113237456 Santa Clara Valley, California, United States Posted: 17-Jan-2018 Weekly Hours: 40.00 **Job Read more
*Apple* Solutions Consultant - Apple (United...
# Apple Solutions Consultant Job Number: 113384559 Brandon, Florida, United States Posted: 10-Jan-2018 Weekly Hours: 40.00 **Job Summary** Are you passionate about Read more
Art Director, *Apple* Music + Beats1 Market...
# Art Director, Apple Music + Beats1 Marketing Design Job Number: 113258081 Santa Clara Valley, California, United States Posted: 05-Jan-2018 Weekly Hours: 40.00 Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.