OT​/0003 :: OSASK計画

OSASKにおける圧縮技術の活用 ^[1]

• OsaTech^[2]より
• (by K, 2009.07.13)

(1)l2d3形式導入のいきさつ ^[3]

• WinやLinuxはアプリに対して.bssセクションに対してゼロクリアを保証することで、.dataセクション内に頻出するゼロの部分を.bssへ追い出し、アプリサイズを節約できるようにしている（本来は.bssに対してゼロクリアを保証する必然性はない。それをあえてそうしたのは、このようなアプリサイズ節約の意図があったためだと思われる）。
• OSASKでは.bssに対してゼロクリアを保証しないのでこの技が使えない。ということで代用として、.dataに対して簡単なスライド辞書圧縮をかけることにした。これなら00の連続以外に対しても圧縮がかけられて、よりいいのではないかと考えた。
• 当初、この圧縮は各アプリのスタートアップルーチンによって.data内に展開することにしていた（つまりOSは.textと初期値未保証の.data+.bssのみを準備してアプリを起動。アプリが自己責任で.text内の圧縮データをもとに.dataを初期化）。そのため複雑な圧縮アルゴリズムだとスタートアップルーチンが肥大化してしまう。このため複雑な圧縮アルゴリズムは試みられることが無かった。
• l2d3の導入は成功を収めた。.dataセクションは非常に圧縮しやすいデータが多く、圧縮することでアプリのサイズをかなり節約できた。

(2)tek0形式までの流れ ^[4]

• l2d3がうまく行くことが分かると、ほとんどのOSASKアプリはこれを採用し、結果としてほとんどのアプリがスタートアップルーチン内にl2d3の展開ルーチンを持つことになった。これは確かに100バイト程度の小さなものではあるが、しかし全てのOSASKアプリがこれをもつということは全てのアプリに100バイト程度の共通部分があるということであり、そんなに利用頻度が高いならOS内に持たせてAPI化するべきではないかと考えた（そのときのOSASKにDLL機能があればDLLにしたかもしれない）。これでOSは100バイト程度増えたが、アプリは90バイトくらいは減った。完全に100バイト減らないのは、APIを呼ぶためのオーバーヘッドが新たに生じたためである。
• またこのころK^[5]はtek0という新しい圧縮形式も導入する。これはl2d3を少し高度にした圧縮符号だ。これを導入したのは、展開ルーチンがOS側の受け持ちになり、それによってやや高級な符号化を導入しても各アプリが肥大するわけではないからだ。むしろ各アプリは.dataの圧縮率が上がるので小さくなる。その寄与の合計と、OSの肥大化とのバランスで、tek0のサポートはプラスであろうと考えた。
• 実際その目論見は当たって、期待以上の結果となった。

(3)ファイル圧縮へ ^[6]

• OSが展開ルーチンを持つようになったので、OSは他のところでも圧縮技術を積極的に利用できるようになった。そこでファイル圧縮の自動展開サポートが導入された。これは、圧縮されたファイルをオープンしても、まるで無圧縮であるかのように普通に読める機能である。これはアプリやユーザが、自分が開こうとしているファイルが圧縮されたものなのかどうかを気にしなくていいという文化を生んだ。そしてOSはファイル圧縮の有無をファイル名ではなくファイルの中身の先頭のシグネチャで判定するので、拡張子などからも圧縮を想起させるような部分はない。オープン時にわずかに時間がかかることと、ファイルサイズが小さくなること、そして圧縮されたものは読み取り専用属性がついてしまうこと以外は、なんらかわらない。こうして頻繁に書きえられることのないファイルについては、ほとんど全てがtek0圧縮をかけられ、それによってアプリのロード時間は短縮され、ディスクの空きスペースも増えて、大成功を収めた。OSASKにおいて圧縮しないことはもはや非常識であるとK^[5]が断言するところくらいにまで進んだ。

(4)tek1～tek5へ ^[7]

• アプリの中の.dataだけではなくアプリも含めたほとんどのファイルが圧縮されるようになると、tek0よりも高度な圧縮を導入したほうがバランスが取れるといえる。というのは、確かに高度なアルゴリズムの導入によってOSは肥大化するが、それによって多くのファイルが少しずつ小さくなり、その寄与の合計は、対象が多くなった分だけ大きくなったからである。
• またそれまでは展開は一度に行うものという前提であったが、大きなファイルをオープンする場合などは、全体を一度に展開するのは非効率である。アクセスされた部分のみを展開するほうが良いと思われる。そこで圧縮対象を複数のブロックに分割し、ブロックごとに圧縮展開できるようにフォーマットを改良した。また符号化の方針も、展開速度重視から圧縮率重視までのラインナップを作り、多様な場面で適切に選択できるようにした。
  • しかし結局マルチブロック形式のサポートは暇がなくて行われていないままである。
• これにより、OSASKはシステム全体として驚異的に小さくなった。実は圧縮する前から十分に小さかったのではあるが、圧縮することで更に小さくなった。

(5)圧縮の予期せぬ効用 ^[8]

• 我々はある程度の規模のプログラムを書くとき、内部にそれなりの構造を持ったテーブルなどを用意する。たとえばジャンプテーブルなどである。こういうものは時に結構な容量になることがある。それが気になると、テーブルを可変長などにして容量を節約するが、これはアルゴリズムを複雑にする傾向がある。
• OSASKアプリの場合、シンプルで何の工夫もないテーブルのままでも、問題にはならない。なぜなら圧縮して小さくなってしまうからである。だから複雑なアルゴリズムを導入することもない。・・・値のほとんどが6bit程度だからこのテーブルはcharにしよう、そして時々出てくる16bitや32bitの値についてはプリフィクスをつけて・・・なんてことはしないのだ。面倒だから全部32bitの単純な配列でいいのだ。上位の00についてはtekが十分に小さくしてくれる。おかげでプリフィクス機能は不要、というわけだ。
• ゲームを作るときにキャラクターデータなどがあるだろうが、tekを前提にするのならそれも全部BMPのようなベタデータのままで十分である。心配しなくてもちゃんと小さくなる。そしてベタデータはもっとも扱いやすく、アプリの構造は単純化され、その分だけさらに小さくなる（単純な構造のプログラムはもちろんそれだけでもコンパクトになる傾向があるが、さらに単純な構造のものは圧縮も効きやすい）。
• 高速化のためにアプリの一部にループアンローリングを施しても問題はない。だってそんな繰り返しは圧縮されてしまうのだから。だからアプリの肥大化を気にせずに、必要なアンローリングは積極的に行う。
• ファイルも圧縮できるので、設定ファイルなどの構造を容量を気にして考える必要がない。単純でせこくないのがいいのだ。そうすることで、拡張性のある設定ファイルとなり、アプリのバージョンアップがあっても、設定ファイルフォーマットを変える必要がなく、複数のバージョンをサポートすることもない。
• こうしてK^[5]は、圧縮技術はOSがサポートすべき機能の一つであると確信した。というのは、圧縮の存在を前提にするかしないかで大きな差があるからである。圧縮サポートが無いか、もしくはオプショナルだと、圧縮サポートを前提にしたこれらのテクニックの利用をためらってしまう。

(6)さらに上を目指して ^[9]

• こうして特に何も苦労しなくてもコンパクトはアプリが簡単に作れるOSASKであるが、これは決して万能ではない。そもそも圧縮というのは、そのデータが持っている無駄を見つけてそれを削るようなものである。つまりもともと無駄のないデータに対しては、圧縮は無力で、むしろ若干のサイズ上昇になってしまうくらいだ。
• OSASKはAPIまでも拡張性重視の仕様になっている。APIのパラメータは全てintかそれ以上の長さで、これをメモリ上に並べたものをAPIパケットというのだが、この長さはつまらない処理でも結構な長さになる。
• いくら圧縮でこれが小さくなるとはいえ、しかし圧縮前の状態はあまりにもスカスカに思えた。ここはもう少し何とかするべきなのではないかと思った。・・・そして改良したところ、アプリの無駄が激減した。つまり、元サイズが小さくなり、さらに圧縮しても小さくならなくなってしまった。
• こうしてできたのが「ぐいぐい01」、つまり第二世代OSASKのAPIである。そして第二世代OSASKのアプリの小ささは、第一世代OSASKをはるかに超えており、これはAPIパケットに対して、「APIの特性を生かした」符号化を採用したからである。・・・tekは汎用圧縮形式であって、それぞれの圧縮対象の特徴に特化できないので、第一世代OSASK+tekでは、第二世代のサイズには及ばないのだ。
• しかしtekの有用性は今も変わらない。独自形式でtekを上回れる場合のみに独自形式を検討し、それ以外は今までどおりにシンプルなものをそのまま使って圧縮はtek任せにすればいいのだ。実際問題としてはtekを超えられるものはめったに作れないので、ほとんど検討に値しない。APIパケットの例は例外的なケースなのだろうと思っている。

こめんと欄 ^[10]