Smalltalk-76 とアルト・エミュレータ(ContrAlto)でマンデルブロ集合

最後はやっぱりアルト実機に対抗(?)して、アルト・エミュレーターContrAlto で動く Smalltalk-76 で書いたマンデルブロ集合描画で締めくくりたい…と思ったのですが、想像以上に遅くてけっこう大変でした。^^;


Smalltalk-76 を動作させるにあたり こちら のディスクパック・イメージ xmst76.dsk44 を使用させていただきました。Smalltalk-76 の起動は resume xmsmall.boot です。


Smalltalk-76 は、Pharo や Squeak Smalltalk の元になっている Smalltalk-80 と似たところが多い(初期の Smalltalk-72 と比べればはるかに!)ですが、それでもいろいろと勝手が違うところもあるので「過渡期」と見るだけでなく「Smalltalk-80とは似て非なる独自の言語」として見ても興味深い処理系です。こちらの文書が参考になります。


ContrAlto Readme には raw packet を使いたいときだけのように書いてありますが、Microsoft Visual C++ 2010 redistributable は設定画面(System → System Configuration...)を正常に機能させるのにも必要ですのでネットに繋げなくとも忘れずにインストールしておきましょう。同設定から Displayタブの Throttle Framerate at 60 frame/sec のチェックを外しておくと手元の環境では気持ち快適に動作しました。あと、ホイールボタンが使用できる3ボタンマウスが必須です。


まずは、複素空間の座標を Point で表わす方法で素朴に書いてみたのがこちら。

http://squab.no-ip.com/collab/uploads/mandelbrot11.png

| size half origin turtle limit start x y c z count zsquared [
   size ← 10.
   half ← size/2.
   origin ← Rectangle new fromuser origin.
   (origin - 1 extent: size⌾size + 2) outline; clear: black.
   turtle ← Turtle init.
   limit ← 10.
   start ← user rawtotalsecs.
   for⦂ y from: (0 to: size-1) do⦂ [
      for⦂ x from: (0 to: size-1) do⦂ [
         c ← x asFloat ⌾ y asFloat - half / half - (0.5⌾0).
         z ← 0.0⌾0.0.
         count ← 0.
         while⦂ ((count ← count + 1) ≤ limit and⦂ z length < 2) do⦂ [
            zsquared ← z x * z x - (z y * z y) ⌾ (2.0 * z x * z y).
            z ← zsquared + c
         ].
         [count > limit ⇒ [turtle black] turtle white].
         turtle penup; place: x⌾y + origin; pendn; go: 0
      ]
   ].
   user rawtotalsecs - start
]


ポイント記号 ⌾ は ctrl + ] 、オープンコロン ⦂ は ctrl + ; 、小なりイコール ≤ は ctrl + , 、〜ならば ⇒ は ctrl + / で入力できます(US キーボードの場合)。


走らせてみたところ 10×10ドット(左下の小さいやつ!)で集合値判定ループも最大10回にまで減らしたにもかかわらず描き終えるのに 6分近くかかるという状態。この様子では全画面はおろか、100×100 でも、おそらく1日かけても終わりません。BCPL よりは遅いかな…程度に軽く考えていましたが、あまかった!


念のため、Squeak Smalltalk でほぼ同じ意味になるように書き換えたのがこちら。100×100ドット、判定ループ最大100回でも 0.2秒ほどで終わります。いい時代になりました。w

| size half origin turtle limit start c z count zsquared |
size := 100.
half := size/2.
origin := Rectangle fromUser origin.
Display border: ((origin extent: size asPoint) expandBy: 2) width: 2 fillColor: Color black.
turtle := Pen new.
limit := 100.
start := Time millisecondClockValue.
(0 to: size-1) do: [:y |
   (0 to: size-1) do: [:x |
      c := x asFloat @ y asFloat - half / half - (0.5@0).
      z := 0.0@0.0.
      count := 0.
      [(count := count + 1) <= limit and: [z r < 2]] whileTrue: [
         zsquared := z x * z x - (z y * z y) @ (2.0 * z x * z y).
         z := zsquared + c
      ].
      turtle color: (count > limit ifTrue: [Color black] ifFalse: [Color white]).
      turtle up; place: x@y + origin; down; go: 0
   ]
].
Time millisecondClockValue - start / 1000.0 "=> 0.211 "


そこで、Point の使用を諦め、主に型変換のコストがかからないように最低限の変更を加えてみたのがこちらです。

http://squab.no-ip.com/collab/uploads/mandelbrot09.png

| size half ori turtle limit start x y cre cim zre zim zre2 zim2 count [
   size ← 101.
   half ← size/2.
   ori ← Rectangle new fromuser origin.
   (ori extent: size asPoint) outline; clear: black.
   turtle ← Turtle init.
   limit ← size/3.
   start ← user rawtotalsecs.
   for⦂ y from: (0 to: half) do⦂ [
      for⦂ x from: (0 to: size-1) do⦂ [
         cre ← x asFloat - half / half - 0.5.
         cim ← y asFloat - half / half.
         zre ← zim ← zre2 ← zim2 ← 0.0.
         count ← 1.
         while⦂ (count ≤ limit and⦂ zre2 + zim2 < 4.0) do⦂ [
            zim ← 2.0 * zre * zim + cim.
            zre ← zre2 - zim2 + cre.
            zim2 ← zim * zim.
            zre2 ← zre * zre.
            count ← count + 1
         ].
         [count > limit ⇒ [turtle black] turtle white].
         turtle penup; place: x + ori x ⌾ (y + ori y); pendn; go: 0.
         turtle penup; place: x + ori x ⌾ (size - y - 1 + ori y); pendn; go: 0
      ]
   ].
   user rawtotalsecs - start
]


もうなりふり構っていられないので、判定ループもドット数(size)の3分の1程度の最大33回にして、さらにこの範囲での上下対称を利用して下半分も同時描画にしています。これでなんとか 9000秒 = 2.5時間程度で描き終わるようにできました。


さらに画面を 赤くする 消すと3倍くらい速くなるという情報が件のアルト実機でのマンデルブロ描画の続報にあったので、どうやらそれっぽい UserView>>#displayoffwhile⦂ を見つけて使ってみたところ、ほんとに速くなりました。

http://squab.no-ip.com/collab/uploads/mandelbrot10.png


まあ、描いている途中を見たいところもあるので微妙ですが。^^;


ということで、同シリーズはこれにておしまい。マンデルブロ集合はもうしばらく見たくないです。w



追記
id:squeaker さんからコメントをいただいたので、Lively Kernel 上にリバイブされた Smalltalk-78 でも試してみました。Smalltalk-78 はノートテイカー(NoteTaker)と呼ばれる 8086を搭載した可搬式 PC 試作機向けに機能を削減した Smalltalk-76 です。

ノートテイカーは、アルトのパワーアップ版のドラド(Dorado)に対し、小型化の方向でダイナブックに一歩近づいたアルト後継機に位置づけられるマシンで、後の有名なオズボーン1の元ネタでもあります(タッチパネルを装備したりバッテリー駆動が可能など、オズボーン1よりずっと高機能です^^;)。

前述エミュレーターは Web アプリフレームワークの Lively Kernel(Lively Web)上にノートテイカーのエミュを構築し、その上で Smalltalk-78 を動作させています。

JS で実装されているので個人的には Smalltalk ゆかりの高速化技術で作られた V8 エンジンをを搭載している Chrome を推奨しています。


http://squab.no-ip.com/collab/uploads/mandelbrot12.png

| size half ori turtle limit start x y cre cim zre zim zre2 zim2 count [
   size ← 101.
   half ← size/2.
   ori ← Rectangle new fromuser origin.
   (ori extent: size asPoint) outline; clear: black.
   turtle ← Turtle init.
   limit ← size/3.
   start ← user ticks.
   for⦂ y from: (0 to: half) do⦂ [
      for⦂ x from: (0 to: size-1) do⦂ [
         cre ← x asFloat - half / half - 0.5.
         cim ← y asFloat - half / half.
         zre ← zim ← zre2 ← zim2 ← 0.0.
         count ← 1.
         while⦂ (count ≤ limit and⦂ zre2 + zim2 < 4.0) do⦂ [
            zim ← 2.0 * zre * zim + cim.
            zre ← zre2 - zim2 + cre.
            zim2 ← zim * zim.
            zre2 ← zre * zre.
            count ← count + 1
         ].
         [count > limit ⇒ [turtle color: black] turtle color: white].
         turtle penup; place: x + ori x ⌾ (y + ori y); pendn; go: 0.
         turtle penup; place: x + ori x ⌾ (size - y - 1 + ori y); pendn; go: 0
      ]
   ].
   (user ticks - start) asFloat / 1000
]


こちらは ContrAlto と違ってコピペでコードを貼り付けできる(必要なら環境からコードをコピペで持ち出すこともできる)のが楽でいいですね。^^;

手入力したい場合は、オープンコロンは : の2連続 :: 、ポイント記号はそのまま @ 、小なりイコールは <= 、〜ならばは => で入力できます。


ちょっと手直してして動かしてみたところ 100×100ドット、最大判定ループ33回で 85秒ほどでした。速い!


これなら最初の素朴な実装も待てる時間で動くのでは?と同様の条件で試してみたところ、驚きの95秒。対称性を利用していないことを考えるとこちらの方が速いのかもしれません。すばらしいですね。

http://squab.no-ip.com/collab/uploads/mandelbrot13.png

| size half origin turtle limit start x y c z count zsquared [
   size ← 101.
   half ← size/2.
   origin ← Rectangle new fromuser origin.
   (origin - 1 extent: size⌾size + 2) outline; clear: black.
   turtle ← Turtle init.
   limit ← size/3.
   start ← user ticks.
   for⦂ y from: (0 to: size-1) do⦂ [
      for⦂ x from: (0 to: size-1) do⦂ [
         c ← x asFloat ⌾ y asFloat - half / half - (0.5⌾0).
         z ← 0.0⌾0.0.
         count ← 0.
         while⦂ ((count ← count + 1) ≤ limit and⦂ z length < 2) do⦂ [
            zsquared ← z x * z x - (z y * z y) ⌾ (2.0 * z x * z y).
            z ← zsquared + c
         ].
         turtle color: [count > limit ⇒ [black] white].
         turtle penup; place: x⌾y + origin; pendn; go: 0
      ]
   ].
   (user ticks - start) asFloat / 1000
]