👑

Nimのメモリ管理を理解する④ ― ORC - アルゴリズムによるアドバンテージ

2023/02/14に公開

Nim

メモリ管理

idea

Nimのメモリ管理を理解するシリーズ、4作目はORCについてのこちらの記事を翻訳します。

〜Nimのメモリ管理を理解するシリーズ〜

バージョン1.4では、いわゆるORCメモリ管理アルゴリズムが同梱されています。ORCは、既存のARCアルゴリズム（バージョン1.2で初搭載）にサイクルコレクタを追加したものです。名前の由来もそこからで、「O」はサイクルを、「RC」は「参照カウント」を表し、このアルゴリズムの基礎となっています。

サイクルコレクタは、Linsらによるかなり有名な「trial deletion」アルゴリズムがベースになっています。このアルゴリズムがどのように機能するかはここでは説明しません。良い説明は論文を読んでください。

※訳者注：
原文にある論文へのURLはリンク切れになっていた。"Bacon01Concurrent"という論文なのだが、このアルゴリズムはPHPにも入っているようで、こちらのスライドでこのアルゴリズムについて見ることができる。
https://www.slideshare.net/y-uti/php-gc

いつものように、私はこのアルゴリズムを改良し、より多くの最適化を加えたいという誘惑に抗えませんでした。Nimコンパイラは関係する型を分析し、潜在的に循環参照になっている場合のみ、サイクルコレクタを呼び出すコードを生成します。この型解析は、型にasyclic と注釈をつけることで助けられています。例えば、二分木は次のようにモデル化されます。

type
  Node {.acyclic.} = ref object
    kids: array[2, Node]
    data: string

サイクルコレクタのオーバーヘッドは実際に測定可能です。ORCの性能をARCに近づけるためには、このアノテーションが欠かせません。

ORCの設計の革新的な点は、周期的ルート候補を定数時間O(1)で登録・解除できることです。その結果、実行時にNimのデータがほとんど周期的でないという事実を利用することができます。

ARC

ARCはNimの純粋な参照カウントGCですが、多くの参照カウント操作が最適化されています。ムーブセマンティクスのおかげで、データ構造の構築には参照カウントの操作が不要です。またNimのARC実装のもう一つの特徴である「カーソル推論」のおかげで、一般的なデータ構造のトラバーサルも参照カウント操作に関係しないのです。ARCとORCの性能は、ヒープサイズに依存しません。

ベンチマーク

このアルゴリズムの違いを示す簡単なベンチマークを作成しました。このベンチマークは、ORCとNimの他のGCの違いを強調するために書かれたもので、現実的なワークロードをモデル化するものではないことに注意してください。

import asynchttpserver, asyncdispatch, strutils, json, tables, streams

# 約135MBのデータ:
var sessions: Table[string, JsonNode]
for i in 0 ..< 10:
  sessions[$i] = parseJson(newFileStream("1.json", fmRead), "1.json")

var served = 0

var server = newAsyncHttpServer() # 10行目
proc cb(req: Request) {.async.} =
  inc served
  await req.respond(Http200, "Hello World")
  if served mod 10 == 0:
    when not defined(memForSpeed):
      GC_fullCollect()

waitFor server.serve(Port(8080), cb) # 18行目

10行目から18行目は、Nim標準ライブラリを使った"Hello World”を返す非同期HTTPサーバーの例です。

4～6行目では、約135MBのJSONデータをグローバル変数sessionsにロードしています。ORCは、このメモリがロードされた後、プログラム実行の残りの間、それが生きているにもかかわらず、決してこのメモリに触れません。古いNimのGCは、このメモリに触れる必要があるのです。このベンチマークでは、マーク&スイープが最も良いパフォーマンスを示したので、ORCをNimの「マーク＆スイープ」GC（M&S）と比較しています。

GC_fullCollectは、プログラムが理論上必要とする135MBのRAMに近いメモリ消費を維持するために、頻繁に呼び出されます。

wrk ベンチマークツールを使って、以下のような結果が得られました。

Metric / algorithm	ORC	M&S
Latency (Avg)	320.49 us	65.31 ms
Latency (Max)	6.24 ms	204.79 ms
Requests/sec	30963.96	282.69
Transfer/sec	1.48 MB	13.80 KB
Max memory	137 MiB	153 MiB

M&Sはスループットでは勝っているが、レイテンシでは勝っていません。しかし、メモリ消費量は約330MBに増加し、プログラムが実際に必要とするメモリの2倍以上になってしまいました。

ORCはレイテンシとメモリ消費量において常に優位に立ち、デストラクタとうまく協調し、したがってカスタムメモリ管理もうまくいき、ヒープサイズに依存せず、スタックルートを正確に追跡し、C/C++エコシステムが提供するすべてのサニタイザでクリーンに動作します。

これらの結果は、他のプログラムで見られる典型的なものです。遅延は減少し、ジッターはほとんどなく、メモリ消費量はプログラムが必要とする最小値に近いままです。組み込み開発には最適な結果です

GCの研究では見落とされていたアイデアがたくさんあることが分かりましたので、サイクル収集アルゴリズム自体もさらに進化させていく予定です。Nimにとってエキサイティングな時代です。

まとめ

ORCを使ってコンパイルするには、コマンドラインで--gc:orc を使用します。

ORCは、Valgrindや他のC++サニタイザーと連携して動作できます。(Valgrindを正確にチェックするために --gc:orc -g -d:useMalloc でコンパイルしてください。)
ORCはこれまでのGCに比べて約半分のメモリしか使いません。
メモリ消費量が重要な場合、ORCはスループットにおいて桁違いに速くなる可能性があります。メモリ消費量がそれほど重要でない場合は、スループットは同等です。
ORCは、CPU固有のトリックを使用せず、Webassemblyのような限定されたターゲットでもハックなしで動作します。
ORCはサブミリ秒のレイテンシを提供します。これは、（ハード）リアルタイム・システムに適しています。GCによる"Stop the World"は起きません。
ORCは、ヒープやスタックスペースの使用量を気にしません。

GitHubで編集を提案

ARC

ベンチマーク

まとめ

Discussion