スタックベースGCの提案とスクリプト言語Luaにおける評価

情報処理学会

書誌事項

タイトル別名
  • A Proposal of Stack-based Garbage Collection and Its Evaluation in Scripting Language Lua

この論文をさがす

抄録

現在多くのスクリプト言語処理系にGarbage Collection（以降GC）が組み込まれている．GCによる自動メモリ管理はスクリプト言語に大幅な自由を与えるが，処理時間とメモリ使用量が増加し，リソースが限られた環境において動作するビデオゲームのようなアプリケーションでは問題となる．本論文では動的なリージョン操作によりオブジェクトを管理するスタックベースGCを提案し，スクリプト言語処理系に組み込む．リージョンベースメモリ管理とはオブジェクトの確保と解放をリージョンという単位で区切って管理する手法である．オブジェクト領域はGC管理領域に格納されるため，オブジェクトスタックからGC管理領域への移動のコストが小さい．またループごとにリージョンを解放するようにするため，解放されたオブジェクト領域がうまく再利用され，キャッシュによる高速化が見込める．評価実験によりGCが必要なプログラムに対してスタックベースGCはGC処理時間が大きく減少させることが確認できた．またリソースの少ないNintendo-DSにおける評価実験では，従来のGCではリソース不足により正常動作しないプログラムが動作することを確認した．

We propose a new scheme of garbage collection (GC) and present its evaluation results through the implementation of the scripting language Lua. Conventional GC schemes embedded in scrpting language processors are often delayed by long pause times, and programs requiring real-time responses need to be carefully coded. There are currently several types of incremental CGs that solve this problem, but in doing so they sacrifice the GC's throughput. In this paper, we propose a stack-based GC scheme based on Corry's “Optimistic stack allocation for java-like languages.” This scheme prepares a stack that stores objects. The stack frame is segmented per loop and deallocated with fine granularity. The pattern of memory allocations and deallocations has a LIFO structure in which objects that are spatially close and placed temporally close as well, resulting in enhanced efficiency of cache usability caused by the regular pattern of memory accesses. Because memory is deallocated at each end of the loop, the GC cost is easily predicted. A periodically invocated finalizer leads to the fine granular deallocation of resources such as file descriptors. We implemented the proposed GC in a Lua processor and observed that the speed is improved up to 1.67 times more than the conventional GC and that the memory usage is reduced by up to 83%. We ported Lua to a Nintendo-DS and observed that programs unable to run with conventional GC can be executed with the stack-based GC.

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1050001337899413888
  • NII論文ID
    110007970945
  • NII書誌ID
    AA11464814
  • ISSN
    18827802
  • Web Site
    http://id.nii.ac.jp/1001/00071437/
  • 本文言語コード
    ja
  • 資料種別
    article
  • データソース種別
    • IRDB
    • CiNii Articles

問題の指摘

ページトップへ