%PDF-1.2 7 0 obj > endobj 8 0 obj > endobj 9 0 obj > endobj 10 0 obj > endobj 11 0 obj > endobj 12 0 obj > endobj 13 0 obj > endobj 14 0 obj > endobj 16 0 obj > stream 0.00 g 0.00 G BT/F1 17.93 Tf 51.9 -12.81 TD[(Reconsidering)-278(Custom)-278(Memor)-10(y)-278(Allocation)]TJ/F2 11.95 Tf -9.58 -40.59 TD[(Emer)-30(y)-278(D)69(.)-277(Berger)]TJ/F2 8.96 Tf -10.04 -10.45 TD[(Dept.)-388(of)-278(Computer)-278(Science)]TJ -1.38 -10.46 TD[(Univ)24(ersity)-277(of)-278(Massachusetts)]TJ 14.83 -10.46 TD[(Amherst,)-277(MA)-556(01002)]TJ/F2 10.96 Tf -13.72 -14.44 TD[(emer)-30(y@cs)14(.umass)15(.edu)]TJ/F2 11.95 Tf 153.81 45.81 TD[(Benjamin)-277(G.)-278(Zor)-25(n)]TJ/F2 8.96 Tf 8.37 -10.45 TD[(Microsoft)-277(Research)]TJ 0.81 -10.46 TD[(One)-278(Microsoft)-278(W)39(a)30(y)]TJ -6.08 -10.46 TD[(Redmond,)-278(W)49(A)-555(98052)]TJ/F2 10.96 Tf -6.49 -14.44 TD[(z)14(or)-24([email protected])]TJ/F2 11.95 Tf 142.83 45.81 TD[(Kathr)-30(yn)-278(S)19(.)-277(McKinle)19(y)]TJ/F2 8.96 Tf -2.8 -10.45 TD[(Dept.)-388(of)-278(Computer)-278(Scie)-1(nces)]TJ -8.3 -10.46 TD[(The)-278(Univ)24(ersity)-277(of)-278(T)119(e)30(xas)-277(at)-278(A)29(ustin)]TJ 29.35 -10.46 TD[(A)29(ustin,)-277(TX)-556(78712)]TJ/F2 10.96 Tf -24.62 -14.44 TD[(mc)20(kinle)20(y@cs)15(.ute)30(xas)15(.edu)]TJ/F3 8.96 Tf -337.09 -44.94 TD[(ABSTRA)54(CT)]TJ/F4 8.96 Tf 0 -12.47 TD[(Programmers)-318(hoping)-318(to)-318(achie)24(v)15(e)-317(performance)-319(impro)14(v)15(ements)-317(often)]TJ 0 -10.46 TD[(use)-233(custom)-232(memory)-233(allocators.)-305(This)-232(in-depth)-233(study)-233(e)14(xamines)-232(eight)]TJ 0 -10.46 TD[(applications)-408(that)-408(use)-407(custom)-408(allocators.)-784(Surprisingly)64(,)-446(for)-408(six)-408(of)]TJ 0 -10.46 TD[(these)-273(applications,)-280(a)-273(state-of-the-art)-274(general-purpose)-273(allocator)-274(\(the)]TJ 0 -10.46 TD[(Lea)-324(allocator\))-324(performs)-323(as)-324(well)-324(as)-324(or)-324(better)-323(than)-324(the)-324(custom)-324(allo-)]TJ 0 -10.45 TD[(cators.)-463(The)-301(tw)9(o)-300(e)14(xceptions)-300(use)-301(re)14(gions,)-313(which)-301(deli)24(v)15(er)-300(higher)-301(per)19(-)]TJ 0 -10.46 TD[(formance)-279(\(impro)14(v)15(ements)-279(of)-279(up)-280(to)-279(44%\).)-398(Re)14(gions)-279(also)-279(reduce)-280(pro-)]TJ 0 -10.46 TD[(grammer)-345(b)19(urden)-344(and)-345(eliminate)-346(a)-345(source)-345(of)-345(memory)-345(leaks.)-596(Ho)24(w-)]TJ 0 -10.46 TD[(e)24(v)15(er)40(,)-303(we)-292(sho)24(w)-292(that)-293(the)-293(inability)-293(of)-293(programmers)-293(to)-293(free)-293(indi)24(vidual)]TJ 0 -10.45 TD[(objects)-241(within)-240(re)14(gions)-240(can)-241(lead)-241(to)-241(a)-240(substantial)-241(increase)-241(in)-241(memory)]TJ 0 -10.46 TD[(consumption.)-581(W)79(orse,)-362(this)-340(limitation)-340(precludes)-341(the)-340(use)-341(of)-340(re)14(gions)]TJ 0 -10.46 TD[(for)-250(common)-250(programming)-250(idioms,)-250(reducing)-250(their)-250(usefulness.)]TJ 8.97 -10.46 TD[(W)80(e)-212(present)-214(a)-213(generalization)-213(of)-214(general-purpose)-213(and)-213(re)14(gion-based)]TJ -8.97 -10.46 TD[(allocators)-317(that)-317(we)-317(call)]TJ/F5 8.96 Tf 83.06 0 TD[(r)37(eaps)]TJ/F4 8.96 Tf 19.58 0 TD[(.)-511(Reaps)-317(are)-317(a)-316(combination)-317(of)-317(re)14(gions)]TJ -102.64 -10.45 TD[(and)-288(heaps,)-297(pro)14(viding)-286(a)-288(full)-288(range)-287(of)-288(re)14(gion)-287(semantics)-287(with)-288(the)-288(ad-)]TJ 0 -10.46 TD[(dition)-312(of)-312(indi)24(vidual)-311(object)-312(deletion.)-496(W)79(e)-312(sho)24(w)-311(that)-312(our)-312(implemen-)]TJ 0 -10.46 TD[(tation)-256(of)-256(reaps)-256(pro)14(vides)-255(high)-256(performance,)-257(outperforming)-256(other)-256(al-)]TJ 0 -10.46 TD[(locators)-344(with)-345(re)14(gion-lik)10(e)-343(semantics.)-593(W)79(e)-344(then)-344(use)-345(a)-344(case)-344(study)-345(to)]TJ 0 -10.46 TD[(demonstrate)-363(the)-363(space)-364(adv)24(antages)-362(and)-363(softw)9(are)-363(engineering)-363(ben-)]TJ 0 -10.45 TD[(e\002ts)-376(of)-377(reaps)-376(in)-376(practice.)-689(Our)-377(results)-376(indicate)-377(that)-376(programmers)]TJ 0 -10.46 TD[(needing)-283(f)9(ast)-282(re)14(gions)-282(should)-284(use)-283(reaps,)-291(and)-283(that)-284(most)-283(programmers)]TJ 0 -10.46 TD[(considering)-247(custom)-247(allocators)-247(should)-247(instead)-247(use)-247(the)-247(Lea)-247(allocator)54(.)]TJ/F3 8.96 Tf 0 -16.58 TD[(Categories)-250(and)-250(Subject)-250(Descriptors)]TJ/F4 8.96 Tf 0 -12.48 TD[(D.3.3)-235([)]TJ/F3 8.96 Tf 25.02 0 TD[(Pr)18(ogramming)-234(Languages)]TJ/F4 8.96 Tf 97.06 0 TD[(]:)-302(Dynamic)-235(storage)-236(management)]TJ/F3 8.96 Tf -122.08 -16.58 TD[(General)-250(T)91(erms)]TJ/F4 8.96 Tf 0 -12.47 TD[(Algorithms,)-250(Experimentation,)-250(Performance,)-250(Reliability)]TJ/F3 8.96 Tf 0 -16.58 TD[(1.)-1000(Intr)17(oduction)]TJ/F4 8.96 Tf 0 -10.98 TD[(Programmers)-413(seeking)-414(to)-413(impro)14(v)15(e)-413(performance)-413(often)-414(incorporate)]TJ 0 -10.46 TD[(custom)-398(memory)-397(allocators)-398(into)-398(their)-398(applications.)-753(Custom)-398(allo-)]TJ ET 0.4 w -18.2 -480.86 m 77.42 -480.86 l S BT/F4 7.97 Tf -11.9 -489.22 TD[(This)-226(w)9(ork)-227(is)-227(supported)-227(by)-228(NSF)-227(ITR)-227(grant)-228(CCR-0085792)-227(and)-227(Darpa)-227(grant)]TJ -6.3 -8.97 TD[(F33615-01-C-1892.)-676(This)-373(w)9(ork)-371(w)9(as)-371(done)-372(while)-372(Emery)-373(Ber)17(ger)-371(w)9(as)-371(a)-372(re-)]TJ 0 -8.96 TD[(search)-236(intern)-237(at)-237(Microsoft)-236(Research)-237(and)-236(a)-237(doctoral)-237(student)-236(at)-237(the)-236(Uni)24(v)15(ersity)]TJ 0 -8.96 TD[(of)-302(T)69(e)15(xas.)-463(Emery)-302(Ber)17(ger)-301(w)9(as)-300(also)-302(supported)-302(by)-301(a)-302(Microsoft)-302(Research)-301(Fel-)]TJ 0 -8.97 TD[(lo)24(wship.)-471(An)14(y)-302(opinions,)-318(\002ndings)-304(and)-304(conclusions)-303(or)-304(recommendations)-304(e)14(x-)]TJ 0 -8.96 TD[(pressed)-250(in)-251(this)-251(material)-250(are)-251(the)-250(authors')-251(and)-250(do)-251(not)-250(necessarily)-251(re\003ect)-250(those)]TJ 0 -8.97 TD[(of)-250(the)-250(sponsors.)]TJ/F4 7.97 Tf 0 -41.57 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/F5 7.97 Tf 0 -8.97 TD[(OOPSLA)36('02,)]TJ/F4 7.97 Tf 43.97 0 TD[(No)14(v)15(ember)-249(4\2558,)-250(2002,)-250(Seattle,)-250(W)79(ashington,)-249(USA.)]TJ -43.97 -8.96 TD[(Cop)9(yright)-249(2002)-250(A)39(CM)-249(1\25558113\255417\2551/02/0011)-250(..)]TJ/F4 8.96 Tf 154.09 0 TD[($)]TJ/F4 7.97 Tf 4.49 0 TD[(5.00)]TJ/F4 8.96 Tf 104.36 503.17 TD[(cators)-269(aim)-269(to)-269(tak)9(e)-268(adv)24(antage)-268(of)-269(application-speci\002c)-269(allocation)-269(pat-)]TJ 0 -10.46 TD[(terns)-351(to)-351(manage)-351(memory)-351(more)-352(ef)24(\002ciently)-350(than)-351(a)-351(general-purpose)]TJ 0 -10.46 TD[(memory)-216(allocator)54(.)-298(F)14(or)-214(instance,)-223(197.parser)-216(\(from)-216(the)-216(SPECint2000)]TJ 0 -10.45 TD[(benchmark)-375(suite\))-376(runs)-375(o)14(v)15(er)-374(60%)-376(f)9(aster)-374(with)-375(its)-376(custom)-375(allocator)]TJ 0 -10.46 TD[(than)-278(with)-278(the)-278(W)39(indo)25(ws)-277(XP)-277(allocator)-278([4].)-394(Numerous)-278(books)-278(and)-278(ar)19(-)]TJ 0 -10.46 TD[(ticles)-334(recommend)-334(custom)-334(allocators)-333(as)-334(an)-334(optimization)-334(technique)]TJ 0 -10.46 TD[([7,)-339(25,)-339(26].)-523(The)-321(use)-321(of)-321(custom)-322(memory)-321(allocators)-321(is)-321(widespread,)]TJ 0 -10.45 TD[(including)-235(the)-235(Apache)-235(web)-235(serv)14(er)-233([1],)-238(the)-235(GCC)-235(compiler)-235([13],)-238(three)]TJ 0 -10.46 TD[(of)-256(the)-256(SPECint2000)-256(benchmarks)-256([34],)-258(and)-256(the)-256(C++)-256(Standard)-256(T)69(em-)]TJ 0 -10.46 TD[(plate)-369(Library)-370([11,)-399(32],)-399(all)-369(of)-370(which)-369(we)-369(e)14(xamine)-369(here.)-668(The)-369(C++)]TJ 0 -10.46 TD[(language)-344(itself)-344(pro)14(vides)-343(language)-344(constructs)-344(that)-344(directly)-344(support)]TJ 0 -10.46 TD[(custom)-296(memory)-296(allocation)-296(\(by)-297(o)14(v)15(erloading)]TJ/F7 8.96 Tf 158.9 0 TD[(operator)-600(new)]TJ/F4 8.96 Tf 67.2 0 TD[(and)]TJ/F7 8.96 Tf -226.1 -10.45 TD[(delete)]TJ/F4 8.96 Tf 32.27 0 TD[(\))-250([10].)]TJ -23.3 -10.46 TD[(The)-341(k)9(e)15(y)-340(contrib)19(utions)-341(of)-341(this)-341(w)9(ork)-341(are)-341(the)-342(follo)24(wing.)-583(W)79(e)-340(per)19(-)]TJ -8.97 -10.46 TD[(form)-273(a)-273(comprehensi)24(v)15(e)-272(e)24(v)25(aluation)-272(of)-272(custom)-273(allocation.)-379(W)79(e)-272(surv)14(e)15(y)]TJ 0 -10.46 TD[(a)-356(v)24(ariety)-356(of)-356(applications)-356(that)-357(use)-356(a)-356(wide)-357(range)-356(of)-357(custom)-356(alloca-)]TJ 0 -10.46 TD[(tors.)-459(W)79(e)-299(compare)-300(their)-300(performance)-300(and)-299(memory)-300(consumption)-300(to)]TJ 0 -10.45 TD[(general-purpose)-207(allocators.)-296(W)79(e)-206(were)-207(surprised)-207(to)-207(\002nd)-207(that,)-216(contrary)]TJ 0 -10.46 TD[(to)-287(con)39(v)15(entional)-286(wisdom,)-297(custom)-287(allocation)-287(generally)-288(does)-287(not)-287(im-)]TJ 0 -10.46 TD[(pro)14(v)15(e)-195(performance,)-207(and)-196(in)-197(one)-196(case,)-207(actually)-196(leads)-196(to)-197(a)-196(performance)]TJ 0 -10.46 TD[(de)14(gradation.)-493(A)-312(state-of-the-art)-311(general-purpose)-312(allocator)-311(\(the)-312(Lea)]TJ 0 -10.45 TD[(allocator)-194([23]\))-195(yields)-194(performance)-195(equi)24(v)25(alent)-193(to)-195(custom)-194(memory)-195(al-)]TJ 0 -10.46 TD[(locators)-235(for)-235(six)-235(of)-235(our)-235(eight)-236(benchmarks.)-305(These)-235(results)-235(suggest)-235(that)]TJ 0 -10.46 TD[(most)-203(programmers)-203(seeking)-203(f)9(aster)-202(memory)-204(allocation)-203(should)-203(use)-203(the)]TJ 0 -10.46 TD[(Lea)-250(allocator)-250(rather)-250(than)-250(writing)-250(their)-250(o)24(wn)-249(custom)-250(allocator)54(.)]TJ 8.97 -10.46 TD[(The)-300(custom)-302(allocators)-301(that)-301(do)-301(pro)14(vide)-300(higher)-301(performance)-301(both)]TJ -8.97 -10.45 TD[(use)]TJ/F5 8.96 Tf 14.58 0 TD[(r)36(e)40(gions)]TJ/F4 8.96 Tf 26.2 0 TD[(.)-440(Re)14(gions)-292(pro)13(vide)-292(high-performance)-293(b)19(ut)-293(force)-293(the)-293(pro-)]TJ -40.78 -10.46 TD[(grammer)-214(to)-214(retain)-213(all)-214(memory)-214(associated)-214(with)-214(a)-214(re)14(gion)-212(until)-214(the)-214(last)]TJ 0 -10.46 TD[(object)-263(in)-264(the)-263(re)14(gion)-262(dies)-264([14,)-266(15,)-267(17,)-267(19,)-266(30,)-267(39].)-350(W)79(e)-262(sho)24(w)-263(that)-263(the)]TJ 0 -10.46 TD[(performance)-251(g)4(ains)-251(of)-251(re)14(gions)-250(\(up)-252(to)-251(44%\))-251(can)-252(come)-251(at)-252(the)-251(e)14(xpense)]TJ 0 -10.46 TD[(of)-356(e)14(xcessi)25(v)15(e)-356(memory)-356(retention)-357(\(up)-356(to)-356(230%\).)-629(More)-357(importantly)64(,)]TJ 0 -10.45 TD[(the)-289(inability)-288(to)-289(free)-289(indi)24(vidual)-287(objects)-289(within)-289(re)14(gions)-287(greatly)-289(com-)]TJ 0 -10.46 TD[(plicates)-233(the)-233(programming)-233(of)-233(serv)14(er)-232(applications)-233(lik)9(e)-232(Apache)-233(which)]TJ 0 -10.46 TD[(rely)-237(on)-237(re)14(gions)-235(to)-237(a)19(v)20(oid)-236(resource)-237(leaks.)-305(Man)14(y)-236(programs)-237(cannot)-237(use)]TJ 0 -10.46 TD[(re)14(gions)-320(because)-321(of)-321(their)-321(memory)-321(allocation)-322(patterns.)-523(If)-321(programs)]TJ 0 -10.45 TD[(with)-389(intensi)24(v)15(e)-389(memory)-389(reuse,)-424(producer)19(-consumer)-389(allocation)-389(pat-)]TJ 0 -10.46 TD[(terns,)-314(or)-301(dynamic)-301(arrays)-301(were)-301(to)-301(use)-301(re)14(gions,)-313(the)14(y)-300(could)-301(consume)]TJ 0 -10.46 TD[(v)14(ery)-249(lar)17(ge)-249(or)-250(e)24(v)15(en)-249(unbounded)-250(amounts)-250(of)-250(memory)64(.)]TJ 8.97 -10.46 TD[(W)80(e)-283(present)-283(a)-283(generalization)-284(of)-283(re)14(gions)-283(and)-283(heaps)-283(we)-284(call)]TJ/F5 8.96 Tf 208.24 0 TD[(r)36(eaps)]TJ/F4 8.96 Tf 19.59 0 TD[(.)]TJ -236.8 -10.46 TD[(Our)-232(implementation)-232(of)-232(reaps)-231(pro)14(vides)-231(the)-232(performance)-232(and)-232(seman-)]TJ 0 -10.45 TD[(tics)-217(of)-218(re)14(gions)-216(while)-218(allo)24(wing)-216(programmers)-218(to)-217(delete)-218(indi)24(vidual)-216(ob-)]TJ 0 -10.46 TD[(jects.)-402(W)79(e)-280(sho)24(w)-280(that)-281(reaps)-280(nearly)-281(match)-281(the)-281(speed)-280(of)-281(re)14(gions)-280(when)]TJ 0 -10.46 TD[(used)-253(in)-253(the)-253(same)-253(w)9(ay)65(,)-253(and)-253(pro)14(vide)-253(additional)-253(semantics)-253(and)-253(gener)19(-)]TJ 0 -10.46 TD[(ality)64(.)-293(Reaps)-201(pro)14(vide)-201(a)-201(reusable)-201(library)-202(solution)-201(for)-202(re)14(gion)-200(allocation)]TJ 0 -10.46 TD[(with)-356(competiti)24(v)15(e)-355(performance,)-382(the)-356(potential)-356(for)-356(reduced)-356(memory)]TJ 0 -10.45 TD[(consumption,)-272(and)-268(greater)-268(memory)-268(management)-268(\003e)14(xibility)-267(than)-268(re-)]TJ 0 -10.46 TD[(gions.)-383(W)79(e)-273(demonstrate)-274(indi)24(vidual)-273(object)-274(deletion)-275(using)-274(reaps)-274(with)]TJ 0 -10.46 TD[(a)-285(case)-285(study)-285(in)-285(which)-286(we)-285(add)-285(a)-285(ne)24(w)-284(module)-285(to)-285(Apache.)-416(The)-285(orig-)]TJ -14.19 -39.34 TD[(1)]TJ ET endstream endobj 18 0 obj > endobj 6 0 obj > endobj 21 0 obj > endobj 24 0 obj > endobj 25 0 obj > stream 0.00 g 0.00 G BT/F4 8.96 Tf -18.2 8.24 TD[(inal)-351(v)13(ersion)-350(of)-352(this)-351(program)-352(uses)]TJ/F7 8.96 Tf 124.84 0 TD[(malloc)]TJ/F4 8.96 Tf 32.27 0 TD[(/)]TJ/F7 8.96 Tf 2.49 0 TD[(free)]TJ/F4 8.96 Tf 21.52 0 TD[(.)-614(W)79(e)-350(sho)24(w)-351(that)]TJ -181.12 -10.46 TD[(by)-257(modifying)-258(only)-257(a)-257(fe)24(w)-256(lines)-258(to)-257(use)-257(the)-258(reap)-257(interf)9(ace,)-258(we)-258(can)-257(get)]TJ 0 -10.46 TD[(re)14(gion)-365(semantics)-367(with)-366(indi)24(vidual)-366(object)-366(deletion)-367(and)-366(thus)-367(reduce)]TJ 0 -10.46 TD[(memory)-250(consumption)-250(signi\002cantly)64(.)]TJ 8.97 -10.45 TD[(The)-262(remainder)-263(of)-263(this)-264(paper)-263(is)-263(or)17(g)5(anized)-262(as)-263(follo)24(ws.)-348(W)79(e)-262(discuss)]TJ -8.97 -10.46 TD[(related)-371(w)9(ork)-370(in)-371(Section)-371(2.)-673(W)79(e)-370(describe)-372(our)-371(benchmarks)-371(in)-371(Sec-)]TJ 0 -10.46 TD[(tion)-323(3.)-530(In)-324(Section)-323(4,)-342(we)-323(analyze)-323(the)-324(structure)-323(of)-323(custom)-324(memory)]TJ 0 -10.46 TD[(allocators)-237(used)-238(by)-237(our)-238(benchmark)-237(applications)-237(and)-238(e)14(xplain)-236(wh)4(y)-237(re-)]TJ 0 -10.46 TD[(gions)-358(do)-358(not)-358(pro)14(vide)-358(suf)24(\002cient)-357(support)-358(for)-358(man)14(y)-358(applications,)-385(in)]TJ 0 -10.45 TD[(particular)-378(serv)14(er)-378(applications)-378(lik)9(e)-377(Apache.)-695(In)-379(Section)-378(5,)-410(we)-379(de-)]TJ 0 -10.46 TD[(scribe)-252(reaps)-253(and)-252(present)-252(our)-253(implementation)-252(in)-252(detail.)-317(W)78(e)-251(describe)]TJ 0 -10.46 TD[(our)-310(e)14(xperimental)-308(infrastructure)-310(and)-310(methodology)-310(in)-310(Section)-309(6.)-490(In)]TJ 0 -10.46 TD[(Section)-238(7,)-240(we)-238(present)-238(e)14(xperimental)-237(results,)-240(including)-238(a)-238(comparison)]TJ 0 -10.46 TD[(to)-320(pre)24(vious)-320(allocators)-320(with)-321(re)14(gion-lik)10(e)-320(semantics,)-338(and)-320(present)-321(our)]TJ 0 -10.45 TD[(case)-252(study)64(.)-314(W)79(e)-251(discuss)-252(our)-252(results)-252(in)-252(Section)-252(8,)-252(e)14(xplaining)-251(wh)4(y)-251(we)]TJ 0 -10.46 TD[(belie)24(v)15(e)-354(programmers)-356(used)-356(custom)-355(memory)-356(allocators)-355(despite)-356(the)]TJ 0 -10.46 TD[(f)9(act)-337(that)-339(these)-338(do)-339(not)-338(pro)14(vide)-338(the)-338(performance)-339(the)14(y)-337(promise,)-361(and)]TJ 0 -10.46 TD[(we)-250(conclude)-250(in)-250(Section)-250(9.)]TJ/F3 8.96 Tf 0 -14.91 TD[(2.)-1000(Related)-250(W)74(ork)]TJ/F4 8.96 Tf 0 -10.98 TD[(Numerous)-265(articles)-266(and)-265(books)-265(ha)19(v)15(e)-265(appeared)-265(in)-266(the)-265(trade)-265(press)-266(pre-)]TJ 0 -10.46 TD[(senting)-385(custom)-385(memory)-386(allocators)-385(as)-385(an)-386(optimization)-385(technique.)]TJ 0 -10.46 TD[(Bulka)-279(and)-280(Mayhe)24(w)-278(de)24(v)20(ote)-278(tw)9(o)-278(entire)-280(chapters)-279(to)-279(the)-280(de)24(v)15(elopment)]TJ 0 -10.46 TD[(of)-243(a)-242(n)-1(umber)-242(of)-243(custom)-243(memory)-243(allocators)-243([7].)-307(Me)14(yers)-242(describes)-243(in)]TJ 0 -10.45 TD[(detail)-280(the)-281(use)-280(of)-281(a)-280(freelist-based)-281(per)19(-class)-279(custom)-281(allocator)-280(in)-281(\223Ef-)]TJ 0 -10.46 TD[(fecti)24(v)15(e)-315(C++\224)-315([24])-316(and)-315(returns)-316(to)-316(the)-315(topic)-316(of)-316(custom)-315(allocators)-316(in)]TJ 0 -10.46 TD[(the)-284(sequel)-285([25].)-413(Mile)24(wski)-284(also)-284(discusses)-285(per)19(-class)-283(allocators)-284(as)-285(an)]TJ 0 -10.46 TD[(optimization)-335(technique)-335([26].)-564(Hanson)-335(de)24(v)20(otes)-334(a)-335(chapter)-335(to)-335(an)-335(im-)]TJ 0 -10.46 TD[(plementation)-276(of)-276(re)14(gions)-276(\(\223arenas\224\),)-283(citing)-276(both)-276(the)-276(speed)-277(and)-276(soft-)]TJ 0 -10.45 TD[(w)9(are)-296(engineering)-297(bene\002ts)-297(of)-298(re)14(gions)-296(as)-297(moti)24(v)25(ation)-296([20].)-452(Ellis)-297(and)]TJ 0 -10.46 TD[(Stroustrup)-359(describe)-359(the)-359(syntactic)-359(f)9(acilities)-358(that)-359(allo)24(w)-358(o)14(v)15(erloading)]TJ/F7 8.96 Tf 0 -10.46 TD[(operator)-600(new)]TJ/F4 8.96 Tf 64.54 0 TD[(,)-236(simplifying)-233(the)-233(use)-233(of)-233(custom)-233(allocators)-233(in)-233(C++)]TJ -64.54 -10.46 TD[([10],)-228(and)-223(Stroustrup)-222(describes)-223(per)19(-class)-221(allocators)-223(that)-223(use)-222(these)-223(f)9(a-)]TJ 0 -10.46 TD[(cilities)-288([37].)-426(In)-289(all)-289(b)19(ut)-287(Hanson')54(s)-288(w)9(ork,)-297(the)-289(authors)-288(present)-289(custom)]TJ 0 -10.45 TD[(memory)-383(allocation)-383(as)-383(a)-383(widely)-383(ef)24(fecti)25(v)15(e)-382(optimization,)-416(while)-383(our)]TJ 0 -10.46 TD[(results)-265(suggest)-265(that)-264(only)-265(re)14(gions)-264(yield)-265(performance)-265(impro)14(v)15(ements.)]TJ 0 -10.46 TD[(W)79(e)-271(present)-271(a)-272(generalization)-272(of)-272(custom)-272(allocators)-271(\(reaps\))-272(and)-272(sho)24(w)]TJ 0 -10.46 TD[(that)-250(reaps)-250(capture)-250(the)-250(high)-250(performance)-250(of)-250(re)14(gion)-249(allocators.)]TJ 8.97 -10.45 TD[(Re)15(gion)-232(allocation,)-237(v)24(ariously)-232(kno)24(wn)-232(as)-233(arenas,)-237(groups,)-236(and)-233(zones)]TJ -8.97 -10.46 TD[([19,)-238(30])-236(has)-235(recently)-236(attracted)-235(attention)-236(as)-235(an)-236(alternati)24(v)15(e)-234(to)-236(g)4(arbage)]TJ 0 -10.46 TD[(collection.)-307(F)14(ollo)25(wing)-242(the)-242(de\002nitions)-243(in)-242(the)-243(literature,)-244(programmers)]TJ 0 -10.46 TD[(allocate)-197(objects)-198(within)-197(a)-198(re)14(gion)-196(and)-197(can)-198(delete)-197(all)-198(objects)-197(in)-197(a)-198(re)14(gion)]TJ 0 -10.46 TD[(at)-224(once)-224(b)19(ut)-223(cannot)-224(delete)-224(indi)24(vidual)-223(objects)-224([14,)-230(15,)-229(17,)-229(19,)-229(30,)-230(39].)]TJ 0 -10.45 TD[(T)79(ofte)-304(and)-306(T)79(alpin)-305(present)-305(a)-306(system)-305(that)-306(pro)14(vides)-304(automatic)-306(re)14(gion-)]TJ 0 -10.46 TD[(based)-266(memory)-266(management)-267(for)-266(ML)-266([39].)-359(Gay)-266(and)-266(Aik)8(en)-265(describe)]TJ/F5 8.96 Tf 0 -10.46 TD[(safe)]TJ/F4 8.96 Tf 16.91 0 TD[(re)15(gions)-274(which)-275(raise)-275(an)-275(error)-275(when)-275(a)-275(programmer)-275(deletes)-274(a)-275(re-)]TJ -16.91 -10.46 TD[(gion)-253(containing)-253(li)24(v)15(e)-252(objects)-253(and)-253(introduce)-253(the)-253(RC)-253(language,)-254(an)-253(e)14(x-)]TJ 0 -10.46 TD[(tension)-287(to)-288(C)-287(that)-288(further)-288(reduces)-287(the)-288(o)14(v)15(erhead)-286(of)-288(safe)-287(re)14(gion)-287(man-)]TJ 0 -10.45 TD[(agement)-273([14,)-278(15].)-378(While)-273(these)-272(authors)-273(present)-273(only)-272(the)-273(bene\002ts)-273(of)]TJ 0 -10.46 TD[(re)14(gions,)-332(we)-317(in)39(v)15(estig)5(ate)-316(the)-316(hidden)-317(memory)-316(consumption)-317(cost)-317(and)]TJ 0 -10.46 TD[(limitations)-338(of)-338(re)14(gions)-337(and)-338(present)-338(an)-339(alternati)24(v)15(e)-337(that)-338(a)19(v)20(oids)-337(these)]TJ 0 -10.46 TD[(dra)14(wbacks)-275(and)-277(combines)-276(indi)24(vidual)-275(object)-277(deletion)-276(with)-276(the)-277(bene-)]TJ 0 -10.45 TD[(\002ts)-250(of)-250(re)14(gions.)]TJ 8.97 -10.46 TD[(T)80(o)-326(compute)-327(the)-327(memory)-327(cost)-326(of)-327(re)14(gion)-326(allocation,)-346(we)-327(measure)]TJ -8.97 -10.46 TD[(the)-360(memory)-361(consumed)-360(using)-360(re)14(gions)-359(and)-361(when)-360(objects)-360(are)-361(freed)]TJ 0 -10.46 TD[(immediately)-283(after)-283(their)-284(last)-283(reference.)-410(W)79(e)-282(use)-284(binary)-283(instrumenta-)]TJ 0 -10.46 TD[(tion)-229(to)-229(determine)-230(when)-229(objects)-229(are)-229(last)-229(referenced)-230(and)-229(post-process)]TJ 0 -10.45 TD[(a)-258(combined)-258(allocation-reference)-258(trace)-258(to)-258(obtain)-258(peak)-258(memory)-258(con-)]TJ 0 -10.46 TD[(sumption)-351(and)-350(object)-351(drag,)-376(the)-350(elapsed)-351(time)-351(between)-350(last)-351(use)-351(and)]TJ 0 -10.46 TD[(reclamation)-394(of)-393(an)-394(object.)-741(Our)-393(de\002nition)-394(of)-394(drag)-393(dif)24(fers)-393(slightly)]TJ 0 -10.46 TD[(from)-218(the)-218(original)-218(use)-218(of)-218(the)-218(term)-218(by)-218(Runciman)-218(and)-218(Rojemo)-218([31].)-300(In)]TJ 0 -10.46 TD[(their)-276(w)9(ork,)-281(drag)-277(is)-276(the)-276(time)-276(between)-276(last)-276(use)-276(and)-276(unreachability)-276(of)]TJ 0 -10.45 TD[(an)-272(object,)-277(which)-272(in)-272(a)-271(g)4(arbage-collected)-271(en)39(vironment)-271(de\002nes)-272(a)19(v)25(ail-)]TJ 0 -10.46 TD[(ability)-235(for)-235(reclamation.)-305(Shaham,)-238(K)34(olodner)-234(and)-236(Sagi)24(v)-234(measure)-235(drag)]TJ 262.94 653.37 TD[(by)-280(performing)-280(periodic)-281(object)-280(reachability)-280(scanning)-280(in)-281(the)-280(conte)14(xt)]TJ 0 -10.46 TD[(of)-250(Ja)19(v)25(a,)-249(a)-250(g)4(arbage-collected)-249(language)-250([33].)]TJ 8.97 -10.46 TD[(The)-206(literature)-208(on)-207(general-purpose)-207(memory)-207(allocators)-207(is)-207(e)14(xtensi)25(v)15(e)]TJ -8.97 -10.46 TD[(\(see)-308(W)39(ilson')55(s)-308(surv)14(e)15(y)-307(for)-309(a)-308(comprehensi)24(v)15(e)-308(description)-308([43]\).)-486(Here)]TJ 0 -10.45 TD[(we)-207(describe)-207(the)-207(W)39(indo)25(ws)-206(XP)-207(and)-207(Lea)-207(allocators)-207([23,)-215(28],)-216(which)-207(we)]TJ 0 -10.46 TD[(use)-243(in)-243(this)-243(study)-243(because)-243(of)-243(their)-243(widespread)-243(use)-243(\(the)-243(Lea)-243(allocator)]TJ 0 -10.46 TD[(forms)-218(the)-219(basis)-218(of)-218(the)-218(Linux)-219(memory)-218(allocator)-218([16]\).)-300(The)-218(W)39(indo)25(ws)]TJ 0 -10.46 TD[(allocator)-323(is)-323(a)-323(best-\002t)-323(allocator)-324(with)-323(127)-323(e)14(xact-size)-322(quicklists)-323(\(one)]TJ 0 -10.46 TD[(link)9(ed)-398(list)-400(of)-399(freed)-400(objects)-399(for)-399(each)-400(multiple)-399(of)-400(8)-399(bytes\),)-437(which)]TJ 0 -10.45 TD[(optimize)-241(for)-241(the)-241(case)-241(when)-241(man)14(y)-241(requests)-241(are)-241(for)-241(small)-241(same-sized)]TJ 0 -10.46 TD[(objects.)-391(Objects)-277(lar)17(ger)-276(than)-277(1024)-278(bytes)-277(are)-277(obtained)-277(from)-277(a)-277(sorted)]TJ 0 -10.46 TD[(link)9(ed)-365(list,)-395(sacri\002cing)-366(speed)-366(for)-366(a)-366(good)-366(\002t.)-658(The)-366(Lea)-366(allocator)-366(is)]TJ 0 -10.46 TD[(an)-312(approximate)-312(best-\002t)-312(allocator)-311(with)-312(dif)24(ferent)-311(beha)19(vior)-311(based)-312(on)]TJ 0 -10.46 TD[(object)-308(size.)-483(Small)-308(objects)-308(\(less)-308(than)-308(64)-307(bytes\))-308(are)-308(allocated)-308(using)]TJ 0 -10.45 TD[(e)14(xact-size)-202(quicklists.)-294(Requests)-203(for)-203(a)-203(medium-sized)-202(object)-203(\(less)-203(than)]TJ 0 -10.46 TD[(128K\))-227(and)-227(certain)-227(other)-227(e)24(v)15(ents)-226(trigger)-227(the)-227(Lea)-227(allocator)-227(to)]TJ/F5 8.96 Tf 208.18 0 TD[(coalesce)]TJ/F4 8.96 Tf -208.18 -10.46 TD[(the)-278(objects)-278(in)-279(these)-278(quicklists)-278(\(combining)-278(adjacent)-279(free)-278(objects\))-278(in)]TJ 0 -10.46 TD[(the)-314(hope)-313(that)-314(this)-314(reclaimed)-314(space)-313(can)-314(be)-314(reused)-313(for)-314(the)-314(medium-)]TJ 0 -10.45 TD[(sized)-237(object.)-305(F)14(or)-236(medium-sized)-237(objects,)-239(the)-237(Lea)-236(allocator)-237(performs)]TJ 0 -10.46 TD[(immediate)-334(coalescing)-333(and)]TJ/F5 8.96 Tf 97.6 0 TD[(splitting)]TJ/F4 8.96 Tf 32.39 0 TD[(\(breaking)-333(objects)-334(into)-333(smaller)]TJ -129.99 -10.46 TD[(ones\))-366(and)-366(approximates)-366(best-\002t.)-657(Lar)17(ge)-365(objects)-366(are)-366(allocated)-366(and)]TJ 0 -10.46 TD[(freed)-328(using)]TJ/F7 8.96 Tf 43.72 0 TD[(mmap)]TJ/F4 8.96 Tf 21.52 0 TD[(.)-543(The)-328(Lea)-328(allocator)-328(is)-329(the)-328(best)-328(o)14(v)15(erall)-327(allocator)]TJ -65.24 -10.46 TD[(\(in)-228(terms)-227(of)-228(the)-228(combination)-228(of)-227(speed)-228(and)-228(memory)-227(usage\))-228(of)-228(which)]TJ 0 -10.45 TD[(we)-250(are)-250(a)14(w)10(are)-249([22].)]TJ 8.97 -10.46 TD[(In)-337(addition)-337(to)-338(the)-337(standard)]TJ/F7 8.96 Tf 100.27 0 TD[(malloc)]TJ/F4 8.96 Tf 32.27 0 TD[(/)]TJ/F7 8.96 Tf 2.49 0 TD[(free)]TJ/F4 8.96 Tf 24.54 0 TD[(interf)10(ace,)-359(W)39(indo)25(ws)]TJ -168.54 -10.46 TD[(also)-252(pro)14(vides)-250(a)-252(W)39(indo)25(ws-speci\002c)-251(memory)-252(allocation)-251(interf)9(ace)-251(that)]TJ 0 -10.46 TD[(we)-206(refer)-206(to)-207(as)-206(W)39(indo)25(ws)-205(Heaps)-207(\(all)-206(function)-206(calls)-206(be)14(gin)-206(with)]TJ/F7 8.96 Tf 212.3 0 TD[(Heap)]TJ/F4 8.96 Tf 21.52 0 TD[(\).)]TJ -233.82 -10.46 TD[(The)-230(W)39(indo)25(ws)-229(Heaps)-230(interf)9(ace)-229(is)-231(e)14(xceptionally)-229(rich,)-234(including)-230(mul-)]TJ 0 -10.45 TD[(tiple)-432(heaps)-432(and)-432(some)-431(re)14(gion)-431(semantics)-432(\(b)19(ut)-431(not)-432(nested)-432(re)14(gions\))]TJ 0 -10.46 TD[(along)-269(with)-270(indi)24(vidual)-268(object)-269(deletion)-270([28].)-368(Vmalloc,)-274(a)-270(memory)-269(al-)]TJ 0 -10.46 TD[(location)-242(infrastructure,)-243(also)-242(pro)14(vides)-241(\(non-nested\))-242(re)14(gions)-241(that)-242(per)19(-)]TJ 0 -10.46 TD[(mit)-353(indi)24(vidual)-352(object)-353(deletion)-354([41].)-619(W)79(e)-352(sho)24(w)-352(in)-354(Section)-353(7.3)-353(that)]TJ 0 -10.46 TD[(neither)-232(of)-231(these)-232(implementations)-232(match)-232(the)-231(performance)-232(of)-232(re)14(gions)]TJ 0 -10.45 TD[(or)-250(reaps,)-250(and)-250(reaps)-250(capture)-250(the)-250(same)-250(semantics.)]TJ 8.97 -10.46 TD[(The)-194(only)-195(pre)24(vious)-194(w)9(ork)-194(e)24(v)25(aluating)-194(the)-195(impact)-195(of)-195(custom)-195(memory)]TJ -8.97 -10.46 TD[(allocators)-289(is)-290(by)-289(Zorn)-290(\(one)-289(of)-289(the)-290(authors\).)-428(Zorn)-289(compared)-290(custom)]TJ 0 -10.46 TD[(\(\223domain-speci\002c\224\))-313(allocators)-312(to)-313(general-purpose)-312(memory)-313(alloca-)]TJ 0 -10.45 TD[(tors)-253([44].)-319(He)-253(analyzed)-253(the)-254(performance)-253(of)-253(four)-253(benchmarks)-253(\(cfrac,)]TJ 0 -10.46 TD[(g)4(a)15(wk,)-307(Ghostscript,)-308(and)-296(Perl\))-297(and)-296(found)-297(that)-296(the)-296(applications')-297(cus-)]TJ 0 -10.46 TD[(tom)-400(allocators)-400(only)-400(slightly)-400(impro)14(v)15(ed)-399(performance)-400(\(from)-400(2%)-400(to)]TJ 0 -10.46 TD[(7%\))-374(e)14(xcept)-373(for)-374(Ghostscript,)-405(whose)-374(custom)-374(allocator)-374(w)9(as)-373(outper)19(-)]TJ 0 -10.46 TD[(formed)-311(by)-310(most)-311(of)-311(the)-311(general-purpose)-310(allocators)-311(he)-311(tested.)-492(Zorn)]TJ 0 -10.45 TD[(also)-414(found)-414(that)-414(custom)-414(allocators)-413(generally)-414(had)-414(little)-414(impact)-414(on)]TJ 0 -10.46 TD[(memory)-388(consumption.)-726(His)-388(study)-389(dif)24(fers)-387(from)-389(ours)-388(in)-388(a)-389(number)]TJ 0 -10.46 TD[(of)-354(w)9(ays.)-620(Ours)-354(is)-353(a)-354(more)-354(comprehensi)24(v)15(e)-353(study)-353(of)-354(custom)-354(alloca-)]TJ 0 -10.46 TD[(tion,)-251(including)-250(a)-251(benchmark)-251(suite)-250(co)13(v)15(ering)-249(a)-251(wide)-251(range)-250(of)-251(custom)]TJ 0 -10.46 TD[(memory)-388(allocators,)-423(while)-389(Zorn')54(s)-387(benchmarks)-389(include)-388(essentially)]TJ 0 -10.45 TD[(only)-377(one)-376(v)24(ariety)65(.)]TJ/F4 5.98 Tf 61.96 3.8 TD[(1)]TJ/F4 8.96 Tf 9.68 -3.8 TD[(W)80(e)-376(also)-376(address)-377(custom)-377(allocators)-376(whose)-377(se-)]TJ -71.64 -10.46 TD[(mantics)-372(dif)24(fer)-371(from)-371(those)-372(of)-372(general-purpose)-372(allocators)-372(\(e.g.,)-402(re-)]TJ 0 -10.46 TD[(gions\),)-288(while)-280(Zorn')54(s)-280(benchmarks)-280(use)-280(only)-281(semantically)-280(equi)24(v)25(alent)]TJ 0 -10.46 TD[(custom)-388(allocators.)-724(Our)-388(\002ndings)-388(therefore)-388(dif)24(fer)-387(from)-387(Zorn')54(s,)-422(in)]TJ 0 -10.45 TD[(that)-231(we)-230(\002nd)-231(that)-231(certain)-230(custom)-231(allocators)-231(\(especially)-230(re)14(gions\))-230(con-)]TJ 0 -10.46 TD[(sistently)-402(yield)-402(performance)-402(impro)14(v)15(ements)-402(o)14(v)15(er)-401(e)14(xisting)-401(general-)]TJ 0 -10.46 TD[(purpose)-190(memory)-190(allocators,)-202(despite)-190(the)-190(f)9(act)-189(that)-190(the)-190(general-purpose)]TJ 0 -10.46 TD[(allocators)-250(are)-250(much)-250(f)9(aster)-249(no)24(w)65(.)]TJ 8.97 -10.46 TD[(While)-220(pre)24(vious)-219(w)9(ork)-220(has)-220(either)-220(held)-221(that)-220(custom)-221(memory)-220(alloca-)]TJ -8.97 -10.45 TD[(tors)-273(are)-272(a)-273(good)-273(idea)-272(\(articles)-273(in)-273(the)-272(trade)-273(press\),)-278(or)-273(a)-273(w)9(aste)-271(of)-273(time)]TJ 0 -10.46 TD[(\(Zorn\),)-407(we)-375(\002nd)-375(that)-375(both)-376(are)-375(true.)-686(Most)-375(custom)-376(allocators)-375(ha)19(v)15(e)]TJ 0 -10.46 TD[(no)-243(impact)-244(on)-243(performance,)-245(b)19(ut)-243(re)14(gions)-242(in)-243(particular)-244(ha)19(v)15(e)-242(both)-244(high)]TJ 0 -10.46 TD[(performance)-194(and)-194(some)-194(softw)9(are)-193(engineering)-194(bene\002ts.)-292(W)79(e)-193(sho)24(w)-193(that)]TJ 0 -10.46 TD[(the)-304(inability)-305(of)-304(programmers)-305(to)-304(delete)-305(objects)-304(within)-305(re)14(gions)-303(may)]TJ ET 0.4 w 244.74 -625.72 m 340.36 -625.72 l S BT/F8 5.98 Tf 245.08 -632.36 TD[(1)]TJ/F4 7.97 Tf 4.15 -3.81 TD[(These)-382(allocators)-383(are)-383(all)-383(v)24(ariants)-382(of)-383(what)-383(we)-383(call)-383(per)19(-class)-382(allocators)-383(in)]TJ -4.49 -8.96 TD[(Section)-250(4.2.)]TJ/F4 8.96 Tf -14.19 -29.88 TD[(2)]TJ ET endstream endobj 26 0 obj > endobj 20 0 obj > endobj 29 0 obj > stream 0.00 g 0.00 G 0.4 w -18.2 18 m 235.16 18 l S 0.4 w -18.2 7.34 m -18.2 17.8 l S BT/F3 8.96 Tf 84.33 10.48 TD[(Benchmarks)]TJ ET 0.4 w 235.16 7.34 m 235.16 17.8 l S 0.4 w -18.2 7.14 m 235.16 7.14 l S 0.4 w -18.2 -3.52 m -18.2 6.94 l S BT 74.99 -0.38 TD[(custom)-250(allocation)]TJ ET 0.4 w 235.16 -3.52 m 235.16 6.94 l S 0.4 w -18.2 -13.97 m -18.2 -3.52 l S BT/F5 8.96 Tf -12.82 -10.84 TD[(197.par)9(ser)]TJ/F4 7.97 Tf 54.03 0 TD[(English)-249(parser)-250([34])]TJ/F5 7.97 Tf 113.62 0 TD[(test.in)]TJ ET 0.4 w 235.16 -13.97 m 235.16 -3.52 l S 0.4 w -18.2 -24.43 m -18.2 -13.97 l S BT/F5 8.96 Tf -12.82 -21.29 TD[(boxed-sim)]TJ/F4 7.97 Tf 54.03 0 TD[(Balls-in-box)-249(simulator)-250([8])]TJ/F5 7.97 Tf 113.62 0 TD[(-n)-249(3)-250(-s)-250(1)]TJ ET 0.4 w 235.16 -24.43 m 235.16 -13.97 l S 0.4 w -18.2 -34.89 m -18.2 -24.43 l S BT/F5 8.96 Tf -12.82 -31.75 TD[(C-Br)36(eeze)]TJ/F4 7.97 Tf 54.03 0 TD[(C-to-C)-249(optimizing)-250(compiler)-250([18])]TJ/F5 7.97 Tf 113.62 0 TD[(espr)37(esso.c)]TJ ET 0.4 w 235.16 -34.89 m 235.16 -24.43 l S 0.4 w -18.2 -45.35 m -18.2 -34.89 l S BT/F5 8.96 Tf -12.82 -42.21 TD[(175.vpr)]TJ/F4 7.97 Tf 54.03 0 TD[(FPGA)-249(placement)-250(&)-250(routing)-250([34])]TJ/F4 8.96 Tf 113.62 0 TD[(test)-249(placement)]TJ ET 0.4 w 235.16 -45.35 m 235.16 -34.89 l S 0.4 w -18.2 -55.81 m -18.2 -45.35 l S BT/F5 8.96 Tf -12.82 -52.67 TD[(176.gcc)]TJ/F4 7.97 Tf 54.03 0 TD[(Optimizing)-249(C)-250(compiler)-250([34])]TJ/F5 7.97 Tf 113.62 0 TD[(scilab)40(.i)]TJ ET 0.4 w 235.16 -55.81 m 235.16 -45.35 l S 0.4 w -18.2 -66.26 m -18.2 -55.81 l S BT/F5 8.96 Tf -12.82 -63.13 TD[(apac)14(he)]TJ/F4 7.97 Tf 54.03 0 TD[(W)80(eb)-249(serv)14(er)-249([1])]TJ/F4 8.96 Tf 113.62 0 TD[(see)-249(Section)-250(3)]TJ ET 0.4 w 235.16 -66.26 m 235.16 -55.81 l S 0.4 w -18.2 -76.72 m -18.2 -66.26 l S BT/F5 8.96 Tf -12.82 -73.58 TD[(lcc)]TJ/F4 7.97 Tf 54.03 0 TD[(Retar)18(getable)-249(C)-250(compiler)-250([12])]TJ/F5 7.97 Tf 113.62 0 TD[(scilab)40(.i)]TJ ET 0.4 w 235.16 -76.72 m 235.16 -66.26 l S 0.4 w -18.2 -87.18 m -18.2 -76.72 l S BT/F5 8.96 Tf -12.82 -84.04 TD[(mudlle)]TJ/F4 7.97 Tf 54.03 0 TD[(MUD)-249(compiler/interpreter)-250([14])]TJ/F5 7.97 Tf 113.62 0 TD[(time)15(.mud)]TJ ET 0.4 w 235.16 -87.18 m 235.16 -76.72 l S 0.4 w -18.2 -87.38 m 235.16 -87.38 l S 0.4 w -18.2 -98.03 m -18.2 -87.58 l S BT/F3 8.96 Tf 57.61 -94.9 TD[(general-pur)10(pose)-249(allocation)]TJ ET 0.4 w 235.16 -98.03 m 235.16 -87.58 l S 0.4 w -18.2 -108.49 m -18.2 -98.03 l S BT/F5 8.96 Tf -12.82 -105.36 TD[(164.gzip)]TJ/F4 7.97 Tf 54.03 0 TD[(GNU)-249(zip)-250(data)-250(compressor)-250([34])]TJ/F5 7.97 Tf 113.62 0 TD[(test/input.compr)37(essed)-249(2)]TJ ET 0.4 w 235.16 -108.49 m 235.16 -98.03 l S 0.4 w -18.2 -118.95 m -18.2 -108.49 l S BT/F5 8.96 Tf -12.82 -115.81 TD[(181.mcf)]TJ/F4 7.97 Tf 54.03 0 TD[(V)111(ehicle)-249(scheduler)-250([34])]TJ/F5 7.97 Tf 113.62 0 TD[(test-input.in)]TJ ET 0.4 w 235.16 -118.95 m 235.16 -108.49 l S 0.4 w -18.2 -129.41 m -18.2 -118.95 l S BT/F5 8.96 Tf -12.82 -126.27 TD[(186.cr)14(afty)]TJ/F4 7.97 Tf 54.03 0 TD[(Chess)-249(program)-250([34])]TJ/F5 7.97 Tf 113.62 0 TD[(test-input.in)]TJ ET 0.4 w 235.16 -129.41 m 235.16 -118.95 l S 0.4 w -18.2 -139.87 m -18.2 -129.41 l S BT/F5 8.96 Tf -12.82 -136.73 TD[(252.eon)]TJ/F4 7.97 Tf 54.03 0 TD[(Ray)-249(tracer)-250([34])]TJ/F5 7.97 Tf 113.62 0 TD[(test/c)15(hair)111(.contr)45(ol.cook)]TJ ET 0.4 w 235.16 -139.87 m 235.16 -129.41 l S 0.4 w -18.2 -150.32 m -18.2 -139.87 l S BT/F5 8.96 Tf -12.82 -147.19 TD[(253.perlbmk)]TJ/F4 7.97 Tf 54.03 0 TD[(Perl)-249(interpreter)-250([34])]TJ/F5 7.97 Tf 113.62 0 TD[(perfect.pl)-249(b)-250(3)]TJ ET 0.4 w 235.16 -150.32 m 235.16 -139.87 l S 0.4 w -18.2 -160.78 m -18.2 -150.32 l S BT/F5 8.96 Tf -12.82 -157.64 TD[(254.gap)]TJ/F4 7.97 Tf 54.03 0 TD[(Groups)-249(language)-250(interpreter)-250([34])]TJ/F5 7.97 Tf 113.62 0 TD[(test.in)]TJ ET 0.4 w 235.16 -160.78 m 235.16 -150.32 l S 0.4 w -18.2 -171.24 m -18.2 -160.78 l S BT/F5 8.96 Tf -12.82 -168.1 TD[(255.vorte)19(x)]TJ/F4 7.97 Tf 54.03 0 TD[(Object-oriented)-249(DBM)-250([34])]TJ/F5 7.97 Tf 113.62 0 TD[(test/lendian.r)15(aw)]TJ ET 0.4 w 235.16 -171.24 m 235.16 -160.78 l S 0.4 w -18.2 -181.7 m -18.2 -171.24 l S BT/F5 8.96 Tf -12.82 -178.56 TD[(300.twolf)]TJ/F4 7.97 Tf 54.03 0 TD[(CAD)-249(placement)-250(&)-250(routing)-250([34])]TJ/F5 7.97 Tf 113.62 0 TD[(test.net)]TJ ET 0.4 w 235.16 -181.7 m 235.16 -171.24 l S 0.4 w -18.2 -192.16 m -18.2 -181.7 l S BT/F5 8.96 Tf -12.82 -189.02 TD[(espr)36(esso)]TJ/F4 7.97 Tf 54.03 0 TD[(Optimizer)-249(for)-250(PLAs)-250([35])]TJ/F5 7.97 Tf 113.62 0 TD[(test2)]TJ ET 0.4 w 235.16 -192.16 m 235.16 -181.7 l S 0.4 w -18.2 -202.61 m -18.2 -192.16 l S BT/F5 8.96 Tf -12.82 -199.48 TD[(lindsay)]TJ/F4 7.97 Tf 54.03 0 TD[(Hypercube)-249(simulator)-250([43])]TJ/F5 7.97 Tf 113.62 0 TD[(script.mine)]TJ ET 0.4 w 235.16 -202.61 m 235.16 -192.16 l S 0.4 w -18.2 -202.81 m 235.16 -202.81 l S BT/F3 8.96 Tf -18.2 -220.14 TD[(T)91(able)-442(1:)-695(Benchmarks)-442(and)-443(inputs.)-888(W)64(e)-442(include)-442(the)-443(general-)]TJ 0 -10.46 TD[(pur)9(pose)-250(benchmarks)-251(f)24(or)-250(comparison)-251(with)-251(custom)-251(allocation)-251(in)]TJ 0 -10.46 TD[(Section)-226(7.3.)-302(All)-226(pr)17(ograms)-225(ar)17(e)-225(written)-226(in)-227(C)-226(except)-226(C-Br)17(eeze)-225(and)]TJ 0 -10.46 TD[(252.eon,)-250(which)-250(ar)17(e)-249(written)-250(in)-250(C++.)]TJ/F4 8.96 Tf 0 -30.54 TD[(lead)-358(to)-358(a)-359(substantial)-358(increase)-358(in)-358(memory)-358(consumption)-359(and)-358(limits)]TJ 0 -10.46 TD[(their)-219(applicability)64(.)-298(W)79(e)-218(de)24(v)15(elop)-217(a)-219(generalized)-219(memory)-218(allocator)-219(that)]TJ 0 -10.45 TD[(preserv)14(es)-276(the)-278(high)-277(performance)-277(of)-278(re)14(gions)-276(while)-277(pro)14(viding)-277(greater)]TJ 0 -10.46 TD[(\003e)14(xibility)-249(and)-250(a)-250(potential)-250(reduction)-250(in)-250(memory)-250(consumption.)]TJ 8.97 -10.46 TD[(Re)15(gions)-292(ha)19(v)15(e)-292(also)-293(been)-292(incorporated)-293(into)-293(Real-T)34(ime)-292(Ja)19(v)25(a)-291(to)-293(al-)]TJ -8.97 -10.46 TD[(lo)24(w)-341(real-time)-341(guarantees)-342(that)-341(c)-1(annot)-341(be)-342(pro)14(vided)-340(by)-342(an)14(y)-341(e)14(xisting)]TJ 0 -10.46 TD[(g)4(arbage)-273(collector)-274(algorithm)-274(or)-273(implementation)-274([5].)-382(These)-274(re)14(gions,)]TJ 0 -10.45 TD[(while)-317(some)24(what)-317(dif)24(ferent)-316(from)-317(traditional)-318(re)14(gion-based)-316(allocators)]TJ 0 -10.46 TD[(in)-192(that)-193(the)14(y)-191(are)-193(associated)-192(with)-193(one)-192(or)-193(more)-192(computations)-193([2],)-204(suf)24(fer)]TJ 0 -10.46 TD[(from)-192(the)-192(same)-192(problems)-192(as)-192(traditional)-192(re)14(gions.)-289(In)-192(particular)39(,)-203(threads)]TJ 0 -10.46 TD[(in)-355(a)-355(producer)19(-consumer)-354(relationship)-355(cannot)-355(use)-355(re)14(gion)-354(allocation)]TJ 0 -10.45 TD[(without)-233(causing)-234(unbounded)-234(memory)-233(consumption.)-305(W)79(e)-232(belie)24(v)15(e)-233(that)]TJ 0 -10.46 TD[(adapting)-336(reaps)-336(to)-336(the)-336(setting)-335(of)-336(Real-T)34(ime)-335(Ja)19(v)25(a)-335(is)-336(a)-336(fruitful)-336(topic)]TJ 0 -10.46 TD[(for)-250(future)-250(research.)]TJ/F3 8.96 Tf 0 -17.44 TD[(3.)-1000(Benchmarks)]TJ/F4 8.96 Tf 0 -10.98 TD[(W)79(e)-301(list)-302(the)-302(benchmarks)-302(we)-301(use)-302(in)-302(this)-302(paper)-302(in)-302(T)79(able)-301(1,)-315(including)]TJ 0 -10.46 TD[(general-purpose)-231(allocation)-231(benchmarks)-231(that)-231(we)-232(use)-231(for)-231(comparison)]TJ 0 -10.46 TD[(with)-378(custom)-379(allocation)-378(in)-379(Section)-379(7.3.)-695(Most)-379(of)-378(our)-379(benchmarks)]TJ 0 -10.46 TD[(come)-231(from)-232(the)-231(SPECint2000)-232(benchmark)-231(suite)-232([34].)-304(F)14(or)-230(the)-232(custom)]TJ 0 -10.45 TD[(allocation)-311(benchmarks,)-325(we)-311(include)-311(a)-310(number)-311(of)-311(programs)-310(used)-311(in)]TJ 0 -10.46 TD[(prior)-337(w)9(ork)-336(on)-337(memory)-337(allocation.)-572(These)-337(programs)-337(include)-337(those)]TJ 0 -10.46 TD[(used)-360(by)-360(Gay)-360(and)-360(Aik)9(en)-360(\(Apache,)-387(lcc,)-388(and)-360(mudlle\))-360([14,)-388(15],)-388(and)]TJ 0 -10.46 TD[(box)14(ed-sim,)-304(used)-294(by)-294(Chilimbi)-294([8].)-442(W)79(e)-293(also)-294(use)-294(the)-294(C-Breeze)-294(com-)]TJ 0 -10.45 TD[(piler)-263(infrastructure)-263([18].)-350(C-Breeze)-264(mak)9(es)-262(intensi)24(v)15(e)-262(use)-263(of)-264(the)-263(C++)]TJ 0 -10.46 TD[(Standard)-200(T)69(emplate)-199(Library)-200(\(STL\),)-200(and)-200(most)-201(implementations)-200(of)-200(the)]TJ 0 -10.46 TD[(STL)-289(use)-290(custom)-290(allocators,)-299(including)-290(the)-290(one)-289(we)-290(use)-290(in)-289(this)-290(study)]TJ 0 -10.46 TD[(\(STLport,)-250(of)24(\002cially)-249(recommended)-250(by)-250(IBM\))-250([11,)-250(32].)]TJ 8.97 -10.46 TD[(W)80(e)-386(use)-388(the)-387(lar)17(gest)-386(inputs)-387(a)19(v)25(ailable)-387(to)-387(us)-387(for)-387(most)-388(of)-387(the)-387(cus-)]TJ -8.97 -10.45 TD[(tom)-246(allocation)-247(benchmarks,)-247(e)14(xcept)-245(for)-247(175.vpr)-246(and)-247(197.parser)54(.)-308(F)14(or)]TJ 0 -10.46 TD[(these)-412(and)-411(the)-412(general-purpose)-411(benchmarks)-412(from)-412(SPEC2000,)-452(we)]TJ 0 -10.46 TD[(used)-324(the)-324(test)-324(inputs.)-533(The)-324(o)14(v)15(erhead)-323(imposed)-324(by)-324(our)-325(binary)-324(instru-)]TJ 0 -10.46 TD[(mentation)-389(made)-390(runtimes)-390(for)-389(the)-390(reference)-389(inputs)-390(and)-389(the)-390(resul-)]TJ 0 -10.46 TD[(tant)-238(trace)-238(\002les)-238(intractable.)-306(W)79(e)-237(e)14(xcluded)-238(just)-238(one)-238(SPEC)-238(benchmark,)]TJ 0 -10.45 TD[(256.bzip2,)-250(because)-250(we)-250(could)-250(not)-250(process)-250(e)24(v)15(en)-249(its)-250(test)-250(inputs.)]TJ 8.97 -10.46 TD[(W)80(e)-232(describe)-233(all)-232(of)-233(the)-232(inputs)-233(we)-233(used)-232(to)-233(dri)24(v)15(e)-232(our)-232(benchmarks)-233(in)]TJ 253.97 653.37 TD[(T)79(able)-316(1)-316(e)14(xcept)-316(for)-316(Apache.)-510(T)79(o)-316(dri)24(v)15(e)-316(Apache,)-333(we)-317(follo)24(w)-315(Gay)-317(and)]TJ 0 -10.46 TD[(Aik)9(en)-233(and)-235(run)-234(on)-235(the)-234(same)-234(computer)-235(a)-234(program)-235(that)-234(fetches)-234(a)-235(lar)17(ge)]TJ 0 -10.46 TD[(number)-270(of)-270(static)-270(web)-270(pages.)-369(While)-270(this)-270(test)-270(is)-270(unrealistic,)-275(it)-270(serv)14(es)]TJ 0 -10.46 TD[(tw)9(o)-227(purposes.)-303(First,)-233(it)-229(isolates)-228(performance)-229(from)-228(the)-228(usual)-229(netw)9(ork)]TJ 0 -10.45 TD[(and)-368(disk)-369(I/O)-368(bottlenecks,)-398(magnifying)-369(the)-368(performance)-368(impact)-369(of)]TJ 0 -10.46 TD[(custom)-272(allocation.)-377(Second,)-278(using)-272(the)-272(same)-272(benchmark)-272(as)-273(Gay)-272(and)]TJ 0 -10.46 TD[(Aik)9(en)-249(f)9(acilitates)-249(comparison)-250(with)-250(their)-250(w)9(ork.)]TJ/F3 8.96 Tf 0 -20.71 TD[(3.1)-1000(Emulating)-250(Custom)-250(Semantics)]TJ/F4 8.96 Tf 0 -13 TD[(Custom)-212(memory)-212(allocators)-212(often)-211(support)-212(semantics)-212(that)-212(dif)24(fer)-211(from)]TJ 0 -10.45 TD[(the)-213(C)-212(memory)-213(allocation)-212(interf)9(ace.)-297(In)-213(order)-212(to)-213(replace)-212(these)-213(custom)]TJ 0 -10.46 TD[(allocators)-256(with)]TJ/F7 8.96 Tf 55.39 0 TD[(malloc)]TJ/F4 8.96 Tf 34.57 0 TD[(and)]TJ/F7 8.96 Tf 15.24 0 TD[(free)]TJ/F4 8.96 Tf 21.51 0 TD[(,)-258(we)-256(must)-256(emulate)-257(their)-256(seman-)]TJ -126.71 -10.46 TD[(tics)-305(on)-306(top)-305(of)-305(the)-306(standard)-305(allocation)-305(calls.)-476(W)78(e)-304(wrote)-305(and)-306(tuned)-305(a)]TJ 0 -10.46 TD[(re)14(gion)-276(emulator)-277(to)-278(pro)14(vide)-276(the)-277(full)-277(range)-277(of)-278(re)14(gion)-276(semantics)-277(used)]TJ 0 -10.46 TD[(by)-204(our)-204(benchmark)-205(applications,)-213(including)-204(nesting)-204(and)-205(obstacks)-204(\(see)]TJ 0 -10.45 TD[(Section)-252(4.2\).)-315(The)-251(re)14(gion)-251(emulator)-252(uses)-252(the)-251(general-purpose)-252(alloca-)]TJ 0 -10.46 TD[(tor)-302(for)-302(each)-302(allocated)-302(object,)-314(b)19(ut)-301(records)-302(a)-302(pointer)-302(for)-302(each)-302(object)]TJ 0 -10.46 TD[(so)-386(that)-386(when)-387(the)-386(application)-386(deletes)-386(a)-386(re)14(gion,)-420(the)-386(re)14(gion)-385(emula-)]TJ 0 -10.46 TD[(tor)-285(can)-286(call)]TJ/F7 8.96 Tf 43.02 0 TD[(free)]TJ/F4 8.96 Tf 24.08 0 TD[(on)-285(each)-285(allocated)-286(object.)-416(W)79(e)-284(record)-286(the)-285(pointer)]TJ -67.1 -10.46 TD[(information)-299(for)-300(allocated)-299(objects)-299(in)-300(an)-299(out-of-band)-300(dynamic)-299(array)]TJ 0 -10.45 TD[(associated)-372(with)-373(each)-372(re)14(gion,)-402(rather)-372(than)-373(within)-372(the)-373(allocated)-372(ob-)]TJ 0 -10.46 TD[(jects.)-751(This)-397(method)-397(ensures)-397(that)-398(the)-397(last)-397(access)-397(to)-397(an)14(y)-396(allocated)]TJ 0 -10.46 TD[(object)-239(is)-239(by)-239(the)-239(client)-239(program)-239(and)-239(not)-239(by)-239(our)-239(re)14(gion)-238(emulator)54(.)-305(Us-)]TJ 0 -10.46 TD[(ing)-352(this)-352(technique)-351(means)-352(that)-352(our)-352(re)14(gion)-351(emulator)-351(has)-352(no)-352(impact)]TJ 0 -10.45 TD[(on)-297(object)-296(drag,)-309(the)-296(elapsed)-297(time)-296(between)-297(last)-297(use)-296(and)-297(reclamation)]TJ 0 -10.46 TD[(of)-335(an)-335(object,)-357(which)-335(we)-336(measure)-335(in)-335(Section)-335(7.3.)-566(Ho)24(we)25(v)15(er)40(,)-356(re)14(gion)]TJ 0 -10.46 TD[(emulation)-272(has)-271(an)-272(impact)-272(on)-272(space.)-375(Ev)14(ery)-270(allocated)-272(object)-272(requires)]TJ 0 -10.46 TD[(4)-250(bytes)-251(of)-250(memory)-251(\(for)-250(its)-250(record)-251(in)-250(the)-251(dynamic)-250(array\))-250(in)-251(addition)]TJ 0 -10.46 TD[(to)-366(per)19(-object)-366(o)14(v)15(erhead)-365(\(4\2268)-366(bytes\).)-659(Eliminating)-366(this)-367(o)14(v)15(erhead)-365(is)]TJ 0 -10.45 TD[(an)-267(adv)24(antage)-266(of)-266(re)14(gions,)-270(b)19(ut)-266(the)-267(inability)-267(to)-266(free)-267(indi)24(vidual)-266(objects)]TJ 0 -10.46 TD[(may)-369(ha)19(v)15(e)-367(a)-369(much)-369(greater)-368(impact)-369(on)-369(space,)-398(which)-369(we)-368(e)14(xplore)-368(in)]TJ 0 -10.46 TD[(Section)-250(6.1.)]TJ/F3 8.96 Tf 0 -20.71 TD[(4.)-1000(Custom)-250(Allocators)]TJ/F4 8.96 Tf 0 -10.98 TD[(In)-258(this)-258(section,)-260(we)-258(e)14(xplain)-257(e)14(xactly)-257(what)-258(we)-258(mean)-258(by)-258(custom)-258(mem-)]TJ 0 -10.46 TD[(ory)-258(allocators.)-333(W)79(e)-257(discuss)-258(the)-258(reasons)-257(wh)4(y)-257(programmers)-258(use)-258(them)]TJ 0 -10.45 TD[(and)-290(surv)14(e)15(y)-289(a)-290(wide)-290(range)-289(of)-290(custom)-290(memory)-290(allocators,)-300(describing)]TJ 0 -10.46 TD[(brie\003y)-250(what)-250(the)14(y)-249(do)-250(and)-250(ho)24(w)-249(the)14(y)-249(w)9(ork.)]TJ 8.97 -10.46 TD[(W)80(e)-270(use)-270(the)-271(term)-271(custom)-270(memory)-271(allocation)-270(in)-271(a)-271(proscribed)-270(w)9(ay)]TJ -8.97 -10.46 TD[(to)-190(denote)-190(an)14(y)-189(memory)-190(allocation)-190(mechanism)-190(that)-190(dif)24(fers)-189(from)-190(general-)]TJ 0 -10.46 TD[(purpose)-237(allocation)-236(in)-237(at)-237(least)-236(one)-237(of)-237(tw)9(o)-236(w)9(ays.)-304(First,)-240(a)-236(custom)-237(allo-)]TJ 0 -10.45 TD[(cator)-284(may)-284(pro)14(vide)-283(more)-284(than)-284(one)-284(object)-284(for)-284(e)24(v)15(ery)-283(allocated)-284(chunk)]TJ 0 -10.46 TD[(of)-314(memory)64(.)-501(Second,)-330(it)-314(may)-315(not)-314(immediately)-314(return)-314(objects)-314(to)-314(the)]TJ 0 -10.46 TD[(system)-283(or)-284(to)-283(the)-284(general-purpose)-283(allocator)54(.)-409(F)14(or)-283(instance,)-292(a)-283(custom)]TJ 0 -10.46 TD[(allocator)-392(may)-391(obtain)-392(lar)17(ge)-390(chunks)-392(of)-391(memory)-392(from)-391(the)-392(general-)]TJ 0 -10.46 TD[(purpose)-324(allocator)-324(which)-323(it)-324(carv)14(es)-323(up)-324(into)-324(a)-324(number)-324(of)-323(objects.)-532(A)]TJ 0 -10.45 TD[(custom)-211(allocator)-212(might)-211(also)-212(defer)-211(object)-211(deallocation,)-220(returning)-211(ob-)]TJ 0 -10.46 TD[(jects)-380(to)-380(the)-380(system)-380(long)-380(after)-379(the)-380(object)-380(is)-380(last)-380(used)-380(or)-380(becomes)]TJ 0 -10.46 TD[(unreachable.)]TJ 8.97 -10.46 TD[(Our)-312(de\002nition)-312(of)-312(custom)-312(memory)-313(allocators)-312(e)14(xcludes)-311(wrappers)]TJ -8.97 -10.45 TD[(that)-375(perform)-375(certain)-375(tests)-376(\(e.g.,)-406(for)-375(null)-375(return)-376(v)24(alues\))-374(before)-375(re-)]TJ 0 -10.46 TD[(turning)-358(objects)-358(obtained)-358(from)-357(the)-358(general-purpose)-358(memory)-358(man-)]TJ 0 -10.46 TD[(ager)54(.)-496(W)79(e)-312(also)-312(e)14(xclude)-311(from)-313(consideration)-312(memory)-313(allocators)-312(that)]TJ 0 -10.46 TD[(serv)14(e)-367(primarily)-368(as)-368(infrastructures)-367(for)-368(implementing)-368(object)-368(layout)]TJ 0 -10.46 TD[(optimizations)-250([9,)-250(40].)]TJ/F3 8.96 Tf 0 -20.7 TD[(4.1)-1000(Wh)14(y)-249(Pr)17(ogrammers)-249(Use)-250(Custom)-250(Allocators)]TJ/F4 8.96 Tf 0 -13 TD[(There)-248(are)-248(a)-249(v)24(ariety)-247(of)-248(reasons)-248(wh)4(y)-247(programmers)-249(use)-248(custom)-248(mem-)]TJ 0 -10.46 TD[(ory)-420(allocators.)-818(The)-420(principal)-420(reason)-419(cited)-420(by)-419(programmers)-420(and)]TJ 0 -10.46 TD[(authors)-319(of)-320(books)-319(on)-320(programming)-319(is)-320(runtime)-319(performance)-320([7,)-337(20,)]TJ 0 -10.46 TD[(24,)-366(25,)-367(26,)-366(37].)-590(Because)-343(the)-343(per)19(-operation)-342(cost)-344(of)-343(most)-343(general-)]TJ 0 -10.45 TD[(purpose)-359(memory)-358(allocators)-359(is)-358(an)-359(order)-358(of)-359(magnitude)-358(higher)-359(than)]TJ 0 -10.46 TD[(that)-290(of)-291(custom)-290(allocators,)-301(programs)-291(that)-290(mak)9(e)-289(intensi)24(v)15(e)-290(use)-290(of)-291(the)]TJ -14.19 -29.88 TD[(3)]TJ ET endstream endobj 30 0 obj > endobj 28 0 obj > endobj 33 0 obj > >> stream xœY[o7~?¿b_*ÑJÇø~yl¥ªR%TA#õB©6 hK}g|ûxÏY*a¿±?ÏÝ΄äÒÛ…ãúp}øxxþJ/·Ÿb¹…¿wí%óÆ/Væ¹_´šÉEá7ËÓÍá݁³œ•fùT~…¿‚š`°*Ñ2I+d­ß/a3ÁƒbzÖh¦ÂrÐFY&EEVŠ¨„4¥¼?ü±