[ruby-dev:11475] Re: Ruby I18N

In article <[e-mail]>,
  [e-mail] (Yukihiro Matsumoto) writes:

>   * 効率がめちゃめちゃ悪くなりそうな

どうなんでしょうねぇ? GNU Emacs さえも(21 の次か?)文字型が入る(同時に
Unicode ベースになる)中、Ruby が依然として整数を直接扱っている、という
のも趣があっていいかも知れませんが。

さて、それはともかくとして、効率について一つ昔話を。

趣旨 1: UTF-8 らしき 31bit 整数配列による文字列以外に、8bit 整数配列に
よる文字列(ないしはバイト列)も入れるべきだ。そして、それらを同じように
扱えるように抽象化たインターフェースを定義すべきだ。

趣旨 2: 昔話

趣旨 3: 笑い話

趣旨 4: emacs の変化に振り回される無力な人々の記録

むかしむかし、GNU Emacs 20.2 から 20.3 のころ、冬は雪に閉ざされて娯楽
もないとあるところに emacs lisp による高速な base64 デコーダの実装に熱
血している人がおりました。ありとあらゆる実験の結果、結局たどり着いた結
論は、メモリの確保やアクセスは最小限、cons セルなんてもってのほか、と
いうなんとも lisp らしくない、しかし C の感覚でいえば至極当然なもので
した。その結論に基づき最終的に最も効率が良いものとして実装されたものは、
文字列を一つ受け取り、それを先頭から順番に読んでデコードしつつその文字
列自身にデコード結果を破壊的に書き込んでいくというものでした。base64 
デコードは入力のだいたい 3/4 の大きさの出力を生成するので、これから入
力する部分を破壊せずに出力を保持することができるのです。これだと出力を
一時的にとっておくバッファも必要ありません。これはとても高速で、他の実
装 --- base64 デコーダはさまざまなパッケージでいろいろな実装が行なわれ
ていました --- よりもかなり速いものでした。ただし、その人自身がそれ以
前に実装した C で記述されたデコーダを DL (Dynamic Loading) で取り込ん
で呼び出してしまうものと、その人の知合いが実装した CCL (Code
Conversion Language)によるものにはかないませんでしたが。まぁ、DL や 
CCL などという移植性に欠けたものを使わない中では最速だったわけです。

さて、最速だったのは 20.2 での話です。ある日、その人の知合いがちゃんと
速度を測定しようと思い立ちました。測定してみると、非常に不思議な結果が
出てきました。なんとその最速だったはずのデコーダは 20.3 では非常に遅い
のです。ただ遅いだけでなく --- 両対数グラフにプロットしてみると傾きが急
で --- オーダーが違うのです。入力の長さ n に対して O(n^2) くらいの時間
がかかっていました。もちろん base64 デコードは O(n) で可能な処理で、こ
んなに遅いのは許し難いことですし、20.2 のころはこんな不合理なことはあ
りませんでした。たちまち原因追求に熱血し、とある ML に話を出すなどして
他の腕利きを巻き込み、さまざまな実験結果や憶測が飛び交いました。不思議
なことに同じ実装で追試して O(n) ですむという話も出てきました。こうなる
と熱血度も上昇します。結局、emacs のソースを調べることになり、最終的に
は原因が判明しました。

判明した原因は 20.3 で文字列の扱いが変化したことであり、文字列を操作す
るプリミティブのオーダーが O(1) から O(n) に悪化していたというものでし
た。もちろん、いろいろと工夫がしてあって、だいたい O(1) で済むようになっ
てはいたのですが、このデコーダは入力によってはそれでは済まない場合に該
当していました。追試で O(n) で済むという話は、入力の違いによるものでし
た。この違いは 20.3 で導入された multibyte string と unibyte string の
差でした。どちらも文字列なのですが、unibyte string は文字が 1 バイトで
表現できる場合に使うもので、n 番目の文字(ないしはバイト)をアクセスする
には O(1) で済みます。multibyte string は文字単位でアクセスされ、n 番
目の文字をアクセスするには最悪 O(n) になります。もちろん、multibyte
string でも先頭や末尾をアクセスするぶんには O(1) ですし、キャッシュに
より直前にアクセスした場所の隣をアクセスする場合には O(1) になるように
はなっていましたが。この破壊型の base64 デコーダではループを i 番目に
回った時の処理でだいたい 4i 番目付近を読んで 3i 番目付近に書き込むとい
う動作をします。もし、そのキャッシュが(LRU でも FIFO でもかまいません
が)二つ値を覚えていたら、全体の処理でも最悪 O(n) ですんだでしょうが、
残念ながら一つしか覚えていなかったのです。結局、その人は文字列のコピー
が一回増えてしまうことを深く嘆き悲しみつつ unibyte string に変換してか
ら処理するように修正したということです。

この話はその後、付随して発見された emacs の bug が修正されたり、その修
正について議論されて aset の仕様が変化したりといった発展がありましたが、
細かい話なのでここではおいておきます。そして base64 についてはずいぶん
と後、20.4 で builtin としてデコーダ/エンコーダが実装され、このような
苦労は泡と化してしまいましたとさ。どっとはらい。

注:
  「熱血」というよりは「現実逃避」としたほうが現実に即していたかも知れ
  ません。

  Ruby とあまり関係ない昔話ですいません。

というように、バイト列を扱いたい時には効率上、(UTF-8 を含む)不定長
multibyte 表現はあまり適していません。バイト列そのままな実装が提供され
ているととてもありがたいです。むろん、この場合、文字列の中身がどちらで
あろうが、同様のインターフェースでアクセスできる必要があります。

そして、そのインターフェースに沿った他の実装を後から(Ruby でも C でも)
追加できるようになっていると素晴らしいと思うのですが...
-- 
[田中 哲][たなか あきら][Tanaka Akira]
「くっだらないコト聞いちゃったねー$(C⊇ ごっめーん$(C⊇」
  (魔法使い養成専門 マジックスター学院 2, 南澤ミヅキ)