Restructuring software A case study

RestructuringSoftware:ACaseStudyTIMHOPKINSComputingLaboratoryUniversityofKentCanterbury,CT27NFKent,[e-mail]2,1998AbstractWeuseknotcountandpathcountmetricstoidentifywhichroutinesintheLevel1BLASmightbenetfromcoderestructuring.Wethencon-siderhowbothlogicalrestructuringandtheimprovementsinthefacilitiesavailablefromsuccessiveversionsofFortranhaveallowedustoimproveboththecomplexityofthecodeasmeasuredbyknotcount,pathcountandcyclomaticcomplexity,andtheuserinterfaceofoneoftheidenti-edroutineswhichcomputetheEuclideannormofavector.Withthesereductionsincomplexitywehopethatwehavecontributedtoimprove-mentsinthemaintainabilityandclarityofthecode.Softwarecomplexitymetricsandthecontrolgraphareusedtoquantifyandprovideavisualguidetothequalityofthesoftware,andtheperformanceofaFortrancoderestructuringtoolisreported.FinallywegivesomeindicationofthecostoftheextranumericalrobustnessoeredbytheBLASroutineovertheuseofnewFortran90intrinsicfunctions.keywords:SoftwarecomplexitymetricsFortranEuclideannormSoft-waretoolsINTRODUCTIONThreeofthemostimportantqualitiesofsoftware,asfarastheenduserisconcerned,arerobustness,reliabilityandeciency.Thoseinterestedinxingbugsandupgradingsoftwarearealsokeenthatthecodebeeasytounderstand,test,andmaintain.Detailsofthese,andotherimportantsoftwarefactorsmaybefoundinFenton[1]andWatts[2].Theabilitytoproduceclear,readablecodedependsbothontheimplemen-tationlanguageandtheprogrammer.Theprogramminglanguageneedstohavethecontrolanddatastructuresavailabletoallowthecodertogenerateacleanandsimple,yetecient,implementationofthealgorithm.Ingeneral,thefewer1facilitiesalanguageprovidesthemoredicultitisforaprogrammertogeneratesuchcode.Fortranhasevolvedfromtheverysimple‘highlevel’languageofthe1950’s,throughFortran66,therstprogramminglanguagetobestandardised[3],andFortran77[4],arelativelyminormodernisation,tothemuchlargerandmorecomplexFortran90[5].TheLevel1BasicLinearAlgebraSubroutines(BLAS)[6],originallypub-lishedinFortran66,implementedanumberofcommonvectoroperationsandweredesignedtobeusedasbuildingblocksforlinearalgebrasoftware.Rou-tineswereprovidedtodealwiththedierentnumericaldatatypesavailableinStandardFortran66(defaultprecisionforrealandcomplexanddoublepre-cisionreal).Theroutinesweredesignedtobebothnumericallyrobustandecient(manyusedloopunrolling[7]toobtainbetterperformance),althoughformaximaleciencyitwasexpectedthatspeciallytunedversionswouldbemadeavailableforparticularhardwareplatforms.FirstwedescribebrieythreesoftwaremetricsandlookathowtheywereusedtohelpidentifywhichoftheLevel1BLASwerelikelytobediculttounderstand,testandmaintain.Wethenconsiderhowrestructuringthecodeaectedthemetricstoascertainwhetherthechosenmeasuresoeranyhelpinquantifyingtheimprovementsmadetothecode.WealsoreportonhowwelltwoFortrancoderestructurersfaredontheoriginalandrewrittenFortran66routines.AFortran77versionofoneoftheroutinesispresented.WethenconsiderhowthenewfacilitiesoeredbyFortran90maybeusedtoimproveboththecodeandtheuserinterface.FinallywelookattheimpactwhichtheuniversaluseofIEEEoating-pointarithmeticmayhaveontheunderlyingmethodandthecostofnumericalrobustness.SOFTWARECOMPLEXITYMEASURESInattemptingtoassistintheproductionofhighqualitysoftware,variousmeth-odshavebeenproposedtolimitthecomplexityofindividualcodemodulesandmanymethodsofmeasuringcodecomplexityhavebeenadvocated(seeZuse[8]foranextensivebibliography).Inordertohelpinquantifyingtheeectsofanychangeswemaketothesoftware,wewillconsidertheuseofthreeofthesemetrics1.knotcount[9]whichprovidessomeindicationofcodingclarity,2.pathcount(avariantonthemetricproposedbyNejmeh[10])whichgivesanestimateoftheeortrequiredfortesting,3.cyclomaticcomplexity[11]whichalsoattemptstoestimatethetestingef-fortrequired.Inadditionwewilllookatapictorialrepresentationofthecodeintheformofacontrolgraph.Theprogramcontrolgraphisadirectedgraphconsistingofbasic2blocksofcode(nodes)connectedbydirectedarcs(edges)correspondingtotheowofcontrolbetweenthesenodes.Abasicblockofcodeisasequenceofex-ecutablestatementscontainingnodecisionsortransfersofcontrol.CyclomaticcomplexityisrelatedtothecontrolgraphandisdenedtobethecyclomaticnumberV(G)=edgesnodes+2Thismaybeshowntobeequivalenttothenumberofpredicatesusedinthecodeplusone.ItisgenerallyacceptedthatcompoundpredicatescontributemoretoprogramcomplexitythansimplepredicatesandMyers[12]suggeststheuseofacomplexityintervalwhoselowerboundisV(G)andwhoseupperboundisonemorethanthetotalnumberofconditions.WorkbyShepperd[13]andShepperd&Ince[14]hashighlightedanumberoftheoreticalproblemswiththeuseofcyclomaticcomplexityasasoftwaremetric;weconsiderthesefurtherintheConclusion.TheknotcountofWoodwardetal[9]givesagoodindicationofprogramclarity.Itisdependentbothontheimplementationlanguageandtheorderofstatementsinthecode.Aknotissaidtooccurinapieceofcodewheneverthepathsassociatedwithtwotransfersofcontrolintersect(seeFigure1fortwoexamples).Thegreaterthenumberofknotsinaprogramunitthelessintelligiblethecodeislikelytobe.do10i=1,na(i)=a(i)+b(i)if(a(i).gt.bmax)goto20continuea(n+1)=1continue1020