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

Macs Fan Control 1.3.1.0 - Monitor and c...
Macs Fan Control allows you to monitor and control almost any aspect of your computer's fans, with support for controlling fan speed, temperature sensors pane, menu-bar icon, and autostart with... Read more
NetShade 6.3.1 - Browse privately using...
NetShade is an anonymous proxy and VPN app+service for Mac. Unblock your Internet through NetShade's high-speed proxy and VPN servers spanning seven countries. NetShade masks your IP address as you... Read more
Dragon Dictate 4.0.7 - Premium voice-rec...
With Dragon Dictate speech recognition software, you can use your voice to create and edit text or interact with your favorite Mac applications. Far more than just speech-to-text, Dragon Dictate lets... Read more
Persecond 1.0.2 - Timelapse video made e...
Persecond is the easy, fun way to create a beautiful timelapse video. Import an image sequence from any camera, trim the length of your video, adjust the speed and playback direction, and you’re done... Read more
GIMP 2.8.14p2 - Powerful, free image edi...
GIMP is a multi-platform photo manipulation tool. GIMP is an acronym for GNU Image Manipulation Program. The GIMP is suitable for a variety of image manipulation tasks, including photo retouching,... Read more
Sandvox 2.10.2 - Easily build eye-catchi...
Sandvox is for Mac users who want to create a professional looking website quickly and easily. With Sandvox, you don't need to be a Web genius to build a stylish, feature-rich, standards-compliant... Read more
LibreOffice 5.0.1.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
f.lux 36.1 - Adjusts the color of your d...
f.lux makes the color of your computer's display adapt to the time of day, warm at night and like sunlight during the day. Ever notice how people texting at night have that eerie blue glow? Or wake... Read more
VirtualBox 5.0.2 - x86 virtualization so...
VirtualBox is a family of powerful x86 virtualization products for enterprise as well as home use. Not only is VirtualBox an extremely feature rich, high performance product for enterprise customers... Read more
File Juicer 4.43 - 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. In computer... Read more

ReBoard: Revolutionary Keyboard (Utilit...
ReBoard: Revolutionary Keyboard 1.0 Device: iOS Universal Category: Utilities Price: $1.99, Version: 1.0 (iTunes) Description: Do everything within the keyboard without switching apps! If you are in WhatsApp, how do you schedule a... | Read more »
Tiny Empire (Games)
Tiny Empire 1.1.3 Device: iOS Universal Category: Games Price: $2.99, Version: 1.1.3 (iTunes) Description: Launch cannonballs and blow tiny orcs into thousands of pieces in this intuitive fantasy-themed puzzle shooter! Embark on an... | Read more »
Astropad Mini (Productivity)
Astropad Mini 1.0 Device: iOS iPhone Category: Productivity Price: $4.99, Version: 1.0 (iTunes) Description: *** 50% off introductory price! ​*** Get the high-end experience of a Wacom tablet at a fraction of the price with Astropad... | Read more »
Emo Chorus (Music)
Emo Chorus 1.0.0 Device: iOS Universal Category: Music Price: $1.99, Version: 1.0.0 (iTunes) Description: Realistic Choir simulator ranging from simple Chorus emulation to full ensemble Choir with 128 members. ### introductory offer... | Read more »
Forest Spirit (Games)
Forest Spirit 1.0.5 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0.5 (iTunes) Description: | Read more »
Ski Safari 2 (Games)
Ski Safari 2 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: The world's most fantastical, fun, family-friendly skiing game is back and better than ever! Play as Sven's sister Evana, share... | Read more »
Lara Croft GO (Games)
Lara Croft GO 1.0.47768 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.47768 (iTunes) Description: Lara Croft GO is a turn based puzzle-adventure set in a long-forgotten world. Explore the ruins of an ancient... | Read more »
Whispering Willows (Games)
Whispering Willows 1.23 Device: iOS Universal Category: Games Price: $4.99, Version: 1.23 (iTunes) Description: **LAUNCH SALE 50% OFF** - Whispering Willows is on sale for 50% off ($4.99) until September 9th. | Read more »
Calvino Noir (Games)
Calvino Noir 1.1 Device: iOS iPhone Category: Games Price: $3.99, Version: 1.1 (iTunes) Description: The film noir stealth game. Calvino Noir is the exploratory, sneaking adventure through the 1930s European criminal underworld.... | Read more »
Angel Sword (Games)
Angel Sword 1.0 Device: iOS Universal Category: Games Price: $6.99, Version: 1.0 (iTunes) Description: Prepare to adventure in the most epic full scale multiplayer 3D RPG for mobile! Experience amazing detailed graphics in full HD.... | Read more »

Price Scanner via MacPrices.net

iPad Air 2 on sale for up to $100 off MSRP
Best Buy has iPad Air 2s on sale for up to $100 off MSRP on their online store for a limited time. Choose free shipping or free local store pickup (if available). Sale prices available for online... Read more
MacBook Airs on sale for $100 off MSRP
Best Buy has MacBook Airs on sale for $100 off MSRP on their online store. Choose free shipping or free local store pickup (if available). Sale prices for online orders only, in-store prices may vary... Read more
Big Grips Lift Handle For iPad Air and iPad A...
KEM Ventures, Inc. which pioneered the extra-large, super-protective iPad case market with the introduction of Big Grips Frame and Stand in 2011, is launching Big Grips Lift featuring a new super-... Read more
Samsung Launches Galaxy Tab S2, Its Most Powe...
Samsung Electronics America, Inc. has announced the U.S. release of the Galaxy Tab S2, its thinnest, lightest, ultra-fast tablet. Blending form and function, elegant design and multitasking power,... Read more
Tablet Screen Sizes Expanding as iPad Pro App...
Larger screen sizes are gaining favor as the tablet transforms into a productivity device, with shipments growing 185 percent year-over-year in 2015. According to a new Strategy Analytics’ Tablet... Read more
Today Only: Save US$50 on Adobe Elements 13;...
Keep the memories. lose the distractions. Summer’s winding down and it’s time to turn almost perfect shots into picture perfect memories with Elements 13. And get the power to edit both photos and... Read more
1.4GHz Mac mini on sale for $449, save $50
Best Buy has the 1.4GHz Mac mini on sale for $50 off MSRP on their online store. Choose free shipping or free local store pickup (if available). Price for online orders only, in-store price may vary... Read more
12-inch 1.1GHz Gold MacBook on sale for $1149...
B&H Photo has the 12″ 1.1GHz Gold Retina MacBook on sale for $1149.99 including free shipping plus NY sales tax only. Their price is $150 off MSRP, and it’s the lowest price available for this... Read more
27-inch 3.3GHz 5K iMac on sale for $1849, sav...
Best Buy has the 27″ 3.3GHz 5K iMac on sale for $1849.99. Their price is $150 off MSRP, and it’s the lowest price available for this model. Choose free shipping or free local store pickup (if... Read more
Worldwide Tablet Shipments Expected to Declin...
Does Apple badly need a touchscreen convertible/hybrid laptop MacBook? Yes, judging from a new market forecast from the International Data Corporation (IDC) Worldwide Quarterly Tablet Tracker, which... 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 Online Store: Customer Insigh...
**Job Summary** Apple Retail (Online Store) is seeking an experienced e-commerce analytics professional to join the Customer Insights Team. The Web e-Commerce Analyst Read more
*Apple* Music, Business Operations - Apple I...
Changing the world is all in a day039s work at Apple . If you love innovation, here039s your chance to make a career of it. You039ll work hard. But the job comes with Read more
WW *Apple* Retail Online Store: Customer In...
**Job Summary** The Apple Retail - Online Store is seeking an experienced web merchandising analytics professional to join the Customer Insights Team. The Web Read more
Senior Payments Security Manager - *Apple*...
**Job Summary** Apple , Inc. is looking for a highly motivated, innovative and hands-on senior payments security manager to join the Apple Pay security team. You will Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.