「メトセラ1.0」

昨日やり始めたNSSetを使ったライフゲームの見直し。まる二日かけて一段落。アプリの名前は「メトセラ」。名前の由来は、ライフゲームでF-ペントミノのような周期のない長生きのパターンのことを「メトセラ」と呼ぶことから。メトセラ（Methuselah）は旧約聖書にでてくる最も長生きの人物の名前で、僕のような仏教徒の日本人にとっては聖書よりもハインラインのSF「メトセラの子ら」で馴染み。

「続きを読む」の最後の方でアプリをダウンロードできるのでMacユーザは試してみて欲しい。Windowsユーザの方ごめんなさい。それと動かしてみた方はぜひバグレーポートをお願いします。

気に入らないところを修正した、というか全部書き直した。どこが違うかと言えば

• ひとつのセルが隣のセルのポインタを保持するようにした
• Hash関数
• ドキュメントスタイルのアプリに整えた

というぐらい。それでも全部書き直したのでけっこう手間がかかった。まる二日間、合計で二十数時間。集中してやったのでけっこう早かった。仕事もこのくらい集中できればいいのに。

もとの実装では新しくできたセルは隣を確認するために一度全部の生きているセルをスキャンしていた。それを、セルが作られたときは隣がいることはわかっているのでそれを保持することで全部のスキャンをやめることができる。しかし新しく作られたセルどうしはお互い隣にいるかどうかはわからない。結局新しいセルの間では一度スキャンする必要がある。このせいで劇的に速くなる、ということはなかった。3年前の話はガセということになる。

また、隣のセルを保持すると、隣同士がお互い保持しあってリテインループになってしまって死んだセルが破棄されない。これは隣のセルの保持に同じNSSetを使っているせいで、ほんとうは単にポインタの値を保持するだけにすれば問題はなくなる。たとえば「NSPointerArray」のインスタンスを使う、などということも考えられるけど、同一性の確認は別途実装しないといけない。それならNSSetと同じ動作をして要素をretainしないクラスを定義した方がいい。けどさすがにそれは面倒なのでNSSetを使って、死ぬセルからは「これから死ぬよ」というメッセージを送ることにした。この部分のコードはあまり美しくない。

NSSetのHashテーブルの実装は簡単なものらしくてもとの実装では高い位置のビットは無視されてしまう。結局ごく普通のX座標とY座標のX-ORをとったものをHash値にする。Hash値の選び方はなかなか悩ましい。

そして最後にドキュメントスタイルのアプリにした。
こんなアイコン。

そもそもの動機である「Fペントミノ」の初期配置からつぎの世代が生まれようとしているところ。

ただし、アプリはビューアで編集機能は持っていない。これはなぜかと言えば、編集には碁盤の目の上に碁石を置いていくイメージが一番簡単だけど、それと今回の生きているセルの座標を持つというやりかたとは相性が良くない。編集のためには結局碁盤に並んだ石を座標に変換するという二度手間になってしまう。最初の碁盤のサイズをどうするかというのも問題だし。

そのかわり、UIはマックらしいシンプルなものにした。ドキュメントウィンドウにはセルの表示とあとは「開始」ボタンだけ。情報の表示や操作はHUD（Head Up Display）のパネルにまとめた。ウィンドウが切り替わるとパネルの内容が同時に切り替わる。これはCocoa Bindingの面目躍如。プログラミングは非常に簡単。

UIはこんな感じ。

機能としては、パネルから

1. 世代、人口、縦横の広がりの表示
2. カラーリストの選択
3. 世代交代の速度指定
4. 表示の拡大/縮小
5. 連続表示のトグル

ができる。またドキュメントウィンドウで

1. 世代交替の停止と継続
2. セルがウィンドウの外に広がるとスクロールバーが現れる
3. スクロールバーがあるときはドラッグして表示位置を変えられる

などができる。またメニューから

1. ファイルの読み込み
2. 途中段階でのファイルへのセーブ
3. TIFFへのビットマップ出力

ができるようになっている。今回もちゃんと日本語リソースをわざわざ作った。

また、まえはカラーのグラデーションを自分で作って、専用のファイル形式で読み込むようにしていた。きれいなグラデーションを作るのは大変なのと、専用の形式では自分で書いたことをすぐ忘れてしまって読み込めなくなってしまう。そこでMacOS Xのシステムが提供しているColorListという形式を使うことにした。これだと決まった場所にファイルがあれば自動的に読み込める。グラデーションのデータそのものは、Mathematicaが6.0から内蔵するようになったColorDataを使って作った。全部やると大変なので使えそうなやつだけをColorListの形式に変換した。

アプリとしては特に大きなバグはないはずだけど、最も大きな問題は「遅い」ということ。同じような発想で書かれているXLifeに較べても一桁遅い。Sharkでどこが律速しているか見ると結局、新しく作られたセルを収容しているNSSetから要素を取り出して隣にいるかどうかを確認するところに一番時間がかかっている。これをスピードアップするのはNSSetをやめる、かあるいは明らかに遠いセルは無視するような位相を導入すること。これ自身はけっこう面白い問題なので、次にやる気が出ればやってみたい。

Xlifeがなんでこんなに速いか不思議だったのでソースを見てみると、これはすごい。いたるところでビットバイトした最適化がされている。僕にはここまではできない。

ということでこの状態で公開しよう。
このMethuselah.zipをダウンロードして展開して欲しい。これには

• メトセラアプリ
• インストール法（HowToInstallJ.txt）
• ColorLists（色のグラデーションデータ）
• dataFiles（パターンデータファイル）
• Methuselah project（ソースのXcodeプロジェクト）

が入っている。dataFilesにあるパターンをダブルクリックするとメトセラが立ち上がるので試してみて欲しい。大きなファイルはすごく遅いことがわかる。dataFilesの中のXlifeにはけっこう面白い動作をするものもある。

アプリはPowerPCとintel32/64ビットの3アーキテクチャのユニバーサルバイナリで、MacOS Xのバージョンは10.5と10.6で動作する。10.4のサポートは今回からあきらめた。動作環境もないし。AppleはレガシーなAPIをすぐdeprecatedにしてしまう。単一コードで動作するOSバージョンがめちゃくちゃ狭い。

そして、ぜひともバグレポートを送って欲しい。

よろしくお願いします。

コメント 11

Retain 無しの NSSet は CFSet 経由で作ると簡単です。
CFSetCallBacks構造体に retain, release の関数ポインタを格納すれば良いので、
　CFSetCallBacks cb = kCFTypeSetCallBacks;
　cb.retain = NULL;
　cb.release = NULL;　// 必要なら hash なども
　void **values; CFIndex num;
　NSSet *set = (NSSet *) CFSetCreate(NULL, values, num, &cb);

これで retain も release もしない NSSet を作れます。
by SY (2010-10-26 14:42) 

追記です。ちょうど同じようなことをやっているので参考になれば。
　「隣に居るかどうか」は CFDictionary を使っています（まだちゃんとテストはしてませんが）。肝となる部分は、key に座標情報を詰め込む事です。key を x, y の alternative な int64 としてつくります。
NS_INLINE int64_t AlternativeFilledBitsMake (int32_t _bits) {
int64_t bits = (int64_t)_bits;
bits = (bits | (bits << 16)) & 0x0000ffff0000ffff;
bits = (bits | (bits << 8)) & 0x00ff00ff00ff00ff;
bits = (bits | (bits << 4)) & 0x0f0f0f0f0f0f0f0f;
bits = (bits | (bits << 2)) & 0x3333333333333333;
bits = (bits | (bits << 1)) & 0x5555555555555555;
return bits;
}
　int64_t altBits = altX OR (altY << 1);
上の関数で一つおきにセットしたビットが得られるので、x, y の情報を詰め込めます。これをポインタ値として扱い辞書の key にします。hash 値としても使いたいのでビットを混ぜるようにしました。
　void *key = (void*)altBits;
　　//64bit。32bitではxy空間をint16で定義。
格納するDictionary は、生成時にCFDictionaryKeyCallBacks の retain, release, equal を NULL に。これで equal はポインタ比較になります。hash は key のポインタ値をつかっています。value は id、オブジェクトとし、こちらは kCFTypeDictionaryValueCallBacks でメモリ管理を辞書に任せます。これで、key のメモリ管理をしない dic ができます。
　アクセス時には中心セルの x, y の値から周辺セルの key を直に生成できるので、直接 CFDictionaryGetValue() でとってこれます。セルの alloc, isEqual: を省けるはずなので速くなるかと。
by SY (2010-10-26 17:55) 

コメントありがとうございます。
CFSetを使う、というのは気がつきませんでした。目からウロコです。Core Foundationのコールバックはなにに使えばいいんだろう、とは思っていましたが、こんな使い方があるとは。
もうひとつのCFDictionaryのkeyは面白いです。しかもこれはperfect hashになって、その上LP64モデルだと単純なアドレス比較と同じ効率になるというのも非常に面白いです。
実はこれはこのままフェイドアウトだなと思っていましたが、試してみたいと思います。
ありがとうございます。
by decafish (2010-10-26 21:50) 

一つ書き忘れた事が。CallBacks を設定して作った CFObj を NSObj にキャストして使うときの注意点です。copy, mutableCopy などは CallBacks を保持したオブジェクトを返してくれます。
ですが、例えば NSArray の arrayByAddingObject: では、設定した CallBacks を無視してオブジェクトが作られます(default の CallBacks を使用)。なので、NSSet の setByAddingObject: などもCallBacksを無視して作られる可能性が。
ちなみに CFSet, CFDictionary の実体は CFBasicHash で、コールバックは __CFBasicHash の pointers[] に格納されています。コールバックにアクセスする関数は用意されていないので、自分で書くしかないようです。格納順は CFSet, Dictionary の __***CreateGeneric にあります。
by SY (2010-10-27 15:01) 

CF.550-13のソースを確認しました。完全に追えていないのですが、どうやらおっしゃる通りのようです。
そういう仕様にする必然性は理解できるような気もしますが、知らないとこれは確実にハマります。ありがとうございます。
ところでCore Foundationも10.6で大幅に書き換えられているというのを今日初めて知りました。アルゴリズムなどの変更はあまりなさそうですが、字面の違いと、似た作業を一般化するためのdispatch関数の多用には驚きました。
よくやるなあ、と言う感じです。それとますます読みづらくなってきました。漫然と見てると何やってるか全然わかりません。
by decafish (2010-10-27 22:14) 

10.5 と違うのですね。CFに …ByAddingObject: 等の拡張したので危なかった、指摘してもらって助かりました。確かにCF550の方が複雑ですね、コールバックの場所を読み解くのにちょっと難儀しました。そのかわりコールバック取得コードがすっきりするという恩恵はありましたが。
クラスクラスタである以上、NS の仕様は仕方の無い事だとは思いますが、コレはよくよく考えないと気付かないですよね。僕はCFの拡張中に気付いたのでよかったですが、100%ハマる自信があります（笑。
もう一つハマりそうなのが、GC にした場合。CFMakeCollectable() してしまうと、この場合ループを作るでしょうからダメ。CF... のまま使わないと release を忘れそうです。
by SY (2010-10-28 15:21) 

僕はいまだにdispatcherを追いきれません。ところでCFSetとCFBag、CFDictionaryの記述の多くが共通になっているのはこれからさらにマージするつもりなんでしょうか。Cocoaのレイヤともマージしていくんでしょうけど、Cocoa側がソースを見られないのは残念です。
GCについてはこういう場合の障害以上に、Cocoa/Objective-Cを使い始めて苦しめられたretain/releaseが逆に今は体に染み付いてしまってまだ馴染めません。もうしばらく使わずに過ごしそうです。
by decafish (2010-10-28 21:26) 

　GCについて、僕も同じく retain/release が染み付いてます。ですがADC の WWDC2010ビデオ（今回から無料）、Session353 "What's New in Obj-C" 20分前後をみると 10.6 の GC がすごく良くなっているようです。これだけ違ってくると GC にするメリットの方が大きそうなので、GC対応コードをretain/releaseしながら書いています。iOS ヒットのおかげか、Mac Dev まで随分低価格化、オープン化したのはありがたいところです。この流れにそって Foundation の中身だけで良いので公開してほしいですね。今は特に、NSZone と CFAllocator の違いについて知りたいです。それが分かるだけで随分違ってくるのに。
　ところで、かな〜り古いFoundationは以下の検索サイトで見れます。
http://www.koders.com/info.aspx?c=ProjectInfo&pid=XU88UMM24GV27GBBQD5F41BVXE
参考にはなりますが、現状とはかけ離れていそう。
　CFBasicHash は .m になってますし、CFは最終的に大部分がCocoa/Objc に吸収されるのではないでしょうか。その頃までに Foundation を公開してくれていると良いですね。
by SY (2010-10-31 12:47) 

WWDC2010のビデオはiTunesUにいっぱい溜まってるのですが全然消化できていませんでした。Session353、確認してみます。
「かな〜り古いFoundation」こ、これはなんでしょう？すごいすごい。Cocoaのご先祖様なのでしょうか。こんなのが読めるとは知りませんでした。これは面白い。ちょっと見てるだけでObjective-Cのスタイルが乗り移りそうです。すごい。
CFはI/O Kitなんかで汎用的に使われているのでフェイドアウトするわけにはいかないでしょう。むしろ今の屋上屋のような状態から、CFにある機能はCocoaではCFの単なるWrapperになるのではないでしょうか。というかそう言う方向に行って欲しいです。CFTypeとisa、reference countを別々に持ちながら内部的に調整するのは無駄に見えますし。
Foundationの公開はとても期待しますが、CocoaはMac OS XとiOS共通のAppleのコアコンピテンスで、僕にはCocoaがなければiPhoneやiPod、iPadはなかったと思われます。従って公開は難しいのではないでしょうか。
by decafish (2010-10-31 21:51) 

Foundation の公開については同じ意見です、悲しい事に期待値が低い。
CFとCocoaの関係については、逆の見解ですね。もちろんCFがなくなるとは思っていませんが、Cocoaと共通する部分はCocoaの実装を使うようになると予想しています。というのもtoll-freeオブジェクトのコードを見ると、CF_OBJC_FUNCTION_DISPATCHでほとんどの処理をobjc_msgSendでCocoaに任せているように見えます。実際NSArrayにはCFのdispather用と思われる非公開メソッド、_cfapply:context:や_cflastIndexOfObject:inRange:などが存在しています（この辺の事に気付いてから、CFの実装って意味あるのか…と悩み中です）。動的なCocoaがCFのラッパーになるよりも、CFがCocoaのラッパーになった方が作業量も抑えられるのではないでしょうか。
by SY (2010-11-01 17:59) 

なるほど、CocoaとCFの関係はおっしゃる通りだというのがわかりました。僕は単にオーバーヘッドの問題などから考えて上のレイヤが下を呼ぶのが当然だと思い込んでいました。追って見ると確かに僕の考えは安直でした。retain countの実装ひとつ取ってもCFの方がずっと素直で簡単な実装だと思っていたので当然CFに合わすものだと思っていたのですが。
とすると、CFの公開はいずれ骨抜きになるということでしょうか。最近のAppleのやり方を見てると十分考えられますが．．．
by decafish (2010-11-01 22:14)