Archive for the ‘リリカル’ Category

Mark-sweepのunmarkをサボる

日曜日, 3月 27th, 2016

ガベージコレクション 自動的メモリ管理を構成する理論と実装を読んでたら、ごみ集めのたびにマークビットの意味を反転させればunmarkのコストを避けれる、という話があったので試してみた。
恐らく、これが効果があるのはヒープが巨大な時と、unmarkのコストが大きい時だろう。巨大なヒープを使うのはいやなので、unmarkのコストが大きい(要するに遅い)NScLisperでこれを実装してみた

Benchmark program:
  (define (muda n . r) (if (<= n 0) r (muda (- n 1) (cons 0 0))))
  (time (muda 3000))
Before: 47143 ms
After:  46688 ms

どちらも評価時にごみ集めは8回走った。

まあ、速くなったといえば速くなったけど、それほど大きな違いはなかった。
恐らくNScLisperのヒープが小さすぎるのが一番の原因だろう。NScLisperのヒープは2900セルしかない。
それから、consingの際に、これまではマークビットが0であることが保証されていた (初期値は0だし、再利用の際もsweep時に0になる) ので何もする必要はなかったが、この変更により「マークされてないことを表す値」をマークビットに設定する必要が出てくる。このコストはunmarkと変わらない。つまり、unmark処理省略の恩恵を受けれるのは基本的に生きているオブジェクトだけだ。
(正確にはプログラム終了時に使われてないセルについてもunmarkのコストを避けたことになるが、逆に最初のごみ集めが起こるまでのconsingでは余計なコストが増えている)
このプログラムでは常に約700セルが使われているので、8回のごみ集めで合計5600回分のunmarkのコストを避けたことになる。これだけで455ms速くなったのだからお得といえばお得な気もする。
ただし、変数が合計で4096個しか作れない(ヒープやスタックも含む)環境下で変数を1つ消費する価値が有るかというと、やはり微妙なところだ。

(自分用メモ)
マーク済みを表す値ではなくマークされてないことを表す値を変数に入れたほうが減算の回数が減るのではないかと気付き試したが、結果に変化は見られなかったのでrevertした。

リリカルLisp ver1.8

月曜日, 9月 16th, 2013

リリカルLisp ver1.8を公開しました。
約6ヶ月ぶりの更新です。

TL;DR: (fib 12)がver1.7と較べて3.2倍程速くなりました。無限ループやスタックオーバフローの際に強制終了ではなくエラーを返すようになりました。

ver1.7のリリース時に
「de Bruijn indexはあまり速さに貢献せず、スペシャルフォームへのアクセスをO(1)にしたのが効果的だった」
と書いている最中に気づいた
「それじゃあグローバル変数のアクセスをO(1)にしたら大幅に速くなるだろ」
という自明なことを実装したのがver1.8となります。
シンボルと値のペアを用意して、グローバル変数を参照する式を直接このペアを参照するように変換することでアクセス時間をO(1)にしています。ただし、式の変換の際にはペアのリストを線形探索するのでO(n)の時間(nはグローバル変数の個数)が必要となります。

肝心の効果のほどですが、
(define(fib n)(if (<= n 1)1(+(fib(- n 1))(fib(- n 2)))))
(fib 12)を評価したところ、ver1.7は16292ms、ver1.8は5097msとなりました。
約3.2倍です。馬鹿みたいに速くなりました。ver1.7とは何だったのか。

もう1つの大きな変更は、評価の安全な中断です。
これまでのバージョンでは、無限ループの(可能性がある)ときは、式の評価を中断するか尋ね、「中断する」が選択された場合はプログラム自体を終了していました。また、スタックオーバフローが起きた際には問答無用でプログラム自体を終了していました。
ver1.8ではプログラム自体を終了する代わりに、(Lispの値としての)エラーを返すように変更しました。

プログラム自体を終了するというのはあんまりなような気がしますが、最初のバージョンでは時間の関係からこのような仕様となっていました。
そして、その後は、面倒で放置し続けていたものをようやく直したという感じです。

リリカルLisp ver1.7

日曜日, 3月 3rd, 2013

リリカルLisp ver1.7を公開しました。
約11ヶ月ぶりの更新です。

TL;DR: 主な変更点は高速化です。(fib 12)がver1.6と較べて1.57倍程速くなりました。

今回の変更では環境の構造を大きく変えました。
ver1.6までは環境は連想リスト(のリスト)で表現されており、
ローカル変数、グローバル変数は特に区別されていませんでした。
今回の変更で、ローカル変数はde Bruijn indexを使って表現するようになり、
ローカル変数の環境は連想リストではなく、
値のみ入った(名前が入っていない)リストになりました。

de Bruijn indexを付けるにはコードウォークをする必要があるのですが、
すべてのスペシャルフォームのためのコードウォークを書くのは骨が折れるので、
letやcondなどのスペシャルフォーム(Schemeの言葉で言うとlibrary syntax)は、
lambdaやifなど(Schemeの言葉で言うとsyntax)に変換してから、
変換した式を対象にコードウォークをすることにしました。
この式の変換やコードウォークはLispで書くという案もあったのですが、
わずか2900セルしかないNScLisperの貴重なヒープを、
内部用のプログラムで使ってしまうのは問題があるだろうと考え、
すべてNScripter側で実装しました。
実に1299 insertions, 940 deletionsという壮大な変更となりました。
(NScLisperのコードは4000行程度です)

ベンチマークに使ったfibの定義は次のようなものです。

(eval
 '(letrec ((fib
            (lambda (n)
              (if (<= n 1)
                  1
                  (+ (fib (- n 1)) (fib (- n 2)))))))
    (fib 12)))

evalでクォートされた式を評価しているのは、
式の変換などにかかる時間も含めるためです。
式の変換時間(の近似値)を図るために(fib 1)も計測しました。

version (fib 12) [sec] (fib 1) [ms]
1.6 44.935 129
1.7 28.551 183

なかなか良い感じです。(fib 1)も54msしか遅くなっていません。

リリカルLispを作り始めてもう6年になり、
私zickはいつの間にか大学生から不幸なことに社会人になってしまいましたが、
今後も可能な範囲でリリカルLispのメンテを続けていこうと思います。

--

と、ここまでの話だけを見ると
「de Bruijn indexを使うことによって速くなってよかったね!」
と錯覚してしまいそうになりますが、実は違うんです。
本当に、本当に悲しいのですが違うんです。

ver1.6まではifやdefineなどのスペシャルフォームを
FEXPRというオブジェクトとして表現していました。
式を評価する際にifといったシンボルが現れると、これを環境から探し出し、
FEXPRという事がわかったら、対応する処理が実行されるという感じです。
これらのスペシャルフォームは大域環境の末尾の方にあるため、
探索に結構な時間が掛かっていました。
上記fibなどは頻繁にifが現れるため、そのコストは顕著なものとなります。

一方、ver1.7ではFEXPRは無くなり、フォーム自身が特別扱いされるようになりました。
式を評価する際に(if ...)というフォームが現れると、
対応する処理が実行されるという感じです。
その際に環境からシンボルを探す処理は行われません。
また、ディスパッチの処理も簡略化され速くなります。

実は、今回の高速化の大部分は、
このスペシャルフォームに対する変更によりもたらされたもので、
de Bruijn indexはあまり速さに貢献していません。

version (fib 12) [sec] (fib 1) [ms]
1.6 44.935 129
1.7 28.551 183
(FSUBRに対する変更) 31.879 59

あんまりな感じです。十分速いじゃないですか。
式の変換やコードウォークのための変更は千行以上。
FSUBRに対する変更はわずか数百行。
それでこの結果は泣きそうになってしまいます。

でもまあ、de Bruijn indexを付けて、
環境が連想リストからただのリストになったのが大事なのではなく、
コードウォークをできるようにしたのが大切だと考えてます。
これにより、変数を可能な限りスタックに置くような
最適化の下地が出来上がりました。
いつしか、大幅な高速化ができたら、と考えています。

リリカルLispの開発がより容易になりました

土曜日, 8月 18th, 2012

結論

リリカルLispにテストコードを追加しました。
本編の練習問題のプログラムが正しく動作するか確認できます。
これで皆さんも、気軽にリリカルLispのソースがいじれますね。

背景

リリカルLispのソース、特にインタプリタの内部に手を加える時はそれなりに気を使う必要があり、
手を加えた後はちゃんと動くかどうか手でテストする必要がありました。
最低限、本編で出てくる練習問題のプログラムがちゃんと動作する
(正しいプログラムを入力した際に正解扱いされる)ことを確認する必要がありますが、
何回も手でプログラムを入力して確認するのはあまりにも面倒すぎます。
そんな訳で、練習問題のプログラムがちゃんと動作するか確認するテストを書きました。

この変更のためのコミットを(NScripterを読める人が)見れば分かることですが、
ラベル名を変数に入れてジャンプをするコードを多用しているため、
このテストと練習問題周辺のコードはとてつもなく可読性が落ちました。
まあ、インタプリタの周りを触る頻度に比べ、
練習問題の周りを触る頻度は遥かに少ない(と信じている)ので、
きっと問題ないでしょう。多分。

リリカルLispのソースのライセンス

火曜日, 5月 29th, 2012

前エントリ

tokumei より:
2012年5月28日 6:29 AM
>githubで公開しても、誰もメンテしてくれないしね。
どのファイルにもライセンスが書いてない(気がする)のでgithubでのforkすら躊躇ってしまう・・・・・・
ファイルは全部BSDLなんでしょうか?

という、もっともなコメントが付いたので、
githubにLICENSEを追加しました。
見ての通りの修正BSDライセンスですので、気軽にforkしてください。

リリカルLisp ver1.6

木曜日, 3月 29th, 2012

リリカルLisp ver1.6を公開しました。
約7ヶ月ぶりの更新です。

今回の変更点は高速化です。
今まで評価した引数をリストにつないでいた(いわゆるevlisを使っていた)ものを、
スタックに積む(つまり普通の手法)ものに書き換えました。
速さと引換に伝統的なLispインタプリタらしさが失われた感じです。
ちなみに、環境はいまだに連想リストで表現しているので、まだまだ速くできます。

ベンチマークとしてfib関数
(define(fib n)(if (<= n 1)1(+(fib(- n 1))(fib(- n 2)))))
(fib 12) を評価したところ、以下のような結果となりました。

バージョン 実行時間(秒) GC回数
1.5 55.855 3
1.6 46.512 1

ヒープへのアロケーションが減った結果、GC回数が削減され、実行時間も短縮されました。
GCが発生しないプログラムでも速くなる(ことがある)ことを確認しています。

何でもかんでもスタックに置くと、apply関係で面倒な事もあるのですが、
まあ、リリカルLispで非常に長いリストを作ることもないだろうと考え、
特に工夫はしないことにしました。

--

リリカルLispを作り始めたのは、私zickが学部1回生のときですが、
気がつけば修士2回生になっており、この3月で学生生活も終わりです。
今後どうなるかはわかりませんが、
可能な範囲でリリカルLispのメンテは続けていこうと思います。
githubで公開しても、誰もメンテしてくれないしね。

リリカルLisp ver1.5

火曜日, 8月 23rd, 2011

リリカルLisp ver1.5を公開しました。
約半年ぶりの更新です。

今回の変更点は、エラーのチェックです。
今までのバージョンでは、実引数が仮引数より多かろうが、少なかろうが、
未束縛の変数を使おうが、シンボルの足し算を行おうが、
どんな無茶をしても、(大抵の場合、意味のない)値が返ってきました。
それが、今回の変更で「エラーです」と通知する機能が付きました。

> x
エラー:top-levelにおいて、xは未束縛です
> (cons 1)
エラー:consに与える引数が少なすぎます
> (+ 'a 'b)
エラー:+において、aは数ではありません
> (let 3 4)
エラー:letの使い方が間違っています

大体こんな感じです。
日本語を選ぶのに苦労しました。

プログラミング言語の学習(した気分になる)ソフトなのだから、
このような機能は付いていて当たり前だとは思うのですが、
最初のバージョンでは時間の関係から付けることができませんでした。
そして、その後は、
「今更、そんなものつけてもなー」
という思いからずっと放置されてきました。

今になってエラーのチェックを付けた理由は、
次のようなメールがきたからです。

I can’t get past lesson 2. When I type
(define x 4)
the result is x
Then, when I type
(* (x+3) 4)
the result is -2358896
I thought it should be 28

なんというか、ごめんなさい。
もう放置しても誰も困らないだろうと思っていたけど、
そんなことはなかったみたいです。

余談ですが、
リリカルLispのソースをgithubで公開してからちょうど1年が過ぎました。
誰も触ってくれないだろうなと思っていたけど、
ほんとに誰も触ってくれませんでした。
ショックですっ ><

リリカルLisp ver1.4.1

木曜日, 7月 28th, 2011

こんなメールがきた。

I get an error using Lyrical Lisp with the latest NScripter.
“グローバル変数設定に写える数字大きすぎます。”
Do you know the cause?

で、実際にNScripterを最新のものに差し替えて実行したら、
確かにエラーメッセージが表示されました。
そんなわけで修正を加えたバージョン、
ver1.4.1を作ったんですが、この変更を嬉しがる人も少なそうなので、
zipで固めたものは作らず、スクリプトファイルだけを置いときます。

nscript.dat (ver1.4.1)
(2011/09/03 追記)
新しいバージョンがリリースされましたので、こちらをご利用ください。

必要な方は、リリカルLisp ver1.4のnscript.datとこれを差し替えてください。

リリカルLispの起動が速くなりました

金曜日, 2月 18th, 2011

リリカルLisp ver1.4を公開しました。
今回の主な変更点は起動の高速化です。
結論から言うと、ver1.4はver1.3より約2.5倍も起動が速くなりました。

一見凄いことをしたように見えますが、
元のコードがシンボル生成の際にメモリを無駄に舐め回す、
アホな作りになっていただけ。ごめんなさい。
そこを普通のコード(?)に変えるだけで馬鹿みたいに速くなりました。

実は、その箇所を変更した時点で起動時間はver1.3の約9倍速くなりました。
しかし、「起動が速すぎてリリカルLispらしくない」という思いから、
なんとか起動時間を引き伸ばせないかと考え、

ver1.3以前ではフリーモードでしか使えなかった関数を、
どこでも使えるように修正しました。

フリーモードでしか使えなかった関数というのは、ここのcaar以下の関数です。
これらの関数はSchemeで書いてあり
使うためにはまずそれらの定義を評価する必要がありますが、
残念なことに、それらの評価にはそれなりに時間がかかってしまいます。

ということで、ver1.3以前は起動時間のさらなる増加を避けるため、
起動時にはそれらの関数定義の評価を行わず、
フリーモードを動かしたときに評価を行うようにしていました。
しかし、今回起動時間が速くなったので、
ver1.4では起動時にこれらの関数定義の評価を行うよう変更しました。

これにより、起動時間が延びて安心
以前より多く関数が本編で使えるようになり便利になったはずです。

私の手元での起動時間 (10回計測の中間値)

ver1.3 (シンボルの生成でアホなことをしていた) 4657ms
未公開版 (シンボルの生成のコードを修正) 515ms
ver1.4 (関数定義を起動時に行う) 1825ms

また、地味な変更点として、シンボルのもつ文字列に対するGCの追加があります。
ver1.3以前では、シンボルを一度つくると、それの文字列は、
シンボル自体が回収されても放置されていたのですが、
今回、Copying GCでそれを回収するようにしました。
(Copying GCにしたのは、もとの実装を極力変更したくなかったため)
今のところシンボルを生成するような関数 (string->symbolなど) は提供していないので、
恐らくこのGCが呼ばれることはないでしょうが。

次世代のリリカルLispを作るのはあなたです

日曜日, 8月 22nd, 2010

先日、COMFRK vol. 1を買いに来た方が
「リリカルLispは拡張したりしないんですか」
と質問されたそうです。

私にはもうリリカルLispのソースを触る元気は残っていません。
githubにソースを置いておいたので、自由に改造して下さい。

http://github.com/zick/Magical-Language-Lyrical-Lisp

流行に乗ってgitとか使ってみたけど、さっぱりわかない。
commitとpushってどう違うんだ。