短寿命オブジェクトを対象とした静的解析GCの提案

୹ण໋ΦϒδΣΫτΛର৅ͱͨ͠੩తղੳ

GC

ͷఏҊ

খ ࣨ

௚

†

_{Ѩ ෦ ެ ً}

† {komuro,abe}@cacao.cs.uec.ac.jp ੈ୅ผ GC ͸΄ͱΜͲͷΦϒδΣΫτ͸ੜ੒ޙ·΋ͳ͘͝ΈͱͳΔ୹ण໋ΦϒδΣΫτͰ͋Δͱ͍ ͏ੑ࣭Λ༻͍ͯޮ཰తʹ͝ΈΛճऩ͢Δ͕ɼ୹ण໋ΦϒδΣΫτͷ൑ผΛಈతʹߦ͏ͨΊॲཧ࣌ؒͷ ༧ଌ͕೉͍͠ɽຊݚڀͰ͸ʮ୹ण໋ΦϒδΣΫτͷଟ͘͸༗ޮൣғ͕੩తʹ൑ผՄೳͳΦϒδΣΫτ Ͱ઎ΊΒΕΔͷͰ͸ͳ͍͔ʯͱͷ༧૝Λͨͯɼͦͷ͔֬͞Λݕূ͢Δɽͦͯ͠੩తղੳʹΑΓ୹ण໋ ΦϒδΣΫτͷ൑ผɾճऩΛޮ཰ྑ͘ߦ͏ख๏ΛఏҊ͢Δɽ༧૝ͷݕূ͸ΦϒδΣΫτࢦ޲εΫϦϓ τݴޠͰ͋Δ Ruby ॲཧܥ MRI ʹͯߦ͏ɽRuby ͸ۙ೥։ൃɾݚڀ༻్Ͱͷར༻͕޿·͍ͬͯΔ͕

GCͷ࣮૷͸ະͩෆे෼Ͱ͋ΓɼఏҊख๏ʹΑΓੑೳ޲্͕ݟࠐΊΔɽ

Static Detection of Short-lived Objects for Effective GC

Sunao Komuro

†

and Kouki Abe

†

{komuro,abe}@cacao.cs.uec.ac.jp

Generational GC schemes effectively collect garbage objects utilizing the fact that most objects die young. However, the time required for the collection is unpredictable because the schemes detect the short-lived objects dynamically. In this paper, we put a hypothesis that most of the short-lived objects are those whose scopes can be statically detected, and we verify the hypothesis experimentally. We also propose a method which effectively collects the short-lived objects detected by the static analysis. The experimental verification is con-ducted using MRI, an interpreter of object-oriented scripting language Ruby. Ruby has been widely used for research and development purposes, but no effective implementation of GC is currently available. The proposed method is expected to improve the performance of Ruby interpreter.

1. ͸ ͡ Ί ʹ

ۙ೥Ͱ͸ඞཁͱ͞ΕΔϓϩάϥϜͷڊେԽɾෳࡶԽ ʹͱ΋ͳ͍ϓϩάϥϜ։ൃʹ͔͔Δ͕࣌ؒ૿͓ͯ͠ ΓɼϓϩάϥϜ։ൃޮ཰Λ্͛Δݚڀ͸ॏཁͳ՝୊ͱ ͳ͍ͬͯΔɽϓϩάϥϜ։ൃʹ͓͍ͯ͸ϝϞϦ؅ཧͷ ෳࡶ͕͞ϘτϧωοΫͷҰͭͰ͋Δɽಛʹಈతʹ֬อ ͨ͠ྖҬͷ؅ཧ͸͠͹͠͹μϯάϦϯάϙΠϯλɼϝ ϞϦϦʔΫͳͲόάͷݩͱͳΓ։ൃ࣌ؒΛංେԽ͞ ͤΔɽͦ͜Ͱಈతʹ֬อͨ͠ྖҬΛࣗಈతʹ։์͢Δ Garbage Collection(GC)͕޿͘༻͍ΒΕΔ1)_ɽ ҰൠʹGCʹΑΓඞཁͳϝϞϦྖҬ͸૿Ճ͢Δɽ· ͨɼGCͷؒଞͷॲཧΛఀࢭ͢Δɽߋʹ͍ͭGC ͕ ൃੜ͢Δ͔༧૝Ͱ͖ͳ͍ͨΊϦΞϧλΠϜγεςϜʹ ૊ΈࠐΉͷ͕೉͍͠ɽ͜ΕΒͷ໰୊Λղܾ͢ΔͨΊʹ † ిؾ௨৴େֶ ৘ใ޻ֶՊ

Department of Computer Science, The University of Electro-Communications ༷ʑͳख๏͕ఏҊ͞Ε͍ͯΔɽதͰ΋ੈ୅ผGC2),3) ͸΄ͱΜͲͷΦϒδΣΫτ͸ੜ੒ޙ·΋ͳ͘͝Έͱͳ Δͱ͍͏Ծઆ(ੈ୅Ծઆ)ʹج͖ͮ୹ण໋ΦϒδΣΫ τΛޮ཰తʹճऩͰ͖Δɽ͔ͦ͠͠ͷ··Ͱ͸อकత ΞϧΰϦζϜ4)_{Λద༻Ͱ͖ͳ͍ͳͲίετ΋େ͖͍ɽ} ຊݚڀͰ͸ʮ୹ण໋ΦϒδΣΫτͷଟ͘͸༗ޮൣғ ͕੩తʹ൑ผՄೳͳΦϒδΣΫτͰ઎ΊΒΕΔͷͰ͸ ͳ͍͔ʯͱͷ༧૝Λͨͯɼͦͷ͔֬͞Λݕূ͢Δɽͦ ͯ͠੩తղੳʹΑΓ୹ण໋ΦϒδΣΫτͷൃݟɾճऩ Λߦ͏ख๏ΛఏҊ͢Δɽ༧૝ͷݕূ͸ΦϒδΣΫτࢦ ޲εΫϦϓτݴޠͰ͋ΔRuby5)ॲཧܥMRIʹͯߦ ͏ɽRuby͸ۙ೥։ൃɾݚڀ༻్Ͱͷར༻͕޿·ͬͯ ͍Δ͕GCͷ࣮૷͸ະͩෆे෼Ͱ͋ΓɼఏҊख๏ʹΑ Γੑೳ޲্͕ݟࠐΊΔɽ ҎԼୈ2ষͰ͸GCͷ֓ཁͱؔ࿈ݚڀʹ͍ͭͯɼୈ 3ষͰ͸είʔϓϩʔΧϧͳΦϒδΣΫτ͕୹ण໋Φ ϒδΣΫτͷଟ͘Λ઎ΊΔͱͷ༧૝ͱɼ༧૝ʹج͍ͮ ͨ੩తղੳGCʹ͍ͭͯड़΂Δɽୈ4ষͰఏҊख๏ͷ

ݕূ࣮ݧͱͦͷ݁Ռɼୈ5ষͰߟ࡯Λड़΂ɼୈ6ষͰ ·ͱΊΔɽ

2. GC ͷ֓ཁͱؔ࿈ݚڀ

Mark Sweep GC6)_{͸ϧʔτηοτ(ώʔϓҎ֎ͷ} ੩తྖҬɼελοΫɼϨδελΛ߹ΘͤͨྖҬ)͔Β ࢀরΛ࠶ؼతʹ୧Γ౸ୡՄೳͰ͋ΔΦϒδΣΫτΛੜ ͖ͨΦϒδΣΫτɼͦΕҎ֎Λ͝ΈΦϒδΣΫτͱݟ ͳ͢Tracing GCΞϧΰϦζϜͷҰͭͰ͋Δɽ࣮૷͕ ؆୯Ͱ͋Δ͜ͱ΋͋Γ޿͘࢖ΘΕΔ͕ɼ୯७ʹͦͷ· ·࣮૷͢ΔͱੑೳΛٻΊΔ৔߹ʹ͸ෆे෼Ͱ͋Δɽ ੈ୅ผGC͸ੈ୅Ծઆʹج͖ͮ୹ण໋ΦϒδΣΫτ Ͱ઎ΊΒΕΔ৽ੈ୅ྖҬͱ௕ण໋ΦϒδΣΫτͰ઎Ί ΒΕΔچੈ୅ྖҬʹ෼͚ͯ؅ཧ͢ΔGCͰ͋Δɽੈ୅ Ծઆ(Generational Hypothesisɼ৽͘͠ੜ੒͞ΕͨΦ ϒδΣΫτ͸ݹ͍ΦϒδΣΫτΑΓੜଘ཰͕௿͍ͱͷ Ծઆ)͸ଟ਺ͷݚڀऀʹΑΓݕূ͞Εɼͦͷ͔͕֬͞ ࣔ͞Ε͍ͯΔɽϝϞϦྖҬ͕ރׇͨ͠ࡍʹ͸·ͣGC ର৅Λ৽ੈ୅ྖҬͱͨ͠Minor GCΛߦ͏ɽچੈ୅ ྖҬΛؚΊͨશମΛର৅ͱͨ͠Major GC͸Minor GCʹΑΓे෼ͳྖҬ͕֬อͰ͖ͳ͔ͬͨ৔߹ͷΈʹ ߦΘΕΔɽ͋Δఔ౓ͷճ਺Minor GCΛੜ͖࢒ͬͨ ΦϒδΣΫτ͸چੈ୅΁Ҡಈ͞ΕΔɽੈ୅ผGCͰ͸ ͦͷॲཧͷଟ͘Λੜଘ཰ͷ௿͍୹ण໋ΦϒδΣΫτΛ ޮ཰తʹճऩ͢ΔMinor GC͕઎Ίɼͦͷ݁Ռ୯७ ͳGCʹൺ΂ͯੑೳ޲্͕ݟࠐΊΔɽ͔͠͠ɼػߏͷ ෳࡶ͞ɼچੈ୅͔Β৽ੈ୅΁ͷࢀরΛه࿥͢ΔͨΊͷ ϥΠτόϦΞͷॻ͖ࠐΈίετɼอकతGC (ϙΠϯ λͱͳΓ͏Δ஋Λ࣋ͭΦϒδΣΫτ͸ϙΠϯλͱݟͳ ͢ΞϧΰϦζϜ)ͱͷ૊Έ߹Θ͕ͤࠔ೉ͳͲͷ໰୊͕ ͋Δɽ ϚϧνίΞϓϩηοαͷීٴʹ൐͍εϨουΤεέʔ ϓղੳ͕஫໨͞Ε͍ͯΔ7)_{ɽੜ੒͞ΕͨΦϒδΣΫτ} ͕୯ҰͷεϨουͰ࢖ΘΕΔ৔߹ʹ͸εϨουϩʔΧ ϧͷώʔϓ͔Βղ์ͯ͠Α͍ɽ͜ͷώʔϓ͸ଞͷε ϨουͱಠཱʹճऩՄೳͰ͋Δɽ͜͏ͨ͠ߟ͑ͷݩʹ ͍͔ͭ͘ͷ࣮༻తͳΤεέʔϓղੳͷղੳਫ਼౓ʹͭ ͍ͯൺֱݕ౼͞Ε͍ͯΔ͕ɼείʔϓϩʔΧϧͳΦϒ δΣΫτ୹ण໋ΦϒδΣΫτͷதͷͲΕ͙Β͍ͷׂ߹ Λ઎ΊΔ͔ͱ͍͏໰୊ʹ͸ؔ৺͕෷ΘΕ͍ͯͳ͍ɽ Ruby͸ɼखܰͳΦϒδΣΫτࢦ޲ϓϩάϥϛϯά Λ࣮ݱ͢ΔͨΊͷछʑͷػೳΛ࣋ͭΦϒδΣΫτࢦ޲ εΫϦϓτݴޠͰ͋Δ5)_{ɽڧྗͳςΩετॲཧɼϓϩ} άϥϛϯάΛ༰қʹ͢Δγϯϓϧͳจ๏ͳͲͷಛ௃͕ ͋Γɼۀ຿ɾݚڀ༻్ʹීٴ͖͍ͯͯ͠Δɽ͔͠͠ɼ ݱࡏओʹར༻͞Ε͍ͯΔRubyॲཧܥMRIͷGC͸ ະͩෆे෼Ͱ͋Δɽ

3. ఏ Ҋ ख ๏

ੈ୅ผGC͸୹ण໋ΦϒδΣΫτΛޮ཰తʹճऩ ͠ੑೳ޲্͕ݟࠐΊΔҰํͰɼͦͷίετ΋খ͘͞͸ ͳ͍ɽຊݚڀͰ͸୹ण໋ΦϒδΣΫτʹରͯ͠ʮ୹ण ໋ΦϒδΣΫτ͸ͦͷଟ͕͘είʔϓϩʔΧϧͳΦϒ δΣΫτ͕઎ΊΔͷͰ͸ͳ͍͔ʯͱͷ༧૝Λݕূ͠ɼ ༧૝ʹج͍ͮͨ੩తղੳʹΑΔ୹ण໋ΦϒδΣΫτͷ ճऩख๏ʹ͍ͭͯఏҊ͢Δɽ 3.1 ୹ण໋ΦϒδΣΫτʹؔ͢Δ༧૝ ΞηϯϒϦݴޠ΍CɼC++ͱ͍ͬͨݴޠʹΑΓϓ ϩάϥϜΛهड़͢ΔϓϩάϥϚ͸ม਺΍ؔ਺͕ϝϞϦ தͷͲͷྖҬʹ֨ೲ͞ΕΔ͔ҙࣝ͢Δඞཁ͕͋Δɽ͜ ͷΑ͏ͳϓϩάϥϜͰ͸ɼؔ਺Ҿ਺΍ฦΓ஋ɼҰ࣌ม ਺ͳͲͷण໋͕୹͔͘ϓϩάϥϜͷߏจ͔Βͦͷม਺ ͷࢀর͞Ε͏Δൣғ(είʔϓ)͕ఆ·͍ͬͯΔม਺ ͸௨ৗελοΫྖҬʹ֬อ͞ΕΔɽ Ұํݹ͘͸Lisp͔Β࢝·Δߴڃϓϩάϥϛϯάύ ϥμΠϜʹ͓͍ͯ͸ϓϩάϥϚ͸ม਺΍ؔ਺͕ϝϞϦ தͷͲͷྖҬʹ֨ೲ͞ΕΔ͔ҙࣝ͢Δඞཁ͕ͳ͍ɽ͜ ͷ৔߹ϓϩάϥϚʹ͸ɼશͯͷม਺΍ؔ਺͸ώʔϓʹ ֨ೲ͞ΕɼϓϩάϥϜऴྃ·ͰࢀরͰ͖ΔΦϒδΣΫ τʹݟ͑Δɽ͜ͷΑ͏ʹɼߴڃϓϩάϥϛϯάύϥμ ΠϜʹ͓͍ͯ͸ɼCͳͲͰελοΫྖҬʹҰ࣌తʹอ ͍࣋ͯͨ͠είʔϓϩʔΧϧͳม਺ʹ͍ͭͯ΋ώʔϓ ྖҬʹ֨ೲ͢ΔɽશͯͷΦϒδΣΫτ͕ϓϩάϥϜऴ ྃ࣌·ͰώʔϓྖҬʹଘࡏ͠ଓ͚Δ͔ͷΑ͏ʹݟͤΔ ͨΊʹGC͕ඞཁͱͳΔɽҰൠʹGCͰ͸είʔϓ ϩʔΧϧͳม਺ʹ͍ͭͯ΋ಈతճऩͷର৅ͱ͢Δɽಛ ʹੈ୅ผGCͰ͸ੜଘ཰ͷ௿͍୹ण໋ΦϒδΣΫτʹ ண໨͠ޮ཰తʹճऩ͢Δɽ୹ण໋ΦϒδΣΫτͰ͋Δ ͔Ͳ͏͔͸ಈతʹ൑ఆ͢Δɽ GCʹ͓͍ͯޮ཰ྑ͘ΦϒδΣΫτΛճऩ͢ΔͨΊ ʹ͸ੜଘ཰ͷ௿͍୹ण໋ΦϒδΣΫτͷ൑ผ͕ॏཁͰ ͋ΔɽຊݚڀͰ͸୹ण໋ΦϒδΣΫτͷଟ͘͸είʔ ϓϩʔΧϧͳΦϒδΣΫτͰ͋Δͱͷ༧૝ΛͨͯΔɽ είʔϓϩʔΧϧͳΦϒδΣΫτ͸ϓϩάϥϜͷߏ଄ ͔Βఆ·Γɼ੩తʹ൑ผ͕ՄೳͰ͋Δɽ͜ͷ༧૝͕ਖ਼ ͚͠Ε͹ੜଘ཰ͷ௿͍୹ण໋ΦϒδΣΫτͷଟ͕͘༰ қʹ൑ผͰ͖Δ͜ͱͱͳΓɼGCͷޮ཰ͷ޲্ʹ໾ཱ ͭͱߟ͑ΒΕΔɽ

3.2 ੩తղੳʹΑΔ୹ण໋ΦϒδΣΫτͷ൑ผͱ ճऩ είʔϓϩʔΧϧͳΦϒδΣΫτ͸ϓϩάϥϜΛղ ੳ͢Δ͜ͱͰɼ࣮ߦͤͣͱ΋গͳ͍ίετͰൃݟ͠ɼ ੜ͖͍ͯΔൣғΛௐ΂Δ͜ͱ͕Ͱ͖Δɽͦ͜Ͱϓϩά ϥϜͷ੩తղੳʹΑΓ࣮ߦલʹ୹ण໋ΦϒδΣΫτΛ ൑ผ͠൑ผ͞ΕͨΦϒδΣΫτΛ࢖༻ޙʹճऩ͢Δํ ๏Λࣔ͢ɽ

RubyॲཧܥMRIʹ͓͍ͯɼϓϩάϥϜ͸Ruby

ݴޠͰॻ͘෦෼ͱCݴޠͰॻ͘ϥΠϒϥϦ෦෼͕͋ ΔͷͰɼͦΕͧΕʹ͍ͭͯϩʔΧϧΦϒδΣΫτͷ൑ ผ͓Αͼճऩʹ͍ͭͯड़΂Δɽ ͜ͷख๏͕༗ޮͰ͋Δ͔Ͳ͏͔͸ɼ੩తղੳʹΑΓ ൑ผ͞ΕΔείʔϓϩʔΧϧͳΦϒδΣΫτ͕୹ण໋ ΦϒδΣΫτશମͷଟ͘Λ઎ΊΔͱͷ༧૝ͷଥ౰ੑʹ ґଘ͢Δɽ༧૝ͷݕূ͸࣍ষͰड़΂Δɽ 3.2.1 RubyϓϩάϥϜʹ͓͚ΔϩʔΧϧΦϒδΣ Ϋτ MRI͸ೖྗͨ͠RubyϓϩάϥϜΛҰ୴ߏจ໦ͱ ͯ͠ߏஙͨ͠ޙʹRubyͷVirtual Machine(VM)ͷ όΠτίʔυʹίϯύΠϧ࣮ͯ͠ߦ͢Δɽ௚ྻԽ͞Ε ͨόΠτίʔυ͸໦ߏ଄Λ࣋ͭෳࡶͳߏจ໦ʹൺ΂ ୯७Ͱղੳ͠΍͍ͨ͢ΊɼRubyϓϩάϥϜதʹग़ͯ ͘ΔϩʔΧϧΦϒδΣΫτͷ൑ผɾճऩͳͲ͸όΠτ ίʔυʹରͯ͠ߦ͏ͷ͕ద੾Ͱ͋Δͱߟ͑ΒΕΔɽ όΠτίʔυʹ͓͍ͯϩʔΧϧΦϒδΣΫτ͕Ͳͷ Α͏ʹੜ੒͞ΕΔ͔Λਤ1ͷΑ͏ͳؔ਺strΛྫͱ͠ ͯߟ͑Δɽ͜ͷϓϩάϥϜͷม਺a ɼb ͸ͦΕͧΕ b = a + aɼ"hoge#{b}"ͱ͍͏ԋࢉҎ߱͸࢖༻͞Ε ͳ͍ɽؔ਺strͷίϯύΠϧ݁ՌΛਤ2ʹࣔ͢ɽ0021 ൪஍ͷtostring໋ྩ͸ɼਤ3ͷίʔυͰఆٛ͞Εɼ༩ ͑ΒΕͨΦϒδΣΫτΛจࣈྻԽͯ͠ฦ͢ɽtostring Ͱੜ੒͞ΕͨจࣈྻΦϒδΣΫτ΋0022൪஍ͷ con-catstringsͰར༻͞Εͨޙ͸࢖ΘΕΔ͜ͱ͸ͳ͍ɽ͜ ΕΒͷείʔϓϩʔΧϧͳΦϒδΣΫτ͸୹ण໋Ͱ͋ Δʹ΋ؔΘΒͣ࣍ճGC·Ͱੜ͖࢒Γଓ͚Δɽ ͜ͷΑ͏ʹRubyόΠτίʔυϓϩάϥϜʹ͓͚Δ ϩʔΧϧΦϒδΣΫτ͸ɼਤ1ͷaɼbͷΑ͏ʹϓϩ άϥϚ͕ॻ͘ϓϩάϥϜதʹ໌ࣔతʹग़ݱ͢Δ΋ͷͱɼ ਤ2ͷtostringͰੜ੒͞ΕΔจࣈྻΦϒδΣΫτͷΑ ͏ʹͦ͏Ͱͳ͍΋ͷ͕͋Δ͕ɼ͍ͣΕ΋RubyόΠτ ίʔυίϯύΠϥʹ࣍ͷΑ͏ͳ࠷దԽΛՃ͑Δ͜ͱͰ ରԠͰ͖Δ: ͦΕΒͷΦϒδΣΫτΛ࢖༻ޙʹճऩ͢ ΔίʔυΛ௥Ճ͢Δɼ·ͨ͸ɼΦϒδΣΫτΛελο 1 def str 2 a = 10.0 3 b = a + a 4 return "hoge#{b}" 5 end ਤ 1 ؔ਺ str(Ruby ϓϩάϥϜ) 0000 trace 8 0002 trace 1 0004 putobject 10.0 0006 setlocal a 0008 trace 1 0010 getlocal a 0012 getlocal a 0014 opt_plus 0015 setlocal b 0017 putobject "hoge" 0019 getlocal b 0021 tostring 0022 concatstrings 2 0024 trace 16 0026 leave ਤ 2 ؔ਺ str(Ruby όΠτίʔυ) 1 /** 2 @c put 3 @e to_str 4 @j to_str ͷ݁ՌΛελοΫʹϓογϡ͢Δ 5 */ 6 DEFINE_INSN 7 tostring 8 () 9 (VALUE val) 10 (VALUE val) 11 { 12 val = rb_obj_as_string(val); 13 } ਤ 3 VM ໋ྩ tostring ΫׂΓ౰ͯʹΑΓੜ੒͢Δɽ 3.2.2 CݴޠϥΠϒϥϦʹ͓͚ΔϩʔΧϧΦϒδΣ Ϋτ MRIʹ͓͍ͯϥΠϒϥϦͷଟ͘͸CݴޠʹΑΓه ड़͞Ε͍ͯΔɽϩʔΧϧΦϒδΣΫτͷதʹ͸͜ͷC ݴޠͷϨϕϧͰੜ੒͞Ε͍ͯΔ΋ͷ΋ଟ͋͘Δɽ Ұྫͱͯ͠ਤ4ʹࣔ͢Bignum(ଟഒ௕੔਺)Φϒ δΣΫτͷՃࢉΛఆٛ͢Δؔ਺ rb_big_plus Λͱ Γ͋͛Δɽ͜ͷίʔυதʹग़ͯ͘Δrb int2big͸ɼ Fixnum(ݻఆ௕ͷ੔਺)ΦϒδΣΫτΛҾ਺ͱͯ͠ BignumΦϒδΣΫτΛੜ੒͢Δؔ਺Ͱ͋Δɽ͜ͷ ίʔυͷ৔߹ɼ5ߦ໨Ͱrb_int2big(FIX2LONG(y)); ʹ Α Γ ੜ ੒ ͞ Ε ͨ Φ ϒ δΣΫ τ y ͸ ɼ͜ ͷ ؔ ਺ rb_big_plusͷऴྃޙ͸ΞΫηε͞Εͳ͍͕ɼ࣍ճ GC͕ൃੜ͢Δ·Ͱ͸ώʔϓதʹੜ͖࢒Γଓ͚Δɽ

1 rb_big_plus(VALUE x, VALUE y) 2 { 3 switch (TYPE(y)) { 4 case T_FIXNUM: 5 y = rb_int2big(FIX2LONG(y)); 6 /* fall through */ 7 case T_BIGNUM: 8 return bignorm(bigadd(x, y, 1)); 9 10 case T_FLOAT: 11 return DOUBLE2NUM(rb_big2dbl(x) 12 + RFLOAT_VALUE(y)); 13 14 default: 15 return rb_num_coerce_bin(x, y, ’+’); 16 } 17 }

ਤ 4 Bignum ͷՃࢉϝιουఆٛ rb big plus

ද 1 Ruby ϕϯνϚʔΫϓϩάϥϜͷઆ໌ app_factorial ֊৐ؔ਺Λ࠶ؼతʹ܁Γฦ͢ app_raise ୯७ͳ૊ΈࠐΈྫ֎ͷൃੜͱ ิ଍Λ܁Γฦ͢ so_object ΦϒδΣΫτͷੜ੒Λ܁Γฦ ͢ so_random ුಈখ਺఺਺ͷԋࢉΛ܁Γฦ ͢ app_strconcat ࣜల։ʹΑΓจࣈྻͷ࿈݁Λ ܁Γฦ͢ so_concatenate จࣈྻͷ࿈݁Λ܁Γฦ͢ so_count_words ೖྗ͞ΕͨςΩετͷߦ਺ɼ ୯ޠ਺ɼจࣈ਺ΛΧ΢ϯτ͢ Δ so_exception Ϣʔβఆٛͷྫ֎ͷൃੜͱิ ଍Λ܁Γฦ͢ so_lists ഑ྻʹؔ͢ΔجຊతͳԋࢉΛ ܁Γฦ͢ so_matrix ଟ࣍ݩ഑ྻʹؔ͢Δجຊతͳ ԋࢉΛ܁Γฦ͢ vm2_array ഑ྻϦςϥϧʹΑΓ഑ྻͷੜ ੒Λ܁Γฦ͢ vm3_thread_create_join εϨουͷੜ੒Λ܁Γฦ͢ hoge app_mandelbrot Ϛϯσϧϒϩʔू߹ܭࢉΛ͢ Δ ͜ͷΑ͏ͳ͝ΈΦϒδΣΫτ͸ɼCͷϥΠϒϥϦ ιʔείʔυΛΦϒδΣΫτ࢖༻ޙʹճऩ͢ΔΑ͏ม ߋ͢Δ͔ɼΦϒδΣΫτΛελοΫׂΓ౰ͯʹΑΓੜ ੒͢Δ΋ͷͱ͢ΔɽϓϩάϥϚʹར༻͞ΕΔϥΠϒϥ Ϧ΁ͷ͜ͷΑ͏ͳมߋ͸༧Ίݴޠॲཧܥ࣮૷ʹ૊Έࠐ Ή͜ͱ͕Ͱ͖Δɽ

4. ݕ ূ ࣮ ݧ

͜͜Ͱ͸୹ण໋ΦϒδΣΫτʹؔ͢Δ༧૝ͷݕূ࣮ ݧʹ͍ͭͯํ๏ͱ݁ՌΛड़΂Δɽ 1 def str 2 a = GC.mark_local(10.0) 3 b = GC.mark_local(a + a) 4 return "hoge#{b}" 5 end ਤ 5 ؔ਺ str ͷ Ruby ϓϩάϥϜʹ͓͚ΔϚʔΩϯά 0000 trace 8 0002 trace 1 0004 getinlinecache <ic>, 11 0007 getconstant :GC 0009 setinlinecache 4 0011 putobject 10.0

0013 send :mark_local, 1, nil, 0, <ic> 0019 setlocal a 0021 trace 1 0023 getinlinecache <ic>, 30 0026 getconstant :GC 0028 setinlinecache 23 0030 getlocal a 0032 getlocal a 0034 opt_plus

0035 send :mark_local, 1, nil, 0, <ic> 0041 setlocal b 0043 putobject "hoge" 0045 getlocal b 0047 tostring 0048 concatstrings 2 0050 trace 16 0052 leave ਤ 6 ؔ਺ str ͷ Ruby όΠτίʔυʹ͓͚ΔϚʔΩϯά 4.1 ํ ๏

Ruby Benchmark Suite8)_{ͷ͏ͪද1ʹࣔ͢Ruby}

ϓϩάϥϜʹ͍ͭͯɼखಈͰϩʔΧϧΦϒδΣΫτΛ ϚʔΫͯ͠ΦϒδΣΫτશମʹର͢Δൺ཰Λௐ΂Δɽ ࣮ݧʹ͸MRI 1.9.0-4ʹҎԼͷมߋΛՃ͑ͨ΋ͷΛ༻ ͍ͨɽ • ΦϒδΣΫτʹϩʔΧϧΦϒδΣΫτͰ͋Δ͜ͱ Λࣔ͢৘ใΛ෇͚Δɽ • શΦϒδΣΫτͷੜ੒࣌ࠁɼ͝ΈʹͳΔ࣌ࠁɼϩʔ ΧϧΦϒδΣΫτ৘ใΛه࿥͠ɼදࣔ͢Δɽ RubyϓϩάϥϜʹՃ͑Δมߋʹ͍ͭͯ3.2.1ͷਤ 1ɼਤ2Ͱࣔ͢ϓϩάϥϜΛྫͱͯ͠આ໌͢Δɽੜ੒ ͞ΕΔϩʔΧϧΦϒδΣΫτͷ͏ͪɼRubyϓϩάϥ Ϝʹ໌ࣔతʹग़ݱ͢ΔϩʔΧϧม਺aɼbʹରͯ͠͸ ਤ5ɼਤ6ʹࣔ͢Α͏ʹGC.mark_local_object(x) ͱͯ͠ϚʔΫ͢ΔɽVM໋ྩͷtostringͰੜ੒͞Ε ΔϩʔΧϧΦϒδΣΫτʹରͯ͠͸ਤ7ʹࣔ͢Α͏ʹ tostring໋ྩͷఆٛΛมߋͯ͠ϚʔΫ͢Δɽ CݴޠϥΠϒϥϦʹՃ͑Δมߋ͸ɼྫ͑͹ਤ4ͷϥ ΠϒϥϦͷྫͰ͸ϓϩάϥϜதͷϩʔΧϧΦϒδΣΫ

1 DEFINE_INSN 2 tostring 3 () 4 (VALUE val) 5 (VALUE val) 6 { 7 val = rb_obj_as_string(val); 8 MARK_LOCAL(val); 9 } ਤ 7 VM ໋ྩ tostring ʹ͓͚ΔϚʔΩϯά 1 VALUE 2 rb_big_plus(VALUE x, VALUE y) 3 { 4 switch (TYPE(y)) { 5 case T_FIXNUM: 6 y = rb_int2big(FIX2LONG(y)); 7 MARK_LOCAL(y); 8 /* fall through */ 9 case T_BIGNUM: 10 return bignorm(bigadd(x, y, 1)); 11 12 case T_FLOAT: 13 return DOUBLE2NUM(rb_big2dbl(x) 14 + RFLOAT_VALUE(y)); 15 16 default: 17 return rb_num_coerce_bin(x, y, ’+’); 18 } 19 } ਤ 8 C ݴޠϥΠϒϥϦʹ͓͚ΔϚʔΩϯάͷྫ 0 20 40 60 80 100 0 20 40 60 80 100 collection rate

age at collection [allocation counts]

short-lived objects / all objects local objects / all objects

ਤ 9 app mandelbrot ʹ͓͚ΔΦϒδΣΫτճऩ཰ (ԣ࣠͸Φϒ δΣΫτͷण໋ (age at collection) Λ ruby ͷΞϩέʔγϣ ϯճ਺ (allocatin counts) Λ୯Ґͱͯ͋͠ΒΘ͢) τyʹରͯ͠ਤ8ʹࣔ͢Α͏ʹMARK_LOCALͰϚʔ Ϋ͢Δɽ 4.2 ݁ Ռ ϕ ϯ ν Ϛ ʔ Ϋ ϓ ϩ ά ϥ Ϝ app_mandelbrot ͱ so_count_wordsΛྫͱͯ͠ɼੜ੒͞ΕΔΦϒδΣΫ τͷճऩ཰Λਤ9ɼਤ10ʹࣔ͢ɽԣ࣠͸ΦϒδΣΫτ ͷण໋(age at collection)ΛrubyͷΞϩέʔγϣϯճ

0 20 40 60 80 100 0 20 40 60 80 100 collection rate

age at collection [allocation counts]

short-lived objects / all objects local objects /all objects

ਤ 10 so count words ʹ͓͚ΔΦϒδΣΫτճऩ཰

਺(allocatin counts)Λ୯Ґͱͯ͋͠ΒΘ͢ɽ( ruby

ͷΞϩέʔγϣϯͰ͸جຊతʹ5ϫʔυ֬อ͞ΕΔͷ Ͱɼ1 allocation count = 5 wordͱ׵ࢉͰ͖Δɽ)ॎ ࣠͸͋Δण໋ʹ͓͍ͯͦͷण໋ҎԼͷΦϒδΣΫτͷ ΦϒδΣΫτશମʹର͢Δׂ߹Λ͋ΒΘ͢ɽਤʹ͓͍ ͯɼ࣮ઢ͸ΦϒδΣΫτશମͷճऩ཰ɼഁઢ͸ϩʔΧ ϧΦϒδΣΫτͷճऩ཰Λࣔ͢ɽਤ͔ΒΞϩέʔγϣ ϯճ਺໿20Ͱ΄ͱΜͲશͯͷΦϒδΣΫτ͕͝Έͱ ͳ͍ͬͯΔ͜ͱ͕Θ͔ΔɽଞͷϕϯνϚʔΫʹ͍ͭͯ ΋ಉ༷Ͱ͋Δɽ ਤ11͸ද1ͷϕϯνϚʔΫϓϩάϥϜʹ͓͚Δશ ΦϒδΣΫτதͷ୹ण໋ΦϒδΣΫτͷׂ߹ͱશΦϒ δΣΫτதͷείʔϓϩʔΧϧͳΦϒδΣΫτͷׂ߹ Λࣔ͢ɽ͜͜Ͱ͸100Ξϩέʔγϣϯճ਺ҎԼͰ͝ ΈͱͳΔΦϒδΣΫτΛ୹ण໋ΦϒδΣΫτͱͨ͠ɽ ਤ͔Β΄ͱΜͲͷΦϒδΣΫτ͕୹ण໋ΦϒδΣΫτ Ͱ͋Δ͜ͱ͕Θ͔Δɽ·ͨɼগ਺ͷϓϩάϥϜͰྫ֎ ͸͋Δ͕ɼ୹ण໋ΦϒδΣΫτͷଟ͘Λείʔϓϩʔ ΧϧΦϒδΣΫτ͕઎Ί͍ͯΔ͜ͱ͕Θ͔ΔɽΑͬͯ ʮ୹ण໋ΦϒδΣΫτ͸ͦͷଟ͕͘είʔϓϩʔΧϧ ͳΦϒδΣΫτ͕઎ΊΔͷͰ͸ͳ͍͔ʯͱͷ༧૝͸ݕ ূ͞Εͨͱݴ͑Δɽ

5. ߟ

࡯

࣮ݧ݁Ռ͔Β༧૝ʹ൓͢ΔϕϯνϚʔΫϓϩάϥϜ ΋͍͔ͭ͘ଘࡏ͢ΔɽͦͷݪҼ͸ϩʔΧϧΦϒδΣΫ τͷதͰϚʔΫͰ͖ͳ͔ͬͨ΋ͷ͕ଘࡏ͢ΔͨΊͰ͋ ΔɽͦΕΒϚʔΫͰ͖ͳ͔ͬͨΦϒδΣΫτʹؔͯ͠ ͸ҎԼͷΑ͏ͳཧ༝͕ߟ͑ΒΕΔɽ ( 1 ) ୹ण໋ΦϒδΣΫτͰ͋Γ੩తղੳͷஈ֊Ͱݕ ग़ՄೳͳείʔϓϩʔΧϧΦϒδΣΫτͰ͋Δ

1 2 3 4 5 6 7 8 9 10 11 12 13 0 20 40 60 80 100 short−lived / all local / all 1 app_factorial 2 app_raise 3 so_object 4 so_random 5 app_strconcat 6 so_concatenate 7 so_count_words 8 so_exception 9 so_lists 10 so_matrix 11 vm2_array 12 vm3_thread_create_join 13 app_mandelbrot ਤ 11 ද 1 ͷϕϯνϚʔΫϓϩάϥϜʹ͓͚ΔશΦϒδΣΫτதͷ୹ण໋ΦϒδΣΫτͷׂ߹ ͱશΦϒδΣΫτதͷείʔϓϩʔΧϧͳΦϒδΣΫτͷׂ߹ 1 $a = [] 2 class Float 3 def +(y) 4 $a.push(self) 5 $a.push(y) 6 self 7 end 8 end 9 def str 10 a = 10.0 11 b = a + a 12 return "hoge#{b}" 13 end 14 p str() # "hoge10.0" 15 p $a # [10.0, 10.0] ਤ 12 ϝιουͷ࠶ఆٛͷྫ ͕ɼࠓճͷ࣮ݧͰ͸ϚʔΫ࿙Ε͍ͯ͠Δɽ ( 2 ) Rubyݴޠʹ͓͍ͯ૊ΈࠐΈϝιου͕࠶ఆٛ ՄೳͰ͋Δ͜ͱʹΑΓϩʔΧϧΦϒδΣΫτͰ ͋Δ͔Ͳ͏͔͕Ұҙతʹఆ·Βͳ͍ɽ ( 3 ) ୹ण໋ΦϒδΣΫτͰ͋Δ͕είʔϓϩʔΧϧ Ͱ͸ͳ͍΋ͷ͕ଘࡏ͠ɼೖྗʹΑΓ୹ण໋ʹͳ Δ৔߹ͱ௕ण໋ʹͳΔ৔߹͕͋Γɼ੩తղੳͷ ஈ֊Ͱ͸൑ผෆՄೳͰ͋Δɽ ࠓճͷ࣮ݧͷ৔߹ϩʔΧϧΦϒδΣΫτͷ൑ผͱ ϚʔΩϯά͸खಈͰߦͬͨͨΊɼϚʔΫ࿙Ε͸Ұ൪໨ ͷཧ༝ʹΑΔ΋ͷ͕΄ͱΜͲͰ͋ΓɼࣗಈԽʹΑͬͯ ͜ͷϚʔΫ࿙Ε͸ݮগͰ͖Δͱߟ͑ΒΕΔɽ ͜͜Ͱ͸ೋ൪໨ͷRubyݴޠͷಛघੑʹ͍ͭͯߟ࡯ ͢ΔɽRubyʹ͸ͲΜͳΫϥεʹରͯ͠΋ϝιουͷ ࠶ఆ͕ٛͰ͖Δͱ͍͏ಛ௃͕͋Δɽྫ͑͹ਤ12ʹࣔ ͢Α͏ʹ૊ΈࠐΈΫϥεͰ͋Δුಈখ਺఺਺ͷՃࢉϝ ιουʹ͍ͭͯ΋࠶ఆ͕ٛՄೳͰ͋Δɽؔ਺str͸ਤ 1ͷఆٛͱಉ͕ͩ͡ɼ͜ͷؔ਺strʹ͓͚Δม਺a͸ άϩʔόϧม਺$a͔Βࢀর͞Ε͍ͯΔͨΊείʔϓ ϩʔΧϧΦϒδΣΫτͱ͸ͳΒͳ͍ɽ͜ͷΑ͏ʹ૊Έ ࠐΈͷՃࢉϝιουͰ͸ϩʔΧϧΦϒδΣΫτͱͳΔ ͕ɼ࠶ఆٛ͞ΕͨՃࢉϝιουͰ͸ϩʔΧϧΦϒδΣ ΫτͱͳΒͳ͍৔߹͕͋ΔɽΑͬͯRubyʹ͓͍ͯ੩ తղੳʹΑΔࣗಈճऩΛߦ͏ͨΊʹ͸ɼݪଇͱͯ͠૊ ΈࠐΈϝιουͷ࠶ఆ͕ٛߦΘΕ͍ͯͳ͍΋ͷͱ͠ɼ ࠶ఆ͕ٛߦΘΕͨ৔߹ʹ͸੩తղੳ͕ෆՄೳͰ͋Δͱ ൑அ͢Δඞཁ͕͋Δɽ ࡾ൪໨ͷΑ͏ͳείʔϓϩʔΧϧͰ͸ͳ͍୹ण໋Φ ϒδΣΫτ͸੩తʹ͸൑ผෆՄೳͰ͋Δɽ Ҏ্ͷΑ͏ʹຊख๏Λద༻ͯ͠΋୹ण໋ΦϒδΣΫ τͷશͯ͸੩తʹ൑ผͰ͖ͳ͍ɽ͔͠͠ैདྷͷಈతͳ GCख๏ʹΑΓճऩ͢΂͖ΦϒδΣΫτͷྔ͸ݮগ͢ ΔɽϩʔΧϧΦϒδΣΫτΛ੩తʹղ์͢Δ෼ۭ͖༰

ྔ͕֬อ͞ΕɼGCͷස౓͕ݮΔͨΊੑೳ͸޲্͢Δɽ

6. ͓ Θ Γ ʹ

࣮ݧʹΑΓ୹ण໋ΦϒδΣΫτʹؔ͢Δʮ୹ण໋Φ ϒδΣΫτ͸ͦͷଟ͕͘είʔϓϩʔΧϧͳΦϒδΣ Ϋτ͕઎ΊΔͷͰ͸ͳ͍͔ʯͱͷ༧૝ͷ͔͕֬͞ݕূ ͞Εͨɽࠓޙ͸CݴޠϥΠϒϥϦͷϩʔΧϧΦϒδΣ ΫτͷߋͳΔআڈɼόΠτίʔυͷղੳʹΑΔϩʔΧ ϧΦϒδΣΫτͷࣗಈ൑ผ͓Αͼճऩ͕ߟ͑ΒΕΔɽ

ࢀ ߟ จ ݙ

1) R. E. Jones. Garbage Collection: Algorithms

for Automatic Dynamic Memory Management.

Wiley, Chichester, July 1996.

2) ໦ࢁਅਓ,ࠤݪେี,௡ా޹෉. ΦϒδΣΫτࢦ ޲εΫϦϓτݴޠruby΁ͷੈ୅ผ͝ΈूΊ࣮૷ ख๏ͷվྑͱͦͷධՁ. ৘ใॲཧֶձ࿦จࢽ,ϓ ϩάϥϛϯά, Vol. 43, No. 1, pp. 25–35, 2002. 3) M. Hirzel. Data layouts for object-oriented

programs. SIGMETRICS Perform. Eval. Rev., Vol. 35, No. 1, pp. 265–276, 2007.

4) H.-J. Boehm. Bounding space usage of con-servative garbage collectors. In Conference

Record of the Twenty-ninth Annual ACM Sym-posium on Principles of Programming Lan-guages, ACM SIGPLAN Notices. ACM Press,

January 2002.

5) RubyίϛϡχςΟ.ΦϒδΣΫτࢦ޲εΫϦϓ τݴޠRuby. http://www.ruby-lang.org/ja/. 6) J. McCarthy. Recursive functions of symbolic

expressions and their computation by machine.

Communications of the ACM, Vol. 3, pp. 184–

195, 1960.

7) K. Lee, X. Fang, and S. P. Midkiff. Practical escape analyses: how good are they? In VEE

’07: Proceedings of the 3rd international con-ference on Virtual execution environments, pp.

180–190, New York, NY, USA, 2007. ACM. 8) The Ruby Benchmark Suite Project. Ruby

Benchmark Suite. http://groups.google.com/ group/ruby-benchmark-suite.