4: 2009-11-17 (火) 12:06:25  |
現: 2024-01-08 (月) 12:58:49 k-tan |
| - | * OSASKにおける圧縮技術の活用 | + | TITLE:x |
| | + | * OSASKにおける圧縮技術の活用 [#ze912594] |
| | -[[OsaTech]]より | | -[[OsaTech]]より |
| | -(by K, 2009.07.13) | | -(by K, 2009.07.13) |
| | //-開発時間に余裕がないときは空振りのリスクは大きすぎるので、素直に既存の技術を活用するほうがいいでしょう。 | | //-開発時間に余裕がないときは空振りのリスクは大きすぎるので、素直に既存の技術を活用するほうがいいでしょう。 |
| | | | |
| - | *** (1)l2d3形式導入のいきさつ | + | *** (1)l2d3形式導入のいきさつ [#s20e8495] |
| | -WinやLinuxはアプリに対して.bssセクションに対してゼロクリアを保証することで、.dataセクション内に頻出するゼロの部分を.bssへ追い出し、アプリサイズを節約できるようにしている（本来は.bssに対してゼロクリアを保証する必然性はない。それをあえてそうしたのは、このようなアプリサイズ節約の意図があったためだと思われる）。 | | -WinやLinuxはアプリに対して.bssセクションに対してゼロクリアを保証することで、.dataセクション内に頻出するゼロの部分を.bssへ追い出し、アプリサイズを節約できるようにしている（本来は.bssに対してゼロクリアを保証する必然性はない。それをあえてそうしたのは、このようなアプリサイズ節約の意図があったためだと思われる）。 |
| | -OSASKでは.bssに対してゼロクリアを保証しないのでこの技が使えない。ということで代用として、.dataに対して簡単なスライド辞書圧縮をかけることにした。これなら00の連続以外に対しても圧縮がかけられて、よりいいのではないかと考えた。 | | -OSASKでは.bssに対してゼロクリアを保証しないのでこの技が使えない。ということで代用として、.dataに対して簡単なスライド辞書圧縮をかけることにした。これなら00の連続以外に対しても圧縮がかけられて、よりいいのではないかと考えた。 |
| | -当初、この圧縮は各アプリのスタートアップルーチンによって.data内に展開することにしていた（つまりOSは.textと初期値未保証の.data+.bssのみを準備してアプリを起動。アプリが自己責任で.text内の圧縮データをもとに.dataを初期化）。そのため複雑な圧縮アルゴリズムだとスタートアップルーチンが肥大化してしまう。このため複雑な圧縮アルゴリズムは試みられることが無かった。 | | -当初、この圧縮は各アプリのスタートアップルーチンによって.data内に展開することにしていた（つまりOSは.textと初期値未保証の.data+.bssのみを準備してアプリを起動。アプリが自己責任で.text内の圧縮データをもとに.dataを初期化）。そのため複雑な圧縮アルゴリズムだとスタートアップルーチンが肥大化してしまう。このため複雑な圧縮アルゴリズムは試みられることが無かった。 |
| | -l2d3の導入は成功を収めた。.dataセクションは非常に圧縮しやすいデータが多く、圧縮することでアプリのサイズをかなり節約できた。 | | -l2d3の導入は成功を収めた。.dataセクションは非常に圧縮しやすいデータが多く、圧縮することでアプリのサイズをかなり節約できた。 |
| - | *** (2)tek0形式までの流れ | + | *** (2)tek0形式までの流れ [#gf87e740] |
| | -l2d3がうまく行くことが分かると、ほとんどのOSASKアプリはこれを採用し、結果としてほとんどのアプリがスタートアップルーチン内にl2d3の展開ルーチンを持つことになった。これは確かに100バイト程度の小さなものではあるが、しかし全てのOSASKアプリがこれをもつということは全てのアプリに100バイト程度の共通部分があるということであり、そんなに利用頻度が高いならOS内に持たせてAPI化するべきではないかと考えた（そのときのOSASKにDLL機能があればDLLにしたかもしれない）。これでOSは100バイト程度増えたが、アプリは90バイトくらいは減った。完全に100バイト減らないのは、APIを呼ぶためのオーバーヘッドが新たに生じたためである。 | | -l2d3がうまく行くことが分かると、ほとんどのOSASKアプリはこれを採用し、結果としてほとんどのアプリがスタートアップルーチン内にl2d3の展開ルーチンを持つことになった。これは確かに100バイト程度の小さなものではあるが、しかし全てのOSASKアプリがこれをもつということは全てのアプリに100バイト程度の共通部分があるということであり、そんなに利用頻度が高いならOS内に持たせてAPI化するべきではないかと考えた（そのときのOSASKにDLL機能があればDLLにしたかもしれない）。これでOSは100バイト程度増えたが、アプリは90バイトくらいは減った。完全に100バイト減らないのは、APIを呼ぶためのオーバーヘッドが新たに生じたためである。 |
| | -またこのころ[[K]]はtek0という新しい圧縮形式も導入する。これはl2d3を少し高度にした圧縮符号だ。これを導入したのは、展開ルーチンがOS側の受け持ちになり、それによってやや高級な符号化を導入しても各アプリが肥大するわけではないからだ。むしろ各アプリは.dataの圧縮率が上がるので小さくなる。その寄与の合計と、OSの肥大化とのバランスで、tek0のサポートはプラスであろうと考えた。 | | -またこのころ[[K]]はtek0という新しい圧縮形式も導入する。これはl2d3を少し高度にした圧縮符号だ。これを導入したのは、展開ルーチンがOS側の受け持ちになり、それによってやや高級な符号化を導入しても各アプリが肥大するわけではないからだ。むしろ各アプリは.dataの圧縮率が上がるので小さくなる。その寄与の合計と、OSの肥大化とのバランスで、tek0のサポートはプラスであろうと考えた。 |
| | -実際その目論見は当たって、期待以上の結果となった。 | | -実際その目論見は当たって、期待以上の結果となった。 |
| - | *** (3)ファイル圧縮へ | + | *** (3)ファイル圧縮へ [#r30ee2ee] |
| | -OSが展開ルーチンを持つようになったので、OSは他のところでも圧縮技術を積極的に利用できるようになった。そこでファイル圧縮の自動展開サポートが導入された。これは、圧縮されたファイルをオープンしても、まるで無圧縮であるかのように普通に読める機能である。これはアプリやユーザが、自分が開こうとしているファイルが圧縮されたものなのかどうかを気にしなくていいという文化を生んだ。そしてOSはファイル圧縮の有無をファイル名ではなくファイルの中身の先頭のシグネチャで判定するので、拡張子などからも圧縮を想起させるような部分はない。オープン時にわずかに時間がかかることと、ファイルサイズが小さくなること、そして圧縮されたものは読み取り専用属性がついてしまうこと以外は、なんらかわらない。こうして頻繁に書きえられることのないファイルについては、ほとんど全てがtek0圧縮をかけられ、それによってアプリのロード時間は短縮され、ディスクの空きスペースも増えて、大成功を収めた。OSASKにおいて圧縮しないことはもはや非常識であると[[K]]が断言するところくらいにまで進んだ。 | | -OSが展開ルーチンを持つようになったので、OSは他のところでも圧縮技術を積極的に利用できるようになった。そこでファイル圧縮の自動展開サポートが導入された。これは、圧縮されたファイルをオープンしても、まるで無圧縮であるかのように普通に読める機能である。これはアプリやユーザが、自分が開こうとしているファイルが圧縮されたものなのかどうかを気にしなくていいという文化を生んだ。そしてOSはファイル圧縮の有無をファイル名ではなくファイルの中身の先頭のシグネチャで判定するので、拡張子などからも圧縮を想起させるような部分はない。オープン時にわずかに時間がかかることと、ファイルサイズが小さくなること、そして圧縮されたものは読み取り専用属性がついてしまうこと以外は、なんらかわらない。こうして頻繁に書きえられることのないファイルについては、ほとんど全てがtek0圧縮をかけられ、それによってアプリのロード時間は短縮され、ディスクの空きスペースも増えて、大成功を収めた。OSASKにおいて圧縮しないことはもはや非常識であると[[K]]が断言するところくらいにまで進んだ。 |
| - | *** (4)tek1～tek5へ | + | *** (4)tek1～tek5へ [#w9887b3b] |
| | -アプリの中の.dataだけではなくアプリも含めたほとんどのファイルが圧縮されるようになると、tek0よりも高度な圧縮を導入したほうがバランスが取れるといえる。というのは、確かに高度なアルゴリズムの導入によってOSは肥大化するが、それによって多くのファイルが少しずつ小さくなり、その寄与の合計は、対象が多くなった分だけ大きくなったからである。 | | -アプリの中の.dataだけではなくアプリも含めたほとんどのファイルが圧縮されるようになると、tek0よりも高度な圧縮を導入したほうがバランスが取れるといえる。というのは、確かに高度なアルゴリズムの導入によってOSは肥大化するが、それによって多くのファイルが少しずつ小さくなり、その寄与の合計は、対象が多くなった分だけ大きくなったからである。 |
| | -またそれまでは展開は一度に行うものという前提であったが、大きなファイルをオープンする場合などは、全体を一度に展開するのは非効率である。アクセスされた部分のみを展開するほうが良いと思われる。そこで圧縮対象を複数のブロックに分割し、ブロックごとに圧縮展開できるようにフォーマットを改良した。また符号化の方針も、展開速度重視から圧縮率重視までのラインナップを作り、多様な場面で適切に選択できるようにした。 | | -またそれまでは展開は一度に行うものという前提であったが、大きなファイルをオープンする場合などは、全体を一度に展開するのは非効率である。アクセスされた部分のみを展開するほうが良いと思われる。そこで圧縮対象を複数のブロックに分割し、ブロックごとに圧縮展開できるようにフォーマットを改良した。また符号化の方針も、展開速度重視から圧縮率重視までのラインナップを作り、多様な場面で適切に選択できるようにした。 |
| | --しかし結局マルチブロック形式のサポートは暇がなくて行われていないままである。 | | --しかし結局マルチブロック形式のサポートは暇がなくて行われていないままである。 |
| | -これにより、OSASKはシステム全体として驚異的に小さくなった。実は圧縮する前から十分に小さかったのではあるが、圧縮することで更に小さくなった。 | | -これにより、OSASKはシステム全体として驚異的に小さくなった。実は圧縮する前から十分に小さかったのではあるが、圧縮することで更に小さくなった。 |
| - | *** (5)圧縮の予期せぬ効用 | + | *** (5)圧縮の予期せぬ効用 [#acaeef3c] |
| | -我々はある程度の規模のプログラムを書くとき、内部にそれなりの構造を持ったテーブルなどを用意する。たとえばジャンプテーブルなどである。こういうものは時に結構な容量になることがある。それが気になると、テーブルを可変長などにして容量を節約するが、これはアルゴリズムを複雑にする傾向がある。 | | -我々はある程度の規模のプログラムを書くとき、内部にそれなりの構造を持ったテーブルなどを用意する。たとえばジャンプテーブルなどである。こういうものは時に結構な容量になることがある。それが気になると、テーブルを可変長などにして容量を節約するが、これはアルゴリズムを複雑にする傾向がある。 |
| | -OSASKアプリの場合、シンプルで何の工夫もないテーブルのままでも、問題にはならない。なぜなら圧縮して小さくなってしまうからである。だから複雑なアルゴリズムを導入することもない。・・・値のほとんどが6bit程度だからこのテーブルはcharにしよう、そして時々出てくる16bitや32bitの値についてはプリフィクスをつけて・・・なんてことはしないのだ。面倒だから全部32bitの単純な配列でいいのだ。上位の00についてはtekが十分に小さくしてくれる。おかげでプリフィクス機能は不要、というわけだ。 | | -OSASKアプリの場合、シンプルで何の工夫もないテーブルのままでも、問題にはならない。なぜなら圧縮して小さくなってしまうからである。だから複雑なアルゴリズムを導入することもない。・・・値のほとんどが6bit程度だからこのテーブルはcharにしよう、そして時々出てくる16bitや32bitの値についてはプリフィクスをつけて・・・なんてことはしないのだ。面倒だから全部32bitの単純な配列でいいのだ。上位の00についてはtekが十分に小さくしてくれる。おかげでプリフィクス機能は不要、というわけだ。 |
| | -ファイルも圧縮できるので、設定ファイルなどの構造を容量を気にして考える必要がない。単純でせこくないのがいいのだ。そうすることで、拡張性のある設定ファイルとなり、アプリのバージョンアップがあっても、設定ファイルフォーマットを変える必要がなく、複数のバージョンをサポートすることもない。 | | -ファイルも圧縮できるので、設定ファイルなどの構造を容量を気にして考える必要がない。単純でせこくないのがいいのだ。そうすることで、拡張性のある設定ファイルとなり、アプリのバージョンアップがあっても、設定ファイルフォーマットを変える必要がなく、複数のバージョンをサポートすることもない。 |
| | -こうして[[K]]は、圧縮技術はOSがサポートすべき機能の一つであると確信した。というのは、圧縮の存在を前提にするかしないかで大きな差があるからである。圧縮サポートが無いか、もしくはオプショナルだと、圧縮サポートを前提にしたこれらのテクニックの利用をためらってしまう。 | | -こうして[[K]]は、圧縮技術はOSがサポートすべき機能の一つであると確信した。というのは、圧縮の存在を前提にするかしないかで大きな差があるからである。圧縮サポートが無いか、もしくはオプショナルだと、圧縮サポートを前提にしたこれらのテクニックの利用をためらってしまう。 |
| - | *** (6)さらに上を目指して | + | *** (6)さらに上を目指して [#yf188d6d] |
| | -こうして特に何も苦労しなくてもコンパクトはアプリが簡単に作れるOSASKであるが、これは決して万能ではない。そもそも圧縮というのは、そのデータが持っている無駄を見つけてそれを削るようなものである。つまりもともと無駄のないデータに対しては、圧縮は無力で、むしろ若干のサイズ上昇になってしまうくらいだ。 | | -こうして特に何も苦労しなくてもコンパクトはアプリが簡単に作れるOSASKであるが、これは決して万能ではない。そもそも圧縮というのは、そのデータが持っている無駄を見つけてそれを削るようなものである。つまりもともと無駄のないデータに対しては、圧縮は無力で、むしろ若干のサイズ上昇になってしまうくらいだ。 |
| | -OSASKはAPIまでも拡張性重視の仕様になっている。APIのパラメータは全てintかそれ以上の長さで、これをメモリ上に並べたものをAPIパケットというのだが、この長さはつまらない処理でも結構な長さになる。 | | -OSASKはAPIまでも拡張性重視の仕様になっている。APIのパラメータは全てintかそれ以上の長さで、これをメモリ上に並べたものをAPIパケットというのだが、この長さはつまらない処理でも結構な長さになる。 |
| | -しかしtekの有用性は今も変わらない。独自形式でtekを上回れる場合のみに独自形式を検討し、それ以外は今までどおりにシンプルなものをそのまま使って圧縮はtek任せにすればいいのだ。実際問題としてはtekを超えられるものはめったに作れないので、ほとんど検討に値しない。APIパケットの例は例外的なケースなのだろうと思っている。 | | -しかしtekの有用性は今も変わらない。独自形式でtekを上回れる場合のみに独自形式を検討し、それ以外は今までどおりにシンプルなものをそのまま使って圧縮はtek任せにすればいいのだ。実際問題としてはtekを超えられるものはめったに作れないので、ほとんど検討に値しない。APIパケットの例は例外的なケースなのだろうと思っている。 |
| | | | |
| - | * こめんと欄 | + | * こめんと欄 [#ca60d039] |
| | #comment | | #comment |
