2025-12-19

Tiny Core LinuxがUnionFSの類を使わない理由

これは Linuxディストリビューション - Qiita Advent Calendar 2025 - Qiita の19日目の記事だ。

このカレンダーを読んでいる向きなら、 Frugal installを謳うPuppy Linux のように圧縮ファイルシステムにOSの大部分を収めたディストリビューションを、収録されているアプリケーションが多い割にストレージ消費量が控えめなのをいいことに取り敢えず何種もインストールし、何種も使いこなせずに大半を放置していることだろう。あるいは、容量もIO性能も低いけどお値段もお徳なストレージに、容量の限界に怯まずに好みのディストリを押し込み、 IO性能を越える読み出し速度で運用するために、不遇の扱いを受けがちなこれらのディストリの仕組みを用いた経験があるはず。

圧縮率を上げることができるため、 SquashFS のような読み込み専用の圧縮ファイルシステムがこれらでは使われる。勿論、このままではファイルシステムに書き込みを行なうプログラムが動かなくなる。そこで多くのディストリでは、別のファイルシステムを重ねて単一のファイルシステムを構成する UnionFS の類を使う。 OSの格納された読み込み専用圧縮ファイルシステムに書き込み可能なファイルシステムを重ねることで、書き込み可能な圧縮ファイルシステムが出来上がる。他方、Tiny Core LinuxではUnionFSの類を使わない。書き込み可能なファイルシステムは、圧縮ファイルシステム内のファイルを指し示すシンボリックリンクのために使われる。プログラムの書き込もうとしたファイルがそれらのシンボリックリンクの場合、それらの指し示す先は読み込み専用ファイルシステム上のファイルだから、そのプログラムは書き込みに失敗する。

なぜ、このような中途半端な方法をTiny Core Linuxは使うのか? 多数の圧縮ファイルシステムにOSが分割格納されているからだ。他の多くのディストリと同様に、パッケージ管理システムをTiny Core Linuxは備えているが、そこで扱うパッケージアーカイブの形式は圧縮ファイルシステムそのものであるSquashFSだ。そして、特にオプションを加えずに Tiny Core Linuxをストレージにインストールすると、 27個ものパッケージファイルが書き込まれる。これらのパッケージファイル = 圧縮ファイルシステムを、素朴な実装のUnionFSの類でまとめて、一つのファイルシステムを構成したとしよう。このファイルシステムに存在しない名前のファイルにアクセスする度に、当該名のファイルが存在しないことを 27個全てのパッケージファイルについて調べねばならない。存在しないファイル名の数が非常に多いことを考えれば、多少、存在しなかったファイル名をキャッシュしても、あまり効果はない。インストールされたパッケージファイルに含まれるファイル名を全て、事前に調べてデータベース化する必要がある。これこそTiny Core Linuxでの書き込み可能ファイルの用途だ。パッケージファイル内のファイルは漏れなく、書き込み可能ファイルに置かれたシンボリックから指し示されている。

このように、 Tiny Core LinuxではOSを格納している圧縮ファイルシステムがパッケージ単位で細かく分割されている。このため、パッケージのアップデートが配布されても当該のパッケージファイルを入れ替えれば済む。他のディストリであれば、アップデート前のパッケージデータが圧縮ファイルシステムに残ってストレージを占有したままか、巨大な圧縮ファイルシステムを作り直す必要があるだろう。最近、日本語入力環境をTiny Core Linux本家に取り込んでもらったので、これを機にTiny Core Linuxを使ってみるのはどうだろう?

2025-12-17

スタックマシンで文明崩壊後のセルフアセンブラ - 変数の実装

これは言語実装 - Qiita Advent Calendar 2025 - Qiita の18日目の記事です。

去年、2024年のAdvent Calendar で手っ取り早く挑戦した「スタックマシンで文明崩壊後のセルフアセンブラ」で、「人間コンパイラ」に丸投げしていた変数の実装ですが。これを支援する機能を追加しました。成果物は去年と同じ場所に置きます。

マクロでニーモニック実装、再び

仕組みとしては、スタック増減を示す注釈を命令毎に付記することで、スタックトップからの変数の相対位置をアセンブラに計算させます。元ネタのstage0と同様に、 stage0riscでもニーモニックの実装には機械語ビット列が実体であるマクロを使っています。

# head.asm
# (このような行指向コメント機能は実装していないことに注意)
# {実体}ニーモニック
{00001 000b}rel         # 相対アドレスから絶対アドレスを計算する
{00010 000b}jmpabs      # 絶対アドレスで表された先へ分岐
{00011 000b}callabs     # 呼び出し元アドレスを残す
{00100 000b}beqzabs     # 追加のフラグ引数が0なら分岐

ほとんどの命令はスタックの増減量が決まっているので、これらのニーモニックのマクロに、スタック増減注釈を付記します。

# head-rsh.asm
{00001 000b    }rel     # 相対アドレスを消費して絶対アドレスを残すから±0
{00010 000b  1-}jmpabs  # アドレスを消費
{00011 000b  1-}callabs # 呼び出し元アドレスは呼び出し先で消費される
{00100 000b 10-}beqzabs # アドレスとフラグを消費(二進数で表記)

このニーモニック定義マクロを用いることで、これが冒頭に追加される各アセンブリコードではスタック増減注釈の付記がほぼ不要になります。

スタック増減の処理はバイナリ生成パス「numlabel」を機能拡張する形で実装しました。 UNIXでの「パイプライン処理」やマルチパスコンパイラと同様に、 stage0riscアセンブラは複数の小さなプログラム「パス」で構成されており、前のパスの出力を次のパスが入力として受け取って少しずつ変換することにより、ソースコードからバイナリイメージを生成します。 numlabelパスには数値を扱う機能が元々実装されているので、これを使いまわすことで、追加するコード量を少なく済まそうと思います。とはいえ、新機能を用いたアセンブラでnumlabelパスのソースコードを書いても、それを扱うnumlabelバイナリは未生成というブートストラップ問題に遭遇します。同じ問題は去年にも遭遇しており、その解決策として去年に倣い、C言語でnumlabelパスを用意しました。

実際に使ってみた感想

セルフアセンブラを名乗る以上、自身のバイナリを生成するために実際に使わざるを得ません。

まずは、この新機能に私自身が習熟するために、去年のバイナリイメージを出力すべく今回のアセンブラでソースコードを書き換えてみました。すると、スタックマシンではスタックトップを引数として暗黙のうちに使うため、変数を使う機会を少なく感じました。今回の機能追加、あまり意味なかったか?

しかし、ブートストラップ問題回避用のC言語版から乗り換えるべく作成した、 numlabelパスの当スタックマシン用バイナリイメージを去年のものと比較してみたところ、スタック増減を記録するために追加した変数のために、広い範囲に散らばったビット化けがみられました。これを去年のアセンブラでデバッグするのは大変だったはずだと思います。

2025-11-24

RISC系CPUがAMD Zen5に並ぶには、IPCが4命令多く必要

以前書いたブログだが、
IPCが2命令多ければ、RISC系CPUの周波数当たり性能はx86のと並ぶ - 一人一党党
https://abo-junghichi.hatenablog.jp/entry/2020/07/03/013148
AMD Zen3からは事情が変わっているようだ。
それまでのx86 CPUではサイクル当たりメモリアクセス数は2回が限度だったのが、先のブログでも世話になった、x86のCPUの構造解析で有名なAgner Fog氏によると、AMD Zen3からは3回、現時点でAMD最新のCPUであるZen5では4回のメモリアクセスが可能らしい。
Instruction tables: Lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD and VIA CPUs
https://www.agner.org/optimize/instruction_tables.pdf

先のブログを書いた時には、メモリアクセス数が増えるとは私は思わなかった。
CPUサイクル当たり演算処理をひとつ増やすにはトランジスタや配線などの資源を一定量追加すれば済むが、メモリアクセスをひとつ増やすには一定量の資源を(L1データキャッシュの)メモリセル毎に追加しなければならないからだ。
正確には「セル毎の資源量 = address配線 × (read配線 + write配線)」であり、既に実装したメモリアクセス数に比例した資源を追加しなければならない。
コンピュータアーキテクチャの話(125) マルチポートレジスタ(1) | TECH+（テックプラス）
https://news.mynavi.jp/techplus/article/architecture-125/
Zen 2まででは「最大アクセス2回 × (read 2回 + write 1回) = 6単位」のところ、Zen 5となると「最大アクセス4回 × (read 4回 + write 2回) = 24単位」であり、同量のL1データキャッシュを実装するのにZen 5はZen 2の4倍の資源を費やしているはず。

なのに、Zen 5のL1データキャッシュ量はZen 2の1.5倍。凄い。

2024-12-20

スタックマシンで文明崩壊後のセルフアセンブラ

これは言語実装のカレンダー | Advent Calendar 2024 - Qiita の22日目の記事です。

1日目の記事でやり残した、スタックマシン上でのセルフホスティング環境構築ですが。やはりforthでは新味がないし、今年のこのカレンダーに間に合わせたいので、手っ取り早くstage0riscを移植してみました。 stack-isaディレクトリに成果物があります。

命令セットアーキテクチャ

前記事である1日目と同様に、まずは仮想マシンエミュレータを製作します。前記事との違いは、CPUの命令セットがスタックマシンのものであることです。スタックマシンとして比較的新しい命令セットアーキテクチャである The Zylin ZPU を元に、コード密度を代償にしてハードウェア寄りの簡略化をしてみました。

固定長命令セットで無限の即値・オペコード

スタックマシン命令セットの長所のひとつは、スタックに積まれた値を暗黙のオペランドとして使うことで、命令の長さを短くできることです。しかしこの長所をハードウェアや、レジスタマシンとスタックマシン - ひとり勉強会で述べられているように、インタプリタで実際に活かすには問題があります。

命令長は固定である方が、より高速なハードウェア実装やインタプリタ実装ができます。ハードウェアであれば、命令長が揃っていないと、前の命令を処理する間に並行して次の命令を読み込む、パイプライン処理が難しくなります。インタプリタでも、命令長がメモリ境界に合っていないサイズだと、命令の読み出しに複数のメモリアクセスが必要となったりなど、不都合が出ます。命令長を揃えるためには、最も長い命令に命令長を合わせる必要があります。ここで、スタックに積まれたオペランドを省略するだけでは、短くならない命令があります。即値をオペランドとする命令です。テキストファイルであるソースコードを扱うため、 stage0riscの各プログラムでは文字コードであるASCIIコードを扱いますが、それらは8bitの即値です。あるいは、分岐命令では飛び先アドレスを指定しますが、それらも即値です。最悪バイナリエディタで16進コードを手打ちする場合を想定しているため、 stage0riscの各プログラムは小さいのですが、それでも256バイトを越えるものがあり、プログラムカウンタ相対アドレッシングでも、前方後方合わせて10bit必要です。また、命令の種類を指定するオペコードの大きさは、命令の種類数に直結します。固定長命令セットだとオペコードの大きさに上限があるため、後から命令の種類を追加するのが難しくなります。

そこでZPUでは、即値ロード命令が連続している場合は、スタック先頭の値に左シフト演算を掛け、空いた下位ビットを後続の即値ビットで満たします。これにより、あたかも即値ビットを繋げた一つの即値命令かのように解釈でき、即値の大きさの制限を取り払うことができます。

#ZPU
1xxxxxxx  #最上位ビットが立っていると、7bit即値xxxxxxxをスタックに積む。
1yyyyyyy  #前の命令も即値ロード命令なので、スタック先頭の値下位にビットを付け足す。
#以上2バイトで、一つの14bit即値xxxxxxxyyyyyyyがスタックに積まれる。

ただしこの方法では、同じビット列の即値ロード命令でも、新しい値をスタックに積むのか、スタックの高さを変えずにスタック先頭の値を更新するのか、前の命令が即値ロード命令か否かで動作が異なります。 ZPUではそのための状態フラグをCPUに追加しています。なので、エラーや割り込み処理でCPUの状態を保存・復元したいとき、プログラムカウンタだけでなく状態フラグも保存・復元しなければなりません。当のZPUでは、高々1bitの状態フラグの為にワード単位の保存領域を消費することを避けるため、割り込みへの応答が遅れることを覚悟で、フラグが立っている間の割り込みを禁止しています。なので当記事では、状態フラグを追加せずに、即値ロードにスタック先頭の値を使用するか否かを、命令ビット列に織り込みます。

#当記事(中途)
01xxxxxx  #最上位ビットが立ってないなら、新しい値を積む。
11yyyyyy  #最上位ビットが立っているなら、スタック先頭の値下位にビットを付け足す。
#以上2バイトで、一つの12bit即値xxxxxxyyyyyyが積まれる。

代償として、ZPUで状態フラグとして扱っていたものを命令ビット列に織り込んだ分、一つの命令で加えられる即値ビットの長さが7bitから6bitに減ってしまいました。

固定長命令で即値の大きさの制限を取り払ったのですから、もう一つの制限であるオペコードの大きさも、同じ方法で取り払うことができます。

#当記事(中途)
00cccccc  #上位2ビット目が0だったら、6bitオペコードccccccで指定された演算を行なう。

01xxxxxx  #即値をスタック先頭に積む。
10yyyyyy  #最上位ビットが立っているので、スタック先頭の値を利用する。
#上位2ビット目が0なので、一つの12bit即値xxxxxxyyyyyyをスタック先頭に戻すのではなく、12bitオペコードで指定された演算を行なう。

今回スタックマシンのエミュレータを製作したところ、前記事で製作したレジスタマシンよりも、必要な命令種類が多かったのは、私には予想外でした。確かに一般的なレジスタマシンでは、「縮小命令セットコンピュータ」として設計されたものでも、 RISC-V命令セットの基本サブセットRV32Iで37種ほどの命令種類が定められています。しかしよく見ると、算術命令を中心に多くの命令で、オペランドにレジスタしかとらないものと即値をとるものの二種が用意されています。他方、多くのスタックマシンでは、即値をオペランドにとる命令は殆ど見られません。即値オペランドが演算に必要なら、即値ロード命令でスタックに積んでから演算命令を実行します。前記事で製作したレジスタマシンでは、一般的なスタックマシンと同様に即値を用いる命令を省いたため、今回のスタックマシンを下回る数の命令種にできたようです。後述しますが、現時点で1バイト当たり6bitあるオペコードは最終的には5bitに減り、 1バイトで表現できる演算命令の種類数に余裕がなくなります。最終的には不要になりましたが、このオペコード拡張の仕組みは、仮想マシンの製作に於いて心の余裕を私に与えてくれました。

レジスタマシンのオペランドフィールド・オペコードフィールドに当たるもの

前記事でも述べたように、レジスタマシンとスタックマシンとの違いは、各命令でのオペランドの指定方法が、レジスタ番号なのか、スタック先頭との相対位置なのか、でしかありません。にも拘らず、全ての命令が全ての汎用レジスタにアクセスできるレジスタマシンと違って、スタックマシンでは殆どの演算命令がスタック先頭からの最低限の要素数の値にしかアクセスできません。そこで、スタックの奥の値にアクセスする命令が大抵のスタックマシンには用意されているのですが。それらの命令ではスタック先頭との相対位置が引数として必要で、その引数をスタックに積むために即値ロード命令などが別に必要となります。レジスタマシンではこの動作を命令内のオペランドフィールドひとつで行なっていることを考えると、スタックマシンでの「相対位置のロード + スタック奥にアクセス」の2命令は冗長です。なので、この動作を単一命令に纏めた1オペランド命令が、ZPUには用意されています。

ところで、1オペランド命令としては既に即値ロード命令があります。演算命令は0オペランド命令ですが、オペコード拡張方法が即値ロード命令でのオペランドの拡張と同じことから考えると、オペコードを引数としてとる1オペランド命令と見做すことができます。そして、命令形態の種類が少ないほど、ハードウェアやインタプリタの実装が簡略になります。なので当記事ではこれらを、同一の大きさ(5bit)のオペランドフィールドを持つ 1オペランド命令として実装します。

#当記事(実装済み版)
76543210
e00xxxxx  #オペランドで指定された演算を行なう。
e01xxxxx  #スタックから値を取り出し、スタック先頭からオペランドで指定された相対位置に書き込む。
e10xxxxx  #スタック先頭からオペランドで指定された相対位置にある値を読み込み、スタックに積む。
e11xxxxx  #オペランドを即値としてスタックに積む。
#eがセットされていたら、スタックから値をとりだして、オペランドの拡張に使う。

スタックをレジスタマシンのレジスタに当たるものと考えると、これら4種の命令群はレジスタマシンでのオペランドフィールド(即値、入力元レジスタ、出力先レジスタ)やオペコードフィールドと同じ働きをします。勿論、命令毎に種類と数が固定されているレジスタマシンでのオペランドフィールドと違い、これらは独立した命令であり、自由に入れ替えたり、省略や複数個の命令列に置き換えることができます。例えば、スタック奥読み出し命令の代わりに即値ロード命令を使うことで、前記事のレジスタマシンでは省いた、即値をオペランドにとる命令と同じことができます。あるいは、単一の即値ロード命令の代わりに複数個の命令を使うことで、メモリ間接参照などの複雑なアドレッシングモードと同様の動作が得られます。 ZPUではスタックポインタを上げ下げするものも1オペランド命令にしていますが、スタックポインタなんてレジスタマシンにはない以上、スタックポインタの上げ下げが無くても ( 2024年12月22日修正: スタックポインタを上げ下げするのではなく、スタックの奥の値のメモリアドレスを取得する命令でした。それでも、メモリアドレスなんてレジスタにはない以上… ) レジスタマシンと同等の動作には十分です。命令形態が一種類で揃っているのもあり、当記事ではこれを採用します。

スタックの数

前記事で述べたように、文明崩壊後のメモリ容量は非常に小さいと思われます。なので、メモリはできるだけ有効活用したいところであり、使い切ってないのにシステムが動かなくなるのは避けねばなりません。この点、冒頭に述べたforthなど、スタックが複数必要なシステムは不利です。どれかのスタック領域が満杯になると、他のスタック領域を使い切っていないのにシステムが動けなくなります。なので、当記事ではスタックの数を最低限の一本にしました。

移植した結果

あとは、この仮想マシンにstage0riscを移植するだけです。レジスタマシンからスタックマシンへの移植ですが、先に述べたように、レジスタマシンと同等の動作が冗長にならないようにスタックマシンを製作したので、アルゴリズムの変更は特には行なっていません。両者のソースコードを見比べると、ラベル名が殆ど使い回されているのが分かるかと。コーディング作業で困ったのは、変数をマクロで扱えないことでした。スタックの値はスタック先頭からの相対位置で参照するため、スタックが伸び縮みする度に相対位置を計算し直す必要があり、固定の値しか扱えないマクロでは参照できません。それでもなんとか移植した結果、当記事のスタックマシンに移植したイメージファイルの合計サイズは、 stage0riscでの合計サイズ996バイトの76%に当たる761バイトになりました。スタックマシン側の方を基準に100%とすると、 stage0risc側は31%ほど大きいということになります。 Virtual Machine Showdown: Stack Versus Registers によると、スタックマシンであるJAVA 仮想マシンのイメージファイルをレジスタマシンのものに変換した結果、26%ほどサイズが増加したそうです。当記事では逆にレジスタマシンのものをスタックマシンのものに変換したのですが、似た結果になったのは興味深いところです。

やり残しは続くよ

変数の実装を「人間コンパイラ」に丸投げしたのは、スタックマシンを取り上げた記事として大きな欠陥でしょう。

勿論、スタックマシン上で変数を扱う言語処理系は、無いわけではありません。しかし、そこで使われている方法が、スタックマシンの構造を活かした効率の良いものかは、別問題です。

全ての汎用レジスタを同一コストでアクセスできるレジスタマシンと違い、スタックマシンでのスタックのアクセスコストは、スタック先頭からの距離により異なるように作られています。一部を除いてレジスタにしかアクセスしないレジスタマシンでの命令と同様に、スタックマシンでの命令は一部を除いてスタック先頭から順番にしかアクセスしないからです。大きな相対位置の指定には大きな即値フィールドのコストが伴うので、 x86命令セットなどで用いられている、スタックの特定のアドレスを指すレジスタ「ベースポインタ」からの相対位置を用いて変数を実装する方法は、スタックマシンのアクセスコスト構造とは少しズレがあると私は考えます。ベースポインタレジスタを汎用レジスタとして目的外利用する最適化が、当のx86向けコンパイラで普及しているのも、これを避けた理由のひとつです。文明崩壊前に再興するであろうスタックマシンでは、過去の遺物と化したベースポインタが省かれていると、私は予想します。対して、スタック先頭からの相対位置でアクセスする方法は、少なくとも仮想マシンインタプリタの実装では、後述のStack Cachingを適用したとき、小さな相対位置を即値オペランドで指定する命令で物理レジスタを活用できます。なので、スタックの奥にアクセスする命令として当記事ではこちらを選択し、命令セットを最小限にするため、ベースポインタを省きました。

forthにも変数はありますが、単純な実装の場合、変数はスタックではなく固定アドレスであるメモリ上の「辞書領域」に割り付けます。レジスタマシンでも使える移植性の高いこの手法は裏を返せば、マシンの構造を活かしたものとは到底言えません。

以上により、スタックマシンの構造を活かした変数実装には、スタックの伸び縮みを把握するコンパイラが必要になるようです。勿論、stage0riscでコンパイラと称するものは、最適化機能などない低機能のアセンブラに過ぎません。しかし、GNU assemblerには "CFI directive" という疑似命令があり、スタックの状態をプログラマから教えてもらうようです。これを真似れば、当記事で製作したセルフ開発環境を僅かに拡張するだけで、変数位置の計算を自動化できるかも知れません。現在のstage0riscでニーモニックを実装しているマクロでは、各ニーモニックの機械語ビット列しか定義していませんが、スタックの増減を知らせる疑似命令も各ニーモニックのマクロに追加すれば、後続のバイナリ生成プログラムでスタックの伸び縮みを把握できそうです。

他にやり残したこととしては、折角の仮想スタックマシンだし、スタックの奥にアクセスする命令の設計で行なった選択の利点を享受するためにも、 Stack Caching for Interpreters 辺りのスタックマシン用高速化手法を試したいところです。

2024-11-20

文明崩壊後に作るセルフホスティングアセンブラ

これは言語実装のカレンダー | Advent Calendar 2024 - Qiita の1日目の記事です。

このカレンダーを読んでいる皆さんの中には、「AI兵器」の衝撃 “機械は犠牲を理解できず” ウクライナの無人機イスラエル軍は？暗い未来の不安 | NHK | WEB特集 | イスラエルなど、スカイネットの実現間近な近年の国際情勢から、 Collapse OSの作者と同様に人類文明の崩壊を心配する方々がいるかと思います。或いは激化する米中対立を背景に、外国産パソコンに仕込まれたハードウェアレベルのバックドアの噂とかコンパイラに仕込まれた細工とシステムのセキュリティの話とかを真に受けた上司の暴走で、半導体の一切無い部屋に監禁されて「バックドア汚染の心配の無い、コンパイラとハードウェアを作れ!」という業務命令を受け、 Jeremiah Orians氏の Stage0 Bootstrap for the Free Software をダウンロードしたは良いが、ハードウェアを構築できずに挫折した経験をお持ちとか。そうではなく単に技術的興味で、命令セットの設計とそれに対応したアセンブラの作成に挑戦したい方々もいるかと。

当記事では、文明崩壊後にアセンブラのセルフホスティングを行なう手法として、小さなバイナリサイズのフィルタプログラムを組み合わせるものを紹介します。成果物は stage0risc からダウンロードできます。

文明崩壊後のハードウェア

まず必要なのは、文明崩壊後でも用意できるハードウェアですが。実際にハードウェアを製作するのは大変なので、当記事では、入出力が連続したバイト列のみの、極めて単純な仕様のエミュレータで済ませます。 UNIX系OSでいうところの「標準入出力」のみです。実際、コンピュータ産業など未だ存在しない黎明期のコンピュータの入出力は穿孔テープやテレタイプ端末でしたから、同様にコンピュータ産業がもう存在しない文明崩壊後でも、これらの入出力装置は製作できるでしょう。冒頭で触れたJeremiah Orians氏のstage0を使ったことのある方々なら、「プログラムはどうやって読み込ませるんだ?」と疑問に思うかもしれません。 Orians氏のstage0では、標準入出力とは別にプログラムを読み込ませる装置を仮定しています。対して当記事では、入力装置を節約するため、ブートローダを焼いた書き換え不能なROMをコンピュータ起動時に使います。このブートローダが、起動時に標準入力からプログラムを読み込みます。読み込まれたプログラムが標準入力を用いる場合は、読み込むデータをプログラムの直後にくっつけます。これは先述の穿孔テープであれば、手作業で可能です。ちなみに、冒頭でお知らせした成果物では、テープの繋ぎ合わせ作業を現在の環境でエミュレーションするのに、複数のファイルをつなぎ合わせるUnixコマンドの「cat」を使っています。

CPUについては、ハードウェアを新規に作るなら、3オペランドマシンよりスタックマシンや 1オペランドマシンの方が部品点数などが少なく作り易いです。とはいえ、1オペランドマシンといえども新規にCPUを作るのは大変なので、まだ使える既存のCPUが残っているならそれらを使いたいところです。が、それらの殆どはレジスタマシンです。また、エミュレータを噛ませることで、当記事のバイナリがそのまま動き、文明崩壊後の手間を軽減するだけでなく、崩壊前の現在でのお試しもラクチンになります。エミュレータ上での動作を前提にするなら、 Virtual Machine Showdown: Stack Versus Registers で明らかにされた様に、3オペランドが有利です。なので当記事では、簡略化した3オペランド RISCのエミュレータを用います。

文明崩壊後のソフトウェア

初期のコンピュータでは、主記憶装置(メモリ)の容量が非常に限られていました。日本初のコンピュータ FUJIC のメモリ容量は8415ビット(255ワード。ワード当たり33ビット。)。 1バイト当たり8ビットに換算すると、1052バイトに1ビット足りません。文明崩壊後でも同様でしょう。あるいは、現在で最も大量に生産されている、すなわち文明崩壊後に最もサルベージし易いであろうコンピュータは、 1個当たりのお値段が数百円にも満たないワンチップマイコンですが。それらに積まれているメモリ容量もキロバイト単位です。なので、ソフトウェアの設計も、メモリをあまり必要としない方向で行きます。

まずは、プログラミング言語Pascal に倣ってのワンパスコンパイル。ソースコードを読み終える前にコンパイル結果を出力し始めれば、出力した部分のソースコードや結果をメモリに残す必要が無くなります。ただし、これを実現するためには、ソースコードの文法に様々な制限が掛かります。アセンブラの場合は、まだ読み込んでいない後方ラベルアドレスを使えなくなります。

そして、バイナリ生成とマクロ機能を別々のプログラムに分割します。

プログラムが小さければ、それを格納するのに必要なメモリも少なくて済みます。また、プログラムの機能が少ないならば、その機能を実現するのに必要なメモリも少なくて済みます。

製作し易さを最優先すべき文明崩壊後のアセンブラに、マクロ機能は余計と思われるかもしれません。しかし、Orians氏のstage0アセンブラでは、英単語などの文字列「ニーモニック」で表された命令を機械語ビット列に変換する処理を、各ソースコード冒頭に追加するマクロ定義ファイルで行なっています。このマクロ定義ファイルが肩代わりしているおかげで、各ニーモニックに対応する機械語ビット列についての情報が stage0のアセンブラコードには不要となり、バイナリサイズの削減になります。例によって、マクロ定義ファイルをソースコード冒頭に追加するのは、穿孔テープであれば手作業で可能です。

結果、当記事の成果物であるstage0riscでは、仮想マシンのメモリ量を1512バイトに設定しても、アセンブラのセルフホスティングが出来ました。

分割した部分を置き換える

バイナリ生成とマクロ機能の分離には、文明崩壊後のコンピューティング以外にも効能がありました。それぞれの部分を別のプログラムに置き換えるのが簡単なことです。

stage0riscの開発当初は、マクロ機能プログラムにはC言語プリプロセッサを使っていました。成果物内のcheatsディレクトリにその名残りのコードがあります。あるいは逆に、バイナリ生成プログラムだけ取り替えてマクロ機能プログラムを使い回すことが出来ます。これを利用して、仮想マシンではなくx86実マシン上でセルフホスティングされたアセンブラを構築しました。 st0l86ディレクトリにありますが、セルフホスティング前にx86バイナリを構築するのに、 stage0risc仮想マシン用のマクロ機能プログラムを流用しています。

やり残したこと

当記事では低水準言語であるアセンブラを構築しましたが、高水準言語なのに容易く実装できるものがあります。バイナリサイズが小さいのであれば、機械語手書きから言語処理系をブートストラップするのように、何らかのバイナリエディタに16進数の羅列を入力する方法が使えます。小さいバイナリサイズといえば、 PC/AT互換機のマスターブートレコード(512バイト)に収まる処理系が幾つかあります。

ガベージコレクタ付きの処理系が512バイトでお釣りが来るなんて、早過ぎか遅過ぎか分かりませんが、時代を間違えているのは確かでしょう。

にも拘らず当記事でアセンブラを取り上げたのは、当記事で取り上げたCPUが、スタックマシンとかではなくレジスタマシンだからです。高水準言語でその豊富なレジスタの恩恵を受けるには、レジスタ割付が必要となり実装難度が大きく跳ね上がります。アセンブラであれば、「人間コンパイラ」に最適化を任せることが出来ます。エミュレータの性能だけでなく現在普及していることも合わせて、当記事ではレジスタマシンを取り上げました。

しかしレジスタマシンと違ってスタックマシンには、まだ十分に研究の進んでいない分野、"stack scheduling"があると私は感じます。レジスタマシンとスタックマシンとの違いは、各命令でのオペランドの指定方法が、固定したレジスタ番号なのか、スタック先頭との相対位置なのか、でしかありません。そして先に述べたように、レジスタマシンの恩恵を得るためにはレジスタ割付が必要であり、多くの研究者の努力によりその方法が確立されています。しかしスタックマシンでは、レジスタマシンのレジスタ割付に当たる、「スタック割付」があまり研究されていません。

など、ないわけではないのですが。レジスタマシンでのレジスタ間コピー命令(x86 アセンブラのレジスタ間mov)に当たる、スタックマシンでのスタック操作命令(dup,swap,rotなど)の削減には至っていないようです。レジスタ割付の主目的の一つがコピー命令の削減であることを考えると、まだ研究の余地があるように私は感じます。そして関数呼び出しは、コピー命令などで適切なレジスタ・スタックに引数・返り値を配置しなければならない「0オペランド命令」であり、多くのスタックマシンでの基本命令と同じです。なので、stack schedulingは、高度にリファクタリングされて関数呼び出しだらけのコードであっても、スタックマシンの性能向上に寄与すると私は考えます。絶対位置であるレジスタ番号でオペランドが指定されるレジスタマシンでは、関数間での引数・返り値の場所が衝突するのを解決するのは簡単ではありません。特に、引数などの配置方法が「呼び出し規約」として同一位置に固定されている外部関数だと、レジスタ割付で削減したはずのコピー命令を追加するしかありません。スタックマシンであれば、スタックポインタが変化すれば各命令オペランドの参照する位置も変わるため、関数を呼び出す順番を並び替えてスタックポインタを操作することで、スタック操作命令など追加の命令を用いずに各関数の引数・返り値の衝突を減らせるかも知れません。ならば、実行速度よりコード密度を重視し、インライン化せずに関数呼び出しを多用するコードを使う用途であれば、スタックマシンの方がレジスタマシンより優位になります。

なので、スタックマシンがあまり生産されない現在の状況が、文明崩壊後まで続くという確信を私は持てません。そうでなくてもコード密度の優位は、メモリの少ない文明崩壊後では重要です。 stack schedulingの確立を前提とするなら、当記事の取り上げるべきCPUはスタックマシンであり。スタックマシンならば、冒頭に述べたCollapse OSがそうしたように、アセンブラではなく、一部のスタックマシンの低水準言語として実装されたこともある高水準言語 forth を検討しないわけにはいかなかったでしょう。

2024-05-09

zstd vs deflate on zswap

パラレルATA からしかbootできない自機で、HDDが死亡寸前。今時、パラレルATA接続のストレージなんて手に入らない。そこで、kexec機構を用いた最小限のlinux カーネルとinitial ram filesystemをCDに焼き、USBメモリに格納したシステムへchainload。

USBフラッシュメモリの寿命は書き込みによって減るので、swap領域への書き込みを減らすためにzswapを導入。ここで、zswapの圧縮アルゴリズム選択で気になったのでネット検索したところ、2024年5月現在、多くのサイトで勧められている圧縮アルゴリズムzstdが、小さなファイルでは圧縮率がよくないらしい。自分がこのことを知ったのは2016年のOSS圧縮ツール選択カタログ #Linux - Qiitaを読んでから。 zstdの開発元でも、Compression ratio worse than zlib for small blobs - Issue #1134 - facebook/zstd - GitHubとして認識されているようだ。そして、swapはページ単位で行われ、自機の属するアーキテクチャであるx86でのページサイズは4キロバイト。 Squash Compression Benchmark - GitHub Pagesによると、4キロバイト前後のファイルサイズでは、zstdはスピードではdeflateを上回るが圧縮率では負ける。なので、自分は圧縮率優先でdeflateをzswapの圧縮アルゴリズムに選択した。

新しめのツールはbrotli以外ファイルヘッダが大きそうですね逆に言うと、gzip/bzip2はまさに汎用と言えるさすがの性能です

2016年のOSS圧縮ツール選択カタログ #Linux - Qiitaの結語は参考になる。

2023-11-29

9キロバイトのコードで関数型言語を実装 - 自作言語revappの理由

これは言語実装のカレンダー | Advent Calendar 2023 - Qiitaの1日目の記事です。

このカレンダーを読んでいる皆さんなら、論文「なぜ関数プログラミングは重要か」に感銘を受けたりして、関数型言語を実装したいと思ったことがあるでしょう。とはいえ、haskellやMLのような複雑な仕様を持つ言語では、それに見合った複雑な実装が必要となって手に負えない、と思った方も多いと思います。しかし、LISPやforthのような単純な実装で済む処理系であれば、一度は実装してみたことが、このカレンダーを読んでいる皆さんにはあるはずです。私の自作言語revapp は、先の論文で挙げられた関数型言語の二つの主要機能である高階関数と遅延評価を持ちながら、静的リンクされた9キロバイトのLinux-i386実行ファイルで実装できます。 Unix系のOSをお使いであれば、終了コード0を返すだけの trueコマンドが用意されているかと思います。あるいは、このカレンダー読んでいる皆さんであれば helloworldプログラムよりも簡単に実装できるでしょう。そのtureコマンド、 Linux-amd64の場合は20キロバイトを越えるようです。それを下回るコードサイズで実装できるほどに、revapp言語は単純なのです。

関数適用の語順が逆のラムダ式

実装を単純にするため、計算モデルとしてラムダ計算をrevappは採用しています。このモデルでは、変数定義と関数適用のたった二つの構文で、高階関数が書けてしまいます。ただし構文解析の実装を単純にするため、一般に使われている「ラムダ式」の文法ではなく、 De Bruijn notation - Wikipedia に類似した文法を使います。ラムダ式の構文のうち関数適用については、結合規則が左結合優先になっていて、左再帰の形になっています。

S -> x          (変数参照)
S -> λx.( S )  (変数定義)
S -> S ( S )    (関数適用)

実装の単純な構文解析手法として再帰下降構文解析が有名ですが、この手法では左再帰の構文を扱えません。この関数適用の語順がDe Bruijn notationではラムダ式の逆になっており、左再帰ではなく右再帰になっています。

S -> x        (変数参照)
S -> [x] S    (変数定義)
S -> ( S ) S  (関数適用)

さらに実装を単純にするためにrevappでは、関数末尾を表現する構文を追加して、変数参照構文も右再帰にします。

S -> 0文字の文字列  (関数末尾)
S -> x     S        (変数への関数適用)
S -> =x    S        (変数定義)
S -> ( S ) S        (関数への関数適用)

勿論、「0文字の文字列」なんて表記も検出もできないので、この文法は構文解析できません。しかし、この構文解析不能なソースコードの末尾に閉じ括弧')'を一文字だけ加えたものは、以下の文法で構文解析できます。

S -> )     (関数末尾)
S -> (S S  (関数への関数適用)
S -> =x S  (変数定義)
S -> x  S  (変数への関数適用)

ここで、関数末尾以外の全ての構文を右再帰の形にしたことが効いてきます。インタプリタの中間表現としてよく使われる、バイトコードの文法と比べてみましょう。

S -> "復帰を示す1byte"             (サブルーチンから復帰)
S -> "命令1を示す1byte" operand S  (仮想命令1)
S -> "命令2を示す1byte" operand S  (仮想命令2)
...

どちらも、1byte目で処理内容を決定できる、右再帰の文法です。 revappソースコード(の末尾に閉じ括弧を足したもの)の構文解析の実装は、バイトコードのそれと同じくらい単純なのです。勿論、バイトコードが中間表現として用いられているのは、構文解析が単純だからだけではありません。メモリ上に並んでいるのと同じ順番で仮想命令を逐次処理する、単純な方法での解釈実行ができるからです。このバイトコードの利点をrevappで利用するため、私の書いたrevappインタプリタ実装では、ローカル環境を加えた仮想スタックマシンを用いています。 revappでは引数が関数本体よりも先に記述されるので、forth言語などと同様に、スタックマシンを基にした仮想マシンでの解釈実行が自然でしょう。勿論、バイトコードと違って命令末尾以外にも再帰箇所がある、関数への関数適用構文の処理だけは単純ではなく、引数として再帰的に記述されたrevappソースコードを構文解析する必要があります。しかし、引数として記述される関数は遅延評価されるので、解釈はしても実行までする必要はありません。スタックに積むのがthunkである点を除いて、変数への関数適用構文の場合と制御の流れは同じです。結果として、既にお気付きかと思いますがこの仮想マシン、先述のrevapp文法を直接解釈実行します。仮想マシンなのに中間表現の仮想命令セットがないという怪しげな点が不安ですが、ソースコードを中間表現へ変換するコードが省け、実装が単純になるのは確かです。

言語自身による言語機能の実装

さらに私の書いたインタプリタでは実装を単純にするために、値呼び機構の実装を省いています。ファイル操作などの入出力には必須だし、いくらラムダ計算がチューリング完全とはいえ整数演算はCPU組み込みの演算命令を使う方が圧倒的に効率的なので、バイナリデータを扱うプリミティブ関数群なら実装しているのですが。それらの引数として、バイナリデータではなくそれを生成するthunkを渡すと、 thunkを評価して値を求める代わりに、このインタプリタは異常終了扱いで停止します。なので、プリミティブ関数に渡すバイナリデータを生成するときは、バイナリデータを関数に渡す

(=プリミティブ関数  バイナリデータ プリミティブ関数)

の形のrevappコードで表される、バイナリデータをラップするthunkを代わりに生成します。そして、

引数thunk プリミティブ関数

と書く代わりに語順を入れ替えて

プリミティブ関数 引数thunk

と書きます。語順を入れ替えることにより、遅延評価なので、関数の位置にある引数thunkがプリミティブ関数より先に評価され、値呼びの場合と同じ評価順序になります。とはいえ、語順を入れ替える表記は見た目に悪いし、複数の引数を取るプリミティブ関数では

((プリミティブ関数 引数thunk1) 引数thunk2) 引数thunk3

と括弧の入れ子が生じるので、関数にもラッパーを用意します。

(=引数thunk1 =引数thunk2 =引数thunk3
 ((プリミティブ関数 引数thunk1) 引数thunk2) 引数thunk3
)=ラッパー関数
( 使い方 )=
引数thunk3 引数thunk2 引数thunk1 ラッパー関数

これらのラッパーは、機械語ではなくrevapp言語自身で実装できます。なので、このインタプリタの実行ファイルにはテキスト形式のままのrevappソースコードが組み込まれています。例えば、条件が成立した場合と不成立の場合の両方の処理を引数とする関数としてブール値を定義することで、条件分岐構文に当たる機能を実装しています。

(=t =f t)=true
(=t =f f)=false

遅延評価なので、片方の引数を捨てるだけで、捨てた方の処理の実行を避けることができます。高階関数と遅延評価があれば、制御構文の実装は省けるのです。ループ構文に当たるものは、ラムダ計算に於ける不動点コンビネータをrevapp言語で定義した関数です。

数値や文字列のリテラル構文の実装も省いています。

(=done done)=[
(=done =head =isend (done head cons) isend)=,
(nil ,)=]

の三つの記号を名前とする関数を定義することにより、

[ 要素 , 要素 ]

のような形式のリスト表記が可能になります。リストが表記できるなら、記述密度は6倍ほど悪くなりますが、一文字を要素とするリスト構造として文字列リテラルを表記できます。

([ 'H' , 'e' , 'l' , 'l' , 'o' ])=Hello

数値リテラル機能は、数字を要素とするリストから数値を計算する関数で足ります。

(([ 1 , 0 , 0 ]) decimal)=100

文字自身の定義は厄介で、

...
('@' one plus)='A'
('A' one plus)='B'
('B' one plus)='C'
('C' one plus)='D'
...

のようなコードを私の代わりに生成するプログラムを用意するハメになりました。遅延評価によるメモ化が効くので、 1の加算を繰り返す効率の悪い計算方法でも使い物になるようです。

バイナリハック

残念ながら当然それらだけでは、無駄だらけのOS添付trueコマンドならともかく、手書きのtrueコマンドより実装サイズが小さくなることはありません。

int main(void)
{
 return 0;
}

なので、くだんの9キロバイトバイナリについては、アセンブラ中の.rodataセクションを.textセクションに書き換えたり、ファイルヘッダを自前生成したりして、セクション領域の数を減らしています。ヘッダや各セクション領域は開始位置がページサイズ単位で揃えられているので、いくらコードサイズを減らしても、ページサイズに合わせる分のパディングによって帳消しとなります。このセクション統合ハックの効果を上げるため、 Tiny Forthインタープリタと同様にベアメタルプログラミングに倣って、ライブラリの動的リンクを避けます。メモリについては動的確保を行わず、巨大な固定サイズのグローバル配列から切り出す方式を採っています。ファイルなどの入出力は、OSのシステムコールを直接叩きます。移植性は失いましたが、このハックで4キロバイト以上ファイルサイズを削れました。

終わりに

jonesforth.s.txtより

Can you imagine writing C's 'if' in C? And that brings me to my third reason: If you can write 'if' in FORTH, then why restrict yourself to the usual if/while/for/switch constructs?

C言語のif構文をC言語で記述するなんて想像できるかい? ここから、私がforthを勧める理由の3番目が出て来るんだ。もしforthでif構文を書けるのなら、どうして、いつものif/while/for/switch構文に拘る必要があるんだい?

以上が、revapp言語の処理系を9キロバイトで実装できる主な理由だと私は考えます。 forthやLISPがしぶとく生き残っていて、新しい処理系まで現れるのは、動作速度や強力な言語機能は勿論ですが、実装のし易さが一番の原因だと私は思います。そして、強力な言語機能、実装のし易さ、この二点はこれらの言語では別々のものではなく車の両輪のように分かち難いものです。言語機能のうち、言語自身で記述できる部分が多いほど、機械語で実装しなければならない部分が少なくなるからです。機能の弱い言語では機械語で実装しなければならない部分でも、強い言語であれば、その言語自身で記述できます。逆に言えば、機械語で実装しなければならない部分こそ、その言語で最も強力な機能と言えます。 forthに於いては、機械語で書かれたルーチンと仮想命令で書かれたルーチンとを同一に扱う仕組み (threaded codeのヘッダに位置するcode field)。 LISPに於いては、特殊形式quote。これが関数型言語についても当て嵌まると、revapp言語は示せたでしょうか? 高階関数と遅延評価の力はその機能を持つ言語自身の実装のし易さに繋げることができると。