日本ソフトウェア科学会第 37 回大会 (2020 年度) 講演論文集

他言語関数呼び出しにおける遠慮のかたまり問題の解決に向けたオブジェクトグラフの解析
山崎 徹郎

千葉 滋

新規に開発されるプログラミング言語はコード資源を持たないため，別の言語で実装されたライブラリを呼び出す他言語関数呼び出し (Foreign Function Call) は重要な機能である．他言語関数呼び出しではその引数や返り値は相手側のデータであるため，言語処理系の境界をまたぐリモート参照がしばしば作られる．呼び出し元である新言語と呼び出し先である既存言語がそれぞれ異なる方法でガベージコレクションを行う場合，このリモート参照の存在が問題となる．例えば新言語と既存言語の両方の領域をまたぐ循環参照は回収が困難である．この種のメモリリークはコレクタ同士が回収を譲り合った結果生じるように見えるため，我々は遠慮のかたまりと呼んでいる．本発表ではこの遠慮のかたまり問題への対策を論じる．アプリケーションとして新言語からの他言語関数呼び出しを想定するため，既存言語は処理系を改造しないものとする．

Since a newly implemented programming language has no code resources, foreign function call which enables
programmars to call libraries implemented in other language is an important feature. Foreign function calls
often create remote references which reference to objects in other language to pass arguments or receive
results those are data in the other language. Remote references are problematic if both caller and callee
languages supports garbage collection. For example, it is hard to collect cyclic references that go throughboth languages. We call this kind of memory leaks “the last piece of cake” since they seems to occur as aresult of hesitance between collectors. In this paper, we present an approach to the last piece of cake problem. Since we suppose foreign function call as the application, we avoid customizing an existing language
system.

によってはグラフィックスライブラリを標準としてサ

1 はじめにポートしていないため，Ruby や Haskell などの言語

近年では多様なプログラミング言語が利用可能でではグラフィカルなプログラムを作成するために Cある．そのため，しばしば複数のプログラミング言語バインディングを利用する．

が連携動作するアプリケーションが開発される．例

ある言語から他の言語で定義された関数を呼び出す

えば web アプリケーションではサーバーサイドとク仕組みを Foreign Function Interface (FFI) という．

ライアントサイドをそれぞれ異なるプログラミング

従来では C 言語との間の FFI さえあればよかった言語で開発することは珍しくない．また機械学習でが，近年では Python や Javascript のようなスクリは広く Python が使用されるが，その主要な計算はプト言語が人気であるため，これらの言語との間のしばしば C 言語で実装される．プログラミング言語

FFI が注目されている．また近年では多くの言語がガベージコレクションによる自動メモリ管理を行う．

∗ A method for object graph analysis toward solving

Python も Javascript もガベージコレクションによっthe last piece of cake problem in foreign function
call.
This is an unrefereed paper. Copyrights belong tothe Author(s).
Tetsuro Yamazaki, Shigeru Chiba, 東京大学情報理工学系研究科, Graduate School of Information Scienceand Technology, The University of Tokyo.て自動的にメモリを管理する．
ガベージコレクションを備えた言語の間の FFI では，ガベージコレクタの間の連携が課題の一つとして挙げられる．ガベージコレクタはふつう言語ごとに開発され，自言語のオブジェクトだけを管理する．しかし FFI のように複数の言語処理系が連携動作する場
合，特に他言語のオブジェクトを直接参照するリモー
ト参照が多用される場合，自言語内の情報だけではオブジェクトの生死を正確に判定することができない．
到達不可能であるオブジェクトをしかし回収しなければメモリリークとなり，到達可能であるオブジェクトを誤って回収してしまうとメモリエラーの原因となり，最悪の場合処理系がクラッシュすることもある．

ソースコード 1 Ruby から Javascript を呼び出す例
1 require ’ jscall ’
2 document = JSCall . eval ( ’ document ’)
3 button= document . getEl ementB yId ( ’button ’)
4 message= document . getEle mentB yId (’ message ’)
5 button . onclick = proc do6message . innerText = ’ click ’
7 end

FFI のためのガベージコレクションでは，ガベージコレクタの改造もまた課題の一つである．FFI は

以下，2 章で FFI 環境下でガベージコレクタ同士すでに存在する言語で定義された関数を呼び出す仕の連携が失敗した場合なにが起きるのかを示し，3 章組みであるため，その言語のガベージコレクタもまたでガベージコレクタ同士で情報共有する方法を提案

すでに存在している．ガベージコレクタは複雑なプロする．4 章では関連研究を示し，5 章でまとめる．

グラムであり，改造するにしても一から作り直すにしても多大な労力が必要である．なるべく既存のコレクタは改造せずに再利用できることが望ましい．

2 Foreign Function Interface と分散ガベージコレクション

我々は FFI のためのガベージコレクションアルゴ

あるプログラムから別の言語で記述された関数をリズムとして，ガベージコレクタの改造を最小限に生呼び出す仕組みを Foregin Function Interface (以下死判定の精度を向上させる手法を提案する．我々のアFFI) という．新しく開発された言語はライブラリ資源

イデアは一方の言語のオブジェクト同士の参照関係を持たないため，FFI のように他言語のライブラリにを，そのままもう一方の言語のオブジェクト同士の参アクセスする仕組みは重要である．従来の FFI は Java照関係として再現するというものである．ガベージコ

Native Interface [9] や libﬃ [2]，Python ctypes [6]レクタ間の連携の失敗はどのコレクタも部分的な情のように C 言語のライブラリを呼び出すことがで報しか持たないために正確な生死判定ができないこきれば十分であった．しかし近年では C 言語だけとが原因であるため，相手側のオブジェクトの参照関でなく PyCall [7] や PyV8 [1] のように Python や係として全ての情報を再現したなら相手側のコレク

Javascript のライブラリを呼び出す FFI も注目を集

タは通常通りのトレースだけで改造なしに正確な生めている．

死判定を行うことができる．このアイデアをベース

例えば我々が開発している Ruby から Javascriptに，コピーする参照関係を必要最小限に圧縮するこを呼び出す FFI を使用するとソースコード 1 のよとで性能を向上させる．我々のアルゴリズムはヒープうなプログラムを作成することができる．このプロの解析に bloom filter [4] を使用する．Bloom filter

グラムはウェブページのボタンがクリックされたとは偽陽性があるため得られる情報には誤りが含まれ，き，メッセージを “click” に設定する．2 行目では100% 正確な生死判定はできない．この誤りの影響に

JSCall.eval 関数によって，文字列 ’document’ をついては 3. 3 節で詳しく触れる．

Javascript の式として評価する．’document’ の評価

我々のアルゴリズムは２ノードの場合を主に想定

結果は Javascript の HTMLDocument オブジェクトでするが，３ノード以上のケースにも適用可能である．

あるため，Ruby から Javascript のオブジェクトを我々の手法では無改造で済むガベージコレクタはた参照するリモート参照が作成される．document のよだ１つだけであり，それ以外のコレクタは全て改造

うにリモート参照によって参照されるオブジェクトする必要がある．３ノード以上のケースについてはを公開オブジェクトと呼ぶ．3 行目では document の3. 2 節で詳しく触れる．

メソッドを呼び出す．このメソッド呼び出しは参照

先である HTMLDocument オブジェクトへと転送され，ジコレクションのように，ガベージコレクタ同士の連Javascript のメソッド呼び出しとして計算される．5

携が課題の一つである．分散環境ではマシンごとに行目では Javascript のオブジェクトである button

メモリ領域も計算資源も分割されているため，マシに onclick コールバックとして Proc オブジェクト

ンごとのローカルコレクタは自領域の情報しか持たを登録する．Proc は Ruby のオブジェクトであるたず，やはりオブジェクトの生死判定を正確に行うこと

め，実際に登録されるコールバック関数は Javascriptはできない．分散ガベージコレクションではローカルから Ruby の Proc オブジェクトを指すリモート参コレクがが収集した情報をグローバルコレクタが分照である．

配することで正確な生死判定を可能とする．我々の知Ruby から Javascript を呼び出す場合のように，る限りでは，既存のコレクタをローカルコレクタとFFI によって連携動作する２つの言語がそれぞれ異して無改造にに再利用できる分散ガベージコレクショなる方法でガベージコレクションを行う場合，コレクンアルゴリズムは知られていない．

タ同士の連携が一つの課題である．ガベージコレクタはふつう言語処理系の一部として実装されるため，自FFI の素朴な実装とメモリリーク言語が管理するメモリ領域の情報しか持たない．しか複数のガベージコレクタが連携動作するアプリケー

し FFI のように複数の言語が連携動作する場合，特ションでは，コレクタ同士の連携に失敗するとメモリに言語の境界をまたぐリモート参照が多用される場リークやメモリエラーが起きることがある．本節では合，自領域の部分的な情報だけではオブジェクトの生コレクタ同士の連携の失敗によって引き起こされる死を正確に判定することができない．オブジェクトがメモリリークの一例を示す．まず素朴な FFI として到達不可能であるにもかかわらず回収できないこと

eval 関数とリモート参照の２つのインターフェースによるメモリリークや，オブジェクトが到達可能であを持つ FFI の設計を示す．そして素朴な FFI ではリるにもかかわらず誤って回収してしまうことによるメモート参照がガベージコレクタによってどう管理されモリエラーが起きる可能性がある．どのようにしてメるかを示し，その後メモリリークの例を示す．

モリリークが起きるのかについては 2 節に詳しい．

FFI の素朴な実装方法として全ての公開オブジェ

FFI のためのガベージコレクションではガベージクトを含むテーブルを用意する方法を考える．このコレクタの改造もまた課題の一つである．FFI はす

テーブルを公開テーブルと呼ぶ．公開テーブルは公でに存在している言語で実装された関数を呼び出す

開 ID から公開オブジェクトへのマッピングである．

ため，その言語のガベージコレクタもまたすでに存在オブジェクトが公開テーブルに登録されるたびに一している．しかしガベージコレクタは非常に複雑なプ意の公開 ID を生成する．両方の言語が公開テーブルログラムであるため，改造するにしても一から作り直を用意する．eval 関数は引数として式を表す文字列すにしても多大な労力を必要とする．例えば ruby のを受け取り，相手側言語の式として評価しその結果をガベージコレクタは 12,000 行からなる巨大なプログ返す．式を評価する間，自言語の実行はブロックされラムである．ガベージコレクタの誤作動によるメモる．評価結果が文字列や数値のようなプリミティブなリエラーは原因の特定が難しく，また再現性も低く，値だった場合は自言語の対応する値に変換し，そうでデバッグが困難なバグの１つである．また改造が誤りなかった場合はリモート参照を作成し返却する．リを含む可能性もあるため，既存ライブラリの動作が保モート参照はプロキシオブジェクトの形で実現する．

証できなくなる問題もある．FFI のためのガベージ

相手側言語のオブジェクトを直接指すリモート参照を

コレクションではコレクタの改造を最小限に，可能で本当に作成してしまうと問題があるため，代わりに相あれば一方のコレクタを無改造に済ませることが望

手側オブジェクトのようにふるまうプロキシオブジェ

ましい．

クトを作成し，リモート参照は直接相手側言語のオブ分散ガベージコレクション [10] では FFI のガベージェクトを参照せず，代わりにプロキシオブジェクトを参照する．プロキシオブジェクトはフィールドやメソッドが参照された場合，内部的に eval 関数を呼び3 提案手法

出すことで参照先オブジェクトのフィールド参照やメ我々は参照関係情報を共有することでガベージコソッド呼び出しを計算し，その結果を返す．プロキシ

レクタの改造を最小限にリモート参照を含む循環参オブジェクトは参照先オブジェクトを特定するため，照 (遠慮のかたまり) を回収可能にする手法を提案す

参照先オブジェクトの公開 ID を記憶する．公開テーる．提案するアルゴリズムは遠慮のかたまりを回収す

ブルに登録されていないオブジェクトは参照できなることに特化した，バックアップ用のガベージコレク

い．プロキシオブジェクトのメソッドに渡された引数ションである．領域ごとの通常のガベージコレクショは，プリミティブな値なら対応する値に変換し，そうンは別途行う．以下では 2 章で示した方法で実装さでなければリモート参照を作成し，参照先オブジェクれた素朴な FFI を仮定する．

トのメソッドに渡す．

我々の基本的なアイデアはメモリ領域 A に存在す

この素朴な FFI において，ガベージコレクタがリるオブジェクトの参照関係を全て，もう一方のメモリモート参照をどう扱うかを示す．公開テーブルはプロ

領域 B にコピーすることである．そうすることでメグラムと同じ寿命を持つグローバルオブジェクトでモリ領域 B を管理するコレクタは全ての参照関係をある．公開テーブルから公開オブジェクトへの参照は辿ることが可能となり，正確なオブジェクトの生死判強参照であるため，公開オブジェクトは基本的には回定が可能となる．このとき，メモリ領域 B を管理す収されない．公開オブジェクトはいつリモート参照をるコレクタの改造は不要である．メモリ領域 B の到経由して参照されるかわからないため，公開オブジェ達不能オブジェクトが回収されたならば，遠慮のかクトが回収されない実装は保守的であり，特別変な実たまりはその一部が回収され循環ではなくなるため，装ではない．一方プロキシオブジェクトは，通常のオ残りも通常のガベージコレクションによる回収が可能

ブジェクトと同様にガベージコレクションによって回となる．

収される．プロキシオブジェクトにファイナライザを本当に全てのオブジェクトをコピーしてしまうとム設定することで，回収されたプロキシオブジェクトのダなので，必要最小限だけをコピーする．正確な生死参照先オブジェクトの公開を停止することができる．

判定のために必要な情報は領域 A・B 両方を含んだ

リモート参照が回収された公開オブジェクトはもはやオブジェクトの参照関係である．そのため，メモリ領公開オブジェクトではないため，公開テーブルから削域 B を管理するコレクタに不足している情報はメモ除することでガベージコレクションによる回収が可能

リ領域 A を経由することでどのプロキシオブジェクとなる．この素朴な FFI ライブラリのガベージコレ

トからどの公開オブジェクトを参照可能であるか，そクタは公開オブジェクトの回収を，リモート参照が回の参照関係である．これはメモリ領域 A を管理する収されるまで保留する．

もう一つのコレクタから見ると，メモリ領域 A の中上で示した公開テーブルによる FFI の実装では，で，メモリ領域 B を経由せずに，どの公開オブジェ公開オブジェクトのガベージコレクションは参照カウクトからどのプロキシオブジェクトが参照可能であント [5] の一種である．リモート参照の数をカウントるかの参照関係である．Tracing Garbage Collection

し，その数が０であった場合は公開オブジェクトの公のマークフェイズのような計算によって調べることが開を停止し，回収可能にする．そのため，参照カウンできる．

トと同様に循環参照を回収することができない．この

我々の提案するガベージコレクションはストップ・

種類のメモリリークはコレクタ同士が回収を譲り合っザ・ワールド方式である．ガベージコレクションを始た結果に見えるため，遠慮のかたまりと呼ぶことにめる前に両方の言語処理系の計算を停止し，ガベーする．

ジコレクションの全てのフェイズが完了した後に計算を再開する．これはユーザースレッドがガベージコ

単純なアルゴリズムを採用した．アルゴリズムの外観
1234567891011121314

ソースコード 2 参照関係情報の収集
stack := ϕfor public domark ( public ) <- { public }push ( stack , public )end
while stack != ϕ doc <- pop ( stack )for n ← pointers ( cur )if mark ( c ) \ not \ subseteq mark ( n )thenmark ( n ) <- mark ( c ) \ cup mark ( n )push ( stack , n )
end
end
end

をソースコード 2 に示す．
各オブジェクトが記憶するマーク (集合) のデータ表現として bloom filter [4] を採用する．集合はやや大きなデータ構造であり，オブジェクトの数だけ用意するとなるとかなりの量のメモリが必要となる．

Bloom filter は任意個の要素からなる集合を固定長のビット数で表現できるデータ構造であるため，オブジェクトごとに 32 ビットか 64 ビット程度の領域を追加で用意すればそれで済む．Bloom filter の欠点は偽陽性があることである．Bloom filter の包含判定は，本当はその要素が含まれていなかったとしても包レクションの不変条件を破ることを防ぐためである．

含すると判定する場合がある．これは我々の手法でユーザースレッドと並列実行可能なガベージコレクは，本当は到達できないオブジェクト同士が誤って到ションも研究されているが，これらはライトバリアや達可能であると判定されるためにメモリリークが起リードバリアが必要である．言語処理系はしばしばきる可能性があることを意味する．偽陽性についてはライトバリア・リードバリアを実装していないため，3. 3 で議論する．

コレクタの改造が必要となる．ワールドストップもま収集した参照関係情報をもう一方の言語に送信し，た，コレクタの改造を必要とする機能である．しかオブジェクト同士の参照関係として再現する．参照

し Ruby，Python のようにグローバル・インタプリ

関係はメモリ領域 A を経由することでどのプロキシタ・ロックを持つ言語や，Javascript のようにシングオブジェクトからどの公開オブジェクトが参照可能でルスレッドで計算する言語であれば改造なしにワールあるかの情報である．プロキシオブジェクトの隠しドストップすることができる．

フィールドとして配列のような可変長のデータを用意し，領域 A を経由することで参照可能な公開オブ

3. 1 アルゴリズム

ジェクトへの参照を格納する．反映が完了した後であ

我々の手法は参照関係情報の取得と，参照関係情報れば正確なオブジェクトの生死判定が可能であるたの反映の２つのステップがある．参照関係情報を取得

め，公開テーブルから各公開オブジェクトへの参照をするために tracing garbage collection のマークフェ弱参照に変更し，通常通りのローカルガベージコレクイズのような計算を行う．通常マークフェイズでは，ションを行う．ローカルガベージコレクションによっオブジェクトに生死を表す 1 ビットのマークを記憶てプロキシオブジェクトが回収された場合ファイナラさせ，ルートセットから深さ (または幅) 優先探索をイザが起動するため，公開テーブルの対応するエント行うことで生死情報を伝搬させる．我々の手法では，リは削除される．ただし，領域 A でルートから到達それぞれのオブジェクトがどの公開オブジェクトから可能である公開オブジェクトは公開テーブルからの参参照可能であるかを調べる．そのため，それぞれのオ照を強参照のままにする．

ブジェクトが記憶するマークはそのオブジェクトを参通常のガベージコレクションが完了した後は公開照可能である公開オブジェクトの集合である．マーク

テーブルから公開オブジェクトへの参照を強参照に戻が真偽の２値ではなくなったため，探索も単純な深さし，ワールドストップを解除する．遠慮のかたまりが(または幅) 優先探索ではうまくいかない．同じマー存在していたならば，そのメモリ領域 B に属する部

クが少しずつ繰り返し更新される可能性があるため分は回収され循環ではなくなっているので，残りは通である．我々はマークが更新される限り探索を続ける

常のガベージコレクションで回収することができる．

ユーザースレッドによってメモリ領域 A のオブジェクトが変更された場合，収集した参照情報と実際のメモリ領域 A との間の整合性が失われてしまう．整合性が失われると参照可能なオブジェクトが誤って回収されてしまう恐れがあるため，公開オブジェクトへの参照を強参照に戻すまで両言語のワールドストップは解除しない．

3. 2 ３ノード以上の環境への適用

1234567891011

ソースコード 3 ハッシュ関数
uint64_t seed ;void hash ( uint64_t * result , int n ,uint64_t x ) {uint64_t h = x ^ seed ;for ( int i = 0; i < n ; i ++) {h = ne xt _ xo r sh if t _1 ( h );result [ i ] = h ;}}void update_seed () {seed = n e xt _ xo rs h if t_ 2 ( seed );}3. 1 節で示したアルゴリズムは２言語間の FFI に特化していた．我々の手法は３言語以上の環境にも適ンだけで回収可能である．最後にワールドストップを用可能である．本節ではその方法のスケッチを示す．

解除する．

３つの言語をそれぞれ A, B, C とする．まず A, B,

このように全ての言語に順序を与え，順序がより先C 全ての言語をワールドストップする．次に言語 Aの言語は自身より順序が後である全ての言語に参照の参照関係情報を収集し，収集した情報を言語 B と関係情報を送信することで，３ノード以上の環境でも言語 C との両方に送信する．言語 B には言語 A を遠慮のかたまりを回収することが可能である．この方経由することで言語 B のどのプロキシからどの公開法では，改造が不要であるコレクタは順序が最後であオブジェクトに到達可能であるかを，言語 C には言るコレクタ１つだけである．

語 A を経由することで言語 C のどのプロキシからどの公開オブジェクトに到達可能であるかをそれぞれ

3. 3 議論: bloom filter の偽陽性送信する．

Bloom filter [4] は，本来集合に含まれていない要

言語 B，言語 C それぞれで言語 A から受信した素でも誤って集合に含まれると判定してしまう場合が参照関係情報を反映する．この時点で言語 A と 言語ある．この性質を疑陽性という．これは我々の手法でB をまたぐ循環参照と言語 A と言語 C をまたぐ循

は，本来到達不可能であるオブジェクト同士が誤って環参照は回収できるが，言語 B と言語 C をまたぐ循

到達可能であると判定されることによるメモリリー

環参照，および言語 A，B，C の全てをまたぐ循環参

クの可能性があることを意味する．一方で，bloom

照は回収できない．

filter に偽陰性はない．これは我々の手法では，到達次に言語 B の参照関係情報を収集し，収集した情可能なオブジェクトを誤って到達不可能であるとみな報を言語 C に送信し，反映する．この時点で言語 Cしてしまうことはないことを意味する．そのため，偽のコレクタは全ての参照関係を調べることができる．

陽性のために回収できないオブジェクトは存在しうる

そのため，全ての循環参照の言語 C に属する部分がが，偽陰性のためにオブジェクトを誤回収し，メモリ回収可能である．言語 C のローカルコレクタを起動エラーを起こしてしまうことはない．

して言語 C の到達不能オブジェクトを回収する．言偽陽の発生率は bloom filter のビット数と公開オ

語 C のローカルガベージコレクションでは言語 A とブジェクトの数に依存する．また，公開オブジェクト

言語 B をまたぐ，言語 C を経由しない循環参照は回とプロキシの間の参照関係が密であるほうが偽陽の収されない．

確率が増す．公開オブジェクトの数が一定数を超える

次に言語 B のローカルコレクタを起動して言語 Bと遠慮のかたまりの回収効率が大幅に低下するため，の到達不能オブジェクトを回収する．このガベージコアプリケーションに合わせた bloom filter のチューレクションによって全ての循環参照は，少なくとも一ニングが重要である．

部が回収される．残りはローカルガベージコレクショ

Bloom filter が使用するハッシュ関数をガベージコレクションごとにランダムに変化させることで，同じ較的我々の手法と似ている．しかしこれらの手法では組み合わせによる偽陽を避け，確率的に回収されるよ

部分的にしかオブジェクトを移動しないため遠慮のかうにすることは可能である．我々が使用したハッシュたまりが回収できず，逆にメモリ消費が悪化する場合

関数をソースコード 3 に示す．ハッシュ関数の内部状がある．

態を 64 ビット整数 seed で表現する．n 種類のハッ

ウェブブラウザでは，Javascript エンジンとレンダシュ関数を使用する bloom filter を考える．あるオラの間で遠慮のかたまりが問題となるようである．例

ブジェクトの n 種類のハッシュ値はそのオブジェク

えば Google Chrome では V8 と Blink の間で循環参トのアドレスと seed の xor を起点に，xorshift [8]照が問題となるため，cross-component tracing ?[] とを n − 1 回適用することで取得する．ガベージコレいう手法が提案されている．Cross-component trac-クションが終わるたびに seed を xorshift で更新すing ではそれぞれのコレクタが自身が管理するメモリる．ハッシュの計算に使用するものと内部状態の更新領域を走査する方法を公開する．どのコレクタも他のに使用するものの２つの xorshift は互いに異なるパ領域を調べてオブジェクトの生死判定を行うことがでラメータのものを使用する．

きるため，オブジェクトの生死判定を正確に行うことができる．この手法でもやはり両方のコレクタの改造

4 関連研究が必要となる．

FFI 環境下で遠慮のかたまりが回収できない問題
は，公開オブジェクトを参照カウント方式で管理す5 まとめることが原因である．Recycler [3] は参照カウント方

本稿では FFI のためのガベージコレクションアル式でありながら循環参照を回収することができるガゴリズムを提案した．このアルゴリズムの特徴は一方ベージコレクタである．Recycler が循環参照を回収の言語のガベージコレクタとして既存のコレクタをするテクニックは試験的削除 (trial deletion) と呼ば再利用し，改造を必要としないことである．ベースとれる．到達不可能であると思われるオブジェクト内のなるアイデアは一方の言語のオブジェクトの参照関係参照を試験的に削除し，その結果自身の参照カウンからなるグラフをもう一方の言語のオブジェクトの間トが 0 になった場合はそのオブジェクトは循環参照の参照関係として再現することで，無改造のコレクタゴミの一部であるとして回収するという方法である．

でも全ての参照関係を調べることができるというも試験的削除を FFI 環境に適用することは可能であるのであった．

が，両方のコレクタの改造が必要となる．また試験的我々の手法は内部的に bloom filter を利用するた削除による参照カウントの増減は言語の境界を越えめ，全ての遠慮のかたまりを回収できない場合があて波及するため，一度の試験的削除によって言語間のる．Bloom filter によってどれだけのメモリが削減で通信が複数回必要になる場合がある．言語間の通信がきるのか，偽陽性によってメモリ消費はどの程度増加

ボトルネックであるような場合に性能が悪化するかもするのか，我々のアルゴリズムはどのくらいの停止時しれないという懸念もある．

間を要求するのかなどの実験による評価は今後の課

メモリが分割された環境でのガベージコレクション題である．という観点では，分散ガベージコレクションとも類似

我々の手法はストップ・ザ・ワールド方式である．

点が見られる．しかし我々の知る分散ガベージコレク

ガベージコレクションが完了するまでユーザープログ

ションでは，通信のエラーがガベージコレクションをラムの計算を停止させる．インクリメンタル，あるい壊さないという耐障害性が問題意識として大きく扱

はコンカレントな手法で停止時間を削減することはわれており，遠慮のかたまりの回収や実装の簡単化に挑戦的な課題である．

取り組んだ研究は多くない．その中でも [11] はオブ

また我々の手法は 3 言語以上の FFI にも適用可能

ジェクトを領域間で移動させるアプローチであり，比であるが，その停止時間は増加する．また，無改造で済むコレクタはただ１つだけである．２つ以上のコレクタを無改造に済ます方法もまた，挑戦的な課題である．

参 考 文 献[ 1 ] : Google Code Archive - pyv8, https://code.
google.com/archive/p/pyv8/.
[ 2 ] : libﬃ, https://sourceware.org/libffi/.
[ 3 ] Bacon, D. and Rajan, V.: Concurrent Cycle Collection in Reference Counted Systems, 08 2002.
[ 4 ] Bloom, B. H.: Space/Time Trade-Oﬀs in Hash
Coding with Allowable Errors, Commun. ACM,Vol. 13, No. 7(1970), pp. 422426.
[ 5 ] Collins, G. E.: A Method for Overlappingand Erasure of Lists, Commun. ACM, Vol. 3,No. 12(1960), pp. 655657.

[ 6 ] Foundation, P. S.: Python Documentation,
https://docs.python.org/ja/3/library/ctypes.html.
[ 7 ] Johonson, S. G.: Calling Python functions fromthe Julia language, https://github.com/JuliaPy/PyCall.jl.
[ 8 ] Marsaglia, G.: Xorshift RNGs, Journal of Statistical Software, Articles, Vol. 8, No. 14(2003),pp. 1–6.
[ 9 ] Oracle: Java Documentation - Java Native Interface 仕様の目次, https://docs.oracle.com/javase/jp/8/docs/technotes/guides/jni/spec/jniTOC.html.
[10] Plainfossé, D. and Shapiro, M.: A Survey ofDistributed Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, IWMM 95, Berlin, Heidelberg,
Springer-Verlag, 1995, pp. 211249.
[11] Vestal, S. C.: Garbage Collection: An Exercise
in Distributed, Fault-Tolerant Programming, PhD
Thesis, USA, 1987.