Reprintedfrom ProceedingsoftheACMSIGPLAN’82SymposiumonCompilerConstruction SIGPLANNotices17,6(June1982),pp120-126.(f †Copyright1982ACM0-89791-074-5/82/006/0120$00.75 Permissiontocopywithoutfeeallorpartofthismaterial isgrantedprovidedthatthecopiesarenotmadeordistributedfor directcommercialadvantage,theACMcopyrightnoticeandthetitle ofthepublicationanditsdateappear,andnoticeisgiventhat copyingisbypermissionoftheAssociationforComputingMachinery. Tocopyotherwise,ortorepublish,requiresafeeand/or specificpermission. gprof:aCallGraphExecutionProfiler1 by SusanL.Graham PeterB.Kessler MarshallK.McKusick ComputerScienceDivision ElectricalEngineeringandComputerScienceDepartment UniversityofCalifornia,Berkeley Berkeley,California94720 Abstract Largecomplexprogramsarecomposedofmanysmallroutinesthatimplementabstractions fortheroutinesthatcallthem.Tobeuseful,anexecutionprofilermustattributeexecutiontime inawaythatissignificantforthelogicalstructureofaprogramaswellasforitstextualdecomposition.Thisdatamustthenbedisplayedtotheuserinaconvenientandinformativeway.The gprofprofileraccountsfortherunningtimeofcalledroutinesintherunningtimeoftheroutines thatcallthem.Thedesignanduseofthisprofilerisdescribed. 1.ProgramstobeProfiled Softwareresearchenvironmentsnormallyincludemanylargeprogramsbothforproduction useandforexperimentalinvestigation.Theseprogramsaretypicallymodular,inaccordancewith generallyacceptedprinciplesofgoodprogramdesign.Oftentheyconsistofnumeroussmallroutinesthatimplementvariousabstractions.Sometimessuchlargeprogramsarewrittenbyone programmerwhohasunderstoodtherequirementsfortheseabstractions,andhasprogrammed themappropriately.Morefrequentlytheprogramhashadmultipleauthorsandhasevolvedover time,changingthedemandsplacedontheimplementationoftheabstractionswithoutchanging theimplementationitself.Finally,theprogrammaybeassembledfromalibraryofabstraction implementationsunexaminedbytheprogrammer. 1ThisworkwassupportedbygrantMCS80-05144fromtheNationalScienceFoundation.

Oncealargeprogramisexecutable,itisoftendesirabletoincreaseitsspeed,especiallyif smallportionsoftheprogramarefoundtodominateitsexecutiontime.Thepurposeofthe gprofprofilingtoolistohelptheuserevaluatealternativeimplementationsofabstractions.We developedthistoolinresponsetooureffortstoimproveacodegeneratorwewerewriting[Graham82]. Thegprofdesigntakesadvantageofthefactthattheprogramstobemeasuredarelarge, structuredandhierarchical.Weprovideaprofileinwhichtheexecutiontimeforasetofroutines thatimplementanabstractioniscollectedandchargedtothatabstraction.Theprofilecanbe usedtocompareandassessthecostsofvariousimplementations. Theprofilercanbelinkedintoaprogramwithoutspecialplanningbytheprogrammer.The overheadforusinggprofislow;bothintermsofaddedexecutiontimeandinthevolumeofprofilinginformationrecorded. 2.TypesofProfiling Thereareseveraldifferentusesforprogramprofiles,andeachmayrequiredifferentinformationfromtheprofiles,ordifferentpresentationoftheinformation.Wedistinguishtwobroadcategoriesofprofiles:thosethatpresentcountsofstatementorroutineinvocations,andthosethat displaytiminginformationaboutstatementsorroutines.Countsaretypicallypresentedintabularform,ofteninparallelwithalistingofthesourcecode.Timinginformationcouldbesimilarly presented;butmorethanonemeasureoftimemightbeassociatedwitheachstatementorroutine. Forexample,intheframeworkusedbygprofeachprofiledsegmentwoulddisplaytwotimes:one forthetimeusedbythesegmentitself,andanotherforthetimeinheritedfromcodesegmentsit invokes. Executioncountsareusedinmanydifferentcontexts.Theexactnumberoftimesaroutine orstatementisactivatedcanbeusedtodetermineifanalgorithmisperformingasexpected. Cursoryinspectionofsuchcountersmayshowalgorithmswhosecomplexityisunsuitedtothe taskathand.Carefulinterpretationofcounterscanoftensuggestimprovementstoacceptable algorithms.Preciseexaminationcanuncoversubtleerrorsinanalgorithm.Atthislevel,profiling countersaresimilartodebuggingstatementswhosepurposeistoshowthenumberoftimesa pieceofcodeisexecuted.Anotherviewofsuchcountersisasbooleanvalues.Onemaybeinterestedthataportionofcodehasexecutedatall,forexhaustivetesting,ortocheckthatoneimplementationofanabstractioncompletelyreplacesapreviousone. Executioncountsarenotnecessarilyproportionaltotheamountoftimerequiredtoexecute theroutineorstatement.Further,theexecutiontimeofaroutinewillnotbethesameforall callsontheroutine.Thecriteriaforestablishingexecutiontimemustbedecided.Ifaroutine implementsanabstractionbyinvokingotherabstractions,thetimespentintheroutinewillnot accuratelyreflectthetimerequiredbytheabstractionitimplements.Similarly,ifanabstraction isimplementedbyseveralroutinesthetimerequiredbytheabstractionwillbedistributedacross thoseroutines. Giventheexecutiontimeofindividualroutines,gprofaccountstoeachroutinethetime spentforitbytheroutinesitinvokes.Thisaccountingisdonebyassemblingacallgraphwith nodesthataretheroutinesoftheprogramanddirectedarcsthatrepresentcallsfromcallsitesto routines.Wedistinguishamongthreedifferentcallgraphsforaprogram.Thecompletecall graphincorporatesallroutinesandallpotentialarcs,includingarcsthatrepresentcallstofunctionalparametersorfunctionalvariables.Thisgraphcontainstheothertwographsassubgraphs. Thestaticcallgraphincludesallroutinesandallpossiblearcsthatarenotcallstofunctional parametersorvariables.Thedynamiccallgraphincludesonlythoseroutinesandarcstraversed bytheprofiledexecutionoftheprogram.Thisgraphneednotincludeallroutines,norneedit includeallpotentialarcsbetweentheroutinesitcovers.Itmay,however,includearcstofunctionalparametersorvariablesthatthestaticcallgraphmayomit.Thestaticcallgraphcanbe determinedfromthe(static)programtext.Thedynamiccallgraphisdeterminedonlybyprofilinganexecutionoftheprogram.Thecompletecallgraphforamonolithicprogramcouldbe determinedbydataflowanalysistechniques.Thecompletecallgraphforprogramsthatchange duringexecution,bymodifyingthemselvesordynamicallyloadingoroverlayingcode,maynever bedeterminable.Boththestaticcallgraphandthedynamiccallgraphareusedbygprof,butit doesnotsearchforthecompletecallgraph. 3.GatheringProfileData Routinecallsorstatementexecutionscanbemeasuredbyhavingacompileraugmentthe codeatstrategicpoints.Theadditionscanbeinlineincrementstocounters[Knuth71][Satterthwaite72][Joy79]orcallstomonitoringroutines[Unix].Thecounterincrementoverheadislow, andissuitableforprofilingstatements.Acallofthemonitoringroutinehasanoverheadcomparablewithacallofaregularroutine,andisthereforeonlysuitedtoprofilingonaroutinebyroutinebasis.However,themonitoringroutinesolutionhascertainadvantages.Whatevercounters areneededbythemonitoringroutinecanbemanagedbythemonitoringroutineitself,rather thanbeingdistributedaroundthecode.Inparticular,amonitoringroutinecaneasilybecalled fromseparatelycompiledprograms.Inaddition,differentmonitoringroutinescanbelinkedinto theprogrambeingmeasuredtoassembledifferentprofilingdatawithouthavingtochangethe compilerorrecompiletheprogram.Wehaveexploitedthisapproach;ourcompilersforC,Fortran77,andPascalcaninsertcallstoamonitoringroutineintheprologueforeachroutine.Use ofthemonitoringroutinerequiresnoplanningonpartofaprogrammerotherthantorequest thataugmentedroutineprologuesbeproducedduringcompilation. Weareinterestedingatheringthreepiecesofinformationduringprogramexecution:call countsandexecutiontimesforeachprofiledroutine,andthearcsofthedynamiccallgraphtraversedbythisexecutionoftheprogram.Bypost-processingofthisdatawecanbuildthe dynamiccallgraphforthisexecutionoftheprogramandpropagatetimesalongtheedgesofthis graphtoattributetimesforroutinestotheroutinesthatinvokethem. Gatheringoftheprofilinginformationshouldnotgreatlyinterferewiththerunningofthe program.Thus,themonitoringroutinemustnotproducetraceoutputeachtimeitisinvoked. Thevolumeofdatathusproducedwouldbeunmanageablylarge,andthetimerequiredtorecord itwouldoverwhelmtherunningtimeofmostprograms.Similarly,themonitoringroutinecannot dotheanalysisoftheprofilingdata(e.g.assemblingthecallgraph,propagatingtimesaroundit, discoveringcycles,etc.)duringprogramexecution.Oursolutionistogatherprofilingdatain memoryduringprogramexecutionandtocondenseittoafileastheprofiledprogramexits.This fileisthenprocessedbyaseparateprogramtoproducethelistingoftheprofiledata.Anadvantageofthisapproachisthattheprofiledataforseveralexecutionsofaprogramcanbecombined bythepost-processingtoprovideaprofileofmanyexecutions. Theexecutiontimemonitoringconsistsofthreeparts.Thefirstpartallocatesandinitializestheruntimemonitoringdatastructuresbeforetheprogrambeginsexecution.Thesecond partisthemonitoringroutineinvokedfromtheprologueofeachprofiledroutine.Thethirdpart condensesthedatastructuresandwritesthemtoafileastheprogramterminates.Themonitoringroutineisdiscussedindetailinthefollowingsections. 3.1.ExecutionCounts Thegprofmonitoringroutinecountsthenumberoftimeseachprofiledroutineiscalled. Themonitoringroutinealsorecordsthearcinthecallgraphthatactivatedtheprofiledroutine. Thecountisassociatedwiththearcinthecallgraphratherthanwiththeroutine.Callcounts forroutinescanthenbedeterminedbysummingthecountsonarcsdirectedintothatroutine.In amachine-dependentfashion,themonitoringroutinenotesitsownreturnaddress.Thisaddress isintheprologueofsomeprofiledroutinethatisthedestinationofanarcinthedynamiccall graph.Themonitoringroutinealsodiscoversthereturnaddressforthatroutine,thusidentifying thecallsite,orsourceofthearc.Thesourceofthearcisinthecaller,andthedestinationisin thecallee.Forexample,ifaroutineAcallsaroutineB,Aisthecaller,andBisthecallee.The prologueofBwillincludeacalltothemonitoringroutinethatwillnotethearcfromAtoBand eitherinitializeorincrementacounterforthatarc. Onecannotaffordtohavethemonitoringroutineoutputtracinginformationaseacharcis identified.Therefore,themonitoringroutinemaintainsatableofallthearcsdiscovered,with countsofthenumbersoftimeseachistraversedduringexecution.Thistableisaccessedonceper routinecall.Accesstoitmustbeasfastaspossiblesoasnottooverwhelmthetimerequiredto executetheprogram. Oursolutionistoaccessthetablethroughahashtable.Weusethecallsiteastheprimary keywiththecalleeaddressbeingthesecondarykey.Sinceeachcallsitetypicallycallsonlyone callee,wecanreduce(usuallytoone)thenumberofminorlookupsbasedonthecallee.Another alternativewouldusethecalleeastheprimarykeyandthecallsiteasthesecondarykey.Such anorganizationhastheadvantageofassociatingcallerswithcallees,attheexpenseoflonger lookupsinthemonitoringroutine.Wearefortunatetoberunninginavirtualmemoryenvironment,and(forthesakeofspeed)wereabletoallocateenoughspacefortheprimaryhashtableto allowaone-to-onemappingfromcallsiteaddressestotheprimaryhashtable.Thusourhash functionistrivialtocalculateandcollisionsoccuronlyforcallsitesthatcallmultipledestinations (e.g.functionalparametersandfunctionalvariables).Aonelevelhashfunctionusingbothcall siteandcalleewouldresultinanunreasonablylargehashtable.Further,thenumberofdynamic callsitesandcalleesisnotknownduringexecutionoftheprofiledprogram. Notallcallersandcalleescanbeidentifiedbythemonitoringroutine.Routinesthatwere compiledwithouttheprofilingaugmentationswillnotcallthemonitoringroutineaspartoftheir prologue,andthusnoarcswillberecordedwhosedestinationsareintheseroutines.Oneneed notprofilealltheroutinesinaprogram.Routinesthatarenotprofiledrunatfullspeed.Certain routines,notablyexceptionhandlers,areinvokedbynon-standardcallingsequences.Thusthe monitoringroutinemayknowthedestinationofanarc(thecallee),butfinditdifficultorimpossibletodeterminethesourceofthearc(thecaller).Ofteninthesecasestheapparentsourceofthe arcisnotacallsiteatall.Suchanomalousinvocationsaredeclared‘‘spontaneous’’. 3.2.ExecutionTimes Theexecutiontimesforroutinescanbegatheredinatleasttwoways.Onemethodmeasurestheexecutiontimeofaroutinebymeasuringtheelapsedtimefromroutineentrytoroutine exit.Unfortunately,timemeasurementiscomplicatedontime-sharingsystemsbythetime-slicing oftheprogram.Asecondmethodsamplesthevalueoftheprogramcounteratsomeinterval,and infersexecutiontimefromthedistributionofthesampleswithintheprogram.Thistechniqueis particularlysuitedtotime-sharingsystems,wherethetime-slicingcanserveasthebasisforsam-plingtheprogramcounter.Noticethat,whereasthefirstmethodcouldprovideexacttimings,the secondisinherentlyastatisticalapproximation. Thesamplingmethodneednotrequiresupportfromtheoperatingsystem:allthatis neededistheabilitytosetandrespondto‘‘alarmclock’’interruptsthatrunrelativetoprogram time.Itisimperativethattheintervalsbeuniformsincethesamplingoftheprogramcounter ratherthanthedurationoftheintervalisthebasisofthedistribution.Ifsamplingisdonetoo often,theinterruptionstosampletheprogramcounterwilloverwhelmtherunningoftheprofiled program.Ontheotherhand,theprogrammustrunforenoughsampledintervalsthatthedistributionofthesamplesaccuratelyrepresentsthedistributionoftimefortheexecutionoftheprogram.Aswithroutinecalltracing,themonitoringroutinecannotaffordtooutputinformation foreachprogramcountersample.Inourcomputingenvironment,theoperatingsystemcanprovideahistogramofthelocationoftheprogramcounterattheendofeachclocktick(1/60thofa second)inwhichaprogramruns.Thehistogramisassembledinmemoryastheprogramruns.

Thisfacilityisenabledbyourmonitoringroutine.Wehaveadjustedthegranularityofthehistogramsothatprogramcountervaluesmapone-to-oneontothehistogram.Wemakethesimpli-fyingassumptionthatallcallstoaspecificroutinerequirethesameamountoftimetoexecute. Thisassumptionmaydisguisethatsomecalls(orworse,somecallsites)alwaysinvokearoutine suchthatitsexecutionisfaster(orslower)thantheaveragetimeforthatroutine. Whentheprofiledprogramterminates,thearctableandthehistogramofprogramcounter samplesiswrittentoafile.Thearctableiscondensedtoconsistofthesourceanddestination addressesofthearcandthecountofthenumberoftimesthearcwastraversedbythisexecution oftheprogram.Therecordedhistogramconsistsofcountersofthenumberoftimestheprogram counterwasfoundtobeineachoftherangescoveredbythehistogram.Therangesthemselves aresummarizedasalowerandupperboundandastepsize. 4.PostProcessing Havinggatheredthearcsofthecallgraphandtiminginformationforanexecutionofthe program,weareinterestedinattributingthetimeforeachroutinetotheroutinesthatcallit.We buildadynamiccallgraphwitharcsfromcallertocallee,andpropagatetimefromdescendants toancestorsbytopologicallysortingthecallgraph.Timepropagationisperformedfromthe leavesofthecallgraphtowardtheroots,accordingtotheorderassignedbyatopologicalnumberingalgorithm.Thetopologicalnumberingensuresthatalledgesinthegraphgofromhigher numberednodestolowernumberednodes.AnexampleisgiveninFigure1.Ifwepropagate timefromnodesintheorderassignedbythealgorithm,executiontimecanbepropagatedfrom descendantstoancestorsafterasingletraversalofeacharcinthecallgraph.Eachparent receivessomefractionofachild’stime.Thustimeischargedtothecallerinadditiontobeing chargedtothecallee. LetCebethenumberofcallstosomeroutine,e,andCerbethenumberofcallsfroma callerrtoacalleee.Sinceweareassumingeachcalltoaroutinetakestheaverageamountof timeforallcallstothatroutine,thecallerisaccountableforCer/Ceofthetimespentbythe callee.LettheSebetheselftimeofaroutine,e.Theselftimeofaroutinecanbedetermined fromthetiminginformationgatheredduringprofiledprogramexecution.Thetotaltime,Tr,we wishtoaccounttoaroutiner,isthengivenbytherecurrenceequation: Tr=Sr+rCALLSeΣTe×CeCer whererCALLSeisarelationshowingallroutinesecalledbyaroutiner.Thisrelationis 89 37 256 14 Topologicalordering Figure1. easilyavailablefromthecallgraph. However,iftheexecutioncontainsrecursivecalls,thecallgraphhascyclesthatcannotbe topologicallysorted.Inthesecases,wediscoverstrongly-connectedcomponentsinthecallgraph, treateachsuchcomponentasasinglenode,andthensorttheresultinggraph.Weuseavariation ofTarjan’sstrongly-connectedcomponentsalgorithmthatdiscoversstrongly-connectedcompo-nentsasitisassigningtopologicalordernumbers[Tarjan72]. Timepropagationwithinstronglyconnectedcomponentsisaproblem.Forexample,aselfrecursiveroutine(atrivialcycleinthecallgraph)isaccountableforallthetimeitusesinallits recursiveinstantiations.Inourscheme,thistimeshouldbesharedamongitscallgraphparents. Thearcsfromaroutinetoitselfareofinterest,butdonotparticipateintimepropagation.Thus thesimpleequationfortimepropagationdoesnotworkwithinstronglyconnectedcomponents. Timeisnotpropagatedfromonememberofacycletoanother,since,bydefinition,thisinvolves propagatingtimefromaroutinetoitself.Inaddition,childrenofonememberofacyclemustbe consideredchildrenofallmembersofthecycle.Similarly,parentsofonememberofthecycle mustinheritallmembersofthecycleasdescendants.Itisforthesereasonsthatwecollapseconnectedcomponents.Oursolutioncollectsallmembersofacycletogether,summingthetimeand callcountsforallmembers.Allcallsintothecyclearemadetosharethetotaltimeofthecycle, andalldescendantsofthecyclepropagatetimeintothecycleasawhole.Callsamongthemembersofthecycledonotpropagateanytime,thoughtheyarelistedinthecallgraphprofile. Figure2showsamodifiedversionofthecallgraphofFigure1,inwhichthenodeslabelled 3and7inFigure1aremutuallyrecursive.ThetopologicallysortedgraphafterthecycleiscollapsedisgiveninFigure3. Sincethetechniquedescribedaboveonlycollectsthedynamiccallgraph,andtheprogram typicallydoesnotcalleveryroutineoneachexecution,differentexecutionscanintroducedifferent cyclesinthedynamiccallgraph.Sincecyclesoftenhaveasignificanteffectontimepropagation, itisdesirabletoincorporatethestaticcallgraphsothatcycleswillhavethesamemembers regardlessofhowtheprogramruns. Thestaticcallgraphcanbeconstructedfromthesourcetextoftheprogram.However,discoveringthestaticcallgraphfromthesourcetextwouldrequiretwomoderatelydifficultsteps: findingthesourcetextfortheprogram(whichmaynotbeavailable),andscanningandparsing thattext,whichmaybeinanyoneofseverallanguages. Inourprogrammingsystem,thestaticcallinginformationisalsocontainedintheexecutable versionoftheprogram,whichwealreadyhaveavailable,andwhichisinlanguage-independent oo •• ooo oo Cycletobecollapsed. Figure2.

78 66 245 13 Topologicalnumberingaftercyclecollapsing. Figure3. form.Onecanexaminetheinstructionsintheobjectprogram,lookingforcallstoroutines,and notewhichroutinescanbecalled.Thistechniqueallowsustoaddarcstothosealreadyinthe dynamiccallgraph.Ifastaticallydiscoveredarcalreadyexistsinthedynamiccallgraph,no actionisrequired.Staticallydiscoveredarcsthatdonotexistinthedynamiccallgraphare addedtothegraphwithatraversalcountofzero.Thustheyareneverresponsibleforanytime propagation.However,theymayaffectthestructureofthegraph.Sincetheymaycomplete stronglyconnectedcomponents,thestaticcallgraphconstructionisdonebeforetopologicalordering. 5.DataPresentation Thedataispresentedtotheuserintwodifferentformats.Thefirstpresentationsimply liststheroutineswithoutregardtotheamountoftimetheirdescendantsuse.Thesecondpresentationincorporatesthecallgraphoftheprogram. 5.1.TheFlatProfile Theflatprofileconsistsofalistofalltheroutinesthatarecalledduringexecutionofthe program,withthecountofthenumberoftimestheyarecalledandthenumberofsecondsofexecutiontimeforwhichtheyarethemselvesaccountable.Theroutinesarelistedindecreasingorder ofexecutiontime.Alistoftheroutinesthatarenevercalledduringexecutionoftheprogramis alsoavailabletoverifythatnothingimportantisomittedbythisexecution.Theflatprofilegives aquickoverviewoftheroutinesthatareused,andshowstheroutinesthatarethemselvesresponsibleforlargefractionsoftheexecutiontime.Inpractice,thisprofileusuallyshowsthatnosingle functionisoverwhelminglyresponsibleforthetotaltimeoftheprogram.Noticethatforthisprofile,theindividualtimessumtothetotalexecutiontime. 5.2.TheCallGraphProfile Ideally,wewouldliketoprintthecallgraphoftheprogram,butwearelimitedbythetwodimensionalnatureofouroutputdevices.Wecannotassumethatacallgraphisplanar,andeven ifitis,thatwecanprintaplanarversionofit.Instead,wechoosetolisteachroutine,together withinformationabouttheroutinesthatareitsdirectparentsandchildren.Thislistingpresents awindowintothecallgraph.Basedonourexperience,bothparentinformationandchildinformationisimportant,andshouldbeavailablewithoutsearchingthroughtheoutput. called/totalparents index%timeselfdescendantscalled+selfnameindex called/totalchildren 0.201.204/10CALLER1[7] 0.301.806/10CALLER2[1] [2]41.50.503.0010+4EXAMPLE[2] 1.501.0020/40SUB1<cycle1>[4] 0.000.501/5SUB2[9] 0.000.000/5SUB3[11] ProfileentryforEXAMPLE. Figure4. Themajorentriesofthecallgraphprofilearetheentriesfromtheflatprofile,augmentedby thetimepropagatedtoeachroutinefromitsdescendants.Thisprofileissortedbythesumofthe timefortheroutineitselfplusthetimeinheritedfromitsdescendants.Theprofileshowswhichof thehigherlevelroutinesspendlargeportionsofthetotalexecutiontimeintheroutinesthatthey call.Foreachroutine,weshowtheamountoftimepassedbyeachchildtotheroutine,which includestimeforthechilditselfandforthedescendantsofthechild(andthusthedescendantsof theroutine).Wealsoshowthepercentagethesetimesrepresentofthetotaltimeaccountedto thechild.Similarly,theparentsofeachroutinearelisted,alongwithtime,andpercentageof totalroutinetime,propagatedtoeachone. Cyclesarehandledassingleentities.Thecycleasawholeisshownasthoughitwereasingleroutine,exceptthatmembersofthecyclearelistedinplaceofthechildren.Althoughthe numberofcallsofeachmemberfromwithinthecycleareshown,theydonotaffecttimepropagation.Whenachildisamemberofacycle,thetimeshownistheappropriatefractionofthetime forthewholecycle.Self-recursiveroutineshavetheircallsbrokendownintocallsfromtheout-sideandself-recursivecalls.Onlytheoutsidecallsaffectthepropagationoftime. Thefollowingexampleisatypicalfragmentofacallgraph. CALLER1CALLER2 EXAMPLE SUB1SUB2SUB3 TheentryinthecallgraphprofilelistingforthisexampleisshowninFigure4. TheentryisforroutineEXAMPLE,whichhastheCallerroutinesasitsparents,andtheSub routinesasitschildren.Thereadershouldkeepinmindthatallinformationisgivenwithrespect toEXAMPLE.TheindexinthefirstcolumnshowsthatEXAMPLEisthesecondentryintheprofilelisting.TheEXAMPLEroutineiscalledtentimes,fourtimesbyCALLER1,andsixtimesby CALLER2.Consequently40%ofEXAMPLE’stimeispropagatedtoCALLER1,and60%ofEXAM-PLE’stimeispropagatedtoCALLER2.Theselfanddescendantfieldsoftheparentsshowthe amountofselfanddescendanttimeEXAMPLEpropagatestothem(butnotthetimeusedbythe parentsdirectly).NotethatEXAMPLEcallsitselfrecursivelyfourtimes.TheroutineEXAMPLE callsroutineSUB1twentytimes,SUB2once,andnevercallsSUB3.SinceSUB2iscalledatotalof fivetimes,20%ofitsselfanddescendanttimeispropagatedtoEXAMPLE’sdescendanttimefield. BecauseSUB1isamemberofcycle1,theselfanddescendanttimesandcallcountfractionare thoseforthecycleasawhole.Sincecycle1iscalledatotaloffortytimes(notcountingcalls amongmembersofthecycle),itpropagates50%ofthecycle’sselfanddescendanttimetoEXAM-PLE’sdescendanttimefield.Finallyeachnameisfollowedbyanindexthatshowswhereonthe listingtofindtheentryforthatroutine. 6.UsingtheProfiles Theprofilerisausefultoolforimprovingasetofroutinesthatimplementanabstraction. Itcanbehelpfulinidentifyingpoorlycodedroutines,andinevaluatingthenewalgorithmsand codethatreplacethem.Takingfulladvantageoftheprofilerrequiresacarefulexaminationofthe callgraphprofile,andathoroughknowledgeoftheabstractionsunderlyingtheprogram. Theeasiestoptimizationthatcanbeperformedisasmallchangetoacontrolconstructor datastructurethatimprovestherunningtimeoftheprogram.Anobviousstartingpointisaroutinethatiscalledmanytimes.Forexample,supposeanoutputroutineistheonlyparentofa routinethatformatsthedata.Ifthisformatroutineisexpandedinlineintheoutputroutine,the overheadofafunctioncallandreturncanbesavedforeachdatumthatneedstobeformatted. Thedrawbacktoinlineexpansionisthatthedataabstractionsintheprogrammaybecome lessparameterized,hencelessclearlydefined.Theprofilingwillalsobecomelessusefulsincethe lossofroutineswillmakeitsoutputmoregranular.Forexample,ifthesymboltablefunctions ‘‘lookup’’,‘‘insert’’,and‘‘delete’’areallmergedintoasingleparameterizedroutine,itwillbe impossibletodeterminethecostsofanyoneoftheseindividualfunctionsfromtheprofile. Furtherpotentialforoptimizationliesinroutinesthatimplementdataabstractionswhose totalexecutiontimeislong.Forexample,alookuproutinemightbecalledonlyafewtimes,but useaninefficientlinearsearchalgorithm,thatmightbereplacedwithabinarysearch.Alternately,thediscoverythatarehashingfunctionisbeingcalledexcessively,canleadtoadifferent hashfunctionoralargerhashtable.Ifthedataabstractionfunctioncannoteasilybespeededup, itmaybeadvantageoustocacheitsresults,andeliminatetheneedtorerunitforidenticalinputs. Theseandotherideasforprogramimprovementarediscussedin[Bentley81]. Thistoolisbestusedinaniterativeapproach:profilingtheprogram,eliminatingonebottleneck,thenfindingsomeotherpartoftheprogramthatbeginstodominateexecutiontime.For instance,wehaveusedgprofonitself;eliminating,rewriting,andinlineexpandingroutines,until readingdatafiles(hardlyatargetforoptimization!)representsthedominatingfactorinitsexecutiontime. Certaintypesofprogramsarenoteasilyanalyzedbygprof.Theyaretypifiedbyprograms thatexhibitalargedegreeofrecursion,suchasrecursivedescentcompilers.Theproblemisthat mostofthemajorroutinesaregroupedintoasinglemonolithiccycle.Asinthesymboltable abstractionthatisplacedinoneroutine,itisimpossibletodistinguishwhichmembersofthe cycleareresponsiblefortheexecutiontime.Unfortunatelytherearenoeasymodificationsto theseprogramsthatmakethemamenabletoanalysis. Acompletelydifferentuseoftheprofileristoanalyzethecontrolflowofanunfamiliarprogram.Ifyoureceiveaprogramfromanotheruserthatyouneedtomodifyinsomesmallway,it isoftenunclearwherethechangesneedtobemade.Byrunningtheprogramonanexampleand thenusinggprof,youcangetaviewofthestructureoftheprogram. Consideranexampleinwhichyouneedtochangetheoutputformatoftheprogram.For purposesofthisexamplesupposethatthecallgraphoftheoutputportionoftheprogramhasthe followingstructure:

CALC1CALC2CALC3 FORMAT1FORMAT2 ‘‘WRITE’’ Initiallyyoulookthroughthegprofoutputforthesystemcall‘‘WRITE’’.Theformatroutineyou willneedtochangeisprobablyamongtheparentsofthe‘‘WRITE’’procedure.Thenextstepisto lookattheprofileentryforeachofparentsof‘‘WRITE’’,inthisexampleeither‘‘FORMAT1’’or ‘‘FORMAT2’’,todeterminewhichonetochange.Eachformatroutinewillhaveoneormoreparents,inthisexample‘‘CALC1’’,‘‘CALC2’’,and‘‘CALC3’’.Byinspectingthesourcecodeforeachof theseroutinesyoucandeterminewhichformatroutinegeneratestheoutputthatyouwishto modify.Sincethegprofentryshowsallthepotentialcallstotheformatroutineyouintendto change,youcandetermineifyourmodificationswillaffectoutputthatshouldbeleftalone.If youdesiretochangetheoutputof‘‘CALC2’’,butnot‘‘CALC3’’,thenformattingroutine‘‘FOR-MAT2’’needstobesplitintotwoseparateroutines,oneofwhichimplementsthenewformat. Youcanthenretargetjustthecallby‘‘CALC2’’thatneedsthenewformat.Itshouldbenoted thatthestaticcallinformationisparticularlyusefulheresincethetestcaseyourunprobablywill notexercisetheentireprogram. 7.Conclusions Wehavecreatedaprofilerthataidsintheevaluationofmodularprograms.Foreachroutineintheprogram,theprofileshowstheextenttowhichthatroutinehelpssupportvarious abstractions,andhowthatroutineusesotherabstractions.Theprofileaccuratelyassessesthe costofroutinesatalllevelsoftheprogramdecomposition.Theprofileriseasilyused,andcanbe compiledintotheprogramwithoutanypriorplanningbytheprogrammer.Itaddsonlyfiveto thirtypercentexecutionoverheadtotheprogrambeingprofiled,producesnoadditionaloutput untilaftertheprogramfinishes,andallowstheprogramtobemeasuredinitsactualenvironment. Finally,theprofilerrunsonatime-sharingsystemusingonlythenormalservicesprovidedbythe operatingsystemandcompilers. 8.References [Bentley81] Bentley,J.L.,‘‘WritingEfficientCode’’,DepartmentofComputerScience,Carnegie-Mellon University,Pittsburgh,Pennsylvania,CMU-CS-81-116,1981. [Graham82] Graham,S.L.,Henry,R.R.,Schulman,R.A.,‘‘AnExperimentinTableDrivenCodeGeneration’’,SIGPLAN’82SymposiumonCompilerConstruction,June,1982. [Joy79] Joy,W.N.,Graham,S.L.,Haley,C.B.‘‘BerkeleyPascalUser’sManual’’,Version1.1,ComputerScienceDivisionUniversityofCalifornia,Berkeley,CA.April1979. [Knuth71] Knuth,D.E.‘‘AnempiricalstudyofFORTRANprograms’’,Software-PracticeandExperi-ence,1,105-133.1971 [Satterthwaite72] Satterthwaite,E.‘‘DebuggingToolsforHighLevelLanguages’’,Software-Practiceand Experience,2,197-217,1972 [Tarjan72] Tarjan,R.E.,‘‘Depthfirstsearchandlineargraphalgorithm,’’SIAMJ.Computing1:2, 146-160,1972. [Unix] UnixProgrammer’sManual,‘‘profcommand’’,section1,BellLaboratories,MurrayHill, NJ.January1979.