Under consideration for publication in Theory and

arXiv:cs/0601003v1[cs.PL]2Jan2006UnderconsiderationforpublicationinTheoryandPracticeofLogicProgramming1IncrementalCopyingGarbageCollectionforWAM-basedPrologsystemsRUBENVANDEGINSTE,BARTDEMOENDept.ofComputerScience,K.U.Leuven,Belgium(e-mail:{ruben,bmd}@cs.kuleuven.ac.be)submitted1Februari2005;revised22September2005;accepted22December2005AbstractThedesignandimplementationofanincrementalcopyingheapgarbagecollectorforWAM-basedPrologsystemsispresented.Itsheaplayoutconsistsofanumberofequal-sizedblocks.OtherchangestothestandardWAMallowtheseblockstobegarbagecol-lectedindependently.Theindependentcollectionofheapblocksformsthebasisofanincrementalcollectingalgorithmwhichemployscopyingwithoutmarking(contrarytothemorefrequentlyusedmark©ormark&slidealgorithmsinthecontextofProlog).Comparedtostandardsemi-spacecopyingcollectors,thisapproachtoheapgarbagecol-lectionlowersinmanycasesthememoryusageandreducespausetimes.Thealgorithmalsoallowsforawidevarietyofgarbagecollectionpoliciesincludinggenerationalones.ThealgorithmisimplementedandevaluatedinthecontextofhProlog.KEYWORDS:memorymanagementoflogicprogramminglanguages,incrementalcopyinggarbagecollection,WAMbasedPrologimplementation.1IntroductionWewillassumesomefamiliaritywithProloganditsimplementation.TheWAM(War83;AK90)(WarrenAbstractMachine)isawell-knownvirtualmachinewithaspecialisedinstructionsetfortheexecutionofPrologcode.TheWAMhasproventobeagoodbasisforefficientPrologimplementations,andmanysystemsarebasedonit.Wealsoassumebasicknowledgeaboutgarbagecollectioningeneral;agoodoverviewisgivenin(Wil92;JL96).GarbagecollectionforPrologisdiscussedin(ACHS88;BRU92;BL94;DNV02).TheWAMdefinesthreememoryareas:amergedstackforenvironmentsandchoicepoints,atrail,andaheap.Differentmemorymanagementtechniquesareavailabletorecoverspaceintheseareas.Inthisworkwefocusonmemorymanage-mentoftheheap.ThebasicWAMalreadyprovidesamechanismtorecoverspaceallocatedontheheap.Eachtimebacktrackingoccurs,alldataallocatedsincethecreationofthemostrecentchoicepointcanbedeallocated.Ifwedefineaheapsegmentasthespaceontheheap,delimitedbytheheappointersintwoconsec-utivechoicepoints,thenuponbacktracking,theWAMcanrecoverallspaceon2Vandeginsteetal.theheapallocatedforthemostrecentheapsegment.Thistechniqueforrecoveringheapspaceiscalledinstantreclaiming.Inpracticehowever,instantreclaimingaloneisnotsufficient.Moreover,manyPrologprogramsaredeterministicorthebacktrackingismainlyshallowandinthesecasesinstantreclaimingisnoteffective.ThereforePrologsystemsneedgarbagecol-lectionfortheheap.Earlyon,manysystemsusedmark&slidegarbagecollection(ACHS88)becauseofthefollowingproperties.Mark&slidegarbagecollectionpre-servesthecellorderandasaconsequencealsopreservesheapsegments(whichisimportantforinstantreclaiming).Anotherimportantissueismemoryusage:be-sidesmarkandchainbits(2extrabitsperheapcell),noextraspaceisneededformark&slidebasedgarbagecollection.Recentlycopyinggarbagecollectionhasbecomemorepopular.Contrarytomark&slidegarbagecollection,copyinggarbagecollectiondoesnotpreservethecellorder,northeheapsegmentsandconsequentlylosestheabilitytodoinstantreclaiming(see(DET96)foranexception).Acopyinggarbagecollector,however,hasbettercomplexitythanamark&slidegarbagecollector:mark&slidecollectionisO(n)withnthetotalnumberofheapcells,whilecopyingcollectionisO(m)withmthenumberofsurvivingheapcells.SincethefractionofheapcellsthatsurviveacollectionistypicallysmallinPrologsystems,copyingcollectorsinmostcasesoutperformmark&slidecollectors.Thiscanbeobservedinthebenchmarksfrom(BL94),thatcomparetheperformanceofmark&slideandcopyinggarbagecollectorsinthecontextofaPrologsystem.1f/1axySLL2543(a)Beforecopying1axySLL2543f/1(b)Aftercopying1&21axySLL2543f/1(c)Aftercopying3,4&5Fig.1.DoubleandmultiplecopyingStill,thereisanissuewithcopyingcollectorsinaPrologimplementationbasedontheWAM:undercertainconditions,someheapcellsarecopiedtwiceorevenmoreduringthecollectionandthiscancausethetospacetooverflow.Therefore,thesecollectorsareconsideredunsafeinthecontextofProlog.Adetaileddiscussionofthisproblemcanbefoundin(DNV02).WeillustratethisherewithFigure1.Thefiguresshowfromlefttoright:therootset,thefromspaceandthetospace.Dashedarrowsindicateforwardingpointers.TheSstandsforSTRUCTandtheLforLIST.Inasemi-spacecopyingalgorithm,heapcellsreferencedfromtherootsetarecopiedfromthefromspacetothetospaceandaforwardingpointerisleftinthefromspace.Theorderinwhichcellsareforwardedisapriorinotknown.IntheIncrementalCopyingGarbageCollectionforWAM-basedPrologsystems3figure,weindicatedtheorderinwhichtherootcellsarevisitedwiththenumbersontheleft.Thefiguresshowthatiftheargument(a)ofafunctor(f/1)isreferencedindependentlyandcopiedtothetospace(seeFigure1(b))beforethestructureasawhole(f(a)),anextrareference(indirectiontoa)iscreatedinthetospace(seeFigure1(c));thisiscalleddoublecopying.Doublecopyingalsohappenswhenoneofthecellsofalistpair(y)iscopiedbeforethelistpair([x|y])iscopiedasawhole.But,ascanbeseeninFigure1(c),itcanbeevenworse:whenseveralLISTcellspointtothesamelistpair,extracopiesofthelistcells(xandy)arecreatedforeachaddit