memo: 2024-01

2024-01-31

Fossilのリポジトリリストをローカル用に立ち上げる

2024-01-26

X11でCtrlとCapsを永続的に入れ替える

タブレットユーティリティなどがキーボード設定をリセットするので困る問題。

2024-01-21

続ループ速度分析

まずArkam。スタックの安全検査などを切ったり、コードをIF/AGAIN使うようにしたり最適化しても35ms。ループ開始まで3msなのでループ時間に30msほどかかってる。更にmodを捨てて単純に100万回何もしないループにしても15ms程度かかる。何かメモリアラインメント周りのミスでもあるのかな、という遅さ。

それからChickenとGambitのインタープリタについて。Cにコンパイルする処理系のはずだから、関数コンパイルに時間かかってるのか？と思ってループ開始前までの速度を測ったけど、どちらもコンパイルかなり速かった。ループ自体にChickenは180ms、Gambitは110msかかる。

PicoLispで完全に何もしない、100万回のループでループカウンタを参照しているだけのコードだと3ms。速すぎる。(for X 1000000 (setq N X))とカウンタをグローバル変数に毎回代入しても9ms。

更にPicoLispを詳しく見ていくと、各イテレーションでf->g->hと3層で関数に引数渡した場合は34msほど、引数を渡さず無引数で呼んだ場合は20msほどになる。引数を渡すためにconsしてその分のGCが走ったのかな。

同様に各イテレーションで３層の関数呼び出しが走った場合は以下。Cは__attribute__((noinline))をそれぞれの関数につけている。

C        2ms
JS       18ms
Pico     33ms
Lua      44ms
Gauche   50ms
Python   82ms
Gambit   117ms
Chicken  204ms

2024-01-20

Ringループ速度分析

スタートアップでコアライブラリを読むのに37msかかるので、そこからの計測。

まずコンパイラ記述言語、S式のBCPLみたいなStoneで書いたループでは、100万回で2ms秒だった。スタックマシンみたいなアセンブリに変換されるから遅いと思ってたけど、まあ許容範囲のスピード。多分。

GC100回で1241msかかってるので、だいたいGC1回につき12ms。重い。

consがある関数の呼び出しを消して、(while (> i 1000000) (set! i (+ i 1))みたいなループシンタックスを追加した場合は3000ms程度。GCは40回。

(prim:+ i 1)とプリミティブ呼び出しにするとGCは4回、400msほど。

更にwhileではなくアセンブリコードでカウンタを操作するシンタックスを追加して、本体部を単なるグローバル変数参照だけにしたコード(times 1000000 some-variable)の場合は15ms。もちろんGCは0回。

考察すると、まず１引数以上の関数呼び出しで必ずconsが入ってしまうので、場合によってはReferenceCountの方がマシかもしれない。リンクを毎回解放してフリーリストにつなぎ直す処理がどれぐらい重いかによるけど。

グローバル変数参照だけにしてもPicoLispに比べて遅い理由はちょっとわからない。単純にこれがスタックマシンっぽいアセンブリ出力の限界なのかな？

ループ速度

単純なループ速度気になったので、とりあえずPCに入ってたインタプリタ系の処理系で計測してみた。

内容は「カウントを10,000で割った余りが0のときに.を出力」という関数fを100万回ループ。Scheme版は以下。

(display "do")

(define (f n)
  (when (= (remainder n 10000) 0)
    (display ".")))

(let loop ((n 1000000))
  (when (> n 0)
    (f n)
    (loop (- n 1))))

(display "done\n")

最適化についてはCで関数呼び出しのインライン化を抑制しただけで、他は放置。JIT等も可ということで。

で、3回実行した平均が以下。ChickenとGambitはインタプリタの方。

C        2ms
Lua      17ms
JS       20ms
Gauche   33ms
Pico     40ms
Python   62ms
Arkam    129ms
Gambit   131ms
Chicken  217ms
Tcl      533ms
Ring     6324ms

拙作のArkamとRingは悲しいことになっている。スタックVMとはいえForthなのにLispより遅いArkamと、論外のRing……

後は順当に感じる中、異様なのがPicoLisp。速すぎる。最適化も多分無い、fexprがあるインタプリタでこんなに速いのは謎。

ChickenやGambitのインタプリタはCに変換して実行したはず……だから仕方ないのかな。大部分がコンパイル処理だと思われる。暇あったらコンパイル版も見てみよう。

次に関数呼び出しを消して、forループやnamed letの本体に処理を書いた場合。

C        1ms
Lua      6ms
Gauche   18ms
JS       20ms
Pico     20ms
Python   41ms
Arkam    52ms
Gambit   111ms
Chicken  192ms
Tcl      379ms
Ring     6088ms

JS(node)があまり変わってないのは元のコードでインライン展開してるのかな。

ここでもPicoLispが速すぎる。まさかnodeに匹敵する速さとは。全てコンスセルだからキャッシュに乗りにくそうなんだけど、起動してすぐだから隣のセルなのか、それとも要求する度にブロックでアロケートして近いとかかな？何にせよちょっと興味出てきた。

※追記　計測結果の計算ミス修正。全て1/2の速度になってた。順位は変わらず。

Ringのシンボルテーブルをハッシュテーブルにした

今でリンクリストだったのを長さ1024のハッシュテーブルにした。

完全ブートストラップテスト（Scheme->Ring->Ring）にそこそこ速いマシンで12.6secかかるから、これで結構高速化できるかも……と思いきや11.0secにしかならなかった。かなり意外な結果。

コアライブラリとコンパイラのシンボルそこそこ多いのに、リンクリストでのルックアップでも普通に戦えてたのか。

じゃあどこが遅いんだろう？と思って、セルフホスティングコンパイラ測ってみたら、案の定……ファイルへのアセンブリ出力だった。はい、やらかしてました。かなり簡単な実装にしてるのでバッファを使わず、１文字ずつファイルに出力してた。

全てのコアライブラリを読み込み、Ring処理系のソースをS式として読み込むまで0.06s。パースしてアセンブリノードにコンパイルするのに0.14sec。そこからアセンブリノードを単に出力するのに2.8sかかってた。

アルゴリズム的に一番重いのはS式を全てWalkするアセンブリノードへのコンパイルなので、これは明らかにFile I/Oがボトルネックになってる。

……その後書き換えて計測してみたけど違った。普通にバッファされてるっぽい。OSの機能かな、調べないと。普通にループがめちゃくちゃ遅い。出力時に26万文字emit-cが呼ばれてるけど、その処理自体が重い。

2024-01-18

CPS変換をできるだけ丁寧に

未来の自分のために解説。

call/ccはやっぱりあやしい。多分あってる、多分。

2024-01-16

Schemeで多値の実装してみた

call-with-valuesやapply-values無しで実装するやつ。

2024-01-15

ここ２日でちょっと実験してて、Cのメモリ管理を書き続けている。

Tclのトークンをできるだけシンボルとして扱う実装（リファレンスカウント）
RingをSECDで再実装（ConservativeGC）

リファレンスカウントのデバッグが難しい。どこかで確保・解放忘れしてるだけなんだけど、追跡が面倒。

valgrindに久々にお世話になってる。オプションはvalgrind --tool=memcheck --leak-check=full -s $(EXEC)

2024-01-13

Tclのモジュール作ってみた

感動するぐらい簡単。

Arkam

昔のプロジェクトを少しずつアップしていってる。

しかしcoreのコード見て、まあ読みやすくなるようかなりがんばった後はあるけど、やっぱもうForth無理だな〜という感想しか抱けない。

いや書くのは今でもできるんだよね多分。読み返すのが凄まじく苦痛。

Fossilで何故かバイナリ(blob)のsyncができない

ファイルでもwikiでも。うーん？

その後Cloneしたり削除したりごちゃごちゃやってたらなんか解決した。うーん？

FPGAでLisp Machine

楽しそう