サーバープログラミングの神話
自戒シリーズ。
- 時刻は変化しない
マーフィーの法則に従い、
時刻はいつでも、そして最悪のタイミングで変更される。
gettimeofday()でタイムアウト判定する者は地獄に堕ちる。
clock_gettime()のモノトニック時間を使おう。- TCPストリームには常に正しい形式のデータが送られてくる
バッファオーバーフローが脆弱性の王様なら、
パケット分割は脆弱性の王宮だ。
ペイロード長方式、区切り文字方式、どちらの方式も脆弱性の温床となる。
ランダムペイロードをバーストして耐障害性を検証しよう。- メッセージパッシングは種別毎に経路を分けた方が良い
別々のスレッドに飛ばす場合は正しいときもある。
しかし、一つのスレッドが複数経路のメッセージを受け付けると、
処理の順序性が非同期的になり厄介なバグを生みやすい。
メッセージシーケンスの各段階を別スレッドに振った場合は更に悲惨だ。
経路を分ける時は、メッセージのデータ型ではなく、シーケンスで纏めよう。- マルチスレッドパイプラインでは、生産者の優先度を消費者よりも高くすべき
消費者が仕事を終えないと、
生産者が頑張ってデータをキューイングしても詰まる一方である。
おまけに生産者が起きる度にプリエンプトされるので余計に効率が悪い。
パイプラインは後段ほど優先度を上げよう。- 標準に似たような物があっても、独自プロトコルを設計した方が拡張性が高い
これは酷い嘘だが、
世の中はそうした糞プロトコルで溢れ返っているようだ。
知れ渡っているプロトコルはほとんどの場合拡張領域を用意している。
パケットモニタツールのサポートも期待出来る。
アンテナを張って、RFCをちゃんと読んで、劣化サブセットの再発明はやめよう。- 32bitカウンタは値域が大きいので安心
秒30でuint32_tをカウントアップするとたった4年でラップアラウンドする。
忘れた頃に惨めな思いをしなくて済むように、64bitを使うか、
極端には16bitでも大丈夫なように設計しよう。- 動的メモリ確保は危険である
自作カスタムアロケータは大抵酷い劣化版mallocだ。
glibcのmallocはツールも含めて10000行以上あって、世界中から試されている。
尊重しよう。
BSS領域はオーバーランすると予想外の場所を破壊するし、
スタックメモリの危険性は言わずもがな。
静的メモリも別の危険性を持つことを忘れないようにしよう。- シングルスレッドは効率が悪い
Node.jsは使ってみた？
非同期IOのシングルスレッドモデルは単純で、
生産性が非常に高いことに最近気付いた。
なんてったってプリエンプトされないんだから。
優先度管理ではマルチスレッドが必要になるけれど、
そもそもSCHED_FIFOな子は起きたらすぐに寝ないといけないので、
そんなに変わらんかもなぁ、という気がしてる。- マルチクライアントは必要になってから対応すれば良い
シングルクライアントで話が済むなら楽だが、
あまりに楽なのでそこで一旦設計が固まってしまうと、
マルチ対応で大幅な修正を迫られる事になる。
YAGNI原則には反するが、いずれにせよ最初は大した手間ではない。
たとえ現在は要求されていなくても、
原則マルチ化でシングルはその特殊ケースとして設計しよう。- 「UNIXネットワークプログラミング」を読まなくてもUNIXネットワークプログラミングは出来る
ダウト！
周知のように、これはその分厚さにして隅から隅まで読む価値がある珍しい本だ。
(XTIのパートは除く。。除いていいよね？)
まだの人はなるべく近所の本屋で入手して地域経済に貢献しよう。
OOP みんなでやめれば 怖くない
まず最初に立場を明らかにしておくと、自分は全くオブジェクト指向が悪い物だとは思っていない。
むしろ自分がプログラムを作る立場ならば、積極的に使おうとするものだ。
ただこのパラダイム自体は、マルチスレッド同様に「おおっぴらには」忌避されるべきものだと思っている。
ソフトウェア工学の歴史は再利用の歴史とも言われている。
そうした中でOOPが実質的にC++、Javaによって再発見されたときには、
まさに再利用性の改善こそがその存在意義だったことは改めて説明するまでもない。
さて、それは本当だろうか。また、いつまで本当だろうか。
短期的には、あるいは一人で何もかもやる場合は、それは常に正しい。
しかし、既に設計済みのオブジェクト指向システムが時代を超えて生き残る理由は次の二つしかない。
1. 設計者が天才だった。
2. それを使わないわけにはいかなくなってしまった。
このうち、前者である確率は無視出来るほど低い。
Haskellがシステムプログラミングの主要言語になる確率と同じ位低いだろう。
理想郷には理想人しか住めないものだ。
と、いうわけで再利用と呼ばれているものの実態はほとんど後者に当てはまる。
継承システム、インタフェースの設計、Javaならば検査例外の問題もあるが、
これらがバージョンアップに耐えうるように初めから設計されると考えるのは、
ソフトウェア開発一般においての時間的制約とチーム平均IQを鑑みれば、ほとんど絵に描いた餅である。
実効的なオブジェクトシステムの成長とはリファクタリングによるスクラップ&ビルドに他ならないのだ。
これには大いに反論があるだろう。
Javaによる大規模システムでは、
開発チームの境界をクラスあるいはパッケージという境界で論理的に分割することが可能になり、
直交的な開発が遥かに容易になったからだ。
しかし、それはオブジェクト指向というよりは、カプセル化による恩恵である。
言うならば、これまでも可能であったベストプラクティスを言語処理系が表にしたことで、
みんながそれに気付いた、とでもいうべき話である。
オブジェクト指向が隠し持つ非生産性の最たるものは多態性だ。
正確に言うと、これもオブジェクト指向の専売特許ではない。
要点はインスタンスに仮想関数テーブルを付けて引き回すだけの話である。
さて、あなたは新しいプロジェクトに加わり、初めてコンパイル可能なソースを与えられたとする。
そしてある仮想関数が実際に何であるかを知りたいものとする。
ここでステップ実行出来るデバッガが無かったとしたら、一体どこまでやれるだろうか？
また、アップキャストがしばしばモジュール境界で用いられることを考えると、
本当に何が呼ばれるか、モジュール結合レベルまで理解しないと分からない事もあるだろう。
そしてそれはどこまでも連鎖し得る。
実際に何が起きるかを不透明にしてしまうような抽象化から恩恵を手に入れるためには、
そのシステムの設計をどっぷりと理解する必要がある。
これは工学というよりは、宗教入信とでも言うべきものだ。
設計の頭が変わったり、チームを移動したりしたならば、そうした思想をまた頭に入れ直す必要がある。
果たしてこれは生産性の進歩と呼べる代物だろうか？
自分も昔はGoFの本を枕にして、
人の手によりし人ならぬ美しきパターンに感動したものだ。
しかし、そうしたパターンはオブジェクト指向言語から少し離れてみると、
単にあるプラクティスが直裁的に実現できない故の迂回に過ぎなかったことが分かってきた。
Strategyが欲しい？
高階関数、あるいは関数ポインタをどうぞ。
Visitorが欲しい？
それはパターンマッチと呼ばれるものだ。
Factoryが欲しい？
カスタムアロケータのことですね。
Commandが欲しい？
テンプレート、または型クラスの事かな？
Iteratorが欲しい？
map/reduceの分厚いカタログからお好きな物をお選びあれ。
Interpretorが欲しい？
ほらよParsecにPEGにluaにyaccだ！
デザインパターンに対して多くの賛辞が寄せられ、
それがオブジェクト指向の発展した姿だと思い込まされそうになりながら、
実はそれとオブジェクト指向には何の関係もなかった、という事実は大変興味深い事であった。
話をデザインパターンに限定しすぎた。
そもそもオブジェクト指向が何であるかという話を遅延してきたので、ここで整理しよう。
一般的な定義は多分無いような気がするが、
差し当たって次の３つを満たす事がオブジェクト指向の要件であるとされる。
１．カプセル化
２．継承
３．多態性
これらはどれも、いわゆるオブジェクト指向言語を使わずとも実現可能な物だ。
継承についてはちゃんと触れていなかったが、これは先に触れたGoF本の冒頭にあったように、
実際は委譲によって代替することが可能だ。
仮想なんちゃらについて何か主張をお望みであるならば、
いつでもあなたを仄暗き(void *)教団へとお誘いしよう。
それは実利的なプラクティスというよりは、トリックプレイに近かかったはずのものである。
多重継承の悲惨さは語るに尽きないものだが、
その迂回としてのミックスインなりグルーなりといった機構がいつも求められているのを見る限り、
かくもオブジェクト指向を全うする事の困難さを痛感する。別に多重継承でよかったんじゃないの？
上に上げた３つのうち、カプセル化は唯一絶対に正しい。
ただ知って欲しいのは、別にCでもprivateとpublicを分ける事は可能だ。
そもそもそのためにstatic修飾がある。ファイルだって分かれるぞ。
だが、そうしたことも含めた、オブジェクト指向的な実装がちょっとだけ面倒くさいのは事実だ。
ただその労力は、C++の地雷を避ける神通力を得る労力に比べたらカスみたいなものだ。
他にも言及すべきものはある。
参照渡し、ガベージコレクション、ダックタイピング、テンプレートメタプログラミング、
リフレクション、JITコンパイル、アスペクト指向、COM、.NET・・・
おっと、全然関係無い話を挟んでしまう所だった。
あるプログラマがオブジェクト指向を指して、
「バナナが欲しかっただけなのに、ゴリラとジャングルが付いてきた」ようなものであると言った事がある。
(Coders at Workはこんなブログより1億倍面白いよ！)
だが、実際手を突っ込んだ多くの人は、本当に欲しかった物がバナナだったことも分からなかったのだ。
いまや我々はバナナが何であるかなんとなく分かってきた。
さあ、ゴリラとジャングルは名残惜しいが、我々はそれに捕われてはいけない。
じゃあ何があるのか？反論は対案を持って、だ。
それに関してはいつでも返せる言葉がある。即ち、銀の弾丸は無い。
我々は既に敗北しているのだ。
少なくともそれは純粋関数型言語パラダイムではないと思う。
一つの道筋はプロセス単位、いわゆるSOAとか呼ばれるものかもしれないが、
そういう方面の人たちから見れば以上の戯れ言は通過済みの話に過ぎないのかもしれない。
（恥ずかしながら、その方面はよく知らないのだ。）
DSLによるドメイン駆動設計は初めて見た時は銀とは言わないまでも銅の弾丸には見えたものだ。
実現手段をちょっと脇に置いておいて、
その額面通りにモデルと実装がシンタックスをインタフェースとして分割されるとするならば、
設計と拡張性と並行テストの面で飛躍的な生産性をもたらすと思えてくる。
しかし、と言ってしまうのだけど、
DSLとして書き下す事が可能なレベルというのは抽象構文にして木か、
あるいは有向非循環グラフ(DAG)までが、一般人の手に負えるせいぜいである。
もしそれが実現したいドメインのセマンティクスとしての限界でもあるならば、
例えば複数のマスターとスレーブが互いに副作用を起こすようなシステム(つまり世のソフトウェアの99%)では、
それらは表現可能だろうか？
シンタックスというのは本質的にステートレスなものだ。
なんだかゴリラが欲しかっただけなのにアマゾンと火星人が付いてたような気分になってきた。
Unixコマンドは再利用の最たるものだが、
例えばそのベースオブジェクトライブラリ(UOMとか名前が付いちゃうような)的なものがあったとして、
それが価値を持つとは思えないように、
またAPIが時代の要請に従ってレガシー化してインフレと破壊を繰り返すように、
カプセル化の適切な境界というのは元々要素還元とは異なる領域にあるのだと思う。
歴史は繰り返し、
ソフトウェアは小人のつま先に小人が乗るようにして発展してきた、という揶揄もある。
オブジェクト指向やガベージコレクションが再発見から発展したように、
案外先人の残した軌跡にこれからの道筋が見えるような気がするよ、
と、お茶を濁していい加減に終わりとしよう。
むしろ自分がプログラムを作る立場ならば、積極的に使おうとするものだ。
ただこのパラダイム自体は、マルチスレッド同様に「おおっぴらには」忌避されるべきものだと思っている。
- 理由１：OOPは再利用出来ない
ソフトウェア工学の歴史は再利用の歴史とも言われている。
そうした中でOOPが実質的にC++、Javaによって再発見されたときには、
まさに再利用性の改善こそがその存在意義だったことは改めて説明するまでもない。
さて、それは本当だろうか。また、いつまで本当だろうか。
短期的には、あるいは一人で何もかもやる場合は、それは常に正しい。
しかし、既に設計済みのオブジェクト指向システムが時代を超えて生き残る理由は次の二つしかない。
1. 設計者が天才だった。
2. それを使わないわけにはいかなくなってしまった。
このうち、前者である確率は無視出来るほど低い。
Haskellがシステムプログラミングの主要言語になる確率と同じ位低いだろう。
理想郷には理想人しか住めないものだ。
と、いうわけで再利用と呼ばれているものの実態はほとんど後者に当てはまる。
継承システム、インタフェースの設計、Javaならば検査例外の問題もあるが、
これらがバージョンアップに耐えうるように初めから設計されると考えるのは、
ソフトウェア開発一般においての時間的制約とチーム平均IQを鑑みれば、ほとんど絵に描いた餅である。
実効的なオブジェクトシステムの成長とはリファクタリングによるスクラップ&ビルドに他ならないのだ。
- 理由２：OOPは生産性が低い
これには大いに反論があるだろう。
Javaによる大規模システムでは、
開発チームの境界をクラスあるいはパッケージという境界で論理的に分割することが可能になり、
直交的な開発が遥かに容易になったからだ。
しかし、それはオブジェクト指向というよりは、カプセル化による恩恵である。
言うならば、これまでも可能であったベストプラクティスを言語処理系が表にしたことで、
みんながそれに気付いた、とでもいうべき話である。
オブジェクト指向が隠し持つ非生産性の最たるものは多態性だ。
正確に言うと、これもオブジェクト指向の専売特許ではない。
要点はインスタンスに仮想関数テーブルを付けて引き回すだけの話である。
さて、あなたは新しいプロジェクトに加わり、初めてコンパイル可能なソースを与えられたとする。
そしてある仮想関数が実際に何であるかを知りたいものとする。
ここでステップ実行出来るデバッガが無かったとしたら、一体どこまでやれるだろうか？
また、アップキャストがしばしばモジュール境界で用いられることを考えると、
本当に何が呼ばれるか、モジュール結合レベルまで理解しないと分からない事もあるだろう。
そしてそれはどこまでも連鎖し得る。
実際に何が起きるかを不透明にしてしまうような抽象化から恩恵を手に入れるためには、
そのシステムの設計をどっぷりと理解する必要がある。
これは工学というよりは、宗教入信とでも言うべきものだ。
設計の頭が変わったり、チームを移動したりしたならば、そうした思想をまた頭に入れ直す必要がある。
果たしてこれは生産性の進歩と呼べる代物だろうか？
- 理由３：それがOOPである必要は無い
自分も昔はGoFの本を枕にして、
人の手によりし人ならぬ美しきパターンに感動したものだ。
しかし、そうしたパターンはオブジェクト指向言語から少し離れてみると、
単にあるプラクティスが直裁的に実現できない故の迂回に過ぎなかったことが分かってきた。
Strategyが欲しい？
高階関数、あるいは関数ポインタをどうぞ。
Visitorが欲しい？
それはパターンマッチと呼ばれるものだ。
Factoryが欲しい？
カスタムアロケータのことですね。
Commandが欲しい？
テンプレート、または型クラスの事かな？
Iteratorが欲しい？
map/reduceの分厚いカタログからお好きな物をお選びあれ。
Interpretorが欲しい？
ほらよParsecにPEGにluaにyaccだ！
デザインパターンに対して多くの賛辞が寄せられ、
それがオブジェクト指向の発展した姿だと思い込まされそうになりながら、
実はそれとオブジェクト指向には何の関係もなかった、という事実は大変興味深い事であった。
話をデザインパターンに限定しすぎた。
そもそもオブジェクト指向が何であるかという話を遅延してきたので、ここで整理しよう。
一般的な定義は多分無いような気がするが、
差し当たって次の３つを満たす事がオブジェクト指向の要件であるとされる。
１．カプセル化
２．継承
３．多態性
これらはどれも、いわゆるオブジェクト指向言語を使わずとも実現可能な物だ。
継承についてはちゃんと触れていなかったが、これは先に触れたGoF本の冒頭にあったように、
実際は委譲によって代替することが可能だ。
仮想なんちゃらについて何か主張をお望みであるならば、
いつでもあなたを仄暗き(void *)教団へとお誘いしよう。
それは実利的なプラクティスというよりは、トリックプレイに近かかったはずのものである。
多重継承の悲惨さは語るに尽きないものだが、
その迂回としてのミックスインなりグルーなりといった機構がいつも求められているのを見る限り、
かくもオブジェクト指向を全うする事の困難さを痛感する。
上に上げた３つのうち、カプセル化は唯一絶対に正しい。
ただ知って欲しいのは、別にCでもprivateとpublicを分ける事は可能だ。
そもそもそのためにstatic修飾がある。ファイルだって分かれるぞ。
だが、そうしたことも含めた、オブジェクト指向的な実装がちょっとだけ面倒くさいのは事実だ。
ただその労力は、C++の地雷を避ける神通力を得る労力に比べたらカスみたいなものだ。
他にも言及すべきものはある。
参照渡し、ガベージコレクション、ダックタイピング、テンプレートメタプログラミング、
リフレクション、JITコンパイル、アスペクト指向、COM、.NET・・・
おっと、全然関係無い話を挟んでしまう所だった。
あるプログラマがオブジェクト指向を指して、
「バナナが欲しかっただけなのに、ゴリラとジャングルが付いてきた」ようなものであると言った事がある。
(Coders at Workはこんなブログより1億倍面白いよ！)
だが、実際手を突っ込んだ多くの人は、本当に欲しかった物がバナナだったことも分からなかったのだ。
いまや我々はバナナが何であるかなんとなく分かってきた。
さあ、ゴリラとジャングルは名残惜しいが、我々はそれに捕われてはいけない。
- でっていう
じゃあ何があるのか？反論は対案を持って、だ。
それに関してはいつでも返せる言葉がある。即ち、銀の弾丸は無い。
我々は既に敗北しているのだ。
少なくともそれは純粋関数型言語パラダイムではないと思う。
一つの道筋はプロセス単位、いわゆるSOAとか呼ばれるものかもしれないが、
そういう方面の人たちから見れば以上の戯れ言は通過済みの話に過ぎないのかもしれない。
（恥ずかしながら、その方面はよく知らないのだ。）
DSLによるドメイン駆動設計は初めて見た時は銀とは言わないまでも銅の弾丸には見えたものだ。
実現手段をちょっと脇に置いておいて、
その額面通りにモデルと実装がシンタックスをインタフェースとして分割されるとするならば、
設計と拡張性と並行テストの面で飛躍的な生産性をもたらすと思えてくる。
しかし、と言ってしまうのだけど、
DSLとして書き下す事が可能なレベルというのは抽象構文にして木か、
あるいは有向非循環グラフ(DAG)までが、一般人の手に負えるせいぜいである。
もしそれが実現したいドメインのセマンティクスとしての限界でもあるならば、
例えば複数のマスターとスレーブが互いに副作用を起こすようなシステム(つまり世のソフトウェアの99%)では、
それらは表現可能だろうか？
シンタックスというのは本質的にステートレスなものだ。
なんだかゴリラが欲しかっただけなのにアマゾンと火星人が付いてたような気分になってきた。
Unixコマンドは再利用の最たるものだが、
例えばそのベースオブジェクトライブラリ(UOMとか名前が付いちゃうような)的なものがあったとして、
それが価値を持つとは思えないように、
またAPIが時代の要請に従ってレガシー化してインフレと破壊を繰り返すように、
カプセル化の適切な境界というのは元々要素還元とは異なる領域にあるのだと思う。
歴史は繰り返し、
ソフトウェアは小人のつま先に小人が乗るようにして発展してきた、という揶揄もある。
オブジェクト指向やガベージコレクションが再発見から発展したように、
案外先人の残した軌跡にこれからの道筋が見えるような気がするよ、
と、お茶を濁していい加減に終わりとしよう。
ユーザー空間でリングバッファが最適なデータ構造であるケースはほとんど無い気がする
リングバッファとは何のためにあるものだろう？
自分の周りでは大体次のようなケースで使われている事が多かった。
これらは結局は一つの事を実現しようとしている。
つまりは、
「静的な領域で排他されたデータに緩衝領域を設けた上で読み書きを無限にやりたい」
ということだ。
それがキューやガベージコレクションでは無い理由は、
おそらくポインタアクセスとインデックスの更新で操作が行えるという意味で、
リングバッファは「高速」だからである。
「高速」とは"高速"の事ではない。
これは一つずつネチネチと見てみよう。
読み書きインデックスの管理方法が定常時と異なる。
これはデータ構造に少なくとも4段階のステートを設ける事を要求するものであって、
既に経済的に許容しがたい。
二分探索をバグ無く実装することがあれほど困難な人類には荷が重すぎるような気がしてならない。
読み込みが最新のもの一枚であれば簡単だが、
例えば可能な限り過去に遡ってデータを参照したい、といったときに、
インデックスの折り返しが生じる（そしてそれは前述の4段階のステートでそれぞれやり方が異なる！）。
しかし、「高速」な動作を期待するならば、
やがて消費者と生産者は別スレッドに割り振りたくなるだろう。
ここで既に単純なポインタアクセスで要を済ますという口上は少し弱まり、
レッドの同期機構を使い、書き込みが読み込みを追い越さないように制御する必要が有る。
もっと「高速」にするためには、書き込みが追いついたときに条件変数を使って待つか、
シグナルでも使う必要が有るかもしれない。
ただし、マルチスレッドでシグナルに頼る者は地獄に落ちる。
さて、ここまで簡単だと思ってきた人もそろそろしんどくなってきたはずだ。
この背景には、リングバッファで管理される各要素の領域は固定長であるという前提がある。
別にオブジェクトを動的に割り当ててreallocとかすればいいんじゃないの？
と思われるかもしれないが、
その方向性ならばこの機構全体が
究極の排他メモリ管理であるmallocとfreeに置き換えられないとおかしいので、
結局何をやりたいのかわからない。
で、固定長はワーストケースデザインでオーバーランが起きないデータでしかうまくいかない。
組み込みソフト開発でやるのはそうした事だが、
問題領域がデータ量的にスケールアップして地獄に落ちるまでに、
一旦リングバッファの存在を忘れておく必要が有る。
複数のスレッドがリングバッファのデータを欲した場合である。
少なくともセマフォを使わないと消費者に他の消費者の存在を隠す事が出来ない。
そしてセマフォを使いこなせるプログラマは日本には８ビットで数えられるぐらいしか存在していない。
ところで、複数生産者の話は敢えてしなかった。
これは完全に止めを刺してしまうのでスポーツマンシップに反する。
それでは代わりに何があるのか？
ちらっと書いたが、例としてはガベージコレクションと固定長キューだ。
大人なら参照カウントのGCぐらいは自前で実装していないとおかしいので、
こっちについては何も問題ない。GCは前説で掲げた問題のうち4つを完全に解決する。
残り1つについては別の機構を用意した方が良いだろう。
ただし、これは「高速」ではないかもしれない。
固定長キューは3つを解決し、残り2つを簡単に解決する手段を提供する。
キューの実装はあまりにも簡単なので、このブログを書いている時間だけで５つは作れる。
これもあまり「高速」ではないかもしれない。
蛇足気味にまとめると、
それでは果たして「高速」である事に意味はあるのだろうか？
いわずもがな、この種の「高速」化は早すぎる最適化である可能性が極めて高い。
それでも複雑さを乗り越えて静的なポインタアクセスにこだわる必要がありうるとしたら、
デバイスドライバレベルで極めて効率的なアクセスが要求されるレベルか、
それぐらいしか思い当たらない。
それでもデザインパターンとかテンプレート使えばいいじゃん、
という声が聞こえた気がするが、
そういったチンピラ共のせいで気合いを入れて作ったバナーを削るハメになるので、お断りである。
というわけで、ユーザー空間でリングバッファが最適なデータ構造であるケースはほとんど無い気がする。
自分の周りでは大体次のようなケースで使われている事が多かった。
- 仮想的に無限の大きさを持つように見える記憶領域を提供する
- 読み出しと書き込みのタイミングが非同期的なデータを安全に更新する
- 随時追加されるが、合計数が有限のキーにより探索されるマップを提供する
これらは結局は一つの事を実現しようとしている。
つまりは、
「静的な領域で排他されたデータに緩衝領域を設けた上で読み書きを無限にやりたい」
ということだ。
それがキューやガベージコレクションでは無い理由は、
おそらくポインタアクセスとインデックスの更新で操作が行えるという意味で、
リングバッファは「高速」だからである。
「高速」とは"高速"の事ではない。
- 初期状態の管理
- 検索の複雑さ
- インデックス更新の一貫性
- 領域のサイズ制約
- 複数消費者間の一貫性
これは一つずつネチネチと見てみよう。
- 初期状態の管理
読み書きインデックスの管理方法が定常時と異なる。
これはデータ構造に少なくとも4段階のステートを設ける事を要求するものであって、
既に経済的に許容しがたい。
二分探索をバグ無く実装することがあれほど困難な人類には荷が重すぎるような気がしてならない。
- 検索の複雑さ
読み込みが最新のもの一枚であれば簡単だが、
例えば可能な限り過去に遡ってデータを参照したい、といったときに、
インデックスの折り返しが生じる（そしてそれは前述の4段階のステートでそれぞれやり方が異なる！）。
- インデックス更新の一貫性
しかし、「高速」な動作を期待するならば、
やがて消費者と生産者は別スレッドに割り振りたくなるだろう。
ここで既に単純なポインタアクセスで要を済ますという口上は少し弱まり、
レッドの同期機構を使い、書き込みが読み込みを追い越さないように制御する必要が有る。
もっと「高速」にするためには、書き込みが追いついたときに条件変数を使って待つか、
シグナルでも使う必要が有るかもしれない。
ただし、マルチスレッドでシグナルに頼る者は地獄に落ちる。
さて、ここまで簡単だと思ってきた人もそろそろしんどくなってきたはずだ。
- 領域のサイズ制約
この背景には、リングバッファで管理される各要素の領域は固定長であるという前提がある。
別にオブジェクトを動的に割り当ててreallocとかすればいいんじゃないの？
と思われるかもしれないが、
その方向性ならばこの機構全体が
究極の排他メモリ管理であるmallocとfreeに置き換えられないとおかしいので、
結局何をやりたいのかわからない。
で、固定長はワーストケースデザインでオーバーランが起きないデータでしかうまくいかない。
組み込みソフト開発でやるのはそうした事だが、
問題領域がデータ量的にスケールアップして地獄に落ちるまでに、
一旦リングバッファの存在を忘れておく必要が有る。
- 複数消費者の問題
複数のスレッドがリングバッファのデータを欲した場合である。
少なくともセマフォを使わないと消費者に他の消費者の存在を隠す事が出来ない。
そしてセマフォを使いこなせるプログラマは日本には８ビットで数えられるぐらいしか存在していない。
ところで、複数生産者の話は敢えてしなかった。
これは完全に止めを刺してしまうのでスポーツマンシップに反する。
それでは代わりに何があるのか？
ちらっと書いたが、例としてはガベージコレクションと固定長キューだ。
大人なら参照カウントのGCぐらいは自前で実装していないとおかしいので、
こっちについては何も問題ない。GCは前説で掲げた問題のうち4つを完全に解決する。
残り1つについては別の機構を用意した方が良いだろう。
ただし、これは「高速」ではないかもしれない。
固定長キューは3つを解決し、残り2つを簡単に解決する手段を提供する。
キューの実装はあまりにも簡単なので、このブログを書いている時間だけで５つは作れる。
これもあまり「高速」ではないかもしれない。
蛇足気味にまとめると、
それでは果たして「高速」である事に意味はあるのだろうか？
いわずもがな、この種の「高速」化は早すぎる最適化である可能性が極めて高い。
それでも複雑さを乗り越えて静的なポインタアクセスにこだわる必要がありうるとしたら、
デバイスドライバレベルで極めて効率的なアクセスが要求されるレベルか、
それぐらいしか思い当たらない。
それでもデザインパターンとかテンプレート使えばいいじゃん、
という声が聞こえた気がするが、
そういったチンピラ共のせいで気合いを入れて作ったバナーを削るハメになるので、お断りである。
というわけで、ユーザー空間でリングバッファが最適なデータ構造であるケースはほとんど無い気がする。
awk: ディレクトリ構造を辿るCGIをAwkで書く
busybox縛りな環境でWebから外部記憶にアクセスする必要に迫られたので、
当然の如くAwkでCGIを書く事になった。
基本的にはAwkのgetlineでコマンドの返りを見て、
JSONにして送るだけ。
ディレクトリに対してはlsを経由し、
txtとjpgについてはその情報もフィードバックするような仕掛けを仕込む。
jpgについてはこの場でデータを送るのではなくて、
一旦ブラウザに返した後、別のCGI(Cで実装)で適宜データを転送するという流れで作っている。
非常にチェックが甘いのだが、
一応意図しないアクセスを防御するためにパス指定で親とルートを辿れないようにしてはいる。
とはいえ、見る人が見たらあっさり攻撃出来てしまうかもしれない。
ちなみにこのやり方の問題点はls -lコマンドを経由するので、
ファイル数が莫大なストレージに対しては非常にレスポンスが悪いということ。
これについては焼け石に水ではないが、一応ページ番号も操作可能にする仕掛けを入っている。
結論から言うと、これはプロトタイプには出来るかもしれないが、
本番で使えるような代物ではなかった。
よって、DBを駆使した高速かつ柔軟な管理システムが求められた訳である。
いい加減再発明がひどすぎるかもしれない。
もっといいやり方はあるかな？
当然の如くAwkでCGIを書く事になった。
- ソース
#! /usr/bin/awk -f
BEGIN {
print "Content-type: text\n";
}
{
if(($2 ~ /\.\.\//) || ($2 !~ /^\./)) {
print "{\"e\":\"EPERM\"}";
exit;
}
op = $1;
lpath = $2;
str = "";
if(op == "d") {
page = $3;
if(!page) page = 0;
path = "/mnt/" lpath;
cmd = "ls -l " path ;
str = str "{\"l\":[";
fst = 1;
fileCnt = 0;
stepCnt = 0;
skipCnt = page * 50;
while((cmd | getline line) > 0) {
if(stepCnt++ < skipCnt) continue;
if(fileCnt++ >= 50) continue;
counts = split(line, vals, "[ \t]");
if(!fst) {
str = str ",";
}
fst = 0;
if(vals[1] ~ /^d/) {
str = str "{\"d\":\"" lpath "/" vals[counts] "\"}";
} else {
str = str "{\"f\":\"" lpath "/" vals[counts] "\"}";
}
}
close(cmd);
str = str "],\"p\":" page ",\"a\":" (stepCnt / 50) ",\"o\":\"" lpath "\"}";
printf("%s", str);
} else if (op == "f") {
path = "/mnt/" lpath;
if(lpath ~ /^.+\.txt/) {
str = str "{\"t\":\"" lpath "\",\"c\":\"";
while ((getline < path) > 0) {
str = str $0;
}
str = str "\"}"
printf("%s", str);
} else if (lpath ~ /^.+\.jpg/) {
str = str "{\"j\":\"" lpath "\",\"c\":\"" path "\"}";
printf("%s", str);
}
} else {
print "{\"e\":\"ECOMMAND\"}";
}
}
基本的にはAwkのgetlineでコマンドの返りを見て、
JSONにして送るだけ。
ディレクトリに対してはlsを経由し、
txtとjpgについてはその情報もフィードバックするような仕掛けを仕込む。
jpgについてはこの場でデータを送るのではなくて、
一旦ブラウザに返した後、別のCGI(Cで実装)で適宜データを転送するという流れで作っている。
非常にチェックが甘いのだが、
一応意図しないアクセスを防御するためにパス指定で親とルートを辿れないようにしてはいる。
とはいえ、見る人が見たらあっさり攻撃出来てしまうかもしれない。
ちなみにこのやり方の問題点はls -lコマンドを経由するので、
ファイル数が莫大なストレージに対しては非常にレスポンスが悪いということ。
これについては焼け石に水ではないが、一応ページ番号も操作可能にする仕掛けを入っている。
結論から言うと、これはプロトタイプには出来るかもしれないが、
本番で使えるような代物ではなかった。
よって、DBを駆使した高速かつ柔軟な管理システムが求められた訳である。
いい加減再発明がひどすぎるかもしれない。
もっといいやり方はあるかな？
C: 固定小数点演算マクロ
C言語が素晴らしい理由の半分はCPPがあるからで、
残りの半分は多くの人がCPPを避けてくれるということだ。
今更固定小数点演算なんて、という向きもあるだろうが、
画像処理系ではfloatなんて使ってられんというか、
そもそも浮動小数点は甘えみたいなアーキテクチャは組み込みでは結構当たり前である。
と、いうわけでマクロを駆使した固定小数点演算をちょっと取り上げてみたい。
仮数部と小数部を構造体のビットフィールドとしてジェネリックに宣言するマクロを用意する。
構造体として宣言するが、普通のコンパイラならば実際の演算は符号無し整数演算に変換される。
四則演算では誤ったQ値の取り扱いをどのように検出するかを気にしていて、
ここでは明示的に構造体にキャストする事で、
指定したQ値とオペランドのQ値が異なる場合にnon scalar type conversionコンパイルエラーを出させて静的なチェックを行う。
浮動小数点リテラルから固定小数点への変換は、コンパイル時に全て終わらせたい。
コードの中で動的な変換をしてしまったら、本末転倒という奴だ。
そこでコンパイル時定数を検出するgccのビルトイン関数を使い定数式でないものを変換しようとした場合は
ゼロ除算警告を出させるように仕向ける。
飽和演算や異なるQ値同士での演算はここでは考慮していない。
発展するにしても、gccではビットフィールドの位置をcontainer_ofマクロみたいな感じで取得する事が出来ないので、
やるとしたらQ値のフラグをぺたぺた追加していくことになるだろうか。
さすがにそこまでいくとアドホックな演算の方が好まれるかもしれない。
オープンソースコンパイラなら改造も出来ようが、
今使ってるアーキテクチャではそれが無いので今のところはそんな方向性で妥協している。
もっといい方法はあるかな？
残りの半分は多くの人がCPPを避けてくれるということだ。
今更固定小数点演算なんて、という向きもあるだろうが、
画像処理系ではfloatなんて使ってられんというか、
そもそも浮動小数点は甘えみたいなアーキテクチャは組み込みでは結構当たり前である。
と、いうわけでマクロを駆使した固定小数点演算をちょっと取り上げてみたい。
- ソース
#ifndef _FIXEDPOINT_H_
#define _FIXEDPOINT_H_
#include <stdint.h>
/* quasi-generic fixed point operators */
/* type specifier: with double expansion */
#define __fix32(n) fix32_q##n##_t
#define fix32(n) __fix32(n)
/* float conversion: float input must be compile-time constant.
* with help of built in constant specifier, use of non-constant value causes 0 division warning.
*/
#define float_to_fix32(x,n) ({\
fix32(n) ____fix; \
____fix.val = (double)((x) / __builtin_constant_p(x)) * (1 << (n)) + 0.5;\
____fix;})
/* other conversions */
#define int_to_fix32(x,n) ({\
fix32(n) ____fix;\
____fix.val = ((int)(x)) << (n);\
____fix;})
#define fix32_to_int(x,n) ({(fix32(n)(x)).val >> (n);})
/* fixed pointed arithmetics:
* if Q-values mismatched, then non-scalar type conversion error will be reported */
#define add_fix32(x,y) ({\
typeof(x) _____res;\
_____res.val = ((typeof(x))y).val + (x).val;\
_____res;})
#define sub_fix32(x,y) ({\
typeof(x) _____res;\
_____res.val = (x).val - ((typeof(x))y).val;\
_____res;})
#define mul_fix32(x,y,n) ({\
fix32(n) _____res;\
_____res.val = (((fix32(n))(x)).val * ((fix32(n))(y)).val) >> (n);\
_____res;})
/* use of division is strongly discouraged, though API provided */
#define div_fix32(x,y,n) ({\
fix32(n) _____res;\
_____res.val = (((fix32(n))(x)).val << (n)) / ((fix32(n))(y)).val;\
_____res;})
/* inefficient but slightly precise version of multiplication:
* though saturation yet be considered.
*/
#define mul_precise_fix32(x,y,n) ({\
fix32(n) _____res;\
fix32(n) _____x = (x);\
fix32(n) _____y = (y);\
_____res.val = ((_____x.val * _____y.frac) >> (n)) + (_____x.val * _____y.mant);\
_____res;})
/* dump function (debug purpose only) */
#define dump_fix32(x, n) printf("0x%08x:%.3f\n",(x).val, ((x).mant ) + ((x).val & ((1 << (n)) - 1)) / (float) (1<<(n)))
/* create struct definition by Q value */
#define __INSTANTIATE_FIX32(n) typedef struct fix32_q##n {\
union{\
struct{\
int32_t frac:(n);\
int32_t mant:32-(n);\
}; \
int32_t val;\
};\
} fix32(n);
/* double expansion */
#define INSTANTIATE_FIX32(n) __INSTANTIATE_FIX32(n)
#endif
仮数部と小数部を構造体のビットフィールドとしてジェネリックに宣言するマクロを用意する。
構造体として宣言するが、普通のコンパイラならば実際の演算は符号無し整数演算に変換される。
四則演算では誤ったQ値の取り扱いをどのように検出するかを気にしていて、
ここでは明示的に構造体にキャストする事で、
指定したQ値とオペランドのQ値が異なる場合にnon scalar type conversionコンパイルエラーを出させて静的なチェックを行う。
浮動小数点リテラルから固定小数点への変換は、コンパイル時に全て終わらせたい。
コードの中で動的な変換をしてしまったら、本末転倒という奴だ。
そこでコンパイル時定数を検出するgccのビルトイン関数を使い定数式でないものを変換しようとした場合は
ゼロ除算警告を出させるように仕向ける。
飽和演算や異なるQ値同士での演算はここでは考慮していない。
発展するにしても、gccではビットフィールドの位置をcontainer_ofマクロみたいな感じで取得する事が出来ないので、
やるとしたらQ値のフラグをぺたぺた追加していくことになるだろうか。
さすがにそこまでいくとアドホックな演算の方が好まれるかもしれない。
オープンソースコンパイラなら改造も出来ようが、
今使ってるアーキテクチャではそれが無いので今のところはそんな方向性で妥協している。
もっといい方法はあるかな？
