Gauche > Archives > 2020/04/25

2020/04/25 12:43:59 UTCkaki
#
.dir-locals.el で begin0 のインデントが 0 になってますが、1 の間違いじゃないですか?(0だと (begin0 arg1 で改行したら arg2 は arg1 に揃えてインデントされますよね?)
2020/04/25 12:48:10 UTCshiro
#
ありゃ、そうですね。直しときます。
2020/04/25 12:54:31 UTCkaki
#
ありがとうございます。
2020/04/25 14:30:03 UTCkaki
#
Haskellのiterate(iterate f x => [x, f x, f (f x), ...])って遅延列を扱う際に頻出だと思うので、それ相当のものが gauche.generator と gauche.lazy にあるといいと思って書いてみました。すると
#
(define (giterate0 f x)
  (^ ()
    (begin0 x
      (set! x (f x)))))

(define (giterate1 f x)
  (gcons* x
          (^ ()
            (set! x (f x))
            x)))

(define (giterate2 f x)
  (^ ()
    (set! x (f x))
    x))

;; gosh> (time ((gdrop (giterate0 (cut + 1 <>) 1) 10000000)))
;; ;(time ((gdrop (giterate0 (cut + 1 <>) 1) 10000000)))
;; ; real   2.295
;; ; user   2.600
;; ; sys    0.020
;; 10000001

;; gosh> (time ((gdrop (giterate1 (cut + 1 <>) 1) 10000000)))
;; ;(time ((gdrop (giterate1 (cut + 1 <>) 1) 10000000)))
;; ; real   1.506
;; ; user   1.480
;; ; sys    0.010
;; 10000001

;; gosh> (time ((gdrop (giterate2 (cut + 1 <>) 1) 10000000)))
;; ;(time ((gdrop (giterate2 (cut + 1 <>) 1) 10000000)))
;; ; real   1.043
;; ; user   1.020
;; ; sys    0.010
;; 10000002
#
giterate0とgiterate1は実装の違いだけでgiterate2は最初の要素を捨てます。思ったより差が出ました。
2020/04/25 14:39:47 UTCkaki
#
これを入れて欲しいという主張と、このgiterate2相当も入れるかどうかと、名前をどうするかという相談です。giterate2を使うと遅延リスト版も速くなります。
#
(define (literate1 f x)
  (generator->lseq (giterate1 f x)))

(define (literate2 f x)
  (cons x (generator->lseq (giterate2 f x))))

;; gosh> (time (list-ref (literate1 (cut + 1 <>) 1) 10000000))
;; ;(time (list-ref (literate1 (cut + 1 <>) 1) 10000000))
;; ; real   2.293
;; ; user   2.260
;; ; sys    0.010
;; 10000001

;; gosh> (time (list-ref (literate2 (cut + 1 <>) 1) 10000000))
;; ;(time (list-ref (literate2 (cut + 1 <>) 1) 10000000))
;; ; real   1.844
;; ; user   1.810
;; ; sys    0.020
;; 10000001
2020/04/25 20:12:54 UTCshiro
#
giterate0が遅いのはbegin0のせいですね。最初の式が多値を返す可能性があるので、begin0は一旦receiveで受けてvaluesで返してるんです。let使うとかなり速くなる (まだ差があるのは、呼び出しごとに環境フレームを一個作らないとならないからじゃないかな) https://gist.github.com/shirok/012504f7c795519d42be099b123ae040
#
(最後のgunfold1は、giterateはgunfoldの特別ケースだなと思って比較。まあ遅いですね)
2020/04/25 20:18:28 UTCshiro
#
begin0のこれはうっかり使うと罠なのでVMレベルで最適化する予定はあるけど(このパターンが出てきたらconsしない)、今回の件ではひとまず置いといて、giterate0-1とgiterate2の差を重視して最初の要素を省くバージョンを提供するかどうか、ですね。
#
APIとしては最初の要素がある方が混乱が少なくて良いと思うんだけど…
2020/04/25 20:38:08 UTCshiro
#
ちょっとバリエーションを試してみたけどやっぱりgiterate2に勝つのは難しいな。giterate2はこれ以上無いくらい単純だからな https://gist.github.com/shirok/d79ebb73a1a1d0ff1bbf0052a5458b93
#
ただ、コンパイラがもっと良くなればgiterate0-1でもそんなに遜色なくなるような気もするんだよね
2020/04/25 20:46:42 UTCshiro
#
あ、でもfに任意の関数が来るってことは結局適用前のxをちゃんと保護して保存しとかないとならいから(適当なレジスタとかに置いとけない)、そうそう速くするのは無理か。
2020/04/25 20:53:16 UTCshiro
#
余分な環境も条件分岐も使わずにgiterate2と競うには、self-modifying codeくらいしか思いつかんな(初回に関数の中身を書き換えてxを返す、次回以降はgiterate2と同じになる)。Gauche本体に手を加えないとできないけど。
2020/04/25 20:59:05 UTCshiro
#
(giterate1-1はGaucheの枠組みの中でそれをやってみたんだけど(ローカル変数genがすげ変わる)、実行時に関数呼び出しがひとつ余分に入るから結局遅い。関数本体のインストラクション列を置き換えるしかない)
#
s/ローカル変数/ローカル関数/
2020/04/25 21:08:05 UTCshiro
#
妥協案としては、初期値を含めるgiterate (ベンチマークのgiterate0-1)と、初期値を含めないgiterate1 (ベンチマークのgiterate2) の両方を提供する。