Zenn
Open7

Ribbon: readの最適化？

okuokuokuoku

とりあえず read がやたら遅いということで、最適化を考える。

14KBくらいのソースコードを読むのに:

https://github.com/okuoku/yuni/blob/e731e8b7681018476c8f97d34a4bfdebd33da41e/lib/yuni/miniread/reader-main.sls

real    1m7.207s
user    1m9.091s
sys     0m2.342s

1分...

ちなみにGaucheで同じreaderを動かした場合は

real    0m0.409s
user    0m0.358s
sys     0m0.140s

400ms。せめて数秒とかのレベルになってくれないと厳しいもんがある。

okuokuokuoku

とりあえず小手先の最適化

string-append と substring が一旦リストを経由していたので、VM側で直接実行するように変えた。基本的にオブジェクトに対するO(N)処理はしない方針なので。

https://github.com/okuoku/yuniribbit-proto/commit/224d20ebfe2d78bbc8cf5fa5dc368175bf22f95b

https://github.com/okuoku/yuniribbit-proto/commit/f500540a21b0c461e195aedec00af6a56537ee71

real    0m40.066s
user    0m41.655s
sys     0m1.966s

... 予想以上に早くなったな。。ただ、これでI/Oのオーバーヘッドが無くなったと仮定してもまだGaucheに100倍負けている。

okuokuokuoku

プロファイルもどきを取る

グローバル変数へのアクセスの数を数えてみる。これはアクセスをテキストファイルに書き出して sort uniq すれば簡単にカウントできる。

$ sort out.txt | uniq -c | sort -nr
3091422 (GET-VAR: eqv?)
1923331 (GET-VAR: rib?)
1923331 (GET-VAR: field2)
1669599 (GET-VAR: pair?)
1583213 (GET-VAR: id)
1301569 (GET-VAR: arg1)
1271658 (GET-VAR: $flonum?)
 911081 (GET-VAR: require-pair)
 738177 (GET-VAR: memv)
 649655 (GET-VAR: null?)
 636536 (GET-VAR: $fx=)
 632571 (GET-VAR: =)
 474495 (GET-VAR: field0)
 474495 (GET-VAR: car)
 436586 (GET-VAR: field1)
 436586 (GET-VAR: cdr)
 265296 (GET-VAR: close)
 225431 (GET-VAR: vector?)
 225431 (GET-VAR: require-vec)
 142535 (GET-VAR: vec-ref)
 125017 (GET-VAR: vector-ref)
 101189 (GET-VAR: vec-set!)
 100414 (GET-VAR: vector-set!)

最適化としては memv の削減かな。。これは case に由来するはずなので、適当なマクロを書いて or に開いてしまえば要らなくなる。というかそもそも論として、これ何とか末尾再帰に書き直せないだろうか。。

あと $flonum? は多分 = の実装に由来していて、これをScheme側で実装するのはちょっと重すぎるからVM側に移しても良いかな。

okuokuokuoku

= をネイティブ実装

https://github.com/okuoku/yuniribbit-proto/commit/d511b03e0126c18dfb0cadb7eafb807d2edc9c6f

real    0m33.826s
user    0m34.873s
sys     0m1.982s

当初のコストより半分くらいまで来たけどまだまだ遅いな。。

$ sort out.txt | uniq -c | sort -nr
2458851 (GET-VAR: eqv?)
1923331 (GET-VAR: rib?)
1923331 (GET-VAR: field2)
1669599 (GET-VAR: pair?)
1583213 (GET-VAR: id)
1301569 (GET-VAR: arg1)
 911081 (GET-VAR: require-pair)
 738177 (GET-VAR: memv)
 632571 (GET-VAR: =)
 474495 (GET-VAR: field0)
 474495 (GET-VAR: car)
 436586 (GET-VAR: field1)
 436586 (GET-VAR: cdr)
 265296 (GET-VAR: close)
 225431 (GET-VAR: vector?)
 225431 (GET-VAR: require-vec)
 142535 (GET-VAR: vec-ref)
 125017 (GET-VAR: vector-ref)
 101189 (GET-VAR: vec-set!)
 100414 (GET-VAR: vector-set!)
okuokuokuoku

case を eqv? に開く

case 構文を or と eqv? に開くのは syntax-rules で簡単にできる。

(define-syntax $case/clause
  (syntax-rules (else)
    ((_ arg (clauses ...) (else frm ...) clause ...)
     ($case/clause arg (clauses ... (else frm ...)) clause ...))
    ((_ arg (clauses ...) ((query ...) body ...) clause ...)
     ($case/clause arg (clauses ... ((or (eqv? 'query arg) ...) body ...)) clause ...))
    ((_ arg (clauses ...))
     (cond clauses ...))))

(define-syntax $case
  (syntax-rules ()
    ((_ arg clause ...)
     (let ((__1 arg))
      ($case/clause __1 () clause ...)))))

ただこれだけやっても

real    0m15.874s
user    0m16.154s
sys     0m1.888s

こんなもんか。。せめてもう半分いきたいところだが。。

 910791 (GET-VAR: eqv?)
 659207 (GET-VAR: =)
 463071 (GET-VAR: arg1)
 422556 (GET-VAR: id)
 352581 (GET-VAR: rib?)
 352581 (GET-VAR: field2)
 276574 (GET-VAR: close)
 236325 (GET-VAR: vector?)
 236325 (GET-VAR: require-vec)
 219007 (GET-VAR: arg2)
 149165 (GET-VAR: vec-ref)
 130908 (GET-VAR: vector-ref)
 106217 (GET-VAR: vec-set!)
 105417 (GET-VAR: vector-set!)
okuokuokuoku

他のSchemeでも試す

VMはyuniで記述しているので、常識的なSchemeであれば割とどこでも動く。

Gauche

$ time cmake -P _run.cmake check.sps

real    0m41.761s
user    0m42.381s
sys     0m0.061s

↑ より遅いのはLinuxの仮想マシンで実行しているため。。だと思う。でもちょっと遅くなりすぎだなコレ。。

Chez

$ time cmake -P _run.cmake check.sps
WARNING: Using FAKE implementation of weak-box
WARNING: MEMORY LEAK will occur

real    0m1.394s
user    0m1.362s
sys     0m0.030s

流石最強Scheme。。Gaucheの10倍早い。まぁJITCだし。。あとR6RSなのでunbound variableに厳しくて修正の必要があった。

https://github.com/okuoku/yuniribbit-proto/commit/ac767defc87eb595386ebe81e0066d567afb1080

s7

TinyScheme由来だったかな。。オーディオエディタsndの内蔵Schemeでパブリックドメインかつシングルソース、高い移植性が特徴。

流石にGaucheより遅い。いわゆるAST型のインタプリタなので最適化が弱いのは仕方ないかな。

real    0m49.556s
user    0m49.469s
sys     0m0.064s

Sagittarius

s7とほぼ同じ速度。

$ time cmake -P _run.cmake check.sps

real    0m48.563s
user    0m49.444s
sys     0m0.088s

Digamma

現在のYpsilon。userがかなり長いのはコンカレントGCだから。。？

$ time cmake -P _run.cmake check.sps

real    0m39.737s
user    0m59.172s
sys     0m0.554s