👑

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

2023/02/14に公開

Nim

メモリ管理

idea

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

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

バージョン1.4には、いわゆるORCメモリ管理アルゴリズムが搭載されています。ORCは、既存のARCアルゴリズム（バージョン1.2で初めて導入）にサイクルコレクタを追加したものです。この名前の由来もここにあります。 "O"はサイクルを表し、"RC"はアルゴリズムの基盤である「参照カウント（Reference Counting）」を意味します。

サイクルコレクタは、Lins氏らによる比較的よく知られた「試行削除（trial deletion）」アルゴリズムに基づいています。このアルゴリズムがどのように機能するかはここでは説明しません。詳細については、論文を参照してください。

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

いつものように、私はこのアルゴリズムを改善し、さらに最適化を追加する誘惑に逆らうことができませんでした。Nimコンパイラは関連する型を分析し、サイクルになる可能性がある場合にのみ、サイクルコレクタを呼び出すコードが生成されます。この型解析は、型をacyclicとして注釈を付けることで助けることができます。例えば、バイナリツリーを次のようにモデリングすることができます。

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

残念ながら、サイクルコレクタのオーバーヘッドは実際に測定可能な場合があります。この注釈は、ORCの性能をARCに近づけるために重要です。

ORCの設計における革新の一つは、サイクルルート候補を定数時間（O(1)）で登録および解除できることです。この結果、実行時にはNimのデータがめったにサイクルにならないという事実を利用することができます。

ARC

ARCはNimの純粋な参照カウントGC（ガベージコレクタ）ですが、多くの参照カウント操作は最適化されて除去されています。ムーブセマンティクスのおかげで、データ構造の構築にはRC操作が関与しません。また、「カーソル推論」と呼ばれるNimのARC実装におけるもう一つの革新のおかげで、一般的なデータ構造のトラバーサルにもRC操作は関与しません！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()
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)

10～18行目は、Nimの標準ライブラリからの「Hello World」非同期HTTPサーバーの例です。

4～6行目では、約135MBのJSONデータをグローバルなsessions変数に読み込んでいます。ORCはこのメモリをロードした後、プログラムが終了するまでこのメモリに触れません。対照的に、古いNimのGCはこのメモリに触れる必要があります。私はM&S GC（マーク＆スイープ）と比較していますが、M&Sはこのベンチマークで最も良いパフォーマンスを発揮します。

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

「wrk」ベンチマークツールを使用して、次の数値を得ました：

メトリック / アルゴリズム	ORC	M&S
レイテンシ（平均）	320.49 us	65.31 ms
レイテンシ（最大）	6.24 ms	204.79 ms
リクエスト/秒	30963.96	282.69
転送/秒	1.48 MB	13.80 KB
最大メモリ	137 MiB	153 MiB

そうです、ORCはM&S GCよりも100倍以上速いのです。理由は、ORCがミューテータが触れるメモリにしか触れないからです。これは、現代のマシンでのパフォーマンスを論理的に推論するための重要な機能です。世代別GCも同様の保証を提供できるかもしれません。実際、ORCは世代別かつインクリメンタルGCと見なすことができ、さらに、サイクルにならない構造はガベージになるとすぐに解放されるという保証があります。

では、積極的なGC_fullCollectの呼び出しが行われない場合はどうでしょうか？次の数値を得ました：

メトリック / アルゴリズム	ORC	M&S（memForSpeed）
レイテンシ（平均）	274.84 us	1.49 ms
レイテンシ（最大）	1.10 ms	46.41 ms
リクエスト/秒	34948.95	39561.97
転送/秒	1.67 MB	1.89 MB
最大メモリ	137 MiB	333 MiB

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

ORCは常にレイテンシとメモリ消費で勝利し、デストラクタともうまく連携し、カスタムメモリ管理とも相性が良く、ヒープサイズに依存せず、スタックルートを正確に追跡し、C/C++エコシステムが提供するすべてのサニタイザときれいに連携します。

これらの結果は他のプログラムでも典型的です：レイテンシは減少し、ジッターはほとんどなく、メモリ消費はプログラムが必要とする最小限に近いままです。組み込み開発にとって素晴らしい結果です！

サイクルコレクションアルゴリズム自体のさらなる改良も進行中です。GC研究が見逃していたアイデアがたくさんあることがわかりました。Nimにとってエキサイティングな時代です！

まとめ

ORCでコードをコンパイルするには、コマンドラインで--gc:orcを使用してください。

ORCはValgrindやその他のC++サニタイザとすぐに互換性があります。（正確なValgrindチェックのために--gc:orc -g -d:useMallocでコンパイルしてください。）
ORCは古典的なGCの2倍少ないメモリを使用します。
ORCは、メモリ消費が重要な場合にスループットで桁違いに速くなります。メモリ消費が重要でない場合でもスループットは比較可能です。
ORCはCPU固有のトリックを使用せず、WebAssemblyのような制限されたターゲットでもハックなしで動作します。
ORCはミリ秒以下のレイテンシを提供します。（ハード）リアルタイムシステムに適しています。「全世界を停止」フェーズはありません。
ORCはヒープサイズや使用スタックスペースのサイズは気にしません。

GitHubで編集を提案

ARC

ベンチマーク

まとめ

Discussion