BT

InfoQ ホームページ ニュース Clojure 1.1,効率のためにトランジェントとチャンクシーケンスを追加

Clojure 1.1,効率のためにトランジェントとチャンクシーケンスを追加

ブックマーク

原文(投稿日:2009/12/17)へのリンク

Clojure 1.1 RC1 が公開された - さあ,最終リリース前に試して,問題を見つけたら報告しよう。ソースコードは GitHub の Clojure 1.1 ブランチにある。Google Code からはバイナリパッケージ が入手できる。継続的インテグレーションサーバによる Clojure ブランチの定期的ビルド も提供されている。
Changes ファイル には 1.1 以前にクローズされた問題点 を含む,Clojure 1.0 からの変更点がリストアップされている。その中には,Clojure プログラムのパフォーマンスを向上させてくれそうな大きな機能もいくつかある。

例えば トランジェント (Transient) は,永続的データ構造(persistent data structure) 構築のパフォーマンスを大幅に改善する。永続的データ構造 は Clojure の Vector,Map,Set などを支えるコンセプトであり,Clojure の重要な要素だ (Clojure の作成者 Rich Hickey 氏による永続データ構造に関する解説 を参照)。永続的データ構造とは,簡単に言えば不変 (immutable)である,ということだ。だから挿入や削除などの変更を行うためには,データ構造のコピーを新たに生成しなければならない。しかしトリックがひとつある。永続データ構造は内部構成やすべての項目が不変であるため,データについてはすべて,データ構造も大部分が共有可能なのだ。そのために,コピー生成のオーバーヘッドはきわめて小さなものになる。

コピーのオーバーヘッドが小さいとはいっても,場合によってはデータ構造体に数多くの要素を挿入しなければならないこともあり得る。トランジェントはそのような場合へのソリューションである。簡単に言うとこれは,修正作業を行う前に永続的なデータ構造を一時的(Transient)なものに転換する,というアイディアだ。transient 関数がこの処理を行う。一時的なものになったデータ構造体は,永続的であったときと同じアクセス関数をサポートする。ただしデータを修正する場合にはサフィックス "!" を付けた別の関数を用いる必要がある。例えば conj に代わって conj! を使用する。

永続的データ構造とその一時的バージョンとの関係を考える上では,java.lang.Stringjava.lang.StringBuilder の関係が参考になるだろう。前者が不変であり,変更が新しいコピーの生成をともなうのに対して,後者はデータを直接修正することができる。ただし共通点はここまでだ。まず StringBuffer の生成について言えば,これは String の内容をコピーするという O(n) オペレーションである。対して永続的なデータ構造体を等価な一時的データに変換する操作は,安価な O(1) オペレーションだ。この操作により新たな一時的オブジェクトが生成され,データ構造体の新しいルートオブジェクトと,一時的(Transient)であることをマークするフラグが保持される。データコピーは発生しない。処理の終了後,一時的データ構造を永続的データ構造にする必要があれば,これと同じような O(1) オペレーションが実行される。

それにしても一時的データ構造を再度永続的なものに戻す必要があるのはなぜだろう? 一時的なデータのまま使い続けることはできないのだろうか? しかし,それは不可能である - なぜなら一時的データ構造にはもうひとつ,単一のスレッドからしか利用できない,という重大な制約があるからだ。その理由は単純である。一時的データは変更可能なので,異なったスレッドからの操作は危険であり,同期処理が必要になるためだ。ここで永続的データ構造を使用すれば,スレッド間のデータ共用はシンプルなものになる。つまり一時的データにすることで,ひとつのスレッドからデータの直接修正が可能になる。それを永続的データ構造に戻すことによって,再び他のスレッドからもアクセス可能になる,ということだ。


Clojure 1.1 のもうひとつの効率向上策はチャンクシーケンス(Chunked Sequence) だ。その概要を知るには,Rich Hickey 氏の チャンクシーケンスに関する説明(注意:PDFファイル) のスライドを参照して頂きたい。
チャンクシーケンスの背景にある基本的なアイデアは,(遅延) シーケンスによって発生するオーバーヘッドの削除にある。
遅延シーケンス (Lazy Sequence) は 確実に必要になるまで処理の実行を遅延させる,というもので,Clojure では全般にわたって使用されている。場合によっては処理がほとんど実行されないこともある。次のコードはその例だ。

 

(take 10 (range 1 1000000000000)  )

range 関数は指定された間隔のすべての数値を発生させるような遅延シーケンスを生成する。一方で take 関数は,それに続くーケンスを 10 回繰り返す。遅延アプローチならば要求される数値は 10 個だけであり,計算が実行されるのも 10 回限りとなる。
lazy-seq マクロ (core.clj に定義されている) を使えば,簡潔なコードでこのような処理を実装することができる。しかし遅延シーケンスには,次の要素にアクセスするときに管理上のオーバーヘッドが発生する,という問題がある。チャンクシーケンスは要素のチャンク (Chunk,かたまり) を生成することによって,このオーバーヘッドの低減を図る。チャンクのサイズは32である。これはつまり,ステップ単位のオーバーヘッドが 32 要素ごとにのみ発生する,ということを示している。

チャンクシーケンスによる最適化を活用するもうひとつの方法として,データ構造体の構造上の欠点を回避する,というものがある。例えば 永続的 Vector はツリー構造で構成され,データは32要素の配列に格納されている。特定の要素にアクセスするためにはこのツリーを走査して,要素を保持している配列を見つける必要がある。このため常にインデックスを使用するような単純なシーケンスでは,要素のアクセスごとにツリー走査の処理コストを負うことになる。チャンクシーケンスを用いた Vector 実装はこの問題を回避するものだ。この方法ではシーケンスが開始する32要素の配列を検索し,その要素それぞれに対して,単純な配列アクセスによる高速な処理を行う。ツリーの走査が必要になるのはこの 32 要素のアクセスが完了して,次のツリーノードを取り出さなければならない時に限定される。

チャンクシーケンスがどのように受け入れられるかは,今後の反響を待たなければならない。利点があることは確かだが,Clojure 1.1 の Changes ファイルには,次のような点も指摘されている。
 

チャンクされたシーケンスの取得 (comsumption) は完全に透過的に,通常のシーケンスと同じように行えるべきです。しかしシーケンス処理の要素が32個以上の場合もあり得るでしょう。取得する必要のない処理結果の生成を防止する方法として完全な遅延処理を期待している場合には,このことが重要な問題になるかも知れません。チャンクシーケンスに対して要素単位のデータ取得を要求するインターフェースは,現在まだ設計段階です。チャンク処理の動作的な違いが原因となった問題がありましたら,そのユースケースをぜひ Closure の google グループで公表してください。


Clojure 1.1 の新機能はこの他にもある。詳細な情報は Clojure 1.1 の Changes ファイル を参照していただきたい。

Clojure そのものに関する詳しい情報は,InfoQ の Clojure タグをチェックしてほしい。中でも Rich Hickey 氏による Persistent Data Structure and Managed Reference など一連の解説は特にお奨めだ。 InfoQ ではさらに QCon London 2009 で収録した Rich Hickey 氏のインタビュービデオも紹介している。
 

この記事に星をつける

おすすめ度
スタイル

こんにちは

コメントするには InfoQアカウントの登録 または が必要です。InfoQ に登録するとさまざまなことができます。

アカウント登録をしてInfoQをお楽しみください。

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

コミュニティコメント

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

BT

あなたのプロファイルは最新ですか?プロフィールを確認してアップデートしてください。

Eメールを変更すると確認のメールが配信されます。

会社名:
役職:
組織規模:
国:
都道府県:
新しいメールアドレスに確認用のメールを送信します。このポップアップ画面は自動的に閉じられます。