5.6. Heap Memory — CS2 Software Design & Data Structures

“Heap” memory, also known as “dynamic” memory, is an alternative to local stack memory. Local memory is quite automatic. Local variables are allocated ... ShowSource|   |About   «  5.5.LocalMemory   ::   Contents   ::   5.7.LinkNodes  » 5.6.HeapMemory¶ 5.6.1.HeapMemory¶ “Heap”memory,alsoknownas“dynamic”memory,isanalternativeto localstackmemory. Localmemoryisquiteautomatic. Localvariablesareallocatedautomaticallywhenafunctioniscalled, andtheyaredeallocatedautomaticallywhenthefunctionexits. Heapmemoryisdifferentineveryway. Theprogrammerexplicitlyrequeststhatspacebeallocated, usingthenewoperatorinJavaorC++. Thismemory“block”willbeofaparticularsize, ususallydeterminedautomaticallyfromthesizeoftheobjectbeing created. Thatmemoryblock(yourobject)continuestobeallocated untilsomethinghappensthatmakesitgoaway. Insomelanguages(noteably,CandC++), anobjectinheapmemoryonlygoesawaywhentheprogrammerexplicitly requeststhatitbedeallocated. Sotheprogrammerhasmuchgreatercontrolofmemory,butwithgreater responsibilitysincethememorymustnowbeactivelymanaged. Droppingallreferencestoamemorylocationwithoutdeallocatingit isasignficantsourceoferrorsinC/C++,andthisissocommonthat ithasaname:memoryleak. (Infact,manycommercialprogramsimplementedinC++havememory leaks,thatwilleventuallymakethemcrashafterbeingusedfora longtime.) Javaremovesthissourceoferrorsbyhandlingmemorydeallocation automatically,usinggarbagecollection. Thedownsideisthatgarbagecollectionisaslowprocessthathappens atunpredictabletimes. Theadvantagesofheapmemoryare: Lifetime.Becausetheprogrammernowcontrolsexactlywhen memoryisallocated,itispossibletobuildadatastructurein memory,andreturnthatdatastructuretothecaller. Thiswasneverpossiblewithlocalmemory,whichwasautomatically deallocatedwhenthefunctionexited. Size.Thesizeofallocatedmemorycanbecontrolledwithmore detail. Forexample,astringbuffercanbeallocatedatrun-timethatis exactlytherightsizetoholdaparticularstring. Withlocalmemory,thecodeismorelikelytodeclareabufferof size1000andhopeforthebest. (SeetheStringCopy()examplebelow.) Thedisadvantagesofheapmemoryare: MoreWork.Heapallocationneedstoarrangedforexplicitlyin thecode,whichisjustmorework. MoreBugs.Becauseit’snowdoneexplicitlyinthecode, onoccasiontheallocationwillbedoneincorrectlyleadingto memorybugs. Localmemoryisconstrained,butatleastit’sneverwrong. Nonetheless,therearemanyproblemsthatcanonlybesolvedwithheap memory,sothat’sthewayithastobe. ThefollowingaresomeimportantpointsaboutGarbageCollection. GarbagecollectionisamechanismthatisinvokedbytheJava VirtualMachinetogetrideoftheunusedheapmemoryobjects. Itremoveseveryobjectthatisnotbeingusedanymorebythe runningJavaprogram. Theresultofthisprocessisfreeinguptheunusedmemorysoother newobjectscanusethatpieceofmemory. InotherprogramminglanguageslikeCandC++,itisthe responsibilityoftheprogrammertotakecareoffreeingupthe memoryfromunusedobjectsandarrays. Doingsoconsumesprogrammer’stimeandincreasescodecomplexity. Ontheotherhand,garbagecollectionmakesprogrammingeasier bytakingcareofthememorymanagementfortheprogrammer. Beforeremovinganobjectfrommemory,garbagecollectioninvokesthe finalize()methodofthatobjectandgivesanopportunitytoperform anysortofcleanuprequired. Iftheprogrammerdoesnotoverridethismethod, thedefaultfinializermethodwillbeinvoked (themethoddefinedintheObjectclass). TheJavaVirtualMachineinvokesgarbagecollectionbasedonthe sizeofthedynamicallyallocatedmemoryfromtheheap. Garbagecollectionisslow,andhardtopredict. Thiscanbeaproblemforprogramsthathavereal-timeperformance constraints. Thefollowingaresomecasesthatmakeanobjectsubjecttoberemoved fromheapmemorybygarbagecollection: Whentheprogrammerchangesallreferencestoanobjecttosomething else. Iftheobjectisdefinedinsideablockofcode,andallreferences tothatobjectarelocal. Whenexcecutionofthatblockiscomplete,thelocalvariablesare destroyedautomatically,leavingtheobjectinheapmemorywithout anyreferences.(Sothisisreallyaspecialcaseofrule(1).) Hereisanexample Java(Generic)Javavoidtest(booleanfound) { if(found) { //employee1isavariablelocaltothisifstatement //buttheEmployeeobjectisinheapmemory. Employeeemployee1=newEmployee("John",1000); //Wecandothingsherewithemployee1,anditsassociatedobject Printout(employee1.name()); } //Atthispoint,theonlyreferencetothecreatedobjectisoutofscope //sinceemployee1waslocaltotheifstatementblock. //SotheEmployeeobjectwillbeeligibleforgarbagecollection. } voidtest(booleanfound) { if(found) { //employee1isavariablelocaltothisifstatement //buttheEmployeeobjectisinheapmemory. Employeeemployee1=newEmployee("John",1000); //Wecandothingsherewithemployee1,anditsassociatedobject Printout(employee1.name()); } //Atthispoint,theonlyreferencetothecreatedobjectisoutofscope //sinceemployee1waslocaltotheifstatementblock. //SotheEmployeeobjectwillbeeligibleforgarbagecollection. } AssumeanobjectAcontainsareferencetoanotherobject B,andAcontainstheonlysuchreferencetoB. ObjectBwillbeeligibleforgarbagecollectionifAis alsoeligibleforgarbagecollection. Hereisanexample. Java(Generic)Java//Dateclasstorepresentdates classDate{ intday; intmonth; intyear; //Dateconstructor publicDate(intd,intm,inty) { day=d;month=m;year=y; } } //AnEmployeeclassthatincludesaDate classEmployee{ Stringname; DatedateOfBirth; //Employeeconstructortoinitializebothnameanddate publicEmployee(Stringname,intd,intm,inty) { this.name=name; dateOfBirth=newDate(d,m,y); } } //Nowlet'stestthiscode classTest{ publicstaticvoidmain(){ EmployeeempPtr=newEmployee("Sam",3,9,1983); //NowempPtrreferencesanobjectthatcontainsareferencetoaDateobject empPtr=null;//NowtheEmployeeobjectiseligibleforgarbagecollection. //SoitsDateobjectwillalsobeeligibleforgarbagecollection //becausenothingelsepointstoit. } } //Dateclasstorepresentdates classDate{ intday; intmonth; intyear; //Dateconstructor publicDate(intd,intm,inty) { day=d;month=m;year=y; } } //AnEmployeeclassthatincludesaDate classEmployee{ Stringname; DatedateOfBirth; //Employeeconstructortoinitializebothnameanddate publicEmployee(Stringname,intd,intm,inty) { this.name=name; dateOfBirth=newDate(d,m,y); } } //Nowlet'stestthiscode classTest{ publicstaticvoidmain(){ EmployeeempPtr=newEmployee("Sam",3,9,1983); //NowempPtrreferencesanobjectthatcontainsareferencetoaDateobject empPtr=null;//NowtheEmployeeobjectiseligibleforgarbagecollection. //SoitsDateobjectwillalsobeeligibleforgarbagecollection //becausenothingelsepointstoit. } } Settings Saving... ServerError Resubmit Beforeseeingtheexactdetails,let’slookataroughexampleof allocationanddeallocationintheheap. 5.6.1.1.Allocation¶ Theheapisalargeareaofmemoryavailableforusebytheprogram. Theprogramcanrequestareas,or“blocks”,ofmemoryforitsuse withintheheap. Inordertoallocateablockofsomesize,theprogrammakesan explicitrequestbycallingtheheapallocationoperation. InJavaorC++,thisisthenewoperator. Theallocationfunctionreservesablockofmemoryoftherequested sizeintheheap(usually,thesizeoftheobjectthatyouwant)and returnsarefernecetoit. Supposeaprogrammakesthreeallocationrequeststoallocatememory toholdthreeseparateGIFimagesintheheap,eachofwhichtakes 1024bytesofmemory. Afterthethreeallocationrequests,memorymightlooklike. Eachallocationrequestreservesacontiguousareaoftherequested sizeintheheapandreturnsareferencetothatnewblocktothe program. Sinceeachblockisalwaysreferredtobyareference,theblock alwaysplaystheroleofa“pointee”(Section1)andtheprogram alwaysmanipulatesitsheapblocksthroughreferences. Theheapblockreferencesaresometimesknownas“baseaddress” pointerssincebyconventiontheypointtothebase(lowestaddress byte)oftheblock. Inthisexample,thethreeblockshavebeenallocatedcontiguously startingatthebottomoftheheap,andeachblockis1024bytesin sizeasrequested. Inreality,theheapmanagercanallocatetheblockswhereveritwants intheheapsolongastheblocksdonotoverlapandtheyareatleast therequestedsize. Atanyparticularmoment,someareasintheheaphavebeenallocated totheprogram,andsoare“inuse”. Otherareashaveyettobecommittedandsoare“free”andare availabletosatisfyallocationrequests. Theheapmanagerhasitsown,privatedatastructurestorecordwhat areasoftheheaparecommittedtowhatpurposeatanymoment. Theheapmanagersatisfieseachallocationrequestfromthepoolof freememoryandupdatesitsprivatedatastructurestorecordwhich areasoftheheapareinuse. 5.6.1.2.Deallocation¶ Whentheprogramisfinishedusingablockofmemory,insome languagestheblockmustbeexplicitlydeallocated. Insuchcases,theblockwillbemarkedunused. InJava,typicallyspaceis“madeavailable”bynothavingany referencestoit. ThisallowsJavagarbagecollectiontoknowthatthisareamustbe cleaned. Garbagecollectionwillimplicitlyfreeuptheunusedmemoryblocksin theheap. Theheapmanagerupdatesitsprivatedatastructurestoshowthatthe areaofmemoryoccupiedbytheblockisfreeagainandsomaybe re-usedtosatisfyfutureallocationrequests. Here’swhattheheapwouldlooklikeifthegarbagecollection deallocatesthesecondofthethreeblocks. Afterdeallocation,thereferencecontinuestopointtothenow deallocatedblock. Theprogramcannolongerreachthedeallocatedpointee. Inalanguage(likeC++)withexplicitmemorydeallocationandno garbagecollection,theprogrammermustmakesurethatheorshedoes nottrytofollowtheoldreferencetothedeallocatedblock. Thisiswhythepointerisdrawningray—thepointeristhere, butitmustnotbeused. Ofcourse,inJavathecodewillhavesetthepointertonullor topointtosomewhereelse,soastotellthegarbagecollectionthat thisobjectisnowunused. ThisisabigpartofwhyJavareferencesaresafertousethanC++ pointers. 5.6.1.3.ProgrammingtheHeap¶ Programmingtheheaplooksprettymuchthesameinmostlanguages. Thebasicfeaturesare: Theheapisanareaofmemoryavailabletoallocateareas(“blocks”) ofmemoryfortheprogram. Thereissome“heapmanager”librarycodewhichmanagestheheapfor theprogram. Theprogrammermakesrequeststotheheapmanager,whichinturn managestheinternalsoftheheap. Theheapmanagerusesitsownprivatedatastructurestokeeptrack ofwhichblocksintheheapare“free”(availableforuse)andwhich blocksarecurrentlyinusebytheprogramandhowlargethose blocksare. Initially,alloftheheapisfree. Theheapmaybeofafixedsize(theusualconceptualization),orit mayappeartobeofafixedbutextremelylargesizebackedby virtualmemory. Ineithercase,itispossiblefortheheaptoget “full”ifallofitsmemoryhasbeenallocatedandsoitcannot satisfyanallocationrequest. Theallocationfunctionwillcommunicatethisrun-timeconditionin somewaytotheprogram—usuallybyraisinganOutOfMemoryError run-timeexception. Theallocationfunctionrequestsablockintheheapofaparticular size. Theheapmanagerselectsanareaofmemorytousetosatisfy therequest,marksthatareaas“inuse”initsprivatedata structures,andreturnsareferencetotheheapblock. Thecallerisnowfreetousethatmemorybyfollowingthe reference. Theblockisguaranteedtobereservedforthesoleuseofthe caller—theheapwillnothandoutthatsameareaofmemoryto someothercaller. Theblockdoesnotmovearoundinsidetheheap—its locationandsizearefixedonceitisallocated. TheJavavirtualmachineinvokesthegarbagecollectiontoremove anyunusedblockofmemory,freeitsspaceandreturnthisspaceof memorytotheheapfreeareaforlaterre-use. 5.6.1.4.AHeapExample¶ Settings Saving... ServerError Resubmit 5.6.1.5.Arrays¶ InJava,arraymemoryisallocatedintheheap. Thesizeofthearraymemoryblockisthesizeofeachelement multipliedbythenumberofelements. Sothefollowingcodeheapallocatesanarrayof100Fraction objectsintheheap,setsthemallto22/7,anddeallocatestheheap array. Java(Generic)Java//Fractionclass classFraction{ intnumerator,denominator; //Fractionconstructor publicFraction(intnum,intden){ numerator=num; denominator=den; } } //Testclass classTestHeapArray{ staticvoidmain(){ Fraction[]fracts; inti; intlength=100; //allocatethearray fracts=newFraction[length]; //useitlikeanarray--inthiscasesetthemallto22/7 for(i=0;i