%PDF-1.2 7 0 obj > endobj 10 0 obj > endobj 13 0 obj > endobj 16 0 obj > endobj 19 0 obj > endobj 22 0 obj > endobj 25 0 obj > endobj 28 0 obj > endobj 31 0 obj > endobj 34 0 obj > endobj 36 0 obj > stream 0.00 g 0.00 G BT/F1 17.93 Tf 110.21 -12.81 TD[(Quantifying)-278(the)-278(P)29(erf)20(ormance)]TJ -115.11 -19.92 TD[(of)-277(Garba)9(g)-9(e)-278(Collection)-278(vs.)-389(Explicit)-278(Mem)-1(or)-10(y)-278(Mana)9(g)-9(ement)]TJ/F2 11.95 Tf 80.54 -47.61 TD[(Matthe)19(w)-277(Her)-40(tz)]TJ/F3 8.96 Tf 80.61 8.96 TD[(\244)]TJ/F2 8.96 Tf -98.11 -19.42 TD[(Computer)-278(Science)-278(Depar)-40(tment)]TJ 28.08 -10.46 TD[(Canisius)-278(College)]TJ -2.43 -10.46 TD[(Buff)30(alo)40(,)-277(NY)-278(14208)]TJ/F2 10.96 Tf -34.05 -14.44 TD[(matthe)19(w)60(.her)-39(tz@canisius)14(.edu)]TJ/F2 11.95 Tf 251.74 45.82 TD[(Emer)-29(y)-278(D)69(.)-277(B)-1(erger)]TJ/F2 8.96 Tf -9.55 -10.46 TD[(Dept.)-278(of)-278(Computer)-278(Science)]TJ -19.8 -10.46 TD[(Univ)25(ersity)-277(of)-278(Massachusetts)-278(Amherst)]TJ 34 -10.46 TD[(Amherst,)-278(MA)-278(01003)]TJ/F2 10.96 Tf -14.96 -14.44 TD[(emer)-29(y@cs)14(.umass)15(.edu)]TJ/F7 8.96 Tf -309.37 -26.54 TD[(ABSTRA)54(CT)]TJ/F6 8.96 Tf 0 -12.48 TD[(Garbage)-248(collection)-248(yields)-248(numerous)-248(softw)9(are)-247(engineering)-248(bene\002ts,)]TJ 0 -10.45 TD[(b)19(ut)-356(its)-357(quantitati)24(v)15(e)-356(impact)-358(on)-357(performance)-357(remains)-357(elusi)24(v)15(e.)-631(One)]TJ 0 -10.46 TD[(can)-250(compare)-250(the)-250(cost)-249(of)]TJ/F8 8.96 Tf 87.37 0 TD[(conservative)]TJ/F6 8.96 Tf 47.54 0 TD[(g)4(arbage)-249(collection)-249(to)-250(e)14(xplicit)]TJ -134.91 -10.46 TD[(memory)-307(management)-307(in)-307(C/C++)-307(programs)-307(by)-307(linking)-307(in)-307(an)-307(appro-)]TJ 0 -10.46 TD[(priate)-284(collector)54(.)-413(This)-285(kind)-284(of)-285(direct)-285(comparison)-284(is)-285(not)-284(possible)-285(for)]TJ 0 -10.45 TD[(languages)-206(designed)-207(for)-207(g)4(arbage)-205(collection)-207(\(e.g.,)-215(Ja)19(v)25(a\),)-214(because)-207(pro-)]TJ 0 -10.46 TD[(grams)-335(in)-335(these)-336(languages)-335(naturally)-335(do)-336(not)-335(contain)-335(calls)-336(to)]TJ/F9 8.96 Tf 215.29 0 TD[(free)]TJ/F6 8.96 Tf 21.51 0 TD[(.)]TJ -236.8 -10.46 TD[(Thus,)-370(the)-346(actual)-346(g)4(ap)-345(between)-346(the)-346(time)-347(and)-346(space)-346(performance)-346(of)]TJ 0 -10.46 TD[(e)14(xplicit)-227(memory)-228(management)-228(and)]TJ/F8 8.96 Tf 123.56 0 TD[(pr)36(ecise)]TJ/F6 8.96 Tf 25.56 0 TD[(,)-232(cop)9(ying)-227(g)4(arbage)-227(collec-)]TJ -149.12 -10.46 TD[(tion)-250(remains)-250(unkno)24(wn.)]TJ 8.97 -10.45 TD[(W)80(e)-189(introduce)-190(a)-190(no)14(v)15(el)-189(e)14(xperimental)-189(methodology)-190(that)-190(lets)-190(us)-190(quan-)]TJ -8.97 -10.46 TD[(tify)-338(the)-339(performance)-339(of)-338(precise)-339(g)4(arbage)-338(collection)-338(v)14(ersus)-338(e)14(xplicit)]TJ 0 -10.46 TD[(memory)-232(management.)-304(Our)-231(system)-232(allo)24(ws)-231(us)-232(to)-231(treat)-232(unaltered)-232(Ja)19(v)25(a)]TJ 0 -10.46 TD[(programs)-294(as)-294(if)-294(the)14(y)-292(used)-294(e)14(xplicit)-293(memory)-294(management)-294(by)-294(relying)]TJ 0 -10.46 TD[(on)-390(oracles)-391(to)-390(insert)-391(calls)-390(to)]TJ/F9 8.96 Tf 105.65 0 TD[(free)]TJ/F6 8.96 Tf 21.51 0 TD[(.)-731(These)-391(oracles)-390(are)-391(generated)]TJ -127.16 -10.45 TD[(from)-348(pro\002le)-347(information)-348(g)4(athered)-347(in)-347(earlier)-348(application)-348(runs.)-603(By)]TJ 0 -10.46 TD[(e)14(x)15(ecuting)-292(inside)-293(an)-293(architecturally-detailed)-294(simulator)39(,)-303(this)-293(\223oracu-)]TJ 0 -10.46 TD[(lar\224)-226(memory)-225(manager)-226(eliminates)-226(the)-226(ef)24(fects)-225(of)-225(consulting)-226(an)-226(oracle)]TJ 0 -10.46 TD[(while)-249(measuring)-249(the)-249(costs)-249(of)-249(calling)]TJ/F9 8.96 Tf 131.4 0 TD[(malloc)]TJ/F6 8.96 Tf 34.51 0 TD[(and)]TJ/F9 8.96 Tf 15.17 0 TD[(free)]TJ/F6 8.96 Tf 21.52 0 TD[(.)-309(W)79(e)-248(e)24(v)25(al-)]TJ -202.6 -10.46 TD[(uate)-221(tw)9(o)-221(dif)24(ferent)-220(oracles:)-296(a)-221(li)24(v)15(eness-based)-220(oracle)-222(that)-221(aggressi)24(v)15(ely)]TJ 0 -10.45 TD[(frees)-365(objects)-364(i)-1(mmediately)-364(after)-365(their)-365(last)-365(use,)-393(and)-365(a)-365(reachability-)]TJ 0 -10.46 TD[(based)-231(oracle)-231(that)-231(conserv)24(ati)25(v)15(ely)-230(frees)-231(objects)-231(just)-231(after)-231(the)14(y)-230(are)-231(last)]TJ 0 -10.46 TD[(reachable.)-508(These)-316(oracles)-316(span)-316(the)-316(range)-316(of)-316(possible)-316(placement)-316(of)]TJ 0 -10.46 TD[(e)14(xplicit)-249(deallocation)-250(calls.)]TJ 8.97 -10.45 TD[(W)80(e)-284(compare)-284(e)14(xplicit)-284(memory)-284(management)-285(to)-284(both)-285(cop)9(ying)-283(and)]TJ -8.97 -10.46 TD[(non-cop)9(ying)-314(g)4(arbage)-315(collectors)-315(across)-315(a)-316(range)-315(of)-315(benchmarks)-316(us-)]TJ 0 -10.46 TD[(ing)-210(the)-209(oracular)-210(memory)-210(manager)39(,)-217(and)-209(present)-210(real)-210(\(non-simulated\))]TJ 0 -10.46 TD[(runs)-259(that)-259(lend)-259(further)-259(v)24(alidity)-257(to)-259(our)-259(results.)-337(These)-259(results)-259(quantify)]TJ 0 -10.46 TD[(the)-371(time-space)-371(tradeof)24(f)-370(of)-371(g)4(arbage)-370(collection:)-552(with)-371(\002)24(v)15(e)-370(times)-371(as)]TJ 0 -10.45 TD[(much)-349(memory)64(,)-373(an)-350(Appel-style)-349(generational)-350(collector)-349(with)-349(a)-350(non-)]TJ 0 -10.46 TD[(cop)9(ying)-430(mature)-431(space)-431(matches)-431(the)-432(performance)-431(of)-431(reachability-)]TJ 0 -10.46 TD[(based)-190(e)14(xplicit)-189(memory)-190(management.)-290(W)39(ith)-189(only)-190(three)-190(times)-190(as)-190(much)]TJ 0 -10.46 TD[(memory)64(,)-411(the)-380(collector)-380(runs)-380(on)-379(a)19(v)15(erage)-379(17%)-380(slo)24(wer)-379(than)-380(e)14(xplicit)]TJ 0 -10.46 TD[(memory)-223(management.)-301(Ho)24(we)25(v)15(er)40(,)-228(with)-223(only)-223(twice)-223(as)-224(much)-223(memory)64(,)]TJ 0 -10.45 TD[(g)4(arbage)-381(collection)-383(de)14(grades)-381(performance)-382(by)-382(nearly)-383(70%.)-707(When)]TJ ET 0.4 w -18.2 -531.13 m 77.42 -531.13 l S BT/F3 8.96 Tf -18.2 -538.07 TD[(\244)]TJ/F6 7.97 Tf 4.49 -3.99 TD[(W)80(ork)-249(performed)-250(at)-250(the)-250(Uni)24(v)15(ersity)-249(of)-250(Massachusetts)-250(Amherst.)]TJ/F6 7.97 Tf -4.49 -42.52 TD[(Permission)-371(to)-370(mak)9(e)-370(digital)-371(or)-371(hard)-370(copies)-371(of)-371(all)-371(or)-370(part)-371(of)-371(this)-370(w)9(ork)-370(for)]TJ 0 -8.96 TD[(personal)-330(or)-330(classroom)-331(use)-330(is)-330(granted)-330(without)-330(fee)-331(pro)14(vided)-329(that)-330(copies)-330(are)]TJ 0 -8.96 TD[(not)-277(made)-277(or)-278(distrib)19(uted)-276(for)-277(pro\002t)-278(or)-277(commercial)-277(adv)24(antage)-277(and)-277(that)-277(copies)]TJ 0 -8.97 TD[(bear)-244(this)-245(notice)-244(and)-245(the)-244(full)-245(citation)-244(on)-245(the)-244(\002rst)-245(page.)-359(T)79(o)-243(cop)9(y)-244(otherwise,)-245(to)]TJ 0 -8.96 TD[(republish,)-233(to)-230(post)-229(on)-229(serv)14(ers)-229(or)-229(to)-229(redistrib)19(ute)-229(to)-229(lists,)-234(requires)-229(prior)-229(speci\002c)]TJ 0 -8.96 TD[(permission)-250(and/or)-250(a)-250(fee.)]TJ/F8 7.97 Tf 0 -8.97 TD[(OOPSLA)36('05,)]TJ/F6 7.97 Tf 43.97 0 TD[(October)-250(16\22620,)-250(2005,)-250(San)-250(Die)14(go,)-249(California,)-250(USA.)]TJ -43.97 -8.96 TD[(Cop)9(yright)-249(2005)-250(A)39(CM)-249(1\25559593\255031\2550/05/0010)-250(..)]TJ/F6 8.96 Tf 154.09 0 TD[($)]TJ/F6 7.97 Tf 4.49 0 TD[(5.00)]TJ/F6 8.96 Tf 104.36 494.62 TD[(ph)4(ysical)-226(memory)-226(is)-227(scarce,)-231(paging)-227(causes)-226(g)4(arbage)-226(collection)-226(to)-227(run)]TJ 0 -10.46 TD[(an)-250(order)-250(of)-250(magnitude)-250(slo)24(wer)-249(than)-250(e)14(xplicit)-249(memory)-250(management.)]TJ/F7 8.96 Tf 0 -16.88 TD[(Categories)-250(and)-250(Subject)-250(Descriptors)]TJ/F6 8.96 Tf 0 -12.48 TD[(D.3.3)-190([)]TJ/F7 8.96 Tf 24.61 0 TD[(Pr)18(ogramming)-190(Languages)]TJ/F6 8.96 Tf 96.66 0 TD[(]:)-279(Dynamic)-190(storage)-190(management;)]TJ -121.27 -10.46 TD[(D.3.4)-250([)]TJ/F7 8.96 Tf 25.15 0 TD[(Pr)18(ocessors)]TJ/F6 8.96 Tf 40.66 0 TD[(]:)-309(Memory)-250(management)-250(\(g)4(arbage)-249(collection\))]TJ/F7 8.96 Tf -65.81 -16.88 TD[(General)-250(T)91(erms)]TJ/F6 8.96 Tf 0 -12.48 TD[(Experimentation,)-250(Measurement,)-250(Performance)]TJ/F7 8.96 Tf 0 -16.88 TD[(K)24(eyw)10(ords)]TJ/F6 8.96 Tf 0 -12.48 TD[(oracular)-331(memory)-331(management,)-351(g)4(arbage)-330(collection,)-351(e)14(xplicit)-330(mem-)]TJ 0 -10.46 TD[(ory)-190(management,)-202(performance)-190(analysis,)-202(time-space)-190(tradeof)24(f,)-201(through-)]TJ 0 -10.45 TD[(put,)-250(paging)]TJ/F7 8.96 Tf 0 -16.89 TD[(1.)-1000(Intr)17(oduction)]TJ/F6 8.96 Tf 0 -10.98 TD[(Garbage)-356(collection,)-382(or)-355(automatic)-356(memory)-356(management,)-382(pro)14(vides)]TJ 0 -10.46 TD[(signi\002cant)-190(softw)9(are)-189(engineering)-190(bene\002ts)-190(o)14(v)15(er)-189(e)14(xplicit)-189(memory)-190(man-)]TJ 0 -10.46 TD[(agement.)-304(F)14(or)-233(e)14(xample,)-236(g)4(arbage)-232(collection)-234(frees)-233(programmers)-234(from)]TJ 0 -10.45 TD[(the)-190(b)19(urden)-189(of)-190(memory)-190(management,)-202(eliminates)-190(most)-190(memory)-190(leaks,)]TJ 0 -10.46 TD[(and)-190(impro)14(v)15(es)-189(modularity)64(,)-201(while)-190(pre)24(v)15(enting)-189(accidental)-190(memory)-190(o)14(v)15(er)20(-)]TJ 0 -10.46 TD[(writes)-227(\(\223dangling)-226(pointers\224\))-227([50,)-231(59].)-302(Because)-227(of)-226(these)-227(adv)24(antages,)]TJ 0 -10.46 TD[(g)4(arbage)-289(collection)-291(has)-290(been)-290(incorporated)-290(as)-291(a)-290(feature)-290(of)-291(a)-290(number)]TJ 0 -10.45 TD[(of)-250(mainstream)-250(programming)-250(languages.)]TJ 8.97 -10.46 TD[(Garbage)-320(collection)-320(can)-320(impro)14(v)15(e)-320(programmer)-320(producti)24(vity)-319([48],)]TJ -8.97 -10.46 TD[(b)19(ut)-286(its)-286(impact)-287(on)-286(performance)-287(is)-286(dif)24(\002cult)-286(to)-287(quantify)64(.)-418(Pre)24(vious)-286(re-)]TJ 0 -10.46 TD[(searchers)-353(ha)19(v)15(e)-351(measured)-353(the)-353(runtime)-353(performance)-352(and)-353(space)-353(im-)]TJ 0 -10.46 TD[(pact)-225(of)]TJ/F8 8.96 Tf 26.44 0 TD[(conservative)]TJ/F6 8.96 Tf 45.3 0 TD[(,)-230(non-cop)9(ying)-224(g)4(arbage)-224(collection)-225(in)-225(C)-225(and)-226(C++)]TJ -71.74 -10.45 TD[(programs)-200([19,)-211(62].)-293(F)14(or)-199(these)-201(programs,)-210(comparing)-200(the)-201(performance)]TJ 0 -10.46 TD[(of)-219(e)14(xplicit)-219(memory)-219(management)-219(to)-219(conserv)24(ati)25(v)15(e)-219(g)4(arbage)-218(collection)]TJ 0 -10.46 TD[(is)-332(a)-331(matter)-332(of)-332(linking)-331(in)-332(a)-332(library)-332(lik)9(e)-330(the)-332(Boehm-Demers-W)79(eiser)]TJ 0 -10.46 TD[(collector)-247([14].)-309(Unfortunately)64(,)-246(measuring)-247(the)-246(performance)-247(trade-of)24(f)]TJ 0 -10.46 TD[(in)-306(languages)-305(d)-1(esigned)-305(for)-306(g)4(arbage)-305(collection)-306(is)-305(not)-306(so)-306(straightfor)19(-)]TJ 0 -10.45 TD[(w)9(ard.)-392(Because)-277(programs)-278(written)-278(in)-277(these)-278(languages)-278(do)-277(not)-278(e)14(xplic-)]TJ 0 -10.46 TD[(itly)-322(deallocate)-322(objects,)-340(one)-322(cannot)-323(simply)-322(replace)-322(g)4(arbage)-321(collec-)]TJ 0 -10.46 TD[(tion)-251(with)-251(an)-251(e)13(xplicit)-250(memory)-251(manager)54(.)-312(Extrapolating)-252(the)-251(results)-251(of)]TJ 0 -10.46 TD[(studies)-284(with)-283(conserv)24(ati)25(v)15(e)-283(collectors)-284(is)-284(impossible)-283(because)-284(precise,)]TJ 0 -10.45 TD[(relocating)-355(g)4(arbage)-354(collectors)-354(\(suitable)-355(only)-355(for)-355(g)4(arbage-collected)]TJ 0 -10.46 TD[(languages\))-190(consistently)-190(outperform)-190(conserv)24(ati)25(v)15(e,)-201(non-relocating)-190(g)4(ar)20(-)]TJ 0 -10.46 TD[(bage)-250(collectors)-250([10,)-250(12].)]TJ 8.97 -10.46 TD[(It)-286(is)-287(possible)-286(to)-287(measure)-287(the)-286(costs)-287(of)-287(g)4(arbage)-286(collection)-286(acti)24(vity)]TJ -8.97 -10.46 TD[(\(e.g.,)-371(tracing)-347(and)-346(cop)9(ying\))-346([10,)-371(20,)-371(30,)-371(36,)-371(56])-347(b)19(ut)-345(it)-347(is)-347(impossi-)]TJ 0 -10.45 TD[(ble)-258(to)-258(subtract)-258(g)4(arbage)-257(collection')54(s)-258(ef)24(fect)-257(on)-258(mutator)-258(performance.)]TJ 0 -10.46 TD[(Garbage)-253(collection)-253(alters)-253(application)-253(beha)19(vior)-252(both)-253(by)-253(visiting)-253(and)]TJ 0 -10.46 TD[(reor)17(g)5(anizing)-378(memory)64(.)-698(It)-379(also)-379(de)14(grades)-379(locality)64(,)-411(especially)-379(when)]TJ 0 -10.46 TD[(ph)4(ysical)-321(memory)-321(is)-322(scarce)-322([61].)-525(Subtracting)-322(the)-321(costs)-322(of)-322(g)4(arbage)]TJ 0 -10.46 TD[(collection)-291(also)-290(ignores)-291(the)-290(impro)14(v)15(ed)-290(locality)-291(that)-290(e)14(xplicit)-290(memory)]TJ 0 -10.45 TD[(managers)-362(can)-363(pro)14(vide)-361(by)-362(immediately)-362(rec)14(ycling)-362(just-freed)-362(mem-)]TJ 0 -10.46 TD[(ory)-369([53,)-400(55,)-399(57,)-400(58].)-668(F)14(or)-369(all)-369(these)-370(reasons,)-399(the)-370(costs)-369(of)-370(precise,)]TJ ET endstream endobj 38 0 obj > endobj 6 0 obj > endobj 41 0 obj > >> stream xœ¬½Kr­=®Ø?£PÛ ÅÇ79·í‚¢ªl‡NÃn¤§o®µ {K¾™×áȈ)n~|à øïÏgÎkäôñàwãëïŸç³¯•Óúøùÿãÿÿ“>þ럔Çú¬õ#ù9[ûø=å©Ÿ5͏TÚøó£äµG¬TKÿL9Ú_RK{h?#ÚÊŸ+Ÿ¬íßÀ/^{¼Ýúç|êøøGŒ(é3ל?üí³ÕÏ*¼½ç´uÆ߇Ï`mÿÆן÷ž÷³øÇŸÿï?ü)ŸùY¹}üÏ}\ÿmèóäµfi¿ÿçþþûn¯µêÐ5¤ýǧ¿’”烅ã#㙧ǕÛÀÏÏÆÓì³i§sF›çÝ>s?#Ú*Ÿ£Ÿ ¬íŸày¿ôx{ï|?oͱOKsè8ÍÞg¬ÂÛ›§ß,5JŠ3õö¹Ùá÷f¿ÿq±8¯ “@õÒ7nâZ÷y䊥yO/{äüøFÏÐWæç*8åý§Úø›gv­¾ ½ûçêI Ð>ÓºGäÏ\â+©ÔõÙ¸ @ Qû' ¥§ÏúdŒ¨Ÿmrs4´ËçþAׄüAúì{àØ´m9êƒ3K£^ÿ=÷*D¬gîuŒò¿žM—Zê¾dü}í_h{eÜ·ß2Ñ?Ѭû¢»v€u®}SÕÀ>}b굯rðNëÞìn\’N)µhãýá"bDÏ{2ΰp¾¥×O¬5â\{ÿl5¾ºÛ{N´Ûgl¯Ï²ÿÝà0gÑ/Ø“7Ø?©ó6Gß'öKßÎ÷¨øÞ¸w¼—‘âPÿ^=RR>g²œ&±$v·÷¢ .U‡¸!æÙÝûî:¢ÅíX›Ëß–¯ûHfºÀbύ%ìö…Ù†wsãfÂ¥ ¢Y¸Ä«96l‘xÏÜÐ¥ù÷¯çø˜kî {Îmâ0±¡°Gì˺âqÚ†}Þ#6¦k†}DøþÚh)rㇸQ;Vd‡¼WØtÈ/×ðò³—¾±¥V"לøáÝöžçô··½æ=vsàOÀÐ>Z.­nƒCÚ@ Jø…Yóg-Äûgÿ°>ó+r¤®Ï¾„¬ß€ (¬ß»&Ø·ñìË>I|y±%!ñìĉ}ÒЯÌÊ/Ž 8``Ñ Ë¬gÿÓq>ƒ]R|㺂ýŸ ™{qA|‘ŽtØ&