5月28日、Matheus Moreiraが「The lone lisp heap」と題した記事を公開した。

mallocもlibcも存在しないfreestanding環境で動作するLispインタープリターを作るとしたら、どうメモリ管理を実現するか？ Lispインタープリター「lone」の開発者が、独自ヒープ実装の3年間にわたる進化の記録を公開した。

freestanding環境とは、標準ライブラリに依存しないC言語の実行環境のことで、組み込みシステムやOSカーネルの開発で使われる。こうした環境では動的メモリ割り当ての仕組みを自前で構築する必要があり、特にLispのような動的言語の実装は困難とされてきた。

シンプルすぎる出発点

loneは事前設計されたものではなく、リアルタイムで構築されている言語だ。「言語自体がその実装の結果として出現している」と著者が表現するように、実装の制約が言語仕様を決めていく興味深いアプローチを取る。

最初の実装は極めてシンプルな構造から始まった：

struct lone_lisp_heap_value {
    bool live: 1;
    bool marked: 1;
    enum lone_lisp_heap_value_type type;
    union {
        struct lone_lisp_list list;
        struct lone_lisp_vector vector;
        struct lone_lisp_table table;
    } as;
};

terrible（ひどい）メモリアロケーター

freestanding環境ではmallocが使えないため、独自アロケーターの実装が必要になる。loneが最初に採用したのは、最も基本的なfirst fit方式だった：

struct lone_memory {
    struct lone_memory *prev, *next;
    bool free;
    size_t size;
    unsigned char pointer[];
};

for (block = system->memory; block; block = block->next)
    if (block->free && block->size >= size)
        break;
if (!block) { return 0; }
block->free = false;
return block->pointer;

著者はこの実装を「terribleという言葉では表現しきれない」と評している。全ての割り当てで線形探索が発生し、メモリ断片化を制御できず、典型的な割り当てで30-50%のメタデータオーバーヘッドが生じる。それでも約3年間この実装を使い続けたというのは、実用最小限主義の極致といえる。

ガベージコレクションの二次計算量問題

Lispのガベージコレクターは保守的な方式を採用している。スタック上の値がLispオブジェクトへのポインタかどうかを判定するため、すべてのLisp値ポインタのリストを維持する必要がある。

しかし、スタック上のすべての単語をすべてのLispポインタと比較するのは二次計算量となり、accidentally quadraticな実装になってしまう。

値の配列のリンクリスト

この問題を解決するため、著者はRuby実装での知見を活用した新しいヒープ設計を導入した：

struct lone_lisp_heap {
    struct lone_lisp_heap *next;
    struct lone_lisp_heap_value values[LONE_LISP_HEAP_VALUE_COUNT];
};

値の配列をリンクリストで繋いだ構造である。これにより個別メモリ割り当てから一括購入方式に変わり、ガベージコレクターは単純な範囲チェックでポインタ判定ができるようになった。アロケーターの役割も割り当てから「復活」に変わった。

ポインタという「NIMBY住民」

しかし配列のリサイズ時に新たな問題が発生した。配列のリサイズは実際には新しい配列の割り当て、データのコピー、古い配列の破棄という過程であり、すべてのポインタが無効になってしまう。

著者はポインタを「プログラミング世界のNIMBY（Not In My Back Yard）」と表現している。怠惰で不動で、永遠に固定された場所を求め、周囲の世界の進化には関心がない存在だ。

インデックスによる位置独立性

この制約を根本的に解決するため、loneはポインタベースからインデックスベースへと移行した：

struct lone_lisp_heap_value *
lone_lisp_heap_value_of(struct lone_lisp *lone, struct lone_lisp_value value)
{
    size_t index = /* 値からインデックスを取得 */;
    return &lone->heap.values[index];
}

ヒープは一つの巨大でシンプルな配列となり、実際のポインタは実行時に計算される。これにより値はメモリ位置から独立し、恐れることなくヒープの再割り当て、移動、リサイズが可能になった。

キャッシュラインとページ境界の最適化

位置独立な設計により、新たな最適化の扉が開いた。loneのヒープ値は現在56バイトだが、これを64バイトにアライメントすることで：

• ページ境界をまたがない（Linuxのページサイズに関係なく）
• ちょうど1キャッシュラインに収まる

ヒープは文字通りページとページの連続となり、Lisp値で満たされる。バイト割り当てから値割り当て、そしてページ割り当てへの進化を遂げている。

実装主導設計の示唆

loneの開発は、制約が創造性を生むという格言を体現している。標準ライブラリという「贅沢」を排除することで、メモリ管理の本質に向き合い、独創的な解決策を生み出している。

freestanding環境でのシステムプログラミングや、WebAssembly System Interface (WASI)のような新しい実行環境への移植性を考える上で、loneのアプローチは示唆に富んでいる。

詳細はThe lone lisp heapを参照していただきたい。